Content deleted Content added
Citation bot (talk | contribs) Alter: title. Add: isbn, volume, series, chapter, s2cid, doi. | Use this bot. Report bugs. | Suggested by SemperIocundus | #UCB_webform 1057/2500 |
m Open access bot: doi added to citation with #oabot. |
||
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|author-link=Mihir Bellare|first2=Phillip|last2=Rogaway|author-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|doi=10.1145/168588.168596 |s2cid=3047274 |url=https://dl.acm.org/doi/10.1145/168588.168596|doi-access=free}}</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 28:
== Random Oracle Hypothesis ==
Although the Baker–Gill–Solovay theorem<ref name="BGS75">{{cite journal| 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 journal| 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 journal|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 journal|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|doi-access= free}}</ref>
== Ideal Cipher == <!--- [[User:Strew]] checked for possible R to section but not sure on this from search, could mean other ciphers -->
| |||