Random oracles are practical: a paradigm for designing efficient protocols

By Mihir Bellare, Phillip Rogaway. 1993

We argue that the random oracle model—where all parties have access to a public random oracle—provides a bridge between cryptographic theory and cryptographic practice. In the paradigm we suggest, a practical protocol <italic>P</italic> is produced by first devising and proving correct a protocol <italic>P<supscrpt>R</supscrpt></italic> for the random oracle model, and then replacing oracle accesses by the computation of an “appropriately chosen” function <italic>h</italic>. This paradigm yields protocols much more efficient than standard ones while retaining many of the advantages of provable security. We illustrate these gains for problems including encryption, signatures, and zero-knowledge proofs.

How researchers see this paper

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

Citations in the corpus

Bulletproofs: Short Proofs for Confidential Transactions and More (2018, methodology): “It is therefore possible to turn the protocol into a noninteractive protocol that is secure and full zero-knowledge in the random oracle model using the Fiat-Shamir heuristic [62].”
Proactively Accountable Anonymous Messaging in Verdict (2012, methodology): “In practice, each of our current implementations of this verifiable DC-nets primitive achieve these security properties in the random-oracle model [5] using noninteractive zero-knowledge proofs [26].”
Riposte: An Anonymous Messaging System Handling Millions of Users (2015, methodology): “The protocol uses a hash function H : {0,1}∗ → {0,1}λ , which we model as a random oracle [6].”
Non-interactive cryptocomputing for NC/sup 1/ (1999, background): “We note that without assuming the trusted random string, proofs which assure robustness on encrypted values whose decryption is assumed not in BPP, seem to require interaction based on our beliefs regarding computational complexity conjectures [24], (unless the random oracle model is assumed as a pr”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, background): “RandomOracle (RO) is a heuristic model for the security of hash functions, introduced by Bellare and Rogaway (1993). The idea is to treat the hash function as a public, idealized random function.”
Applications of Multilinear Forms to Cryptography (2002, background): “Unique signature schemes were known to exist in the common random string model [12] and in the random oracle model [1], but until the results of Micali et al.”
Faster Secure Two-Party Computation Using Garbled Circuits (2011, methodology): “The protocol we implement can be proven secure based on the decisional Difﬁe-Hellman assumption in the random oracle model [2].”
Provable data possession at untrusted stores (2007, methodology): “h is computed by squaring the output of the full-domain hash function for the provably secure FDH signature scheme [8, 9] based on RSA.”
Reusable cryptographic fuzzy extractors (2004, methodology): “extractor with insider security using random oracles [1].”
Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation (2014, methodology): “Some of our constructions will be analyzed in the random oracle model [1], with the random oracle denoted H .”
Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology (2004, methodology): “Its importance in cryptography is due to the so called random oracle methodology, first made explicit by Bellare and Rogaway [ 1 ], where the security of cryptosystems is proven under the assumption that any party has access to a random oracle.”
Information sharing across private databases (2003, methodology): “In the proofs of our security statements we shall rely on the standard random oracle model [8, 24, 46].”
Scalable, transparent, and post-quantum secure computational integrity (2018, unknown): “[10] Mihir Bellare and Phillip Rogaway.”
Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives (2017, background): “Lattice-based signature schemes secure under the short integer solution (SIS) problem on lattices following the Full-Domain-Hash (FDH) paradigm [13] have been introduced in [43].”
Secure Hybrid Encryption from Weakened Key Encapsulation (2007, background): “1 This is reminiscent to the notion of plaintext awareness for public-key encryption [5] where it is infeasible for an adversary to come up with a valid ciphertext without being aware of the corresponding plaintext.”
Bitcoin-NG: A Scalable Blockchain Protocol (2015, background): “Each node can poll a random oracle [6] as a random bit source.”
Merkle-Damgård Revisited: How to Construct a Hash Function (2005, methodology): “The random oracle model has been introduced by Bellare and Rogaway as a “paradigm for designing efficient protocols” [4].”
RingCT 2.0: A Compact Accumulator-Based (Linkable Ring Signature) Protocol for Blockchain Cryptocurrency Monero (2017, background): “Signature schemes generated as such are provably secure [27] against existential forgery under adaptively chosen message attack in the random oracle model [8].”