Random oracle
Encyclopedia
In cryptography
, a random oracle is an oracle
(a theoretical black box) that responds to every query with a (truly) random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query. Put another way, a random oracle is a mathematical function mapping every possible query to a random response from its output domain.
Random oracles are a mathematical abstraction used in cryptographic proofs; they are typically used when no known implementable function provides the mathematical properties required by the proof. A system that is proven secure using such a proof is described as being secure in the random oracle model, as opposed to secure in the standard model
. In practice, random oracles are typically used to model cryptographic hash function
s in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof generally 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 the protocol. Not all uses of cryptographic hash functions require random oracles: schemes that require only some property or properties that have a definition in the 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
(e.g. Bennett & Gill). Fiat and Shamir (1986) showed a major application of random oracles - the removal of interaction from protocols for the creation of signatures. Impagliazzo and Rudich (1989) showed the limitation of random oracles - namely that their existence alone is not sufficient for secret-key exchange.
Bellare and Rogaway (1993) advocated their use in cryptographic constructions. In this definition, the random oracle produces a bit-string of infinite 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).
No real function can implement a true random oracle. In fact, certain artificial
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. Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence that an attack which does not break the other assumptions of the proof, if any (such as the hardness of integer factorization
) must discover some unknown and undesirable property of the hash function used in the protocol to work. Many schemes have been proven secure in the random oracle model, for example OAEP
and PSS.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a random oracle is an oracle
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
(a theoretical black box) that responds to every query with a (truly) random response chosen uniformly from its output domain, except that for any specific query, it responds the same way every time it receives that query. Put another way, a random oracle is a mathematical function mapping every possible query to a random response from its output domain.
Random oracles are a mathematical abstraction used in cryptographic proofs; they are typically used when no known implementable function provides the mathematical properties required by the proof. A system that is proven secure using such a proof is described as being secure in the random oracle model, as opposed to secure in the standard model
Standard Model (cryptography)
In cryptography the standard model is the model of computation in which the adversary is only limited by the amount of time and computational power available. Other names used are bare model and plain model....
. In practice, random oracles are typically used to model cryptographic hash function
Cryptographic hash function
A cryptographic hash function is a deterministic procedure that takes an arbitrary block of data and returns a fixed-size bit string, the hash value, such that an accidental or intentional change to the data will change the hash value...
s in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof generally 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 the protocol. Not all uses of cryptographic hash functions require random oracles: schemes that require only some property or properties that have a definition in the standard model (such as collision resistance
Collision resistance
Collision resistance is a property of cryptographic hash functions: a hash function is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H = H, and a ≠ b.Every hash function with more inputs than outputs will necessarily have...
, preimage resistance, second preimage resistance, etc.) can often be proven secure in the standard model (e.g., the Cramer-Shoup cryptosystem
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 computational intractability of the decisional Diffie–Hellman...
).
Random oracles have long been considered in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
(e.g. Bennett & Gill). Fiat and Shamir (1986) showed a major application of random oracles - the removal of interaction from protocols for the creation of signatures. Impagliazzo and Rudich (1989) showed the limitation of random oracles - namely that their existence alone is not sufficient for secret-key exchange.
Bellare and Rogaway (1993) advocated their use in cryptographic constructions. In this definition, the random oracle produces a bit-string of infinite 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).
No real function can implement a true random oracle. In fact, certain artificial
Pathological (mathematics)
In mathematics, a pathological phenomenon is one whose properties are considered atypically bad or counterintuitive; the opposite is well-behaved....
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. Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence that an attack which does not break the other assumptions of the proof, if any (such as the hardness of integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
) must discover some unknown and undesirable property of the hash function used in the protocol to work. Many schemes have been proven secure in the random oracle model, for example OAEP
Optimal Asymmetric Encryption Padding
In cryptography, Optimal Asymmetric Encryption Padding is a padding scheme often used together with RSA encryption. OAEP was introduced by Bellare and Rogaway....
and PSS.
External links
- The Random Oracle Model — link farmLink farmOn the World Wide Web, a link farm is any group of web sites that all hyperlink to every other site in the group. Although some link farms can be created by hand, most are created through automated programs and services. A link farm is a form of spamming the index of a search engine...
maintained by Helger Lipmaa