PRG ⇒ PRF (GGM)

A length-doubling PRG implies a PRF, by the GGM binary-tree construction.

Construction

Migrated verbatim from PRF § Other results:

The GGM tree construction: given a length-doubling PRG $G:\{0,1{\}}^n\to \{0,1{\}}^{2n}$, define $\mathsf{Eval}(k,x_1\cdots x_{\ell })$ by starting from $k$ and at each bit $x_i$ applying either the left or right half of $G$

Notes

class is fully-black-box on the authority of Black-Box Separations, which uses this construction as its worked example of the notion: the $\mathsf{PRG}$ is invoked as an oracle, and the security proof reduces any $\mathsf{PRF}$ adversary — treated as an oracle — to a $\mathsf{PRG}$ distinguisher.

The length-doubling hypothesis is load-bearing and is stated only in the construction sketch, not in the one-line claims that cite this result.