{
 "id": "epd4fk40h4",
 "slug": "random-oracle-model",
 "title": "Random oracle model",
 "updated": "2026-10-15",
 "topic_path": [
  {
   "id": "physical",
   "label": "Physical world and mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical"
  },
  {
   "id": "physical.math",
   "label": "Mathematics and statistics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math"
  },
  {
   "id": "physical.math.discrete",
   "label": "Logic and discrete mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/topics/physical.math.discrete"
  }
 ],
 "geo": [
  {
   "id": "geo.nongeo.t1946.physical.math.discrete",
   "label": "Non-geographic · 1946 to 2000: Logic and discrete mathematics",
   "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete",
   "path": [
    {
     "id": "geo.nongeo",
     "label": "Non-geographic",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo"
    },
    {
     "id": "geo.nongeo.t1946",
     "label": "Non-geographic · 1946 to 2000",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946"
    },
    {
     "id": "geo.nongeo.t1946.physical",
     "label": "Physical world and mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical"
    },
    {
     "id": "geo.nongeo.t1946.physical.math",
     "label": "Mathematics and statistics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math"
    },
    {
     "id": "geo.nongeo.t1946.physical.math.discrete",
     "label": "Logic and discrete mathematics",
     "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.physical.math.discrete"
    }
   ]
  }
 ],
 "excerpt": "The random oracle model is a cryptographic proof technique treating a hash function as a perfectly random public function, formulated by Bellare and Rogaway in 1993.",
 "snippet": "The random oracle model is a cryptographic proof technique treating a hash function as a perfectly random public function, formulated by Bellare and Rogaway in 1993.",
 "node": "physical.math.discrete",
 "markdown": "# Random oracle model\n\nThe random oracle model (ROM) is a proof technique in cryptography that treats a hash function as a perfectly random public function, making it possible to give rigorous security proofs for schemes such as Full Domain Hash signatures and OAEP encryption.<sup>[1](https://eprint.iacr.org/2015/140.pdf)</sup> Formally, the model defines a map \\( H: \\{0,1\\}^{*} \\to \\{0,1\\}^{n} \\) that associates a random bitstring to every string, and gives all parties, including the adversary, oracle access to it; the final heuristic step replaces \\( H \\) with something like a cryptographic hash function.<sup>[2](https://malb.io/7CCSMATC/lecture-rom.pdf)</sup> No efficiently computable hash function can actually be a random function, since a true random function would need an exponentially large description, so a ROM proof is no guarantee of real-world security, though it is better than no proof at all.<sup>[3](https://www.cs.umd.edu/~jkatz/crypto/f02/lectures/lecture39.pdf)</sup> The paradigm yields protocols far more efficient than standard-model ones, and many widely relied-upon primitives are proven secure only in this model; as one set of lecture notes puts it, essentially the Internet runs on the random oracle model.<sup>[2](https://malb.io/7CCSMATC/lecture-rom.pdf)</sup>\n\n| Key fact | Detail |\n|---|---|\n| Model assumption | The hash \\( H \\) is a black box returning a fresh random value per query, repeating the same response if the same input is queried again<sup>[1](https://eprint.iacr.org/2015/140.pdf)</sup> |\n| Formulation | Bellare and Rogaway, \"Random Oracles are Practical\", CCS '93, pp. 62-73<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> |\n| Methodology | Prove security in the ROM, then replace oracle calls by computation of an \"appropriately chosen\" function \\( h \\); this step is a heuristic trusted from experience<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> |\n| Proof levers | Observability (the reduction sees all hash queries) and programmability (the reduction sets oracle answers, correctly distributed)<sup>[5](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)</sup> |\n| Impossibility | Signature and encryption schemes exist that are secure in the ROM but insecure under any implementation of the oracle<sup>[6](https://dl.acm.org/doi/10.1145/1008731.1008734)</sup> |\n| Concrete bounds | With \\( T \\) queries to an \\( n \\)-bit oracle, preimage success is bounded by \\( T/2^{n} \\) and collision success by \\( T^{2}/2^{n} \\)<sup>[7](https://www.khoury.northeastern.edu/home/wichs/class/crypto-fall17/lecture11.pdf)</sup> |\n| Quantum extension | The QROM, where the adversary queries the oracle in superposition, was studied by Boneh and colleagues in 2010<sup>[8](https://doi.org/10.48550/arxiv.1008.0931)</sup> |\n\n## How it works\n\nIn the model, the hash function \\( H \\) is a black box that answers a query for \\( H(M) \\) with a random value, keeping a record so the same \\( M \\) always gets the same answer.<sup>[1](https://eprint.iacr.org/2015/140.pdf)</sup> A ROM security proof is a reduction: given a hypothetical forging algorithm with a specified success probability, one constructs an algorithm that inverts the underlying trapdoor one-way permutation with comparable probability.<sup>[9](https://cs.uwaterloo.ca/~dstinson/CO_685/randomoracle.html)</sup> The reduction exploits two properties unavailable in the standard model. Observability means the reduction sees every hash query the adversary makes; programmability means the reduction can set oracle answers to values of its choice, as long as they are correctly distributed.<sup>[5](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)</sup> The simulator is also allowed to prescribe a small, polynomial-sized piece of the oracle and have the rest filled in at random, an operation Bellare and Rogaway call random oracle completion.<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> In simulation-based proofs the simulator sees the queries parties make and chooses the answers, which lets it plant chosen return values for strategically chosen queries; in chosen-ciphertext proofs the adversary effectively hands over the plaintext through its own calls to \\( H \\), so for schemes admitting such proofs, CCA attacks are no more powerful than CPA attacks.<sup>[2](https://malb.io/7CCSMATC/lecture-rom.pdf)</sup>\n\n## How it is done\n\nThe methodology has four steps: find a formal definition in a model where all parties share a random oracle \\( R \\); devise an efficient protocol \\( P \\) for that model; prove \\( P \\) satisfies the definition; and replace oracle accesses to \\( R \\) by computation of an appropriately chosen function \\( h \\).<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> The reduction itself typically proceeds by guess-and-program. For the Full Domain Hash signature, which signs \\( M \\) by computing \\( s = f^{-1}(H(M)) \\) with \\( H \\) mapping onto the full domain, the inverter guesses which of the adversary's \\( q_{h} \\) hash queries will be forged, programs \\( O(m^{*}) = y^{*} \\) for the challenge \\( y^{*} \\), answers other queries with \\( f(x) \\) for random \\( x \\), and aborts on signature requests for \\( m^{*} \\); it inverts with probability at least \\( \\varepsilon/q_{h} \\).<sup>[5](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)</sup><sup> • </sup><sup>[10](https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf)</sup> Schnorr-signature proofs instead run the adversary twice with the same random tape but different hash answers at the guessed query, extracting the discrete log as \\( x = (s - s')/(h - h') \\bmod q \\), with success probability roughly \\( \\varepsilon^{2}/q_{h} \\), a quadratic loss.<sup>[5](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)</sup> Concrete security is read off from query complexity: an adversary making \\( T \\) queries to an \\( n \\)-bit oracle succeeds at a preimage-style task with probability at most \\( T/2^{n} \\), and finds a collision with probability at most \\( T^{2}/2^{n} \\), the birthday bound.<sup>[7](https://www.khoury.northeastern.edu/home/wichs/class/crypto-fall17/lecture11.pdf)</sup> When the oracle is instantiated by a concrete hash, these guarantees are modified in a hand-wavy manner, with \\( T \\) replaced by the running time of the hash.<sup>[7](https://www.khoury.northeastern.edu/home/wichs/class/crypto-fall17/lecture11.pdf)</sup>\n\n## Origin\n\nThe model and the methodology were formulated by Mihir Bellare and Phillip Rogaway in \"Random Oracles are Practical: A Paradigm for Designing Efficient Protocols\", presented at CCS '93 in December 1993, pages 62-73.<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> The public random oracle model, accessible to all parties including the adversary, was adopted in an identification-to-signature transformation, and hash functions were concurrently viewed as public random oracles to justify an efficient signature scheme with exact, non-asymptotic security.<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> The same paper traces the prove-then-instantiate pattern, modeling one-way functions as random oracles to show that proving existence of secret key exchange from a black-box one-way function is as hard as separating P from NP.<sup>[4](https://dl.acm.org/doi/10.1145/168588.168596)</sup> Serious criticism began with Canetti, Goldreich, and Halevi's 1998 uninstantiability result, published in journal form in the Journal of the ACM 51(4) in July 2004.<sup>[6](https://dl.acm.org/doi/10.1145/1008731.1008734)</sup>\n\n## Variants\n\nVariants differ in how much power the simulator has over the oracle. The fully programmable (FPRO), explicitly programmable (EPRO, equivalent to the Bellare-Rogaway formulation), and non-programmable (NPRO, a term coined by Nielsen) models form a hierarchy in which NPRO security implies EPRO, which implies FPRO.<sup>[11](https://www2.seas.gwu.edu/~hoeteck/pubs/zkrom-ac09.pdf)</sup> Programmability matters: only languages in BPP have a one-round NPRO zero-knowledge protocol, a triviality result showing the non-programmable oracle is far weaker.<sup>[11](https://www2.seas.gwu.edu/~hoeteck/pubs/zkrom-ac09.pdf)</sup> The Weakly-Programmable Random Oracle (WPRO) model, where outputs are \\( \\rho(r) \\) for random coin-strings \\( r \\) visible only to adversaries, is equivalent to the ROM as a model, yet no black-box reduction proves FDH secure even in the weak WPROM sense.<sup>[12](https://rist.tech.cornell.edu/papers/npro.pdf)</sup> On the realization side, Canetti proposed in 1997 a program of identifying and realizing useful oracle properties, introducing oracle hashing, a probabilistic hash function that hides all partial information about its input while allowing verification.<sup>[13](https://courses.csail.mit.edu/6.885/spring05/papers/canetti-crypto97.pdf)</sup> Indifferentiability is a generalization of indistinguishability for settings where the adversary sees additional information such as the public description of the hash.<sup>[14](https://crypto-test.ethz.ch/publications/files/MaReHo04.pdf)</sup> When adversaries can query the oracle in superposition, the model becomes the quantum random oracle model, studied in \"Random Oracles in a Quantum World\" by Boneh and colleagues, published on arXiv in 2010.<sup>[8](https://doi.org/10.48550/arxiv.1008.0931)</sup>\n\n## Applications\n\nFlagship constructions are defined and proven secure in the ROM. Full Domain Hash signs by computing \\( s = f^{-1}(H(M)) \\), and its security follows from the assumption that RSA is a trapdoor permutation when the hash is ideal.<sup>[10](https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf)</sup> Its reduction is loose, losing a factor on the order of the number of hash and signing queries, whereas the PSS scheme achieves tight security: the forgery probability stays within an additive, rather than multiplicative, factor of the RSA inversion probability, with the additive term decreasing exponentially in the seed parameters \\( k_{0} \\) and \\( k_{1} \\).<sup>[10](https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf)</sup> OAEP encryption and Schnorr signatures are ROM-proven, though the Schnorr security reductions were lost in going from Schnorr to DSA, and the same remark applies to ECDSA.<sup>[1](https://eprint.iacr.org/2015/140.pdf)</sup> The BLS reduction programs one hash query to the co-CDH challenge and extracts the forgery, winning with probability at least \\( \\varepsilon \\cdot (1 - 1/q_{h})^{q_{s}} \\cdot (1/q_{h}) \\).<sup>[5](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)</sup> Post-quantum schemes also lean on idealized hashes: Fujisaki-Okamoto transformations are analyzed in the QROM, and recent work certifies ML-KEM-768 decapsulation-failure bounds within an explicit random-function abstraction.<sup>[15](https://link.springer.com/article/10.1186/s42400-024-00228-6)</sup><sup> • </sup><sup>[16](https://arxiv.org/abs/2609.09983)</sup>\n\n## Limitations and alternatives\n\nCanetti, Goldreich and Halevi proved that there exist signature and encryption schemes secure in the ROM for which any implementation of the oracle is insecure.<sup>[6](https://dl.acm.org/doi/10.1145/1008731.1008734)</sup> Their schemes search for a preimage pair lying in an evasive relation (input-output relation that a random oracle almost never satisfies), rare under a random oracle, and output the secret key if found; any adversary can force this under any concrete implementation, and the argument relies on the function's description being shorter than its input.<sup>[6](https://dl.acm.org/doi/10.1145/1008731.1008734)</sup> They also show that correlation intractability, the infeasibility of finding an input-output pair satisfying an evasive relation, cannot be achieved by any fully specified function ensemble, so even the minimal property behind heuristics like Fiat-Shamir is unrealizable.<sup>[6](https://dl.acm.org/doi/10.1145/1008731.1008734)</sup> A concrete variant of the counterexample encrypts a boolean circuit for \\( H \\) itself, which leaks the key for any public efficiently computable \\( H \\).<sup>[2](https://malb.io/7CCSMATC/lecture-rom.pdf)</sup> There are also cryptanalytic gaps between idealized and real instantiations of the Bellare-Rogaway constructions themselves: for 1024-bit digests, a \\( 2^{30} \\) preimage attack on the BR93 instantiation and a \\( 2^{106} \\) collision attack on BR96 fall short of the ideal \\( 2^{n} \\) and \\( 2^{n/2} \\) levels.<sup>[17](https://eprint.iacr.org/2008/441.pdf)</sup> Separation results extend further: FDH security cannot be established without random oracles when the trapdoor permutation is a black box, though chosen-message security of FDH is achievable in the standard model with a special replacement hash function.<sup>[1](https://eprint.iacr.org/2015/140.pdf)</sup> Against this, no practical protocol proven secure in the ROM has been broken when used with a currently secure hash function such as [SHA-2](https://www.edgepedia.org/sha-2) or [SHA-3](https://www.edgepedia.org/sha-3), whereas SHA-1 was deprecated by NIST in 2011 and disallowed for digital signatures at the end of 2013 after practical collision attacks; the CGH counterexample was an artificial protocol designed explicitly for the proof.<sup>[9](https://cs.uwaterloo.ca/~dstinson/CO_685/randomoracle.html)</sup> Standard-model alternatives include oracle hashing, which hides all partial information and can replace the oracle in some Bellare-Rogaway encryption schemes.<sup>[13](https://courses.csail.mit.edu/6.885/spring05/papers/canetti-crypto97.pdf)</sup>\n\n## References\n\n1. [The Random Oracle Model: A Twenty-Year Retrospective (Koblitz and Menezes)](https://eprint.iacr.org/2015/140.pdf)\n2. [The Random Oracle Model, Advanced Topics in Cryptography (King's College London lecture notes)](https://malb.io/7CCSMATC/lecture-rom.pdf)\n3. [Lecture 39: The Random Oracle Model (Jonathan Katz, University of Maryland)](https://www.cs.umd.edu/~jkatz/crypto/f02/lectures/lecture39.pdf)\n4. [Random oracles are practical: a paradigm for designing efficient protocols (Bellare & Rogaway, CCS '93)](https://dl.acm.org/doi/10.1145/168588.168596)\n5. [Random Oracles, FDH, Schnorr, BLS, CS 276 lecture notes (UC Berkeley)](https://crypto-berkeley.github.io/cs276-spring26/assets/lecture-notes/chap5-3.pdf)\n6. [The random oracle methodology, revisited (Canetti, Goldreich, Halevi; JACM 51(4), 2004; ePrint 1998/011 and author copies merged)](https://dl.acm.org/doi/10.1145/1008731.1008734)\n7. [Lecture 11: Hash Functions and Random Oracle Model (Northeastern University)](https://www.khoury.northeastern.edu/home/wichs/class/crypto-fall17/lecture11.pdf)\n8. [Boneh, Dan and colleagues (2010). Random Oracles in a Quantum World. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.1008.0931)\n9. [The Random Oracle Model, What Does It Mean? (Doug Stinson, University of Waterloo)](https://cs.uwaterloo.ca/~dstinson/CO_685/randomoracle.html)\n10. [Exact Security of Digital Signatures: How to Sign with RSA and Negligible Security Loss (Bellare & Rogaway, Crypto '96)](https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf)\n11. [Zero-knowledge in the random oracle model (FPRO/EPRO/NPRO variants)](https://www2.seas.gwu.edu/~hoeteck/pubs/zkrom-ac09.pdf)\n12. [Modeling (non-)programmability in random oracle reductions (WPRO model)](https://rist.tech.cornell.edu/papers/npro.pdf)\n13. [Towards Realizing Random Oracles: Hash Functions that Hide All Partial Information (Canetti, CRYPTO '97)](https://courses.csail.mit.edu/6.885/spring05/papers/canetti-crypto97.pdf)\n14. [Indifferentiability and Irreducibility (Maurer, Renner, Holenstein)](https://crypto-test.ethz.ch/publications/files/MaReHo04.pdf)\n15. [Double-sided: tight proofs for guessing games in the quantum random oracle model (Cybersecurity, 2024)](https://link.springer.com/article/10.1186/s42400-024-00228-6)\n16. [Dependency-Aware ROM/CBD Correctness Bounds for ML-KEM-768 at the Heuristic Failure Scale (arXiv, 2026)](https://arxiv.org/abs/2609.09983)\n17. [How Risky is the Random-Oracle Model? (ePrint 2008/441)](https://eprint.iacr.org/2008/441.pdf)\n\n---\n*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n",
 "same_as": [
  "https://www.cs.umd.edu/~jkatz/crypto/f02/lectures/lecture39.pdf",
  "https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf",
  "https://www2.seas.gwu.edu/~hoeteck/pubs/zkrom-ac09.pdf"
 ],
 "url": "https://www.edgepedia.org/random-oracle-model",
 "markdown_url": "https://www.edgepedia.org/random-oracle-model.md",
 "license": {
  "name": "Edgepedia Community License 1.0",
  "url": "https://www.edgepedia.org/edgepedia/license",
  "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.",
  "spdx": "LicenseRef-Edgepedia-Community-1.0"
 },
 "credit": "\"Random oracle model\", Edgepedia (EdgeChat), https://www.edgepedia.org/random-oracle-model. Edgepedia Community License 1.0.",
 "credit_md": "\"[Random oracle model](https://www.edgepedia.org/random-oracle-model)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/random-oracle-model](https://www.edgepedia.org/random-oracle-model). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).",
 "credit_html": "\"<a href=\"https://www.edgepedia.org/random-oracle-model\">Random oracle model</a>\", Edgepedia (EdgeChat), <a href=\"https://www.edgepedia.org/random-oracle-model\">https://www.edgepedia.org/random-oracle-model</a>. <a href=\"https://www.edgepedia.org/edgepedia/license\">Edgepedia Community License 1.0</a>.",
 "speakable": "The random oracle model is a cryptographic proof technique treating a hash function as a perfectly random public function, formulated by Bellare and Rogaway in 1993."
}