I\'m not sure I understand really the implications of proofs of security in the

Question

I'm not sure I understand really the implications of proofs of security in the random oracle model. Does a proof of security in ROM translate to a reduction of security of the crypto-system to the security of the hash function in the standard model? If not, then this would imply that the meaning of the ROM proof in the SM depends on the particular algorithm and it would seem almost impossible to say anything general about implications of proofs like this. However, people seem to put a lot of effort in producing proofs of security in ROM so perhaps these proofs do have some value (I just don't exactly understand what, and it would seem extremely hard to point out any general implications). Textbooks tend to be typically quite vague at explaining this.

A very much related question: Does anyone have any insight to whether there is some general reason why proofs of CCA security are expected to be hard (if they even exist) in SM?

By the way, are random oracles really impossible to have in reality? True randomness could be produced by quantum phenomena, so why not use that?

Explanation / Answer

If you can show a reduction of a security property of your protocol to the security of a hash function is the standard model, you do not need the random oracle assumption. So a proof in the ROM does not have any general (positive) meaning in the SM; hence why it is controversial. About the only general thing you can say is that some (arguably highly contrived) protocols that are secure in the ROM are insecure in the SM with a concrete hash function.

The value of a ROM proof is that it still narrows the range of attacks possible on a protocol. Unlike an unproven protocol where it could break in any number of ways, a ROM protocol will only break if the hash function does not live up our theoretic expectations of it. Further, no "natural" protocol that is secure in the ROM has ever been broken.

There is a good discussion in Katz-Lindell. Basically their conclusions is, a ROM protocol is better than no proof. A SM protocol should be preferred up to a reasonable decrease in efficiency.

A RO needs to return the same output value if queried on the same input. That is essentially why quantum randomness does not work.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.