Random oracle: Difference between revisions

Revision as of 10:30, 24 May 2007

Revision as of 16:55, 24 May 2007

Line 1:

In [[cryptography]], a '''random oracle''' is an [[oracle machine|oracle]] (a theoretical [[black box (systems)|black box]], one of many such [[Oracle machine]]s) that responds to every query with a (truly) [[random]] response chosen [[uniform distribution (mathematics)|uniformly]] from its output ___domain, except that for any specific query, it responds the same way every time it receives that query. Put another way, a random oracle is a [[mathematical function]] mapping every possible query to a random response from its output ___domain.

Random oracles are a mathematical abstraction used in cryptographic proofs; they are typically used when no known implementable function provides the mathematical properties required by the proof. A system that is proven secure using such a proof is described as being secure in the ''random oracle model'', as opposed to secure in the ''standard model''. In practice, random oracles are typically used to model [[cryptographic hash function]]s in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof generally shows that a system or a protocol is secure by showing that an attacker must require impossible behavior from the oracle, or solve some 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]]).