This is a method of using a PRNG to construct a PRF [GGM’84].

Let $G:\{0,1\}^s\rightarrow\{0,1\}^{2s}$ be a PRNG.

Define $G_0,G_1$ to be the left and right halves of $G$, so that $G(X)=G_0(X)||G_1(X)$.

For any $K \in \{0,1\}^s$, define $F_K:\{0,1\}^n\rightarrow\{0,1\}^s$ by

\[F_K(x_1...x_n) = G_{x_n}(G_{x_{n-1}}(...(G_{x_2}(G_{x_1}(K))...))\]

Theorem: If $G$ is a $(t,\epsilon)$-PRNG then $F$ is a $(t-cn,\epsilon q n,q)$-PRF for some constant $c$.

Proof: We use a hybrid argument. For $i = 0,...,n$ define

\[ F^i_{h^i}(x_1,...,x_n) = G_{x_n}(G_{x_{n-1}}(...(G_{x_{i+1}}(h^i(x_i...x_1)))...)) \]

where $h^i$ is a function $h^i : \{0,1\}^i \rightarrow \{0,1\}^s$. Observe $h^0$ is a constant in $\{0,1\}^s$.

Also define the distributions

\[ D_i = \{F^i_{h^i}|h^i \leftarrow \{ h:\{0,1\}^i\rightarrow\{0,1\}^s\} \} \]

Observe $D_0 = \{F_K^GGM\}_{K\leftarrow\{0,1\}^s}$ and $D_n = \{F\}_{F\leftarrow\mathcal{F}}$

TODO…