OWF ⇒ PRG

Fully-black-box reduction · standard model · HILL99

Statement

Every unkeyed one-way function $f$ yields a PRG — HILL99. The construction extracts, by universal hashing, the computational entropy that the GL89 hard-core predicate adds to the output of $f$.

Notes

• For a one-way permutation $f$, $G(x,r)=(f(x),r,⟨x,r⟩)$ already stretches by one bit — GL89.
• Seed length $\tilde{O}(n^4)$ via next-block pseudoentropy, with a generator that is non-adaptive in $f$ and parallelizable — HRV10.
• Seed length $\tilde{O}(n^3)$ and a single hashing step, from a characterization of pseudoentropy by KL-hardness of sampling — VZ12.
• Conversely, every PRG is a one-way function (PRG ⇒ OWF), so OWF $\iff$ PRG — folklore.