# 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 💡