# Prove that function G is not a pseudo-random generator

I'm trying to do the following assignment:

Let $$G:\{0,1\}^n \rightarrow \{0,1\}^{n+1}$$ and $$G':\{0,1\}^n \rightarrow \{0,1\}^{n+2}$$ be two pseudorandom generators. Prove that the function $$G'':\{0,1\}^n \xrightarrow{}\{0,1\}^{2n+3}$$ defined by $$G''(s_1, \dots, s_n) = (G(s_1,\dots,s_n),G'(G(s_1,\dots,s_n)))$$ is not a pseudorandom generator.

I know that despite $$G$$ and $$G'$$ are pseudorandom functions, the way in which they are combined makes the new function vulnerable. Letting $$G''(s_1,\dots, s_n) = (y_1, \dots, y_{2n+3})$$ is possible to create $$(y_{n+2}, \dots, y_{2n+3})$$ from $$(y_1, \dots, y_{n+1})$$. I think it's possible to crete a distinguisher that exploits this fact, but I don't know how to prove it.

Any help about how to move on?

• Hint: in cryptography, the design of primitives is assumed public by Kerckhoffs's principle, therefore your distinguisher for $G''$ can be built using $G'$ as a subprogram. – fgrieu Mar 28 at 12:23

This discriminator has no false negatives and a false positive rate of $$2^{-n-2}$$.