# 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)>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)}>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!

• If you seek to show that it is not a PRG in general, you do not need to find a generic attack on "any PRG of this form"; rather, you can come up with a specific construction that is a PRG, yet becomes clearly insecure when applied to $(x,x)$. – Geoffroy Couteau Dec 10 '18 at 10:16
• Excuse me if I'm wrong, I'm just a beginner in this field. I was under the impression we don't know whether a PRG exists, and that it's existence is equivalent to P!=NP problem. – Ungoliant Dec 10 '18 at 13:55
• Assume that PRGs actually exist (because the question becomes vacuous otherwise.) I.e. assume there is a PRG $G''$ for some convenient stretch. Use that to construct a PRG $G$, such that $G$ is secure but $G'$ is not. – Maeher Dec 10 '18 at 15:05
• What does convenient stretch mean? And obviously I assume G exists, but I can't make any assumptions on it... – Ungoliant Dec 10 '18 at 15:44

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.
• This is indeed a correct solution. Another approach (with a somewhat simpler reduction) would be $G' : (x\|y) \mapsto x\|G(y)$. – Maeher Dec 10 '18 at 16:54