Name
Abstract | ||
|---|---|---|
We show that a black-box construction of a pseudorandom generator from a one-way function needs to make Omega(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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/FOCS.2012.51 | foundations of computer science |
Keywords | DocType | Volume |
one-way function,gold reich,black-box construction,pseudorandom generator,underlying one-way function,almost linear number,known construction,siam j. comp,random number generation,cryptography,one way functions,computational complexity,functions | Conference | abs/1205.4576 |
ISSN | ISBN | Citations |
0272-5428 | 978-1-4673-4383-1 | 8 |
PageRank | References | Authors |
0.52 | 22 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Holenstein | 1 | 375 | 24.93 |
| Makrand Sinha | 2 | 12 | 3.67 |