cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...

, a random oracle is an

oracle An oracle is a person or agency considered to provide wise and insightful counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. As such, it is a form of divination. Description The word ''o ...

(a theoretical

black box In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...

) that responds to every ''unique query'' with a (truly)

random In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...

response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted. Stated differently, a random oracle is a

mathematical function In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the func ...

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 Mihir Bellare is a cryptographer and professor at the University of California San Diego. He has published several seminal papers in the field of cryptography (notably in the area of provable security), many of which were co-written with Phillip ...

and

Phillip Rogaway Phillip Rogaway is a professor of computer science at the University of California, Davis. He graduated from Beverly Hills High School, and later earned a BA in computer science from UC Berkeley and completed his PhD in cryptography at MIT, in ...

(1993). They are typically used when the proof cannot be carried out using weaker assumptions on the

cryptographic hash function A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output re ...

. 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 of cryptography.

Applications

Random oracles are typically used as an idealised replacement for

s in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof often shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some mathematical problem believed hard in order to break it. However, it only proves such properties in the random oracle model, making sure no major design flaws are present. It is in general not true that such a proof implies the same properties in the standard model. Still, a proof in the random oracle model is considered better than no formal security proof at all. 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 The Standard Model of particle physics is the theory describing three of the four known fundamental forces (electromagnetic, weak and strong interactions - excluding gravity) in the universe and classifying all known elementary particles. It w ...

(such as

collision resistance In cryptography, collision resistance is a property of cryptographic hash functions: a hash function ''H'' is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs ''a'' and ''b'' where ''a'' ≠ '' ...

, preimage resistance, second preimage resistance, etc.) can often be proven secure in the standard model (e.g., the

Cramer–Shoup cryptosystem The Cramer–Shoup system is an asymmetric key encryption algorithm, and was the first efficient scheme proven to be secure against adaptive chosen ciphertext attack using standard cryptographic assumptions. Its security is based on the computation ...

). Random oracles have long been considered in

computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...

, and many schemes have been proven secure in the random oracle model, for example Optimal Asymmetric Encryption Padding, RSA-FDH and

Probabilistic Signature Scheme Probabilistic Signature Scheme (PSS) is a cryptographic signature scheme designed by Mihir Bellare and Phillip Rogaway. RSA-PSS is an adaptation of their work and is standardized as part of PKCS#1 v2.1. In general, RSA-PSS should be used as a rep ...

. In 1986, Amos Fiat and

Adi Shamir Adi Shamir ( he, עדי שמיר; born July 6, 1952) is an Israeli cryptographer. He is a co-inventor of the Rivest–Shamir–Adleman (RSA) algorithm (along with Ron Rivest and Len Adleman), a co-inventor of the Feige–Fiat–Shamir identifica ...

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 showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange. In 1993,

and

were the first to advocate their use in cryptographic constructions. In their definition, the random oracle produces a bit-string of

infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music *Infinite (group), a South Korean boy band *''Infinite'' (EP), debut EP of American mu ...

length which can be truncated to the length desired. When a random oracle is used within a security proof, it is made available to all players, including the adversary or adversaries. 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).

Limitations

According to the

Church–Turing thesis In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of com ...

, no function computable by a finite algorithm can implement a true random oracle (which by definition requires an infinite description because it has infinitely many possible inputs, and its outputs are all independent from each other and need to be individually specified by any description). In fact, certain

artificial Artificiality (the state of being artificial or manmade) is the state of being the product of intentional human manufacture, rather than occurring naturally through processes not involving or requiring human activity. Connotations Artificiality ...

signature and encryption schemes are known which are proven secure in the random oracle model, but which are trivially insecure when any real function is substituted for the random oracle.Craig Gentry and Zulfikar Ramzan
"Eliminating Random Permutation Oracles in the Even-Mansour Cipher"
2004. Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the ''practical'' security of the protocol. 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 In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

, 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 Oracle Hypothesis

Although the Baker–Gill–Solovay theorem showed that there exists an oracle A such that P^A = NP^A, subsequent work by Bennett and Gill, showed that for a ''random oracle'' B (a function from ⁿ to 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 In probability theory, Kolmogorov's zero–one law, named in honor of Andrey Nikolaevich Kolmogorov, specifies that a certain type of event, namely a ''tail event of independent σ-algebras'', will either almost surely happen or almost su ...

), 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). This hypothesis was later shown to be false, as the two acceptable complexity classes IP and

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''t''(''n'')), the set of all problems that can b ...

were shown to be equal despite IP^A ⊊ PSPACE^A for a random oracle A with probability 1.

Ideal Cipher

An ''ideal'' cipher is a

random permutation A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and sim ...

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 In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other ...

. Some cryptographic proofs make not only the "forward" permutation available to all players, but also the "reverse" permutation. Recent works showed that an ideal cipher can be constructed from a random oracle using 10-round or even 8-round

Feistel network In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher) is a symmetric structure used in the construction of block ciphers, named after the German-born physicist and cryptographer Horst Feistel, who did pioneering research wh ...

Ideal Permutation

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 Random Oracles

Post-quantum cryptography In cryptography, post-quantum cryptography (sometimes referred to as quantum-proof, quantum-safe or quantum-resistant) refers to cryptographic algorithms (usually public-key algorithms) that are thought to be secure against a cryptanalytic attack ...

studies quantum attacks on classical cryptographic schemes. As a random oracle is an abstraction of a

hash function A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...

, it makes sense to assume that a quantum attacker can access the random oracle in

quantum superposition Quantum superposition is a fundamental principle of quantum mechanics. It states that, much like waves in classical physics, any two (or more) quantum states can be added together ("superposed") and the result will be another valid quantum s ...

. Many of the classical security proofs break down in that quantum random oracle model and need to be revised.

References

{{Cryptographic models Cryptography Cryptographic hash functions Theory of cryptography Computation oracles