The Random Oracle Model: A Twenty-Year Retrospective.
Neal Koblitz, Alfred Menezes · 2015
Abstract. It has been roughly two decades since the random ora-cle model for reductionist security arguments was introduced and one decade since we first discussed the controversy that had arisen concern-ing 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 pres-ence 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 ar-gue 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. 1.