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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Mar 28, 2020 at 12:23

1 Answer 1


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.