# Post processing operations on pseudo-random generators

I am struggling to solve this proof.

The goal is to prove that $$H \circ G$$, which is a composite function $$H(G(s))$$ can be a pseudo-random generator under some conditions on $$H$$, given that $$G$$ is also a pseudo-random generator. Note that $$H$$ is length-preserving.

However, I can't find a way to prove (using the definition of a pseudo-random generator) that if $$H$$ is bijective, deterministic, can be computed in polynomial time and doesn't convey any information regarding the original input $$s$$, $$H \circ G$$ is also a pseudo-random generator.

I would appreciate some help on this topic.

• Assume this isn't the case --- i.e. $H\circ G$ is not a PRG under your assumptions. What does this imply about $G$?
– Mark
Oct 24, 2022 at 14:20
• @Mark I guess that would mean that G cannot be a PRG. However, I can't find a way to prove this contradiction with the formal definition of a PRG Oct 24, 2022 at 15:05
• What does it mean for something to not be a PRG?
– Mark
Oct 24, 2022 at 16:59
• @Mark Informally speaking, if $G$ is not a PRG, then it would be possible for an adversary to distinguish between its output and a truly random string. Oct 24, 2022 at 17:08
• If you think so, try to prove it. Roughly, (formally) build $\mathcal{A}_G$ however you can, then see if the assumptions you require on $H$ are implied by the conditions you were given as part of the problem statement.
– Mark
Oct 24, 2022 at 17:21