Random Oracle Model

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time that query is submitted. Random oracles as a mathematical abstraction were firstly used in rigorous cryptographic proofs in the 1993 publication by Mihir Bellare and Phillip Rogaway (1993).[1] They are typically used when the proof cannot be carried out using weaker assumptions on the cryptographic hash function. A system that is proven secure when every hash function is replaced by a random oracle is described as being secure in the random oracle model, as opposed to secure in the standard model of cryptography.

Application

When a random oracle is used within a security proof, it is made available to all players, including the adversary or adversaries. A single oracle may be treated as multiple oracles by pre-pending a fixed bit-string to the beginning of each query (e.g., queries formatted as "1|x" or "0|x" can be considered as calls to two separate random oracles, similarly "00|x", "01|x", "10|x" and "11|x" can be used to represent calls to four separate random oracles).

Limitations

In 1989, Russell Impagliazzo and Steven Rudich[5] showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange.

Usage within ZK

The Fiat-Shamir Heuristic depends on the security of the ROM (Random Oracle Model). This heuristic is used, for example, to convert a Linear Interactive Proof into A NILP before the final construction of a zk-SNARK for an arithmetic circuit.