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.
展开▼
机译：我们表明，单向函数的伪随机生成器的黑盒结构需要对基础单向函数进行Omega（n / log（n））调用。如果单向函数被保证是规则的，则边界甚至成立。在这种情况下，它与Gold Reich，Krawczyk和Luby（SIAM J. Comp。22，1993）所使用的O（n / log（n））调用最匹配。
展开▼
