# Prove that H(s) = G(!s) is a CPRNG if G(s) is one

Given a cryptographic pseudo-random number generator $G$, prove that $H$ with $H(s) = G(!s)$ is also a cryptographic pseudo-random number generator. Here $s$ is a binary string; $!s$ is its complement.

For this we have to prove the two properties of a cryptographic pseudo-random number generator: the expansion and the pseudo-randomness.

The expansion is trivial to prove, because that's the same for $H$ and $G$. How can we prove that it is also cryptographically pseudo-random?

• Assume someone could break $H$. Show how this would result in a break of $G$. This is a contradiction since $G$ is cryptographically secure. Therefore, $H$ must be cryptographically secure also. This is a proof by contradiction. Or, if it is easier, formulate it as a proof by contrapositive. – mikeazo Aug 18 '15 at 14:58
• I've tried and failed. I don't know how to show that breaking G(!s) results in breaking G(s). – Daniel S. Aug 18 '15 at 15:02
• Say you want to break $G(s)$, well, feed $H$ with $!s$. $H(!s)=G(!!s)=G(s)$. Therefore, you've broken $G(s)$ since you can break $H$. – mikeazo Aug 18 '15 at 15:07
• So the proof is to first argument why !s is evenly distributed if s is evenly distributed and then follow that H(!s) can be broken, because we assumed so, and therefor G(s) can be broken. And that's a contradiction to G(s) being secure, so our assumption (that H is insecure) must be wrong, thus H is secure. – Daniel S. Aug 18 '15 at 15:12
• Is the security of G contingent upon $s$ being evenly distributed? If not, then you don't need to state that. Other than that possible change, looks good. – mikeazo Aug 18 '15 at 15:15

Assume that $H$ is not cryptographically secure. This means it fails to provide at least one of the properties of a CSPRNG as defined in your class, textbook, whatever. Then you must show how you can use an attack on $H$ to attack the cryptographic security of $G$. To do this, note that $H(!s)=G(!!s)=G(s)$. Since $G$ is cryptographically secure, your assumption must be incorrect. Therefore, you can conclude that $H$ is in fact cryptographically secure.
• A proof by contradiction seems unnecessarily complicated here. It's enough to observe that for uniformly random $s$, the distribution of $t=!s$ is also uniform. So $H(s)$ and $G(t)$ are identically distributed, and the latter is pseudorandom because $t$ is uniform. – Chris Peikert Aug 18 '15 at 21:36