6
$\begingroup$

$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?

Intuition

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.

| improve this question | |
$\endgroup$
  • $\begingroup$ Is this homework? You should explicitly say so. Anyway, your intuition is taking you in the wrong direction. $\endgroup$ – Yehuda Lindell May 11 '16 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 '16 at 12:56
  • 2
    $\begingroup$ Hint: it is NOT secure. $\endgroup$ – Yehuda Lindell May 11 '16 at 13:48
  • $\begingroup$ It seems $G'$ is not expanding. So it's not even an insecure PRG. $\endgroup$ – Maeher Oct 27 '19 at 13:31

Your Answer

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

Browse other questions tagged or ask your own question.