Paper 2013/270

Pseudorandom Generators from Regular One-way Functions: New Constructions with Improved Parameters

Yu Yu

Abstract

We revisit the problem of basing pseudorandom generators on regular one-way functions, and present the following constructions: (1) For any known-regular one-way function (on $n$-bit inputs) that is known to be $\text{eps}$-hard to invert, we give a neat (and tighter) proof for the folklore construction of pseudorandom generator of seed length $\mathrm{\Theta }(n)$ by making a single call to the underlying one-way function. (2) For any unknown-regular one-way function with known $$-hardness, we give a new construction with seed length $$ and $$ calls. Here the number of calls is also optimal by matching the lower bounds of Holenstein and Sinha [FOCS 2012]. Both constructions require the knowledge about $$, but the dependency can be removed while keeping nearly the same parameters. In the latter case, we get a construction of pseudo-random generator from any unknown-regular one-way function using seed length $$ and $$ calls, where $$ omits a factor that can be made arbitrarily close to constant (e.g. $$ or even less). This improves the \emph{randomized iterate} approach by Haitner, Harnik and Reingold [CRYPTO 2006] which requires seed length $$ and $$ calls.