# GGM construction

(Redirected from GGM PRF)

The GGM construction is a construction of a pseudorandom function from a pseudorandom generator. It is named after its creators, Oded Goldreich, Shafi Goldwasser, and Silvio Micali.

## Construction

Let k be a security parameter and $G: \{0, 1\}^{k} \rightarrow \{0, 1\}^{2k}$ be a pseudorandom generator. We define $G_0(x)\,$ and $G_1(x)\,$ to be the first k bits and last k bits of $G(x)\,$, respectively.

For any polynomial $\ell$, we construct a pseudorandom function $F : \{0,1\}^k \times \{0,1\}^{\ell(k)} \to \{0,1\}^k$ as follows:

$F_s(\sigma) = G_{\sigma_{\ell(k)}}( G_{\sigma_{\ell(k)-1}}( \cdots G_{\sigma_2}( G_{\sigma_1}(s) ) \cdots ))$

It is convenient to think of this construction as a complete binary tree with height $\ell(k)$. Each node in the tree is an application of the PRG $G(x)\,$, which sends its left child $G_0(x)\,$ and its right child $G_1(x)\,$. The root node receives s as input, we traverse the tree according to the bits of $\sigma\,$, and output the value at the leaf.

We can extend the construction to give longer outputs by simply applying a PRG with suitable stretch to the k bits given by the basic construction.