Random Oracle Model

The Random Oracle Model (ROM) is a heuristic commonly used in cryptography to prove security of systems, which are either difficult or impossible to prove secure otherwise. In this model, all parties are given access to an oracle, which is instantiated as a random and independent function. Then, proofs argue with high probability over the choice of a random oracle, schemes remain secure.

The ROM is related to the Random Oracle Hypothesis (attributed to Bennett and Gill), which conjectured that complexity-class relationships holding for almost all relativized worlds also hold unrelativized. The hypothesis was disproved by CCG+94.

Quantum random oracle model

In the quantum random oracle model (QROM), every party gets a uniformly random function $H:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\lambda }$; quantum algorithms, the adversary included, may query it in superposition through the unitary $|x,y⟩\mapsto |x,y\oplus H(x)⟩$, while honest parties query it classically — BDF+11. A proof in the classical ROM need not carry over: some scheme is secure against adversaries with classical oracle access and insecure against superposition queries — BDF+11.

Known Results

• The refutation of the ROH

• Fiat-Shamir is uninstantiable in the standard model — Goldwasser and Kalai constructed a 3-round public-coin protocol whose Fiat-Shamir transform is existentially forgeable under every concrete hash function, even though it is secure in the ROM GK03. This shows the random oracle cannot always be replaced by a concrete function.

• No fixed-construction reduction from Fiat-Shamir + GKR to SNARK

• ROM ⇒ OIHF

• OIHF ⇒ OT

• No fully-black-box reduction from OIHF to OT

Participates in

Builds on Random Oracle Model

• QROM ⇒ zk-SNARK (Micali’s construction in the QROM) (via Quantum random oracle model)
• ROM ⇒ Merkle puzzles
• ROM ⇒ OIHF
• ROM ⇒ SNARK (Micali’s CS proofs)

Barriers

• No reduction from ROM to KE
• No oracle-free-encoding reduction from ROM to public-key DEPIR with a sublinear key

Proved in the Random Oracle Model

• BDH ⇒ IBE (random oracle model)
• Bilinear pairing + q-DLOG ⇒ Universal SNARK (PLONK)
• Bilinear pairing ⇒ CP-ABE
• co-CDH ⇒ BLS multi-signatures with public-key aggregation
• co-CDH ⇒ Aggregate signatures (BGLS)
• co-CDH ⇒ BLS signatures
• DCR ⇒ TPKE
• DLOG ⇒ Schnorr signatures
• DLOG ⇒ BLS signatures
• DLOG ⇒ PCS
• HVZK ⇒ NIZK (Fiat–Shamir)
• CRHF ⇒ PCS
• CRHF ⇒ STARK
• ID ⇒ DS
• IND-CPA PKE ⇒ IND-CCA KEM (Fujisaki–Okamoto)
• LWE ⇒ IBE (Gentry–Peikert–Vaikuntanathan, random oracle model)
• Module LWE + Module-SIS ⇒ DS
• Module LWE ⇒ IND-CCA KEM
• NTRU + NTRU-SIS ⇒ DS
• NTRU ⇒ IND-CCA KEM
• OMDL + ROS ⇒ Blind Schnorr signatures
• OMDL ⇒ MuSig2
• OT ⇒ OT extension (IKNP)
• Extractable PCS ⇒ SNARK
• Φ-Hiding ⇒ DS (RSA full-domain hash, tight)
• Prime-order CDH ⇒ EDL signatures
• Prime-order DDH ⇒ Katz–Wang signatures
• DLOG ⇒ Blind Okamoto–Schnorr signatures
• DLOG ⇒ EdDSA
• DLOG ⇒ MuSig
• DLOG ⇒ Schnorr signatures (tight, AGM)
• RSA ⇒ IND-CCA PKE (RSA-OAEP)
• RSA ⇒ IND-CCA KEM
• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)
• SIS ⇒ DS
• Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG)
• Succinct state-restoration-sound IOP ⇒ STARK (BCS transform)
• TDP ⇒ DS (full-domain hash, random oracle model)
• Type 1 pairing + CDH ⇒ Multi-signatures in the KOSK model (Boldyreva)
• Type 1 pairing + CDH ⇒ Multi-signatures with proofs of possession