Pseudorandom generators from regular one-way functions: New constructions with improved parameters ?
We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions: For any known-regular one-way function (on n-bit inputs) that is known to be ? -hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length ?(n) ? ( n ) by making a single call to the underlying one-way function. For any unknown-regular one-way function with known ? -hardness, we give a new construction with seed length ?(n) ? ( n ) and O(n/log?(1/?)) O ( n / log ? ( 1 / ? ) ) calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha (2012) [6].
pseudorandom generators one-way functions foundations randomized iterate