Random oracle

From Wikipedia, the free encyclopedia

In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique 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.

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

Random oracles are a mathematical abstraction used in cryptographic proofs. They are typically used when the cryptographic hash functions 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.

Applications

In practice, random oracles are typically used as an ideal replacement for 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[1]), and many schemes have been proven secure in the random oracle model, for example OAEP and PSS. Fiat and Shamir (1986)[2] showed a major application of random oracles – the removal of interaction from protocols for the creation of signatures. Impagliazzo and Rudich (1989)[3] showed the limitation of random oracles – namely that their existence alone is not sufficient for secret-key exchange. Bellare and Rogaway (1993) [4] 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).

Limitations

No real function can implement a true random oracle.[citation needed]

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.[5][6] 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.[citation needed]

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.

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.

One can construct an ideal cipher from a random oracle using a 14-round Feistel network.[7]

See also

References

  1. ↑ Bennett, Charles H.; Gill, John (1981), "Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1", SIAM Journal on Computing 10 (1): 96–113, ISSN 1095-7111 
  2. ↑ Amos Fiat and Adi Shamir: How to Prove Yourself: Practical Solutions to Identification and Signature Problems. CRYPTO 1986: pp. 186–194
  3. ↑ Russell Impagliazzo and Steven Rudich: Limits on the Provable Consequences of One-Way Permutations STOC 1989: pp. 44–61
  4. ↑ Mihir Bellare and Phillip Rogaway, Random Oracles are Practical: A Paradigm for Designing Efficient Protocols, ACM Conference on Computer and Communications Security 1993, pp. 62–73 (PS and PDF).
  5. ↑ Ran Canetti, Oded Goldreich and Shai Halevi, The Random Oracle Methodology Revisited, STOC 1998, pp. 209–218 (PS and PDF).
  6. ↑ Craig Gentry and Zulfikar Ramzan. "Eliminating Random Permutation Oracles in the Even-Mansour Cipher". 2004.
  7. ↑ Holenstein, Thomas; Künzler, Robin; Tessaro, Stefano (2011). "The equivalence of the random oracle model and the ideal cipher model, revisited". STOC '11. ACM. pp. 89–98. doi:10.1145/1993636.1993650. 

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.