Stream Cipher and Pseudorandom Generators $[12$ Marks$].$

In class, we have seen how to build a stream cipher from a secure PRG $G$ with expansion factor $p.$ Namely,

the Encryption Algorithm Enc takes as input a key kin$\{0,1{\}}^n$ and message min$\{0,1{\}}^{p(n)},$ and outputs the

ciphertext $En{c}_k(m)=c$:$=G(k)o+m.$ We have proved that if $G$ is a secure pseudorandom generator, then

the Stream Cipher construction is a fixed$-$length private$-$key encryption scheme that has indistinguishable

encryptions in the presence of an eavesdropper, i$.$e$.,$ is semantically secure$.$

Prove that the converse is true: If the Stream Cipher construction is a semantically secure private$-$key encryp$-$

tion scheme, then the $G$ used in the construction must be a secure pseudorandom generator.