<p>(I am interpreting this question in the following way due to the comments.)  In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings.  This situation is troublesome for formal analyses (reductions) of these systems because, when modeled in the straightforward way, there is no obvious way to "assume" some important security notions like collision-resistance for such functions.  To be explicit, we might take a function $H:\{0,1\}^* \rightarrow \{0,1\}^{256}$ and say that</p>

<blockquote>
  <p>$H$ is <em>collision-resistant</em> if no probabilistic poly-time algorithm outputs distinct $x,y$ such that $H(x) = H(y)$.</p>
</blockquote>

<p>Under this definition, no function $H$ is collision resistant:  By the pigeon-hole principle such an $x,y$ exists, and there also exists a constant-time algorithm that outputs them.  (We're leaving aside the additional problem that "probabilistic poly-time" is ill-defined here.)  Most modifications of the definition, like asking for long $x,y$ or something, are unsatisfying.  Let me mention also that some properties are (I believe) achievable, such as when the $x$ is chosen at random and the adversary has to find a $y$ that collides.</p>

<p>But if one models the hash as a <em>keyed</em> function that take an additional key input, then these security notions can be plausibly assumed to be achieved.  Thus we often give security reductions where a keyed hash function is used and random hash key is chosen in the model.  Though this is incongruous with reality, it seems fine.</p>

<p>To better address this disparity, Rogaway in <a href="http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf" rel="nofollow noreferrer">suggested</a> that we forget about the formal assumption per se and instead focusing on the existence of an explicit reduction to doing something with the hash function.  This is exploiting the fact that we apparently don't "know" of an algorithm finding collisions in SHA-256, even though there is a "constant-time" algorithm for doing exactly that.</p>

<p>By the way, the random oracle model generally addresses a different issue:  sometimes we don't have any way to reduce security to any reasonable property of our (keyed or keyless) hash function, so we instead analyze the system in a model where the evaluations of the hash are replaced by evaluations of a random oracle (which everyone can access).  Incidentally, doing this also makes the hash appear to be keyless and thus superficially "closer to reality," but this is in fact not the case:  Now the <em>entire function</em> has become the key, and indeed an exponentially long key.</p>

CC BY-SA 3.0
2013-02-09T06:23:11.903Z
@RickyDemer Yes that is the informal notion that corresponds to what I was talking about.
David Cash
CC BY-SA 3.0
2013-02-07T19:58:11.593Z
2016-12-05T14:45:39.350Z
2016-12-05T14:45:39.350Z
David Cash
<p>I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as having been picked from a family of functions). Are there any other?</p>

<p>EDIT -- To make my question less vague: It seemed to me that the ROM or CRS was not modeling what a hash function is in reality and so proofs of security in the ROM model were problematic (considering all real hash functions are deterministic, keyless, and WILL always have collisions that can be found -- facts ignored by ROM and CRS). So I was looking for alternatives. </p>

<p>David Cash pointed out the Rogaway paper that deals exactly with the problem I'd been having. His reply below summarizes how the paper deals with this issue -- i.e., by requiring the explicit knowledge of the collision finding algorithm by an adversary.</p>

CC BY-SA 3.0
2013-02-06T21:11:08.627Z
Perhaps you are looking for standard notions for security for hash functions, like collision resistance, target collision resistance, and so on. Googling should turn up many sources for these.  If you are referring to the issue that real hash functions are not usually keyed, then this paper may be interesting to you:  http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf.  For cryptographic purposes one can also get by with universal hashes and variants in certain settings.
David Cash
CC BY-SA 3.0
2013-02-07T17:04:33.817Z
Actually now that I've read it, that paper is exactly what I was looking for! Thank you so much!
RDN
CC BY-SA 3.0
2013-02-07T18:13:44.800Z
@DavidCash: Could you make your comment an answer??
Jeffε
CC BY-SA 3.0
2013-02-07T19:31:27.623Z
Sure.  Though I'm still not sure how the question jives with the subsequent comments.
David Cash
<cr.crypto-security><hash-function><random-oracles>
What are alternatives to the random oracle model for modelling hash functions?
RDN
# What are alternatives to the random oracle model for modelling hash functions?

(Asked by: username_0 on 2013-02-06)

I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as having been picked from a family of functions). Are there any other?

EDIT -- To make my question less vague: It seemed to me that the ROM or CRS was not modeling what a hash function is in reality and so proofs of security in the ROM model were problematic (considering all real hash functions are deterministic, keyless, and WILL always have collisions that can be found -- facts ignored by ROM and CRS). So I was looking for alternatives.

David Cash pointed out the Rogaway paper that deals exactly with the problem I'd been having. His reply below summarizes how the paper deals with this issue -- i.e., by requiring the explicit knowledge of the collision finding algorithm by an adversary.

**Tags:** cr.crypto-security, hash-function, random-oracles
> **Comments:**
> **username_1**: Perhaps you are looking for standard notions for security for hash functions, like collision resistance, target collision resistance, and so on. Googling should turn up many sources for these.  If you are referring to the issue that real hash functions are not usually keyed, then this paper may be interesting to you:  http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf.  For cryptographic purposes one can also get by with universal hashes and variants in certain settings.  
> **username_0**: Actually now that I've read it, that paper is exactly what I was looking for! Thank you so much!  
> **username_2**: @DavidCash: Could you make your comment an answer??  
> **username_1**: Sure.  Though I'm still not sure how the question jives with the subsequent comments.  

---

## 1 answers

### Answer by username_1 on 2013-02-07. Score: 9 | Accepted answer

(I am interpreting this question in the following way due to the comments.) In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings. This situation is troublesome for formal analyses (reductions) of these systems because, when modeled in the straightforward way, there is no obvious way to "assume" some important security notions like collision-resistance for such functions. To be explicit, we might take a function $H:\{0,1\}^\* \rightarrow \{0,1\}^{256}$ and say that

> $H$ is *collision-resistant* if no probabilistic poly-time algorithm outputs distinct $x,y$ such that $H(x) = H(y)$.

Under this definition, no function $H$ is collision resistant: By the pigeon-hole principle such an $x,y$ exists, and there also exists a constant-time algorithm that outputs them. (We're leaving aside the additional problem that "probabilistic poly-time" is ill-defined here.) Most modifications of the definition, like asking for long $x,y$ or something, are unsatisfying. Let me mention also that some properties are (I believe) achievable, such as when the $x$ is chosen at random and the adversary has to find a $y$ that collides.

But if one models the hash as a *keyed* function that take an additional key input, then these security notions can be plausibly assumed to be achieved. Thus we often give security reductions where a keyed hash function is used and random hash key is chosen in the model. Though this is incongruous with reality, it seems fine.

To better address this disparity, Rogaway in [suggested](http://www.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf) that we forget about the formal assumption per se and instead focusing on the existence of an explicit reduction to doing something with the hash function. This is exploiting the fact that we apparently don't "know" of an algorithm finding collisions in SHA-256, even though there is a "constant-time" algorithm for doing exactly that.

By the way, the random oracle model generally addresses a different issue: sometimes we don't have any way to reduce security to any reasonable property of our (keyed or keyless) hash function, so we instead analyze the system in a model where the evaluations of the hash are replaced by evaluations of a random oracle (which everyone can access). Incidentally, doing this also makes the hash appear to be keyless and thus superficially "closer to reality," but this is in fact not the case: Now the *entire function* has become the key, and indeed an exponentially long key.

> **Comments:**
> **username_1**: @RickyDemer Yes that is the informal notion that corresponds to what I was talking about.  

---

