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

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.

| improve this answer | |

Your Answer

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

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