# 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 '20 at 12:23

## 1 Answer

You can construct a discriminator which applies G' on the first half of the output in question and compares it to the second half. If they match claim it came from G'' otherwise call it random.

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

The ability to build an efficient discriminator with non negligible success probability proves G'' is not pseudo random.