Srikar at 18:40, 15 July 2020

2020-07-15T18:40:25Z

Srikar: Created page with "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 dom..."

2020-07-01T00:17:55Z

Created page with "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 dom..."

New page

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.

← Older revision		Revision as of 18:40, 15 July 2020
Line 7:		Line 7:
	===Limitations===		===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.		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.

Random Oracle Model - Revision history

Srikar at 18:40, 15 July 2020

Srikar: Created page with "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 dom..."