PRG ⇒ PRF (GGM)

Fully-black-box reduction · standard model · GGM86 · security loss: factor $q\ell$ for $q$ queries on $\ell$-bit inputs: a hybrid over the $\ell$ tree levels, each step a hybrid over the at most $q$ nodes queried at that level

Statement

If $G:\{0,1{\}}^n\to \{0,1{\}}^{2n}$ is a length-doubling PRG, written $G(s)=G_0(s)\Vert G_1(s)$ with $|G_0(s)|=|G_1(s)|=n$, then the following is a PRF with key space and range $\{0,1{\}}^n$ and domain $\{0,1{\}}^{\ell }$: $\mathsf{KeyGen}(1^{\lambda })$ outputs $k\stackrel{\$}{\leftarrow }\{0,1{\}}^n$, and $\mathsf{Eval}(k,x_1\cdots x_{\ell }):=G_{x_{\ell }}(G_{x_{\ell -1}}(\cdots G_{x_1}(k)\cdots ))$ — GGM86.

Sketch

$\mathsf{Eval}$ walks a binary tree of depth $\ell$ from the root $k$, keeping the left or right half of $G$‘s output on each input bit. A hybrid over the $\ell$ tree levels reduces any $q$-query PRF distinguisher to a PRG distinguisher with a factor $q\ell$ loss — standard.

\begin{algorithm}
\algname{Algorithm}
\caption{$\Eval(k, x_1 \cdots x_\ell)$}
\begin{algorithmic}
\State $y \gets k$
\Comment{$G(s) = G_0(s) \,\|\, G_1(s)$ with $|G_0(s)| = |G_1(s)| = |s|$}
\For{$i = 1, \ldots, \ell$}
\State $y \gets G_{x_i}(y)$
\EndFor
\Return $y$
\end{algorithmic}
\end{algorithm}