# Proof that PRG of itself is a PRG (composition)

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?

• 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.
– fgrieu
Nov 15 '20 at 13:24
• 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$.
– fgrieu
Nov 15 '20 at 15:15