Paper 2023/1451

Counting Unpredictable Bits: A Simple PRG from One-way Functions

Noam Mazor, Cornell Tech
Rafael Pass, Tel-Aviv University and Cornell Tech

A 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.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
Pseudorandom generatorsone-way functionnext-bit unpredictability
Contact author(s)
noammaz @ gmail com
rafaelp @ tau ac il
2023-09-24: approved
2023-09-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Noam Mazor and Rafael Pass},
      title = {Counting Unpredictable Bits: A Simple PRG from One-way Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1451},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.