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.
Original language | English (US) |
---|---|
Article number | 6375349 |
Pages (from-to) | 698-707 |
Number of pages | 10 |
Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
DOIs | |
State | Published - 2012 |
Externally published | Yes |
Event | 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States Duration: Oct 20 2012 → Oct 23 2012 |
Keywords
- Black-box separation
- One-way Functions
- Pseudorandom Generators
ASJC Scopus subject areas
- General Computer Science