Prove that a PRG is a one$-$way function. Let $G$:$\{0,1{\}}^n\{0,1{\}}^m$ be a PRG with

$m>n.$ Prove that if there is an efficient algorithm A such that

Prob$[slarr\{0,1{\}}^n$;$A[G(s)]=s^{\text{'}}$:$G(s^{\text{'}})=G(s)]$

where $$ is non$-$negligible, then $G$ is not a secure PRG$.$

Hint: You have to build a distinguisher for $G$ that distinguishes between the

distribution generated by $G$ and the uniform distribution over $\{0,1{\}}^m.$ Note that

this is easy if $=1$ and you can use that as your starting point, but your reduction

must work for any non$-$negligible $.$