3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – mikeazo Aug 18 '15 at 14:58
  • $\begingroup$ I've tried and failed. I don't know how to show that breaking G(!s) results in breaking G(s). $\endgroup$ – Daniel S. Aug 18 '15 at 15:02
  • 2
    $\begingroup$ 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$. $\endgroup$ – mikeazo Aug 18 '15 at 15:07
  • $\begingroup$ 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. $\endgroup$ – Daniel S. Aug 18 '15 at 15:12
  • $\begingroup$ 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. $\endgroup$ – mikeazo Aug 18 '15 at 15:15
3
$\begingroup$

A proof by contradiction seems most appropriate here.

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Chris Peikert Aug 18 '15 at 21:36
  • $\begingroup$ @ChrisPeikert True. For some reason, proof by contradiction has always been may favorite. You know what they say, when you have a hammer... $\endgroup$ – mikeazo Aug 19 '15 at 2:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.