Bad Proof. We want to prove that if $G()$ is a secure PRG$,$ then $$ is a secure encryp$-$

tion scheme under the EAV security definition. We will do a proof by contradiction

so we first state the contrapositive statement:

If $$ is not a secure EAV encryption scheme, $G()$ is not a secure PRG$.$

To prove the contrapositive, we begin by assuming that $$ is not a secure EAV en$-$

cryption scheme, thus, there exists an adversary A that breaks the EAV security of

II with non$-$negligible advantage, i$.$e$.$

$Pr[A$ breaks EAV $of]=\frac{1}{2}+p(n),$

where $p(n)$ is a non$-$negligible value.

Then, using $A$ we construct an distinguisher $D$ that breaks the security of $G().$

$D$ is given as input a string $w$ of size $2n$ from its challenger.

$D$ starts running $A.$

When A sends $m_0,m_1$ to $D,D$ will first flip a bit bin$\{0,1\},$ encrypt $m_b$ as

follows: $c^{**}=m_{b,L}o+w||m_{b,R}o+w$ and send $c^{**}$ to $A.$

A outputs a bit $b^{\text{'}}.$

If $b^{\text{'}}=b$ then $D$ outputs $1($i$.$e$.$ claims that $w$ was the output of a PRG$),$ else

$D$ outputs $0.$

Analysis. We consider $2$ cases:

Suppose $w$ was a truly random string, then

$Pr[A$ breaks EAV $of]=\frac{1}{2}$

and thus $Pr[D(r)=1]=\frac{1}{2}.$

Suppose $w$ was the output of a PRG$,$ then $($by assumption$)$

$Pr[A$ breaks EAV $of]=\frac{1}{2}+p(n),$

and thus $Pr[D(G(s))=1]=\frac{1}{2}+p(n).$

Thus,

$|Pr[D(G(s))=1]-Pr[D(r)=1]|=|\frac{1}{2}+p(n)-\frac{1}{2}|=p(n)$

and since $p(n)$ is a non$-$negligible value, $D$ is a good distinguisher for $G(),$ i$.$e$.$ broke

the security of the PRG $G().$