Random oracle: Difference between revisions

Revision as of 16:46, 28 January 2024

Revision as of 17:08, 5 February 2024

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 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|author-link=Charles Bennett|first2=John|last2=Gill|author-link2=John 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 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 |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]].

Line 45:

== Quantum-accessible Random Oracles ==

[[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=Bon+11"Bon11">{{cite conference

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

| title = Advances in Cryptology – ASIACRYPT 2011