Random oracle: Difference between revisions

Revision as of 23:26, 5 November 2023

Revision as of 23:16, 28 December 2023

Line 26:

According to the [[Church–Turing thesis]], no function [[Computable function|computable]] by a finite algorithm can implement a true random oracle (which by definition requires an infinite description because it has infinitely many possible inputs, and its outputs are all independent from each other and need to be individually specified by any description).

In fact, certain [[Pathological (mathematics)|artificial]] signature and encryption schemes are known which are proven secure in the random oracle model, but which are trivially insecure when any [[Real-valued function|real function]] is substituted for the random oracle.<ref>Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 [https://arxiv.org/abs/cs.CR/0010019 (PS and PDF)].</ref><ref name="gentry_ramzan">Craig Gentry and Zulfikar Ramzan. [https://www.iacr.org/cryptodb/archive/2004/ASIACRYPT/218/218.pdf "Eliminating Random Permutation Oracles in the Even-Mansour Cipher"]. 2004.</ref> Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the ''practical'' security of the protocol.<ref name=anotherloook>{{cite journal|last1=Koblitz|first1=Neal|last2=Menezes|first2=Alfred J.|title=The Random Oracle Model: A Twenty-Year Retrospective|journal=Another Look|date=2015|url=http://cacr.uwaterloo.ca/~ajmeneze/anotherlook/papers/rom.pdf|access-date=6 March 2015|archive-date=2 April 2015|archive-url=https://web.archive.org/web/20150402165659/http://cacr.uwaterloo.ca/~ajmeneze/anotherlook/papers/rom.pdf|url-status=dead}}</ref>

In general, if a protocol is proven secure, attacks to that protocol must either be outside what was proven, or break one of the assumptions in the proof; for instance if the proof relies on the hardness of [[integer factorization]], to break this assumption one must discover a fast integer factorization algorithm. Instead, to break the random oracle assumption, one must discover some unknown and undesirable property of the actual hash function; for good hash functions where such properties are believed unlikely, the considered protocol can be considered secure.