Question: Pseudorandom generator: Given a pseudorandom generator (PRG) G : {0, 1 }n {0, 1} 2n , and let us denote G(x) = y 1 ||y
Pseudorandom generator: Given a pseudorandom generator (PRG) G : {0, 1}n {0, 1}2n , and let us denote G(x) = y1||y2, where |y1| = |y2| = n
Question: Let us define G : {0, 1}n {0, 1}4n as follows, on input an n-bit string x, First, it runs G(x) and obtains y1||y2;
Second, it runs G again on the first n-bit of the output y1, i.e., computes G(y1) and obtains z1,...,z2n. Then, it runs G again on the second n-bit of the output y2, i.e., computes G(y2) and obtains z2n+1,...,z4n. Finally, outputs z1, . . . , z4n. Note that the final output will be 4n bits.
Is G() still a PRG? If yes, explain why; if not, give an explicit attack that violates the PRG definition, i.e., define a distinguisher explicitly.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
