Suppose $G$ is a PRG$.$ For each $,G$ maps strings from $\{0,1{\}}^{}$ to $\{0,1{\}}^{m()},$ where $m()>.$ Define

the following game:

Consider the following game, with $k()$ a function in $$ such that $k()>0$ for all $$ :

MULTI$-$PRG$-$IND $()$ :

Chal samples a bit blarr$\{0,1\}$ uniformly randomly.

Repeat the following for at most $k()$ times:

Adv queries Chal for a sample.

If $b=0,$ Chal samples xlarr$\{0,1{\}}^{}$ uniformly randomly, and sets $y=G(x).$ Otherwise, Chal

samples ylarr$\{0,1{\}}^{m()}$ uniformly randomly.

Chal sends $y$ to Adv.

At the end, Adv outputs a guess bit $b^{\text{'}},$ and wins if $b=b^{\text{'}}.$

We say that $G$ is MULTI$-$PRG$-$IND$-$secure if for any PPT adversary $A,$

$Pr[A$ wins MULTI$-PRG-$IND

$u()$

for some negligible function

$u().$

Problem $1\mathrm{.}4(4$ points$).$ Show that for any polynomial $k,G$ is MULTI$-$PRG$-$IND$-$secure if and only if

$G$ is a PRG$.$