ECCC-Report TR23-143https://eccc.weizmann.ac.il/report/2023/143Comments and Revisions published for TR23-143en-usFri, 22 Sep 2023 08:07:48 +0300
Revision 1
| Counting Unpredictable Bits: A Simple PRG from One-way Functions |
Noam Mazor,
Rafael Pass
https://eccc.weizmann.ac.il/report/2023/143#revision1A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).
Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT).
Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor O(log^2 n).
The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on n input bits (after hashing the input and the output) has n + O(log n) unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.Fri, 22 Sep 2023 08:07:48 +0300https://eccc.weizmann.ac.il/report/2023/143#revision1
Paper TR23-143
| Counting Unpredictable Bits: A Simple PRG from One-way Functions |
Noam Mazor,
Rafael Pass
https://eccc.weizmann.ac.il/report/2023/143A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).
Our goal is to provide a construction of a PRG from OWFs with a simple proof of security; we thus focus on the setting of non-uniform security (i.e., we start off with a OWF secure against non-uniform PPT, and we aim to get a PRG secure against non-uniform PPT).
Our main result is a construction of a PRG from OWFs with a self-contained, simple, proof of security, relying only on the Goldreich-Levin Theorem (and the Chernoff bound). Although our main goal is simplicity, the construction, and a variant there-of, also improves the efficiency—in terms of invocations and seed lengths—of the state-of-the-art constructions due to [Haitner-Reingold-Vadhan, STOC’10] and [Vadhan-Zheng, STOC’12], by a factor O(log^2 n).
The key novelty in our analysis is a generalization of the Blum-Micali [FOCS’82] notion of unpredictabilty—rather than requiring that every bit in the output of a function is unpredictable, we count how many unpredictable bits a function has, and we show that any OWF on n input bits (after hashing the input and the output) has n + O(log n) unpredictable output bits. Such unpredictable bits can next be “extracted” into a pseudorandom string using standard techniques.Fri, 22 Sep 2023 08:03:07 +0300https://eccc.weizmann.ac.il/report/2023/143