Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

Thomas Holenstein, Makrand Sinha

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 hol…