Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > NEXT-BIT UNPREDICTABILITY:
Reports tagged with next-bit unpredictability:
TR23-143 | 22nd September 2023
Noam Mazor, Rafael Pass

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

Revisions: 3

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




ISSN 1433-8092 | Imprint