The Goldreich-Goldwasser-Micali Construction
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…