Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls
This provides a lower bound for cryptographic constructions, addressing a foundational problem in theoretical computer science, but it is incremental as it matches existing upper bounds.
The paper tackles the problem of constructing pseudorandom generators from one-way functions, showing that any black-box construction requires at least Omega(n/log(n)) calls to the underlying one-way function, matching the O(n/log(n)) calls in the best known construction.
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 Goldreich, Krawczyk, and Luby (SIAM J. Comp. 22, 1993), which uses O(n/log(n)) calls.