Acceptable assumptions when proving security

Considering the output of a cryptographic primitive, like an encryption scheme (CBC, ...), a hash function or even the output of any schemes based on number theoretic assumptions, is it reasonable (acceptable) to assume that these outputs are random when proving the security of a protocol/algorithm which relies on the use of such a primitive? Is this a good starting point?

• If you assume that they are random you immediately are finished with the proof. In general you define how the ideal object of the cryptographic primitive you want to prove looks like. For instance for hash functions you assume the existence of a perfect hash functions with random output. Then going down into your construction you prove that your construction is close to the ideal one. For data confidentiality the proof of secure encryption schemes implies indistinguishability between given ciphertexts. This proofs are formulated with simulation games CPA,CCA,... – curious May 31 '13 at 11:59
• Thank you curious. So is it acceptable or not ? Try to proove something like "as long as the output of an encryption scheme is indistinguishable from random data the new protocol is secure". Thank you in advance. – user7078 May 31 '13 at 18:32

The answer is "it depends". There are two fairly commonly used sets of assumptions, the so-called standard model, and the random oracle model. In the standard model, hash functions are one-way functions. In the random oracle model they are random oracles. The random oracle model isn't actually true, but it is useful and many protocols inspired by it are in fact secure as no one has been known to attack them.

For ciphers the usual model is PRP, pseudo-random permutation, although the ideal cipher model is also used, but generally PRP is realistic and strong enough to prove things secure.

Number theoretic primitives do not output random strings. For instance DH never produces all zeros. You should use hashing to make this truer.

For protocols usually a game is designed where an adversary tries to get bad things to happen. Showing that the game is lost if the cipher is a PRP implies that a real version will be secure if the cipher behaves like a PRP, and so is generally considered a proof of security. However, the constants involved matter: if you haven't read DJB "Non-uniform cracks in the concrete" you should before embarking on any sort of provable security work.

The answer I normally see is the protocol's documentation will reference the strength of the underlying algorithm. You don't have to assume it's perfect, just adequate.

• This is about provable security, not documentation. – Watson Ladd Jun 1 '13 at 13:58
• @WatsonLadd: There is no such thing as provable security : proving some communication system is unconditionally secure means separating the complexity classes P and NP, one of the Clay Mathematics Institute Millenium challenges. – William Hird Jun 10 '13 at 22:29
• There is such a field as provable security, reducing scheme and protocol security to that of hard problems. – Watson Ladd Jun 11 '13 at 1:17
• @WatsonLadd: Yes you can reduce the algorithm to a known hard problem but that is not proving that either is hard, to PROVE hardness ( and therefore proving security) is to prove that P is not equal to NP. – William Hird Jun 11 '13 at 2:10