### The Random Oracle Model: A Twenty-Year Retrospective

Neal Koblitz and Alfred Menezes

##### Abstract

It has been roughly two decades since the random oracle model for security reductions 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 reductions are known for these two schemes. If one shuns these models, then no provable security result is known for them.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
ajmeneze @ uwaterloo ca
History
2015-05-02: revised
See all versions
Short URL
https://ia.cr/2015/140

CC BY

BibTeX

@misc{cryptoeprint:2015/140,
author = {Neal Koblitz and Alfred Menezes},
title = {The Random Oracle Model: A Twenty-Year Retrospective},
howpublished = {Cryptology ePrint Archive, Paper 2015/140},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/140}},
url = {https://eprint.iacr.org/2015/140}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.