Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls

Thomas Holenstein, Makrand Sinha

2012 · 22 citations · 18 references

Concepts

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.

References

18