Random oracle: Difference between revisions

Revision as of 17:08, 5 February 2024

Revision as of 14:40, 26 February 2024

Line 32:

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.

== Random Oracleoracle Hypothesishypothesis ==

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^A = NP^A, 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}ⁿ 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^B ⊊ NP^B 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₁ and C₂ 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|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|doi-access=free}}</ref> despite IP^A ⊊ PSPACE^A for a random oracle A with probability 1.<ref name="CCGHHRR">{{cite journal|first1=Richard|last1= Chang|first2= Benny|last2= Chor|author2-link= Benny Chor |first3= Oded |last3=Goldreich|first4= Juris|last4= Hartmanis|first5= Johan|last5= Hastad|first6= Desh|last6= Ranjan|first7= Pankaj|last7= 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 Ciphercipher == <!--- [[User:Strew]] checked for possible R to section but not sure on this from search, could mean other ciphers -->

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.

Line 41:

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 | book-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 | book-title= CRYPTO 2016 | publisher = Springer | title=Indifferentiability of 8-Round Feistel Networks}}</ref> [[Feistel network]]s.

== Ideal Permutationpermutation ==

An ideal permutation is an idealized object sometimes used in cryptography to model the behaviour of a permutation whose outputs are indistinguishable from those of a random permutation. In the ideal permutation model, an additional oracle access is given to the ideal permutation and its inverse. The ideal permutation model can be seen as a special case of the ideal cipher model where access is given to only a single permutation, instead of a family of permutations as in the case of the ideal cipher model.

== Quantum-accessible Randomrandom Oraclesoracles ==

[[Post-quantum cryptography]] studies quantum attacks on classical cryptographic schemes. As a random oracle is an abstraction of a [[hash function]], it makes sense to assume that a quantum attacker can access the random oracle in [[quantum superposition]].<ref name="Bon11">{{cite conference

| author = Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry