Random oracle: Difference between revisions

Revision as of 21:55, 30 July 2005

Revision as of 08:31, 15 September 2005

Line 1:

A '''random oracle''' is a mathematical abstraction used in [[cryptography|cryptographic]] proofs. Random oracles are typically included in proofs when no "real" function (that can be implemented) provides sufficient mathematical properties to satisfy the proof of security. Proofs which make use of random oracles are referred to as secure in the "random oracle model", as opposed to the "standard model". In practice, random oracles are typically used to model [[cryptographic hash functionsfunction]]s in schemes where strong randomness assumptions are needed of the hash function's output. Such proofs indicate that systems or protocols are secure by showing that an attacker must require impossible behavior from the oracle, or solve some other mathematical problem believed hard, in order to break the protocol. Not all uses of cryptographic hash functions require random oracles: schemes which require only the property of [[collision resistance]] can be proven secure in the standard model (e.g., the [[Cramer-Shoup]] cryptosystem).

When a random oracle is given a query ''x'' it does the following: