Editing Random oracle (section)

== Applications ==
Random oracles are typically used<!--{{who|date=June 2015}} See talk page "Weasel Words"--> as an [[platonic ideal|idealised]] replacement for [[cryptographic hash function]]s in schemes where strong randomness assumptions are needed of the hash function's output. Such a proof often 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 [[NP-hardness|hard]] in order to break it. However, it only proves such properties in the random oracle model, making sure no major design flaws are present. It is in general not true that such a proof implies the same properties in the standard model. Still, a proof in the random oracle model is considered better than no formal security proof at all.<ref name="katz">{{cite book |last1=Katz |first1=Jonathan |last2=Lindell |first2=Yehuda |title=Introduction to Modern Cryptography |date=2015 |publisher=Chapman & Hall/CRC |location=Boca Raton |isbn=978-1-4665-7027-6 |pages=174–175, 179–181 |edition=2}}</ref>

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]],<ref>{{Citation | last1=Bennett | first1=Charles H. | author1-link=Charles H. Bennett (computer scientist) | last2=Gill | first2=John | title=Relative to a Random Oracle A, P^A != NP^A != co-NP^A with Probability 1 | year=1981 | journal=SIAM Journal on Computing | issn=1095-7111 | volume=10 | issue=1 | pages=96–113 | doi=10.1137/0210008}}</ref> 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|PSS]]. In 1986, [[Amos Fiat]] and [[Adi Shamir]]<ref>{{cite news|first1=Amos|last1=Fiat|first2=Adi|last2=Shamir|title=How to Prove Yourself: Practical Solutions to Identification and Signature Problems|work=[[CRYPTO]]|year=1986|pages=186–194}}</ref> 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]]<ref>{{cite journal|first1=Russell|last1=Impagliazzo|first2=Steven|last2=Rudich|title=Limits on the Provable Consequences of One-Way Permutations|journal=[[Symposium on Theory of Computing|STOC]]|year=1989|pages=44–61}}</ref> 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]]<ref name="bellrog"/> were the first to advocate their use in cryptographic constructions. In their definition, the random oracle produces a bit-string of [[infinity|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.