Admin: Created page with "In cryptography, a '''random oracle''' is an oracle (a theoretical black box) that responds to every ''unique query'' with a (tr..."

2019-07-03T08:43:52Z

Created page with "In cryptography, a '''random oracle''' is an oracle (a theoretical black box) that responds to every ''unique query'' with a (tr..."

New page

In [[cryptography]], a '''random oracle''' is an [[oracle machine|oracle]] (a theoretical [[black box (systems)|black box]]) that responds to every ''unique query'' with a (truly) [[random]] response chosen [[uniform distribution (discrete)|uniformly]] from its output domain. If a query is repeated it responds the same way every time that query is submitted.

Stated differently, a random oracle is a [[mathematical function]] chosen uniformly at random, that is, a function mapping each possible query to a (fixed) random response from its output domain.

Random oracles as a mathematical abstraction were firstly used in rigorous cryptographic proofs in the 1993 publication by [[Mihir Bellare]] and [[Phillip Rogaway]] (1993). They are typically used when the [[cryptographic hash function]]s in the method cannot be proven to possess the mathematical properties required by the proof. A system that is proven secure when every hash function is replaced by a random oracle is described as being secure in the '''random oracle model''', as opposed to secure in the [[Standard Model (cryptography)|standard model of cryptography]].

== Applications ==
Random oracles are typically used as an [[platonic ideal|ideal]] replacement for [[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 [[List of hard mathematical problems|hard]] in order to break it.

Not all uses of cryptographic hash functions require random oracles: schemes that require only one or more properties having a definition in the [[Standard model (cryptography)|standard model]] (such as [[collision resistance]], [[preimage resistance]], [[second preimage resistance]], etc.) can often be proven secure in the standard model (e.g., the [[Cramer–Shoup cryptosystem]]).

Random oracles have long been considered in [[computational complexity theory]], and many schemes have been proven secure in the random oracle model, for example [[Optimal Asymmetric Encryption Padding]], [[Full Domain Hash|RSA-FDH]] and [[Probabilistic Signature Scheme]]. In 1986, [[Amos Fiat]] and [[Adi Shamir]] showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures.

In 1989, Russell Impagliazzo and Steven Rudich showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange.

In 1993, [[Mihir Bellare]] and [[Phillip Rogaway]] Nonetheless, for any more natural protocol a proof of security in the random oracle model gives very strong evidence of the ''practical'' security of the protocol.

In general, if a protocol is proven secure, attacks to that protocol must either be outside what was proven, or break one of the assumptions in the proof; for instance if the proof relies on the hardness of [[integer factorization]], to break this assumption one must discover a fast integer factorization algorithm. Instead, to break the random oracle assumption, one must discover some unknown and undesirable property of the actual hash function; for good hash functions where such properties are believed unlikely, the considered protocol can be considered secure.

== Random Oracle Hypothesis ==
Although the Baker–Gill–Solovay theorem showed that there exists an oracle A such that PA = NPA, subsequent work by Bennett and Gill, showed that for a ''random oracle'' B (a function from {0,1}n to {0,1} such that each input element maps to each of 0 or 1 with probability 1/2, independently of the mapping of all other inputs), PB ⊊ NPB with probability 1. Similar separations, as well as the fact that random oracles separate classes with probability 0 or 1 (as a consequence of the [[Kolmogorov's zero–one law]]), led to the creation of the '''Random Oracle Hypothesis''', that two "acceptable" complexity classes C1 and C2 are equal if and only if they are equal (with probability 1) under a random oracle (the acceptability of a complexity class is defined in BG81 despite IPA ⊊ PSPACEA for a random oracle A with probability 1.

== Ideal cipher == 

An ''ideal'' cipher is a [[random permutation]] oracle that is used to model an idealized block cipher.
A random permutation decrypts each ciphertext block into one and only one plaintext block and vice versa, so there is a [[one-to-one correspondence]].
Some cryptographic proofs make not only the "forward" permutation available to all players, but also the "reverse" permutation.

Recent works showed that an ideal cipher can be constructed from a random oracle using 10-round or even 8-round [[Feistel network]]s.

== See also ==
* [[Sponge function]]
* [[Oracle machine]]
* [[Standard model (cryptography)]]
* [[Topics in cryptography]]

==Source==

[http://wikipedia.org/ http://wikipedia.org/]

Random oracle - Revision history

Admin: Created page with "In cryptography, a '''random oracle''' is an oracle (a theoretical black box) that responds to every ''unique query'' with a (tr..."