Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
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 :) –  Ninefingers Mar 7 '12 at 23:04
1  
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 –  fgrieu Mar 8 '12 at 0:40
    
(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. –  user4982 Nov 22 '13 at 20:06

1 Answer 1

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.

share|improve this answer
    
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. –  Kim Mar 8 '12 at 1:14
    
What actually is the "standard model" for hash functions? Preimage/second preimage/collision resistance? –  Paŭlo Ebermann Mar 9 '12 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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