-1
$\begingroup$

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: https://cstheory.stackexchange.com/questions/16383/what-are-alternatives-to-the-random-oracle-model-for-modelling-hash-functions -- explains exactly what I was looking for.

| improve this question | |
$\endgroup$
  • $\begingroup$ I just commented at the cstheory version of your question. $\:$ $\endgroup$ – user991 Feb 8 '13 at 21:26
  • $\begingroup$ Please don't post the same question at two StackExchange sites. (Cross-posting is discouraged on StackExchange.) Pick one to keep, and flag the other the moderators to ask them to close it: you can click the "flag" button beneath the question to do so. $\endgroup$ – D.W. Feb 8 '13 at 21:55
1
$\begingroup$

Another approach is to assume that the hash function is collision-resistant, and see if you can prove your protocol is secure under this weaker assumption. For some protocols, it is possible, and then you're good. For others, it's not. (More precisely, you demonstrate that any successful attack on the protocol can be turned into an algorithm that produces collisions for the hash function.)

| improve this answer | |
$\endgroup$
1
$\begingroup$

There's the common random string model (where hash functions can be modeled as having been picked from a family of functions using public coins).

There are also "whatever-tractable random oracles", where adversaries also have an oracle that finds a whatever with respect to the random oracle.
(Usually 'whatever' is one of {'preimage','second-preimage','collision'}.)

There's also something I've thought of that I've never heard of actually being used, where the oracle is drawn from a distribution of oracles such that, for any algorithm that adaptively makes a feasible number of queries to the oracle and then outputs a guessed $\:\langle \hspace{.01 in}x\hspace{.01 in},\hspace{-0.02 in}y\rangle\:$ pair, the probability that
the algorithm did not query the oracle on $\hspace{.01 in}x$ $\:$ and $\:$ the oracle's output on $x$ is $y$
is negligible. (Perhaps the "Unpredictable Oracle Model"?)

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Okay, just a question ... why do you manually add line breaks and complicated spaces in your answer? This seems like a lot of work for little benefit (it might even look worse on some browsers). $\endgroup$ – Paŭlo Ebermann Feb 6 '13 at 20:24
  • $\begingroup$ Well, the last two line breaks and the spaces between them were to aid in parsing. I put in the "purely spacing" TeX and the rest of the line breaks because I didn't realize that some (at least mobile) browsers would not display the TeX and/or break lines on their own, and so thought it would be worth making the answer look nicer (on browsers that didn't do either of those). I put and just kept the spacing in other TeX because I thought and still think that any browser that does display the TeX will display it in the same way, so I think that is worth the extra work. $\endgroup$ – user991 Feb 7 '13 at 0:24

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