|
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 firstly used in rigorous cryptographic proofs in the 1993 publication by [[Mihir Bellare]] and [[Phillip Rogaway]] (1993).<ref name="bellrog">{{cite journal|firstfirst1=Mihir|lastlast1=Bellare|authorlink=Mihir Bellare|first2=Phillip|last2=Rogaway|authorlink2=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 ==
Random oracles have long been considered in [[computational complexity theory]],<ref>{{Citation | last1=Bennett | first1=Charles H. | author1-link=Charles H. Bennett (computer scientist) | last2=Gill | first2=John | title=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1 | year=1981 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=10 | issue=1 | pages=96–113 | doi=10.1137/0210008}}</ref> and many schemes have been proven secure in the random oracle model, for example [[Optimal Asymmetric Encryption Padding]], [[Full Domain Hash|RSA-FDH]] and [[Probabilistic Signature Scheme]]. In 1986, [[Amos Fiat]] and [[Adi Shamir]]<ref>{{cite news|first1=Amos|last1=Fiat|first2=Adi|last2=Shamir|title=How to Prove Yourself: Practical Solutions to Identification and Signature Problems|work=[[CRYPTO]]|year=1986|pages=186–194}}</ref> showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures.
In 1989, Russell Impagliazzo and Steven Rudich<ref>{{cite journal|firstfirst1=Russell|lastlast1=Impagliazzo|first2=Steven|last2=Rudich|title=Limits on the Provable Consequences of One-Way Permutations|workjournal=[[STOC]]|year=1989|pages=44–61}}</ref> showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange.
In 1993, [[Mihir Bellare]] and [[Phillip Rogaway]]<ref name="bellrog"/> were the first to advocate their use in cryptographic constructions. In their definition, the random oracle produces a bit-string of [[infinity|infinite]] length which can be truncated to the length desired.
== Random Oracle Hypothesis ==
Although the Baker–Gill–Solovay theorem<ref name="BGS75">{{cite articlejournal| first1 = Theodore | last1 = Baker | first2 = John | last2 = Gill | first3 = Robert | last3 = Solovay | title = Relativizations of the P =? NP Question | year = 1975 | journal = SIAM J. Comput. |volume=4|issue=4| publisher = SIAM | pages = 431–442 | doi = 10.1137/0204037 }}</ref> showed that there exists an oracle A such that P<sup>A</sup> = NP<sup>A</sup>, subsequent work by Bennett and Gill,<ref name="BG81">{{cite articlejournal| title = Relative to a Random Oracle A, P != NP != co-NP with Probability 1 | first1 = Charles | last1 = Bennett | first2 = John | last2 = Gill | year = 1981 | publisher = SIAM | journal = SIAM J. Comput.|volume=10|issue=1 | pages = 96–113| doi = 10.1137/0210008 }}</ref> showed that for a ''random oracle'' B (a function from {0,1}<sup>n</sup> to {0,1} such that each input element maps to each of 0 or 1 with probability 1/2, independently of the mapping of all other inputs), P<sup>B</sup> ⊊ NP<sup>B</sup> with probability 1. Similar separations, as well as the fact that random oracles separate classes with probability 0 or 1 (as a consequence of the [[Kolmogorov's zero–one law]]), led to the creation of the '''Random Oracle Hypothesis''', that two "acceptable" complexity classes C<sub>1</sub> and C<sub>2</sub> are equal if and only if they are equal (with probability 1) under a random oracle (the acceptability of a complexity class is defined in BG81<ref name="BG81" />). This hypothesis was later shown to be false, as the two acceptable complexity classes [[IP (complexity)|IP]] and [[PSPACE]] were shown to be equal<ref>{{cite articlejournal|first=Adi|last=Shamir|url=http://portal.acm.org/citation.cfm?doid=146585.146609|title= IP = PSPACE|journal=Journal of the ACM|volume=39|issue=4|pages=869–877|date=October 1992|doi=10.1145/146585.146609|s2cid=315182}}</ref> despite IP<sup>A</sup> ⊊ PSPACE<sup>A</sup> for a random oracle A with probability 1.<ref name="CCGHHRR">{{cite articlejournal|first1=Richard|last1= Chang|first2= Benny Chor|last2= Oded Goldreich|first3= Juris|last3= Hartmanis|first4= Johan|last4= Hastad|first5= Desh|last5= Ranjan|first6= Pankaj|last6= Rohatgi|title= The Random Oracle Hypothesis is False|journal=Journal of Computer and System Sciences|volume= 49|issue=1|pages=24–39|date=August 1994|doi= 10.1016/S0022-0000(05)80084-4|issn=0022-0000|url= http://citeseer.ist.psu.edu/282397.html}}</ref>
== Ideal cipher == <!--- [[User:Strew]] checked for possible R to section but not sure on this from search, could mean other ciphers -->
| title = Random oracles in a quantum world
| year = 2011
| pages = 41--6941–69
| publisher = Springer | doi = 10.1007/978-3-642-25385-0_3 | arxiv = 1008.0931}}</ref>. Many of the classical security proofs break down in that quantum random oracle model and need to be revised.
| 