2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Geoffroy Couteau Dec 10 '18 at 10:16
  • $\begingroup$ 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. $\endgroup$ – Ungoliant Dec 10 '18 at 13:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Maeher Dec 10 '18 at 15:05
  • $\begingroup$ What does convenient stretch mean? And obviously I assume G exists, but I can't make any assumptions on it... $\endgroup$ – Ungoliant Dec 10 '18 at 15:44
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is indeed a correct solution. Another approach (with a somewhat simpler reduction) would be $G' : (x\|y) \mapsto x\|G(y)$. $\endgroup$ – Maeher Dec 10 '18 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.