Exercise 3. Pseudorandom Generators (PRGs) [40 points] Let G, GI , G2. {0, }n (0, l }2n be PRGs (for every n), and let s.si , spe {0, } k. For each of the following, prove that it is a PRG or provide a counterexample to show that it is not a PRG. (a) Ga (s) = G(s), where x =+9 1kl, i.e. x is obtained by flipping every bit of x. (b) Gb(s) - Gi(s) o G2(s), where o denotes concatenation. (c) Ge(s) = Gi (s) BG2(s), where denotes the XOR operator. (d) Ga(s) G(G(s)). Exercise 3. Pseudorandom Generators (PRGs) [40 points] Let G, GI , G2. {0, }n (0, l }2n be PRGs (for every n), and let s.si , spe {0, } k. For each of the following, prove that it is a PRG or provide a counterexample to show that it is not a PRG. (a) Ga (s) = G(s), where x =+9 1kl, i.e. x is obtained by flipping every bit of x. (b) Gb(s) - Gi(s) o G2(s), where o denotes concatenation. (c) Ge(s) = Gi (s) BG2(s), where denotes the XOR operator. (d) Ga(s) G(G(s))