Cryptography

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

Let $G:\{\mathrm{0,1}{\}}^s\to \{\mathrm{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)\mid \mid G_1(X)$.

For any $K\in \{\mathrm{0,1}{\}}^s$, define $F_K:\{\mathrm{0,1}{\}}^n\to \{\mathrm{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-\mathrm{cn},\epsilon qn,q)$-PRF for some constant $c$.

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

$$F_{h^i}^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:\{\mathrm{0,1}{\}}^i\to \{\mathrm{0,1}{\}}^s$. Observe $h^0$ is a constant in $\{\mathrm{0,1}{\}}^s$.

Also define the distributions

$$D_i=\{F_{h^i}^i\mid h^i\leftarrow \{h:\{\mathrm{0,1}{\}}^i\to \{\mathrm{0,1}{\}}^s\}\}$$

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

TODO…