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.
- Oded Goldreich, Shafi Goldwasser, Silvio Micali, How to construct random functions, J ACM, vol33, no4, October 1986, pp792-807.