Random oracle: Difference between revisions

Revision as of 13:05, 19 February 2023

Revision as of 22:18, 21 April 2023

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^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|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^A ⊊ PSPACE^A for a random oracle A with probability 1.<ref name="CCGHHRR">{{cite journal|first1=Richard|last1= Chang|first2= Benny|last2= Chor|last2author2-link= Benny Chor |first3= Oded |last3=Goldreich|first3first4= Juris|last3last4= Hartmanis|first4first5= Johan|last4last5= Hastad|first5first6= Desh|last5last6= Ranjan|first6first7= Pankaj|last6last7= 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 -->