3
$\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!

Improve this question
$\endgroup$
4
  • 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
    Commented Dec 10, 2018 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$
    – Idra
    Commented Dec 10, 2018 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
    Commented Dec 10, 2018 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$
    – Idra
    Commented Dec 10, 2018 at 15:44

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Dec 10, 2018 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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