The random oracle methodology, revisited

By Ran Canetti, Oded Goldreich, Shai Halevi. JACM, 2000

1,392 citations recorded by the source corpus.

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions".The main result of this article is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the above schemes, we consider possible definitions for the notion of a "good implementation" of a random oracle, pointing out limitations and challenges.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/1b7f8752c24da7b0b90f29e602c646f7d35a3f91

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Improved Garbled Circuit: Free XOR Gates and Applications (2008, background): “Although it was shown [5] that a protocol secure in the RO model may not be secure once RO is instantiated, “natural” RO protocols maintain their security in practice, and are widely used.”
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency (2008, background): “As shown by Canetti, Goldreich, and Halevi [8] and others in different contexts, we expect that there may be other non-interactive CS proof constructions for which no way to replace the oracle exists.)”
Chosen-Ciphertext Security from Identity-Based Encryption (2004, background): “Unfortunately, only a handful of public-key encryption schemes have been proven secure against adaptive chosenciphertext attacks without resorting to heuristics such as the random oracle methodology [3], a controversial and problematic approach [ 16 ].”
Random Oracles in a Quantum World (2010, methodology): “After all, the (classical) random oracle model already allows for provable secure solutions that lose any security guarantees when translated into the standard model, where the random oracle is instantiated by an eﬃcient hash function [CGH98].”
On the (im)possibility of obfuscating programs (2001, background): “’s critique of the Random Oracle Methodology [Canetti et al. 1998a].”
Sequential Aggregate Signatures and Multisignatures Without Random Oracles (2006, result): “A series of papers beginning with the uninstantiability result of Canetti, Goldreich, and Halevi [10] has cast some doubt on the soundness of the random oracle methodology, making random-oracle–free schemes more attractive.”
A Forward-Secure Public-Key Encryption Scheme (2003, neutral): “is instantiated with an efficiently computable “cryptographic hash function” [ 11 ].”
Security of public-key cryptosystems based on Chebyshev polynomials (2004, background): “However, it has been shown that there are schemes secure in the random oracle model but insecure in any implementation in the real world [6].”
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology (2004, methodology): “We show the following proposition which directly implies the separation result as formulated in [5]:”
Formal certification of code-based cryptographic proofs (2009, background): “hash functions, are assumed to be indistinguishable from random functions (despite the fact that no real function can implement a truly random function [ 13 ]).”
Introduction to Property Testing (2017, background): “, CS-proofs [190, 207] and their applications [31, 67]), and the length of the PCP affects the complexity of those applications.”
A Signature Scheme with Efficient Protocols (2002, background): “the plain model [12], and therefore in the plain model, these signature schemes are not provably secure.”
Advances in Cryptology — CRYPTO 2002 (2002, methodology): “A major improvement of this idea was the “subset difference” (SD) technique developed in Naor Naor and Lotspiech (NNL[6]), which is the current state of the art in stateless broadcast schemes.”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “Recent work [8, 19, 26] (see also [17]) has improved Micali’s construction by removing the random oracle, which is known to be uninstantiable [15], and replacing it with an “extractable collision-resistant hash function” (ECRH), whose security relies on the plausible, but non-falsifiable [37], assum”
Merkle-Damgård Revisited: How to Construct a Hash Function (2005, background): “In fact, many recent “separation” results [12, 27, 20, 2, 13, 16] illustrated various cryptographic systems secure in the random oracle model but completely insecure for any concrete instantiation of the random oracle (even by a family of hash functions).”
Short Pairing-Based Non-interactive Zero-Knowledge Arguments (2010, background): “Unfortunately, there are several examples of protocols that are secure in the random oracle model, but do not have any secure standard model instantiation no matter which hash-function is used [9,10,34,3,37].”
An Uninstantiable Random-Oracle-Model Scheme for a Hybrid-Encryption Problem (2004, background): “The example schemes provided by [8], however, are complex and contrived ones that do not resemble the kinds of RO schemes typically being designed.”