5
$\begingroup$

Hash functions are often used in cryptographic schemes and protocols, and that doesn't necessarily mean that their proofs are on the Random Oracle model. That leads to the following question: What is the "turning point" in which the use of a hash function requires a proof on the Random Oracle model?

  • Is it when the proofs require observability and/or programmability of the random oracle?
  • Is it when it is essential to guarantee a random output?
  • Is it related to the usual characteristics of cryptographic hash functions (i.e., pre-image resistance, second pre-image resistance, collision resistance)? If so, how?
Improve this question
$\endgroup$
1
  • $\begingroup$ The third point is captured by the standard definition of a secure hash function. $\endgroup$
    – SEJPM
    Sep 14, 2015 at 16:17

2 Answers 2

Reset to default
2
$\begingroup$

A hash's security in the Random Oracle Model implies its collision-resistance, first-preimage resistance, and second-preimage resistance. In addition, security in the ROM implies that the hash's output is indistinguishable from random for an adversary without knowledge of the input, and that the hash is resistant to length-extension attack, neither of which is implied by collision-resistance, first-preimage resistance, or second-preimage resistance. So when randomness or length-extension matters, a hash secure in the ROM is useful in practice, and therefore in formal proofs.

Rigorous formal proofs of protocols often are easier with a hash secure in the ROM than with some weaker hypothesis. I pass at characterizing exactly when the ROM is indispensable, and if that's related to observability and/or programmability of the random oracle.

Improve this answer
$\endgroup$
1
  • $\begingroup$ OK, but then, in some cases it should be sufficient to require, for example, that the hash function is also resistant to length-extension attacks, without resorting to the ROM, right? $\endgroup$
    – cygnusv
    Sep 14, 2015 at 13:21
1
$\begingroup$

It is not the only requirement the behavior of the hash functions, which is assumed as a random function, in order to model a proof in the RO model. Also imprortantly it is the assumption that under the RO in order someone to learn the output of the random oracle which is a hash function, has to make queries in the oracle. Otherwise with no random oracle anyone can learn the output on any input. By this interaction during the proof usually an instance of an assumed hard problem is transformed into the RO output such that this transformation is not observable to an adversary. And basically this is the property that facilitates the proof and works under the ROM.

Improve this answer
$\endgroup$

Your Answer

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

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