GGM construction


Jump to: navigation, search

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.


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.


Personal tools