I have this question and I am struggling to find a formal answer to this:

Given $G$ is a PRG, show that $H(s)=G(G(s))$ is also a PRG.

I know that a proof for this would assume that there exists a p.p.t. $\mathcal{A}$ that wins the adversary game against $H(s)$ and thereby there also has to exist one that wins against $G(s)$. But how can I formalize this?

  • 1
    $\begingroup$ Welcome to crypto-SE. We have a homework policy requiring effort to be shown. Please write down the definition of PRG used (there are variations, and it might lead you to the answer). Katz&Lindell have an Expansion criteria, $|s|<|G(s)|$, making $H(s)=G(G(s))$ ambiguous. Is $G(s)$ truncated to $|s|$ before use as seed of an outer $G$ parametrized as the inner one? Or is the full $G(s)$ used, implying different parametrization of the two instances of $G$ ? If using a definition requiring expansion, please show that easy part of the proof. $\endgroup$
    – fgrieu
    Nov 15 '20 at 13:24
  • $\begingroup$ Hint for the remaining: whatever the definition of PRG used, $G$ is implemented by a Polynomial Time algorithm $\mathcal G$. Meaningfully combine it with the Probabilistic Polynomial Time algorithm $\mathcal A$ of the question to form a new PPT algorithm $\mathcal A'$ that can be applied to $G(s)$, and prove that if $\mathcal A$ wins with non-vanishing probability against $H$, then $\mathcal A'$ wins with non-vanishing probability against $G$. $\endgroup$
    – fgrieu
    Nov 15 '20 at 15:15

Your Answer

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

Browse other questions tagged or ask your own question.