Random oracle: Difference between revisions

Revision as of 11:19, 3 August 2006

Revision as of 21:08, 8 August 2006

Line 1:

In [[cryptography]], a '''random oracle''' is a theoretical [[black box (systems)|black box]] 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 returns 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.

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 function]]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_system|Cramer-Shoup cryptosystem]]).

ARandom '''randomoracles oracle''' isare a mathematical abstraction used in [[cryptography|cryptographic]] proofs.; Random oraclesthey are typically included in proofsused when no "real"known implementable function (that can be implemented) provides sufficientthe mathematical properties torequired satisfyby the proof. of security.A system Proofsthat whichis makeproven usesecure ofusing randomsuch oraclesa areproof referredis todescribed 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 proofsa indicateproof generally shows that systemsa system or protocolsa areprotocol is 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_system|Cramer-Shoup cryptosystem]]).

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

*If the oracle has been given the query ''x'' before, it responds with the same value it gave the last time.

*If the oracle hasn't been given the query ''x'' before, it generates a [[random]] response which has uniform probability of being chosen from anywhere in the [[oracle]]'s output ___domain.

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

No real function can implement a true random oracle. In fact, certain very artificial protocols have been constructed which are proven secure in the random oracle model, but which are trivially insecure when any real hash 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_PaddingOptimal Asymmetric Encryption Padding|OAEP]] and [[Probabilistic_Signature_SchemeProbabilistic Signature Scheme|PSS]].

==See also==

Line 17 ⟶ 15:

==External links==

* [http://www.cs.ut.ee/~helger/crypto/link/rom/ The Random Oracle Model] -— [[link farm]] maintained by [[Helger Lipmaa]]

[[Category:Cryptographic hash functions]]