Random oracle: Difference between revisions

Revision as of 13:42, 8 May 2007

Revision as of 03:45, 17 May 2007

Line 3:

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]]).

In the more precise definition formalized by Bellare/Rogaway (1993), the random oracle produces a bit-string of infinite length which can be truncated to the length desired. 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 seperateseparate random oracles).

No real function can implement a true random oracle. In fact, certain artificial signature and encryption schemes are known which are proven secure in the random oracle model, but which are trivially insecure when any real function is substituted for the random oracle. Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence that an attack which does not break the other assumptions of the proof, if any (such as the hardness of [[integer factorization]]) must discover some unknown and undesirable property of the hash function used in the protocol to work. Many schemes have been proven secure in the random oracle model, for example [[Optimal Asymmetric Encryption Padding|OAEP]] and [[Probabilistic Signature Scheme|PSS]].