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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2023
Keywords
Pseudorandom generatorsone-way functionnext-bit unpredictability
Contact author(s)
noammaz @ gmail com
rafaelp @ tau ac il
History
2024-07-12: revised
2023-09-22: received
See all versions
Short URL
https://ia.cr/2023/1451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1451,
      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},
      url = {https://eprint.iacr.org/2023/1451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.