Random oracle: Difference between revisions

Revision as of 19:16, 29 February 2024

Latest revision as of 10:10, 31 July 2025

(10 intermediate revisions by 9 users not shown)

Line 1:

{{Short description|Cryptographic model of a random function}}

{{for|random replies to random questions|Internet Oracle}}

In [[cryptography]], a '''random oracle''' is an [[oracle machine|oracle]] (a theoretical [[black box (systems)|black box]]) that responds to every ''unique query'' with a (truly) [[random]] response chosen [[uniform distribution (discrete)|uniformly]] from its output ___domain. If a query is repeated, it responds the [[Deterministic algorithm | same way]] every time that query is submitted.

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 first appeared in the context of complexity theory, in which they were used to argue that complexity class separations may face relativization barriers, with the most prominent case being the [[P vs NP problem]], two classes shown in 1981 to be distinct relative to a random oracle [[almost surely]].<ref name="bennett-gill">{{cite journal|first1=Charles|last1=Bennett|first2=John|last2=Gill|title= Relative to a Random Oracle A, N^A != NP^A != coNP^A with Probability 1|journal=SIAM Journal on Computing|year=1981|pages=96–113|doi=10.1137/0210008|doi-access=free}}</ref> They made their way into cryptography by the publication of [[Mihir Bellare]] and [[Phillip Rogaway]] in 1993, which introduced them as a formal cryptographic model to be used in reduction proofs.<ref name="bellrog">{{cite journalbook|first1=Mihir|last1=Bellare|author-link=Mihir Bellare|first2=Phillip|last2=Rogaway|author-link2title=PhillipProceedings of the 1st ACM conference on Computer and communications security - CCS '93 Rogaway|titlechapter=Random Oraclesoracles are Practicalpractical: A Paradigmparadigm for Designingdesigning Efficientefficient protocols Protocols|journalauthor-link2=ACMPhillip Conference on ComputerRogaway and Communications Security|year=1993|pages=62–73|doi=10.1145/168588.168596 |s2cid=3047274 |doi-access=free|isbn=0-89791-629-8 }}</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''', asa opposeddifferentiation tofrom being secure in the [[Standard model (cryptography)|standard model of cryptography]].

== Applications ==

Line 14 ⟶ 15:

Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the [[Standard model (cryptography)|standard model]] (such as [[collision resistance]], [[preimage resistance]], [[second preimage resistance]], etc.) can often be proven secure in the standard model (e.g., the [[Cramer–Shoup cryptosystem]]).

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 [[Probabilisticprobabilistic Signaturesignature Schemescheme|PSS]]. 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|first1=Russell|last1=Impagliazzo|first2=Steven|last2=Rudich|title=Limits on the Provable Consequences of One-Way Permutations|journal=[[Symposium on Theory of Computing|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.

Line 23 ⟶ 24:

== Domain separation ==

{{main|Domain separation}}

A single oracle may be treated as multiple oracles by pre-pending a fixed bit-string to the beginning of each query (e.g., queries formatted as "1||x" or "0||x" can be considered as calls to two separate random oracles, similarly "00||x", "01||x", "10||x" and "11||x" can be used to represent calls to four separate random oracles). This practice is usually called '''[[___domain separation''']]. ''Oracle cloning'' is the re-use of the once-constructed random oracle within the same proof (this in practice corresponds to the multiple uses of the same [[cryptographic hash]] within one algorithm for different purposes).{{sfn|Bellare|Davis|Günther|2020|p=3}} Oracle cloning with improper ___domain separation breaks security proofs and can lead to successful attacks.{{sfn|Bellare|Davis|Günther|2020|p=4}}

== Limitations ==

Line 33 ⟶ 35:

== Random oracle hypothesis ==

{{section rewrite|date=February 2024}}

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>