2
$\begingroup$

Currently I am trying to understand random oracle model in order to make a small presentation about it but I seem to be very confused about it.

Since it's an hypothetical model without a real life application (no function can be completely random), how cryptographic functions are modeled as random oracles (e.g are all hash functions modeled as random oracles?) and how can a cryptographic scheme can be secure under random oracle if there is not concrete proof or implementation of that model?

I think that one difference of standard model with the random oracle model is that is actually secure under some assumptions. Are there any security proofs for random oracle at all?

Can you give an example of a cryptographic protocol/function modeled as an random oracle and one that is not?

Is a hash algorithm an secure under RO until there is a proof that it isn't? (Doesn’t sound very logical).

I have read various sources and most posts from this sitw for random oracle but I didn't find much answers to the ones I stated, so I hope this won't be labeled as duplicate.

$\endgroup$
4
$\begingroup$

Indeed, this question is answered by What is the "Random Oracle Model" and why is it controversial?. However, I would like to add a few more thoughts on this. (Please read the other answer as well, since I will not repeat the very important things said there.)

First and foremost, the random oracle is a model and not an assumption. We do not assume that hash functions are random oracles (until proven otherwise) because they are provably not random functions, and they are trivially distinguished from such. Rather, we prove a scheme secure when a random oracle is used instead of the hash function. This is all that the proof of security says. It says nothing whatsoever about the security of the scheme with a concrete hash functions instead.

The claim to security of the real scheme with a concrete hash function is then a "leap of faith" that if the scheme cannot be broken in the random oracle model, then it is very unlikely that it will not be broken with a real hash function. In other words, this is a heuristic argument. Although highly unsatisfactory from a theoretical perspective, this has proven itself quite well over the past decade or two in that real protocols proven secure in the random oracle model are rarely (if ever) broken.

Some people claim that the random oracle model is no different from assuming things like that the discrete log problem or RSA problem is hard. I completely disagree with this. If someone breaks a protocol that is proven secure under the RSA assumption then this will be translated into an attack on RSA. Thus, this is a rigorous proof of security that holds under a given assumption. In contrast, as I have mentioned, the random oracle is a model and not an assumption.

Finally, consider a MAC defined by $h(k||m)$. This is secure in the random oracle model but not secure for any Merkle-Damgård based hash function. Thus, there is clearly a separation.

Personally, I am happy to live with a random oracle in practice when there are not efficient enough alternatives. However, I will always prefer to get rid of a random oracle, and view doing so as an important research goal. We only have IBE since the first constructions used a random oracle, and afterwards future research managed to get rid of this use. Thus, as with many cryptographers, I have a love-hate relationship with the model.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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