Title :
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Author :
Holenstein, Thomas ; Sinha, Makrand
Author_Institution :
ETH Zurich, Zurich, Switzerland
Abstract :
We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Ω(n/log(n)) calls to the underlying one-way function. The bound even holds if the one-way function is guaranteed to be regular. In this case it matches the best known construction due to Gold Reich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.
Keywords :
computational complexity; cryptography; functions; random number generation; Ω(n/log(n)) calls; O(n/log(n)) calls; black-box construction; one-way function; pseudorandom generator; Computer science; Context; Encoding; Generators; Polynomials; Radio frequency; Security; Black-box separation; One-way Functions; Pseudorandom Generators;
Conference_Titel :
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location :
New Brunswick, NJ
Print_ISBN :
978-1-4673-4383-1
DOI :
10.1109/FOCS.2012.51
