Random Oracle

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every query with a (truly) random response chosen 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 functions 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 that require only some property or properties that have a definition in the 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 (e.g. Bennett & Gill), and many schemes have been proven secure in the random oracle model, for example OAEP and PSS. Fiat and Shamir (1986) showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures. Impagliazzo and Rudich (1989) showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange. Bellare and Rogaway (1993) advocated their use in cryptographic constructions. In this definition, 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 separate 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 of the security of the protocol. In general, if a protocol is proven secure, attacks to that protocol must 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.

Other articles related to "random oracle, random":

Forking Lemma - Statement of The Lemma - Example
... for breaking a digital signature scheme in the random oracle model ... public parameters (including the public key) A is attacking, and hi would be the output of the random oracle on its ith distinct input ... of use when it would be possible, given two different random signatures of the same message, to solve some underlying hard problem ...
Forking Lemma
... if the adversary is re-run on new inputs but with the same random tape, its second output will also have the property ... a digital signature scheme instantiated in the random oracle model ... is a non-negligible probability that the same adversary with the same random tape can create a second forgery in an attack with a different random oracle ...
Probabilistic Encryption
... one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm ... Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding ... Techniques such as OAEP integrate random padding in a manner that is secure using any trapdoor permutation ...

Famous quotes containing the words oracle and/or random:

    There be three things which are too wonderful for me, yea, four which I know not: the way of an eagle in the air; the way of a serpent upon a rock; the way of a ship in the midst of the sea; and the way of a man with a maid.
    Bible: Hebrew Proverbs, 30:18-19.

    From the oracle of Agur, son of Jakeh.

    Man always made, and still makes, grotesque blunders in selecting and measuring forces, taken at random from the heap, but he never made a mistake in the value he set on the whole, which he symbolized as unity and worshipped as God. To this day, his attitude towards it has never changed, though science can no longer give to force a name.
    Henry Brooks Adams (1838–1918)