# Is this PRG secure?

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

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