A '''random oracle''' is a theoreticalmathematical modelabstraction of aused in [[cryptography|cryptographic hash function]] proofs. ItRandom isoracles usedare typically included in proofs thatwhen indicateno "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 [[cryptography|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 eitherfind considernon-random howproperties in the hashrandom functionoracle's worksoutput, 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 example, the [[Cramer-Shoup]] cryptosystem).
When a random oracle is given a query ''x'' it does the following:
Line 5:
*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 a more precise definition, the random oracle produces an infinite-length output 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 in the security definition, including the adversary or adversaries. A single oracle 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 hash 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 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]].
