Random oracle: Difference between revisions

Revision as of 16:09, 3 January 2021

Revision as of 21:14, 13 January 2021

Line 5:

Stated differently, a random oracle is a [[mathematical function]] chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output ___domain.

Random oracles as a mathematical abstraction were first used in rigorous cryptographic proofs in the 1993 publication by [[Mihir Bellare]] and [[Phillip Rogaway]] (1993).<ref name="bellrog">{{cite journal|first1=Mihir|last1=Bellare|authorlinkauthor-link=Mihir Bellare|first2=Phillip|last2=Rogaway|authorlink2author-link2=Phillip Rogaway|title=Random Oracles are Practical: A Paradigm for Designing Efficient Protocols|journal=ACM Conference on Computer and Communications Security|year=1993|pages=62–73|url=http://www.cs.ucsd.edu/users/mihir/papers/ro.html}}</ref> They are typically used when the proof cannot be carried out using weaker assumptions on the [[cryptographic hash function]]. A system that is proven secure when every hash function is replaced by a random oracle is described as being secure in the '''random oracle model''', as opposed to secure in the [[Standard Model (cryptography)|standard model of cryptography]].

== Applications ==

Line 23:

According to the [[Church–Turing thesis]], no 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 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|accessdateaccess-date=6 March 2015}}</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.

Line 34:

An ''ideal'' cipher is a [[random permutation]] oracle that is used to model an idealized block cipher. A random permutation decrypts each ciphertext block into one and only one plaintext block and vice versa, so there is a [[one-to-one correspondence]]. Some cryptographic proofs make not only the "forward" permutation available to all players, but also the "reverse" permutation.

Recent works showed that an ideal cipher can be constructed from a random oracle using 10-round<ref name="DKT16">{{cite conference | first1 = Dana | last1 = Dachman-Soled | first2 = Jonathan | last2 = Katz | first3 = Aishwarya | last3 = Thiruvengadam | title = 10-Round Feistel is Indifferentiable from an Ideal Cipher | year = 2016 | booktitlebook-title = EUROCRYPT 2016 | publisher = Springer | pages = 649–678 | doi = 10.1007/978-3-662-49896-5_23 }}</ref> or even 8-round<ref name="C:DaiSte16">{{cite conference | first1=Yuanxi | last1=Dai | first2=John | last2=Steinberger | year=2016 | booktitlebook-title= CRYPTO 2016 | publisher = Springer | title=Indifferentiability of 8-Round Feistel Networks}}</ref> [[Feistel network]]s.

== Quantum-accessible Random Oracles ==