Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
m →Applications: Turn CS prof names into links to their pages |
||
Line 14:
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]]. 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.
== Domain separation ==
| |||