Problem 2. (30 points) (a) (15 points) Suppose G is a pseudorandom generator. Someone proposes a pseudorandom gener- ator G1 that outputs one more bit than G via the following construction for Gi(s): run G(s) to get z. Let a single bit b be the exclusive-or of all the bits of z. Let z1 be z followed by b. Output z1. Prove that G is not secure by building an adversary to who can distinguish L prg-real Irom with high advantage and low running time. prg-random (b) (15 points) We can compose pseudorandom generators to get longer outputs from shorter seeds. Specifically, let Gi : {0,1} {0,1}2 and G2 : {0,1}2 {0,1}3 be (t,e)-secure pseudorandom generators. Prove that G3(s) = G2G(s)) is also a secure pseudorandom generator (for approx imately the same t and e). Hint: the proof is reasonably similar to the proof of Ros18, Claim 5.4 Let p > 2 be a prime. Zp denotes the field of integers modulo p: that is, the values f0,...,p-1} with addition, subtraction, multiplication, and division (except by 0) done modulo p, as on the first problem set. Z is the multiplicative group of that field (i.e., all of Zp except 0) Because multiplication and division are well-defined in Z, raising to positive and negative integer powers is also well-defined (positive powers correspond to repeated multiplication, while negative powers correspond to repeated division). Fractional powers are more complicated, and we will wait to figure them out. Problem 2. (30 points) (a) (15 points) Suppose G is a pseudorandom generator. Someone proposes a pseudorandom gener- ator G1 that outputs one more bit than G via the following construction for Gi(s): run G(s) to get z. Let a single bit b be the exclusive-or of all the bits of z. Let z1 be z followed by b. Output z1. Prove that G is not secure by building an adversary to who can distinguish L prg-real Irom with high advantage and low running time. prg-random (b) (15 points) We can compose pseudorandom generators to get longer outputs from shorter seeds. Specifically, let Gi : {0,1} {0,1}2 and G2 : {0,1}2 {0,1}3 be (t,e)-secure pseudorandom generators. Prove that G3(s) = G2G(s)) is also a secure pseudorandom generator (for approx imately the same t and e). Hint: the proof is reasonably similar to the proof of Ros18, Claim 5.4 Let p > 2 be a prime. Zp denotes the field of integers modulo p: that is, the values f0,...,p-1} with addition, subtraction, multiplication, and division (except by 0) done modulo p, as on the first problem set. Z is the multiplicative group of that field (i.e., all of Zp except 0) Because multiplication and division are well-defined in Z, raising to positive and negative integer powers is also well-defined (positive powers correspond to repeated multiplication, while negative powers correspond to repeated division). Fractional powers are more complicated, and we will wait to figure them out