Exercise 2. PRGs [70 points) Let G: {0,1}" {0,1}?" be a PRG (for every n), and let s {0,1}" All the following constructions are not secure PRGs. For each one of them first state the expansion factor and then provide a counterexample to show that they are not PRGs, i.e. design a successful distinguisher and compute its advantage. (a) G.(8)=G(8)||G(8), where || denotes concatenation. (b) G.(s) = G(8)||G(0), where 0" denotes the all 0 string of length n. (c) Ge(s)=G(1||$), where 1 denotes the all 1 string of length equal to the length of s. (d) Ge(s): first run G(s) = x|ly (where (3=lv n-bits. Then run G(y) = uller Output ally@ullu. Exercise 2. PRGs [70 points) Let G: {0,1}" {0,1}?" be a PRG (for every n), and let s {0,1}" All the following constructions are not secure PRGs. For each one of them first state the expansion factor and then provide a counterexample to show that they are not PRGs, i.e. design a successful distinguisher and compute its advantage. (a) G.(8)=G(8)||G(8), where || denotes concatenation. (b) G.(s) = G(8)||G(0), where 0" denotes the all 0 string of length n. (c) Ge(s)=G(1||$), where 1 denotes the all 1 string of length equal to the length of s. (d) Ge(s): first run G(s) = x|ly (where (3=lv n-bits. Then run G(y) = uller Output ally@ullu