Random oracle
In cryptography, a random oracle is an (a theoretical ) that responds to every unique query with a (truly) response chosen 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 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 firstly used in rigorous cryptographic proofs in the 1993 publication by and (1993). They are typically used when the cryptographic hash functions in the method cannot be proven to possess the mathematical properties required by the proof. 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 .
Contents
Applications
Random oracles are typically used<!– See talk page “Weasel Words”–> as an replacement for cryptographic hash functions 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 in order to break it.
Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the (such as , , , etc.) can often be proven secure in the standard model (e.g., the ).
Random oracles have long been considered in , and many schemes have been proven secure in the random oracle model, for example , and . In 1986, and 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 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 , 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<sup>A</sup> = NP<sup>A</sup>, subsequent work by Bennett and Gill, showed that for a random oracle B (a function from {0,1}<sup>n</sup> 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<sup>B</sup> ⊊ NP<sup>B</sup> 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 ), led to the creation of the Random Oracle Hypothesis, that two “acceptable” complexity classes C<sub>1</sub> and C<sub>2</sub> 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 despite IP<sup>A</sup> ⊊ PSPACE<sup>A</sup> for a random oracle A with probability 1.
== Ideal cipher == <!— checked for possible R to section but not sure on this from search, could mean other ciphers –>
An ideal cipher is a 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 . 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 .