# GGM construction

### From CRYPTUTOR

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 be a pseudorandom generator. We define and to be the first *k* bits and last *k* bits of , respectively.

For any polynomial , we construct a pseudorandom function as follows:

It is convenient to think of this construction as a complete binary tree with height . Each node in the tree is an application of the PRG , which sends its left child and its right child . The root node receives *s* as input, we traverse the tree according to the bits of , 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.

## References

- Oded Goldreich, Shafi Goldwasser, Silvio Micali, How to construct random functions, J ACM, vol33, no4, October 1986, pp792-807.