4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm passing through very quickly, so haven't read your Q fully, but if you've got two separate questions you are more than welcome to ask them both as separate questions. I know most forums dislike that; we however prefer it :) Anyway, up to you, don't take this comment as meaning you have to (it might be best to keep them as one) but just so you know you can, if you want to - and welcome to crypto :) $\endgroup$
    – user46
    Commented Mar 7, 2012 at 23:04
  • 1
    $\begingroup$ I'll refrain to comment about something I barely understand. Instead I suggest that you read the seminal paper by Mihir Bellare & Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols $\endgroup$
    – fgrieu ♦
    Commented Mar 8, 2012 at 0:40
  • $\begingroup$ (Old question, but I added comment in case it may help somebody in future). "Are random oracles really impossible to have in reality?" The answer to another question by Thomas Pornin clarifies this. But in short: quantum phenomena may generate true randomness, but modeling a notebook with quantum phenomena would be very hard. $\endgroup$
    – user4982
    Commented Nov 22, 2013 at 20:06

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the clarification! Right, so the ROM proofs always employ the random oracle in the strongest possible sense which can not be in any way replaced by a real hash function. Interesting, I guess I should look at some examples of the type that you mentioned. For the quantum oracle I thought that it would always make a list of values that are queried and then in case of a repeated query it outputs the value from the list. $\endgroup$
    – Kim
    Commented Mar 8, 2012 at 1:14
  • $\begingroup$ What actually is the "standard model" for hash functions? Preimage/second preimage/collision resistance? $\endgroup$
    – Paŭlo Ebermann
    Commented Mar 9, 2012 at 12:21

Your Answer

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

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