GGM construction

From CRYPTUTOR

(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.

[edit]

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.