In this section, we will examine the GGM (Goldreich, Goldwasser, Micali) construction of a PRF assuming we have a PRG G:{0,1}n{0,1}2n which is "length doubling". For a length doubling PRG G, and x{0,1}n, we parse the output G(x){0,1}2n as G(x)=(G(x)0,G(x)1), so G(x)0 denotes the first n bits of G(x), and G(x)1 denotes the second n bits. Recall that a PRF is a pair of algorithms (Sel, Eval). Given a length doubling PRG G, (Sel, Eval) work as follows: - Sel(): Choose and output a random "seed" s{0,1}n, which defines the function fs:{0,1}n {0,1}n - Eval(fs,x): Parse x=x1xn{0,1}n, and set y0=s{0,1}n. For i=1,,n, do the following: - let yi=G(yi1)xi{0,1}n\ the bit xi selects the first or last half of G(yi1)\. Output yn{0,1}n Problem 9. Prove that (Sel, Eval) is a secure PRF family assuming that G is a secure PRG