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.

  • 1
    $\begingroup$ Assume this isn't the case --- i.e. $H\circ G$ is not a PRG under your assumptions. What does this imply about $G$? $\endgroup$
    – Mark
    Oct 24, 2022 at 14:20
  • $\begingroup$ @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 $\endgroup$ Oct 24, 2022 at 15:05
  • $\begingroup$ What does it mean for something to not be a PRG? $\endgroup$
    – Mark
    Oct 24, 2022 at 16:59
  • $\begingroup$ @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. $\endgroup$ Oct 24, 2022 at 17:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mark
    Oct 24, 2022 at 17:21


Your Answer

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

Browse other questions tagged or ask your own question.