]> Cryptography - The Goldreich-Goldwasser-Micali Construction

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

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

Define ${G}_{0},{G}_{1}$ to be the left and right halves of $G$, so that $G\left(X\right)={G}_{0}\left(X\right)\mid \mid {G}_{1}\left(X\right)$.

For any $K\in \left\{0,1{\right\}}^{s}$, define ${F}_{K}:\left\{0,1{\right\}}^{n}\to \left\{0,1{\right\}}^{s}$ by

${F}_{K}\left({x}_{1}...{x}_{n}\right)={G}_{{x}_{n}}\left({G}_{{x}_{n-1}}\left(...\left({G}_{{x}_{2}}\left({G}_{{x}_{1}}\left(K\right)\right)...\right)\right)$

Theorem: If $G$ is a $\left(t,\epsilon \right)$-PRNG then $F$ is a $\left(t-\mathrm{cn},\epsilon qn,q\right)$-PRF for some constant $c$.

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

${F}_{{h}^{i}}^{i}\left({x}_{1},...,{x}_{n}\right)={G}_{{x}_{n}}\left({G}_{{x}_{n-1}}\left(...\left({G}_{x}{}_{i+1}\left({h}^{i}\left({x}_{i}...{x}_{1}\right)\right)\right)...\right)\right)$

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

Also define the distributions

${D}_{i}=\left\{{F}_{{h}^{i}}^{i}\mid {h}^{i}←\left\{h:\left\{0,1{\right\}}^{i}\to \left\{0,1{\right\}}^{s}\right\}\right\}$

Observe ${D}_{0}=\left\{{F}_{K}^{\mathrm{GGM}}{\right\}}_{K←\left\{0,1{\right\}}^{s}}$ and ${D}_{n}=\left\{F{\right\}}_{F←ℱ}$

TODO…