1. Let G and F be PRGs. Prove that F ◦G (where ◦ is function composition) is also a PRG. Follow the proof structure provided in the note which is sent by email. 2. Let G and F be PRGs. Is (F; G) a PRG? Note that (F; G)(s) is (F (s); G(s)). Please justify your answer. 3. Let G be a pseudorandom generator and define G0(s) to be the output of G truncated to n bits (where jsj = n). Prove that the function Fk(x) = G0(k) ⊕ x is not pseudorandom. 4. (Exercise 3.14) Prove that if F is a length-preserving pseudorandom function, then G(s) def = Fs(1)kFs(2)k : : : kFs(‘) is a pseudorandom generator with expansion factor ‘ · n.
