1
$\begingroup$

I am not really sure where I read that, but I have been thought that Random Oracles cannot be used in practice.

Then, I stumbled upon this paper that says: "Random Oracles are Practical: Paradigm for Designing Efficient Protocols" which totally confused my understanding

  • Why do they not exist in practice?
  • Why do we end up using them in practice anyway?
$\endgroup$
1
  • $\begingroup$ Given the definition of a random oracle, what should something like that look like in practice? I've seen a description where someone keeps a coin-flipping list-keeping leprechaun in a box (or something like that), but that doesn't seem all that practical.. $\endgroup$ Apr 25, 2017 at 7:55

1 Answer 1

1
$\begingroup$

We don't use random oracles. They are not practical. What we really do is modelling our theoretical work after the random oracle model.

There are many schemes which use hash functions. For some of them we have a proof of security, but only with some special cases. For example the padding scheme Optimal asymmetric encryption padding (OAEP) is proven to be semantically secure under chosen plaintext attacks - but only in the random oracle model. OAEP uses hash functions to randomize the message before encrypting with an asymmetric cipher, but what if these hash functions are not secure? Are they secure? We don't know, but probably not. Many were broken, like MD5 or SHA-1.
How can we prove that a scheme is secure if we are not sure that our underlying algorithms are secure? We can't. That's the reason why we have the random oracle model.

In the Random Oracle Model we just do everything like we always do, but there is a "magical" algorithm which represents a proven secure, perfect hash algorithm. In practice that's not really doable, because for this algorithm to work we need a true random number generator and a (nearly) infinite list of input und output values. That's already hard to do, but what's even more problematic is that every program / person who uses this algorithm has to have access to this number generator and list. How should that be done? Most likely with a central position which accepts messages and outputs the hashes for them. But how would you secure the connection between your program and this central position? It's just not practical doable to get a random oracle as your hash function in algorithms. It's like the one-time pad - nice to look at, provable secure and fully useless except for really special cases. We want fast and easy encryption for our bank details, not secure the Moscow–Washington hotline.

What we really do is just pretending to use them. We create our protocols and say "here we use a random oracle" if we need a secure hash function. Now we can try to prove our protocol and sometimes are even succesful with it. In most cases that works only because we used a random oracle. In reality we still implement something like SHA-256 or SHA-3 then and just ignore the possible problems - as long as nobody knows how to break our hash function and it works indistinguishable like a random oracle we should be save. Having a prove also helps to rule out mistakes in our protocol itself. Either we have a secure scheme or there's a problem with the hash algorithm. Without a prove there could also be a small, but fatal mistake nobody has thought of.

See also the article series "What is the Random Oracle Model and why should you care?" from Matthew Green.

$\endgroup$

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.