Today we show how to construct a pseudorandom function from a pseudorandom generator.
1. Construction of Pseudorandom Functions
Lemma 1 (Generator Evaluated on Independent Seeds) Suppose that is a pseudorandom generator. Fix a parameter , and define as
Then is a pseudorandom generator.
Let be a length-doubling pseudorandom generator. Define such that equals the first bits of , and define such that equals the last bits of .
The the GGM pseudorandom function based on is defined as follows: for key and input :
Theorem 2 If is a pseudorandom generator and is computable in time , then is a secure pseudorandom function.