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

) 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

) and

O

(

n

/log(1/

ε

)) 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

$\tilde{O}(n)$

and

$\tilde{O}(n/\log{n})$

calls, where

$\tilde{O}$

omits a factor that can be made arbitrarily close to constant (e.g. logloglog

n

or even less). This improves the

randomized iterate

approach by Haitner, Harnik and Reingold (CRYPTO 2006) which requires seed length

O

(

n

·log

n

) and

O

(

n

/log

n

) calls.