** Summary **

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

### Like this:

Like Loading...

*Related*