The Goldreich-Goldwasser-Micali Construction

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…


Ben Lynn blynn@cs.stanford.edu 💡