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.

Known Results

• No relativizing reduction from ROM to 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 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

• DLOG + ROM ⇒ Schnorr signatures
• ID + ROM ⇒ DS
• interactive protocol + ROM ⇒ NIZK
• interactive protocol + ROM ⇒ SNARK
• IP + ROM ⇒ SNARK
• ROM + ZKP ⇒ DS
• ROM + ZKP ⇒ NIZK
• ROM ⇒ OIHF

Barriers

• No reduction from ROM to KE
• No reduction from ROM to Merkle puzzles
• No relativizing reduction from ROM to ROH