Is PRG On Concatenation of Input a PRG This is a homework assignment, so I'm not expecting full solutions, just general guidance.


  Let a PRG $G:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{l\left(n\right)}$ (where $l\left(n\right)$ is a polynomial and
  $l\left(n\right)&gt;n$).
  
  Is $G':x\mapsto G\left(x\|x\right)$ a PRG? (where $\|$ is the concatenation operator).


My intuition (that is probably wrong) says it is not, since $\left|Im\left(G'\right)\right|\leq2^{n}$ whereas $\left|Im\left(U_{l\left(2n\right)}\right)\right|=2^{l\left(2n\right)}&gt;2^{2n}$.

I'm not sure however how to show this.

I want to show a distinguisher between $U_{l\left(2n\right)}$ and $G'\left(U_{n}\right)$ with a non-negligible advantage, so I get input $z\in\left\{ 0,1\right\} ^{2n}$ and need to decide from which distribution it came from.

I thought about just checking whether $z\in Im\left(G'\right)$, but that can take $2^{n}$ to compute.

I would love some direction. Thanks!
I think I figured out the solution.

Assume such G exists (a PRG).

Then G' as described here is a PRG as well.

But applying it on $x\|x$ results in $G'':x\mapsto G\left(x\right)\circ G\left(x\right)$, which is not a PRG (easy to construct a distinguisher that checks if its input $z=z'\|z'$).

It is also possible to use $G′:\left(x\|y\right)↦x\|G\left(y\right)$ instead.