$G$ is a secure PRG in range $\{0,1\}^n\rightarrow\{0,1\}^{n+1}$.

Let us define $G'(S)=G(S\oplus G(S)_{1,...,n})$, s.t. $G(S)_{1,...,n}$ is the first n bits of $G(S)$.

Is $G'(S)$ a secure PRG?


I'd like to say that since $G(S)$ is a secure PRG then it's first n bits should also be pseudo random, else if they weren't, we'd have a distinguisher for the first n-bits, and then last bit could be 0 or 1, and we could distinguish $G(S)$ with high probability... but I might be missing something.

  • $\begingroup$ Is this homework? You should explicitly say so. Anyway, your intuition is taking you in the wrong direction. $\endgroup$ May 11, 2016 at 5:34
  • $\begingroup$ @YehudaLindell This is homework without grade, it's an extra. Actually I study in your university but this is not your course. (; $\endgroup$
    – Jjang
    May 11, 2016 at 12:56
  • 2
    $\begingroup$ Hint: it is NOT secure. $\endgroup$ May 11, 2016 at 13:48
  • $\begingroup$ It seems $G'$ is not expanding. So it's not even an insecure PRG. $\endgroup$
    – Maeher
    Oct 27, 2019 at 13:31


Your Answer

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