The random oracle model: a twenty-year retrospective

• Published in: Designs, codes, and cryptography codes, and cryptography, 2015-12, Vol.77 (2-3), p.587-610
• Main Authors: Koblitz, Neal, Menezes, Alfred J.
• Format: Article
• Language: English
• Subjects: Circuits; Coding and Information Theory; Computer Science; Cryptology; Data Structures and Information Theory; Discrete Mathematics in Computer Science; Information and Communication
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-015-0094-2

It has been roughly two decades since the random oracle model for reductionist security arguments was introduced and one decade since we first discussed the controversy that had arisen concerning its use. In this retrospective we argue that there is no evidence that the need for the random oracle assumption in a proof indicates the presence of a real-world security weakness in the corresponding protocol. We give several examples of attempts to avoid random oracles that have led to protocols that have security weaknesses that were not present in the original ones whose proofs required random oracles. We also argue that the willingness to use random oracles gives one the flexibility to modify certain protocols so as to reduce dependence on potentially vulnerable pseudorandom bit generators. Finally, we discuss a modified version of ECDSA, which we call ECDSA + , that may have better real-world security than standard ECDSA, and compare it with a modified Schnorr signature. If one is willing to use the random oracle model (and the analogous generic group model), then various security arguments are known for these two schemes. If one shuns these models, then no provable security result is known for them.