In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random 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 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. 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. 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, a differentiation from being secure in the standard model of cryptography.
Applications Random oracles are typically used as an idealised replacement for cryptographic hash functions 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 (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, and many schemes have been proven secure in the random oracle model, for example Optimal Asymmetric Encryption Padding, RSA-FDH and PSS. In 1986, Amos Fiat and Adi Shamir 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 used random oracles to show an oracle separation between one-way functions and secret-key exchange, by exhibiting an oracle relative to which one-way functions exists but secret-key exchange — and thus also public-key encryption — does not exist. Their result show that there is no black-box construction of public-key encryption from one-way functions, thus suggesting that one-way functions are a weaker assumption than public-key encryption. In 1993, Mihir Bellare and Phillip Rogaway were the first to advocate their use in cryptographic constructions. In their 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.
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). Oracle cloning with improper domain separation breaks security proofs and can lead to successful attacks.
Limitations According to the Church–Turing thesis, 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 contrived 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 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, 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
… excerpt ends here. Continue reading the full article.
