Random oracle: Difference between revisions

Revision as of 16:30, 30 July 2005

Revision as of 16:33, 30 July 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 functions]] 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 find non-random properties in the random oracle's output, or solve some other 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 (for examplee.g., the [[Cramer-Shoup]] cryptosystem).

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