Random oracle

from Wikipedia, the free encyclopedia

A random oracle ( English random oracle ) is in the cryptology used an ideal cryptographic hash function to model. The hash function is evaluated by accessing an oracle . The random oracle returns a random output value for each input if this input is queried for the first time, otherwise the same output as for the last query. Due to the construction of the random oracle, it fulfills the classic properties of a cryptological hash function, strong collision resistance and one-way function, in a perfect way.

The Random Oracle Model

From a security proof , which uses a random oracle, they say he is in the random oracle model was performed. The Random Oracle model was developed by Mihir Bellare and Phillip Rogaway . Protocols whose security has been proven in the Random Oracle Model are generally more efficient than those with a security proof in the standard cryptological model without a random oracle. However, this gain in efficiency comes at the expense of safety. Because of the special properties of a random oracle, it is impossible to construct a real hash function that replaces it in every protocol that uses a random oracle. There are protocols (specially constructed for this proof) that are provably secure in the Random Oracle model, but are insecure for every concrete instantiation of the random oracle by a hash function. Since no examples are known for real-world protocols in which this problem occurs, evidence in the Random Oracle model continues to be viewed as a strong indicator of real-world security.

literature

  • Douglas R. Stinson: Cryptography. Theory and Practice. 3. Edition. Chapman & Hall / CRC, 2005, ISBN 1-58488-508-4 , pages 122-123
  • Jonathan Katz, Yehuda Lindell: Introduction to Modern Cryptography: Principles and Protocols , p. 457, Chapman & Hall / CRC, 2007

Individual evidence

  1. ↑ Mihir Bellare and Phillip Rogaway: Random oracles are practical: A paradigm for designing efficient protocols . In: ACM Conference on Computer and Communications Security . 1993, p. 62-73 ( ucsd.edu ).
  2. ^ Ran Canetti, Oded Goldreich, and Shai Halevi: The Random Oracle Methodology, Revisited . In: STOC . 1998, p. 209-218 ( weizmann.ac.il ).