DocumentCode
2434477
Title
Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
Author
Holenstein, Thomas ; Sinha, Makrand
Author_Institution
ETH Zurich, Zurich, Switzerland
fYear
2012
fDate
20-23 Oct. 2012
Firstpage
698
Lastpage
707
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on
Conference_Location
New Brunswick, NJ
ISSN
0272-5428
Print_ISBN
978-1-4673-4383-1
Type
conf
DOI
10.1109/FOCS.2012.51
Filename
6375349
Link To Document