OWF ⇒ PRG

Fully-black-box reduction · standard model · HILL99 · security loss: polynomial: a distinguisher of time $T$ and advantage $\epsilon$ yields an inverter of time-success ratio $\mathrm{poly}(n,T/\epsilon )$, but the seed is polynomially longer than the input length $n$ of $f$, so the generator’s security at seed length $m$ rests on that of $f$ at input length $m^{\Omega (1)}$

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$.

Sketch

Hashing $x$ down to about $\log |f^{-1}(f(x))|$ bits and appending the hard-core bit gives a false-entropy generator: its output has more computational than real entropy. Concatenating many independent copies turns that gap into a min-entropy gap, and universal hashing then extracts more pseudorandom bits than the seed holds, by the leftover hash lemma — HILL99.

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.
• Every black-box construction of a PRG from a one-way function on $n$ bits calls it $\Omega (n/\log n)$ times, even when the function is regular, which matches the $O(n/\log n)$-call construction from regular one-way functions — HS12, GKL88.
• Conversely, every PRG is a one-way function (PRG ⇒ OWF), so OWF $\iff$ PRG — folklore.