Random oracle
In
Stated differently, a random oracle is a
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
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 of cryptography.
Applications
Random oracles are typically used as an
Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the
Random oracles have long been considered in
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[6] showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange.
In 1993, Mihir Bellare and Phillip Rogaway[2] 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
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.[9][10] 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.[11]
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
This section may need to be rewritten to comply with Wikipedia's quality standards. (February 2024) |
Although the Baker–Gill–Solovay theorem[12] showed that there exists an oracle A such that PA = NPA, subsequent work by Bennett and Gill,[13] showed that for a random oracle B (a function from {0,1}n 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), PB ⊊ NPB 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), led to the creation of the Random Oracle Hypothesis, that two "acceptable" complexity classes C1 and C2 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[13]). This hypothesis was later shown to be false, as the two acceptable complexity classes IP and PSPACE were shown to be equal[14] despite IPA ⊊ PSPACEA for a random oracle A with probability 1.[15]
Ideal cipher
An ideal cipher is a
Recent works showed that an ideal cipher can be constructed from a random oracle using 10-round
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 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.[18] Many of the classical security proofs break down in that quantum random oracle model and need to be revised.
See also
- Sponge function
- Oracle machine
- Topics in cryptography
References
- doi:10.1137/0210008.
- ^ S2CID 3047274.
- ISBN 978-1-4665-7027-6.
- ISSN 1095-7111
- CRYPTO. pp. 186–194.
- ^ Impagliazzo, Russell; Rudich, Steven (1989). "Limits on the Provable Consequences of One-Way Permutations". STOC: 44–61.
- ^ Bellare, Davis & Günther 2020, p. 3.
- ^ Bellare, Davis & Günther 2020, p. 4.
- ^ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).
- ^ Craig Gentry and Zulfikar Ramzan. "Eliminating Random Permutation Oracles in the Even-Mansour Cipher". 2004.
- ^ Koblitz, Neal; Menezes, Alfred J. (2015). "The Random Oracle Model: A Twenty-Year Retrospective" (PDF). Another Look. Archived from the original (PDF) on 2 April 2015. Retrieved 6 March 2015.
- doi:10.1137/0204037.
- ^ doi:10.1137/0210008.
- S2CID 315182.
- ISSN 0022-0000.
- .
- ^ Dai, Yuanxi; Steinberger, John (2016). "Indifferentiability of 8-Round Feistel Networks". CRYPTO 2016. Springer.
- ISBN 978-3-642-25384-3.)
{{cite conference}}
: CS1 maint: multiple names: authors list (link
Sources
- Bellare, Mihir; Davis, Hannah; Günther, Felix (2020). "Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability". Advances in Cryptology – EUROCRYPT 2020. Lecture Notes in Computer Science. Vol. 12106. Cham: Springer International Publishing. pp. 3–32. S2CID 214642193.