It is a fact that if there exists a pseudorandom generator, then there exists a pseuorandom function. However, the process of constructing a pseudorandom function from a given pseudorandom generator is a bit tricky. Heres one idea: Suppose that G is a pseudorandom generator. Define

(Here k||x just denotes the concatenation of the two strings.) Show that even if G is a pseudorandom generator, it may be that F is not a pseudorandom function. (Hint: Suppose that G is a pseudorandom generator; then so is the function x||y 7 x||G(y) (where |x| = |y| or |x| = |y| + 1 depending on whether the input length is even or odd.) Show that this sort of G can mess up the construction above.)

Fk(first bits of G(llk Fk(first bits of G(llk