The random oracle model: a twenty-year retrospective | Designs, Codes and Cryptography Skip to main content
Springer Nature Link
Log in

The random oracle model: a twenty-year retrospective

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. It has long been known that one has to use the random oracle assumption carefully if the protocol uses an iterated hash function, because of the extension attack (see Example 9.64 in [55]). That is, the random oracle assumption essentially says that a deterministic function \(H(K,M)\) behaves like a random function to someone who does not know the key \(K\). However, if a message is obtained by adding a suffix to a queried message, then the hash of the whole message is the hash of the suffix with known key, and so the random oracle assumption does not apply. It is because of this extension attack that prefix-MAC, defined by \(H(K,M)\), is insecure. Despite the need for caution, in fact this potential pitfall has never, to the best of our knowledge, led anyone to a fallacious proof. In particular, no one ever claimed a security result for prefix-MAC under the random oracle model.

  2. This assumes that the message space is bounded; in [44] it is suggested that if one wants to allow messages of arbitrary length, one should first hash the message using a collision-resistant hash function.

  3. Suppose you find the exact order of \(H(M)^k\) for each of 50 random messages. The subset of messages \(M\) for which this order is divisible by \(p_j\) will all have the same bit \(b_j\) occurring as the \(i_j\)-th bit of the corresponding encodings. Any other bit of those encodings will have both 0’s and 1’s (except with negligible probability). Thus, you can easily spot \((i_j,b_j)\).

  4. Remark 1 of [44] suggests that in the exponentiation, rather than first computing \(\pi (M')\), “it might be more efficient to incrementally raise an accumulated value to each \(a_{i,M'_i}\).” However, such a highly sequential algorithm would have circuit depth in the thousands, and hence its obfuscation would have a multilinearity level whose bitlength is also in the thousands.

  5. Bernstein D.: Personal communication, 23 Feb 2015.

  6. This definition of \(r\) applies to ECDSA over a prime field; a different method of determining \(r\) from \(kP\) is needed for ECDSA over a binary field.

  7. In [20] Brown also proved unforgeability in the random oracle model for the hash function but without the generic group assumption. However, he needed to make the so-called semi-logarithm assumption, which has been little studied and is presumably stronger than intractability of discrete logs.

  8. More precisely, in Table 1 of [19] the description of the oracle’s response to a “hint command” (that is, a signature query) is modified as follows. The input is a message \(M\) rather than a hash value \(h\), and instead of random generation of \(z_{m+1}\) one queries \((K,M)=(z_2/z_1,M)\) to the hash oracle. A few minor modifications are then needed in the proof of Lemma 1 of [19].

  9. Two-key versions of signature schemes are just as impractical for deployment as are two-key message authentication codes. See [51] for an analysis of the security theorems that under suitable conditions enable one to carry over security results from two-key nested MACs to one-key variants.

  10. A somewhat similar modification of ECDSA was proposed by NIST in [32]. The NIST modification randomizes the message by combining it with an ECDSA signature component; however, the procedure for generating ephemeral secret keys is the same as in ECDSA. The NIST modification appears not to be sufficient for obtaining the reductionist security result we want. We also note that Brickell et al. [18] obtained several security results for modifications of DSA, that is, for a broad class of signature schemes based on the discrete log problem in a finite field.

  11. Strictly speaking, one cannot even assume that the forger has selected a \(k\) at all, since all that is required of a forger is a message and signature that satisfy the verification algorithm. The preceding discussion is intended to be informal and intuitive; it is not a formal argument.

  12. A very similar version was considered in [54], where it was denoted ECDSA III. The version of Malone-Lee and Smart differs from ECDSA\({}^+\) in just two respects: the ephemeral key \(k\) is random rather than given by \(H'(K,M)\), and in the signing equation instead of \(kP\) (that is, the \(x\)-coordinate along with an additional bit to indicate \(y\)) they hash the sum of the \(x\)- and \(y\)-coordinates along with \(M\).

  13. We shall ignore the possibility that the \(j\)-th \(H\)-query repeats an earlier query, in which case we need to choose a different \(j\), and also the (negligible) probability that \(h_1=h_2\).

  14. The splitting lemma [62, 63], which is proved by a simple counting argument, says the following. Suppose we have two sets \(A\) and \(B\) containing \(a\) and \(b\) elements, respectively. Suppose that a pair \((\alpha ,\beta )\in A\times B\) has probability \(\ge \epsilon \) of having a certain property, that is, there are at least \(\epsilon ab\) such “good” pairs. Let \(A_0\subset A\) be the set such that \(\alpha _0\in A_0\) if at least \(\epsilon b/2\) pairs \((\alpha _0,\beta )\) (\(\beta \in B\)) are “good.” The splitting if at least \(\epsilon b/2\) pairs \((\alpha _0,\beta )\) (\(\beta \in B\)) are “good.” The splitting lemma says that there are at least \(\epsilon a/2\) elements in \(A_0\).

  15. Tightness issues arise in [56] if one wants to use short hash values, which would give a 25 % reduction in signature length compared with ECDSA and compared with Schnorr with full-length hash.

References

  1. Apon D., Huang Y., Katz J., Malozemoff A.: Implementing cryptographic program obfuscation, Crypto 2014 rump session (2014). http://eprint.iacr.org/2014/779.

  2. Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vadhan S., Yang K.: On the (im)possibility of obfuscating programs. J. ACM 59, 6 (2012).

  3. Barwood G.: Digital signatures using elliptic curves (1997). http://groups.google.com/group/sci.crypt/msg/b28aba37180dd6c6.

  4. Beame P.W., Cook S.A., Hoover H.J.: Log depth circuits for division and related problems. SIAM J. Comput. 15, 994–1003 (1986).

  5. Bellare M.: Caught in between theory and practice. In: Crypto 2014 IACR Distinguished Lecture (2014). https://www.youtube.com/watch?v=SPVWSG7-i_E.

  6. Bellare M., Rogaway P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73. ACM, New York (1993).

  7. Bellare M., Rogaway P.: Optimal asymmetric encryption—how to encrypt with RSA. In: Advances in Cryptology—Eurocrypt’94. LNCS, vol. 950, pp. 92–111. Springer, Berlin (1994).

  8. Bellare M., Boldyreva A., Palacio A.: An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: Advances in Cryptology—Eurocrypt 2004. LNCS, vol. 3027, pp. 171–188. Springer, Berlin (2004).

  9. Bellare M., Hoang V.T., Keelveedhi S.: Instantiating random oracles via UCEs. In: Advances in Cryptology—Crypto 2013 (Part II). LNCS, vol. 8042, pp. 398–415. Springer, Berlin (2013); full version available at http://eprint.iacr.org/2013/424.

  10. Bernstein D., Duif N., Lange T., Schwabe P., Yang B.-Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2, 77–89 (2012).

  11. Bernstein D., Hülsing A., Lange T., Niederhagen R.: Bad directions in cryptographic hash functions, preprint (2015); available at http://obviouscation.cr.yp.to/obviouscation-20150223.

  12. Blake-Wilson S., Menezes A.: Unknown key-share attacks on the station-to-station (STS) protocol. In: Public Key Cryptography—PKC 1999. LNCS, vol. 1560, pp. 156–170. Springer, Berlin (1999).

  13. Boneh D., Boyen X.: Short signatures without random oracles. In: Advances in Cryptology—Eurocrypt 2004. LNCS, vol. 3027, pp. 56–73. Springer, Berlin (2004).

  14. Boneh D., DeMillo R., Lipton R.: On the importance of checking cryptographic protocols for faults. J. Cryptol. 14, 101–119 (2001).

  15. Boneh D., Lynn B., Shacham H.: Short signatures from the Weil pairing. In: Advances in Cryptology—Asiacrypt 2001. LNCS, vol. 2248, pp. 514–532. Springer, Berlin (2001).

  16. Boneh D., Wu D., Zimmerman W.: Immunizing multilinear maps against zeroizing attacks (2014). Available at http://eprint.iacr.org/2014/930.

  17. Boyen X., Mei Q., Waters B.: Direct chosen ciphertext security from identity-based techniques. In: 12th ACM Conference on Computer and Communications Security—CCS’05, pp. 320–329. ACM, New York (2005).

  18. Brickell E., Pointcheval D., Vaudenay S., Yung M.: Design validations for discrete logarithm based signature schemes. In: Public Key Cryptography—PKC 2000. LNCS, vol. 1751, pp. 276–292. Springer, Berlin (2000).

  19. Brown D.: Generic groups, collision resistance, and ECDSA. Des. Codes Cryptogr. 35, 119–152 (2005).

  20. Brown D.L.: On the provable security of ECDSA. In: Blake I., Seroussi G., Smart N. (eds.) Advances in Elliptic Curve Cryptography, pp. 21–40. Cambridge University Press, Cambridge (2005).

  21. Brown D., Gallant R.: The static Diffie–Hellman problem (2004). http://eprint.iacr.org/2004/306.

  22. Buterin V.L.: Critical vulnerability found in Android wallets. http://bitcoinmagazine.com/6251/critical-vulnerability-found-in-android-wallets/. Accessed 11 Aug 2013.

  23. Camenisch J., Neven G., Shelat A.: Simulatable adaptive oblivious transfer. In: Advances in Cryptology—Eurocrypt 2007. LNCS, vol. 4515, pp. 573–590. Springer, Berlin (2007).

  24. Canetti R., Goldreich O., Halevi S.: The random oracle model, revisited. In: Proceedings of 30th Annual Symposium Theory of Computing, pp. 209–218, ACM, New York (1998); full version available at http://eprint.iacr.org/1998/011.

  25. Chatterjee S., Karabina K., Menezes A.: Fault attacks on pairing-based protocols revisited. IEEE Trans. Comput. (to appear); available at http://eprint.iacr.org/2014/492.

  26. Chatterjee S., Menezes A., Sarkar P.: Another look at tightness. In: Selected Areas in Cryptography—SAC 2011. LNCS, vol. 7118. Springer, Berlin (2012); available at http://anotherlook.ca.

  27. Cheon J.: Security analysis of the strong Diffie–Hellman problem. In: Advances in Cryptology—Eurocrypt 2006. LNCS, vol. 4004, pp. 1–11. Springer, Berlin (2006).

  28. Cheon J., Han K., Lee C., Ryu, H., Stehlé D.: Cryptanalysis of the multilinear map over the integers. In: Advances in Cryptology—Eurocrypt 2015, Part I. LNCS, vol. 9056, pp. 3–12 . Springer, New York (2015).

  29. Coron J.-S., Lepoint T., Tibouchi M.: Practical multilinear maps over the integers. In: Advances in Cryptology—Crypto 2013. LNCS, vol. 8042, pp. 476–493, Springer, Berlin (2013); full version available at http://eprint.iacr.org/2013/183.

  30. Coron J.-S., Lepoint T., Tibouchi M.: Cryptanalysis of two candidate fixes of multilinear maps over the integers (2014). Available at http://eprint.iacr.org/2014/975.

  31. Coron J.-S., Lepoint T., Tibouchi M.: New multilinear maps over the integers (2015). Available at http://eprint.iacr.org/2015/162.

  32. Dang Q.: Randomized hashing for digital signatures, NIST Special Pub. 800–106 (2009). http://csrc.nist.gov/publications/nistpubs/800-106/NIST-SP-800-106.

  33. Dodis Y., Oliveira R., Pietrzak K.: On the generic insecurity of the full domain hash. In: Advances in Cryptology—Crypto 2005. LNCS, vol. 3621, pp. 449–466. Springer, Berlin (2005).

  34. Fildes J.: iPhone hacker publishes secret Sony PlayStation 3 key, 6 Jan 2011. www.bbc.com/news/technology-12116051.

  35. Freire E., Hofheinz D., Paterson K., Striecks C.: Programmable hash functions in the multilinear setting. In: Advances in Cryptology—Crypto 2013. LNCS, vol. 8042, pp. 513–530. Springer, Berlin (2013); full version available at http://eprint.iacr.org/2013/354.

  36. Gallant R.: The static Diffie–Hellman problem. In: Presented at ECC (2005). Available at http://cacr.waterloo.ca/conferences/2005/ecc2005/gallant.

  37. Gennaro R., Halevi S., Rabin T.: Secure hash-and-sign signatures without the random oracle. In: Advances in Cryptology—Eurocrypt’99. LNCS, vol. 1592, pp. 123–139. Springer, Berlin (1999).

  38. Gentry C.: Practical identity-based encryption without random oracles. In: Advances in Cryptology—Eurocrypt 2006. LNCS, vol. 4004, pp. 445–464. Springer, Berlin (2006).

  39. Gentry C., Halevi S., Maji H., Sahai A.: Zeroizing without zeroes: cryptanalyzing multilinear maps without encodings of zero (2014). Available at http://eprint.iacr.org/2014/929.

  40. Goldreich O.: On post-modern cryptography (2006). http://eprint.iacr.org/2006/461.

  41. Goldwasser S., Tauman Kalai Y.: On the (in)security of the Fiat–Shamir paradigm. In: Proceedings of the 44th Annual Symposium Foundations of Computer Science, pp. 102–113. IEEE (2003); full version available at http://eprint.iacr.org/2003/034.

  42. Goldwasser S., Micali S., Rivest R.: A paradoxical solution to the signature problem. In: Proceedings of the 25th Annual IEEE Symposium on the Foundations of Computer Science, pp. 441–448 (1984).

  43. Green M., Katz J., Malozemoff A., Zhou H.-S.: A unified approach to idealized model separations via indistinguishability obfuscation (2015). Available at: http://eprint.iacr.org/2014/863.

  44. Hohenberger S., Sahai A., Waters B.: Replacing a random oracle: full domain hash from indistinguishability obfuscation. In: Advances in Cryptology—Eurocrypt 2014. LNCS, vol. 8441, pp. 201–220. Springer, Berlin (2014).

  45. Jao D., Yoshida K.: Boneh–Boyen signatures and the strong Diffie–Hellman problem. In: Pairing-Based Cryptography—Pairing 2009. LNCS, vol. 5671, pp. 1–16. Springer, Berlin (2009); full version available at http://eprint.iacr.org/2009/221.

  46. Koblitz N., Menezes A.: Another look at provable security. In: II Progress in Cryptology—Indocrypt 2006. LNCS, vol. 4329, pp. 148–175. Springer, Berlin (2006); available at http://anotherlook.ca.

  47. Koblitz N., Menezes A.: Another look at provable security. J. Cryptol. 20, 3–37 (2007); available at http://anotherlook.ca.

  48. Koblitz N., Menezes A.: Another look at generic groups. Adv. Math. Commun. 1, 13–28 (2007); available at http://anotherlook.ca.

  49. Koblitz N., Menezes A.: The brave new world of bodacious assumptions in cryptography, Not. Am. Math. Soc. 57, 357–365 (2010); available at http://anotherlook.ca.

  50. Koblitz N., Menezes A.: Another look at security definitions. Adv. Math. Commun. 7, 1–38 (2013); available at http://anotherlook.ca.

  51. Koblitz N., Menezes A.: Another look at security theorems for 1-key nested MACs. In: Open Problems in Mathematics and Computational Science, pp. 69–89. Springer, Berlin (2014).

  52. Lenstra A.K., Hughes J.P., Augier M., Bos J., Kleinjung T., Wachter C.: Public keys. In: Advances in Cryptology—Crypto 2012. LNCS, vol. 7417, pp. 626–642. Springer, Berlin (2012).

  53. Lysyanskaya A.: Unique signatures and verifiable random functions from the DH–DDH separation. In: Advances in Cryptology—Crypto 2002. LNCS, vol. 2442, pp. 597–612. Springer, Berlin (2002).

  54. Malone-Lee J., Smart N.: Modifications of ECDSA. In: Selected Areas in Cryptography—SAC 2003. LNCS, vol. 2595, pp. 1–12. Springer, Berlin (2002).

  55. Menezes A., van Oorschot P., Vanstone S.: Handbook of Applied Cryptography. CRC, Boca Raton (1996).

  56. Neven G., Smart N., Warinschi B.: Hash function requirements for Schnorr signatures. J. Math. Cryptol. 3, 69–87 (2009).

  57. Nielsen J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: Advances in Cryptology—Crypto 2002. LNCS, vol. 2442, pp. 111–126. Springer, Berlin (2002).

  58. Nguyen P., Shparlinski I.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30, 201–217 (2003).

  59. Page D., Vercauteren F.: A fault attack on pairing-based cryptography. IEEE Trans. Comput. 55, 1075–1080 (2006).

  60. Paillier P., Vergnaud D.: Discrete-log-based signatures may not be equivalent to discrete log. In: Advances in Cryptology—Asiacrypt 2005. LNCS, vol. 3788, pp. 1–20. Springer, Berlin (2005).

  61. Perlroth N., Larson J., Shane S.: N.S.A. able to foil basic safeguards of privacy on web. The New York Times, 5 Sept 2013.

  62. Pointcheval D., Stern J.: Security proofs for signature schemes. In: Advances in Cryptology—Eurocrypt’96. LNCS, vol. 1070, pp. 387–398. Springer, Berlin (1996).

  63. Pointcheval D., Stern J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13, 361–396 (2000).

  64. Pornin T.: Deterministic usage of the digital signature algorithm (DSA) and elliptic curve digital signature algorithm (ECDSA), RFC 6979, IETF, August (2013).

  65. Ramchen K., Waters, B.: Fully secure and fast signing from obfuscation. In: Proceedings of ACM CCS’14, pp. 659–673. ACM, New York (2014).

  66. Schnorr C.P.: Efficient signature generation for smart cards. J. Cryptol. 4, 161–174 (1991).

  67. Seurin Y.: On the exact security of Schnorr-type signatures in the random oracle model. In: Advances in Cryptology—Eurocrypt 2012. LNCS, vol. 7237, pp. 554–571. Springer, Berlin (2012).

  68. Whelan C., Scott M.: The importance of the final exponentiation in pairings when considering fault attacks. In: Pairing-Based Cryptography—Pairing 2007. LNCS, vol. 4575, pp. 225–246. Springer, Berlin (2007).

  69. Wigley J.: Removing need for rng in signatures (1997). http://groups.google.com/group/sci.cryp/msg/a6da45bcc8939a89.

  70. Zimmerman J.: How to obfuscate programs directly. In: Advances in Cryptology—Eurocrypt 2015, Part II. LNCS, vol. 9057, pp. 439–467. Springer, Berlin (2015).

Download references

Acknowledgments

We would like to thank Dan Brown for valuable discussions of security reductions for ECDSA, Kenwrick Mayo for useful discussions of obfuscation constructions, Sanjit Chatterjee for thoughtful comments on an earlier draft, and Ann Hibner Koblitz for helpful editorial suggestions. We would also like to thank Dan Bernstein for informing us of the work [11] and Francisco Rodríguez-Henríquez for bringing the paper [54] to our attention. Finally, we thank the referees for their helpful comments.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Washington, Box 354350, Seattle, WA, 98195, USA

    Neal Koblitz

  2. Department of Combinatorics & Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada

    Alfred J. Menezes

Authors
  1. Neal Koblitz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alfred J. Menezes
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alfred J. Menezes.

Additional information

This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Cryptography, Codes, Designs and Finite Fields: In Memory of Scott A. Vanstone”.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Koblitz, N., Menezes, A.J. The random oracle model: a twenty-year retrospective. Des. Codes Cryptogr. 77, 587–610 (2015). https://doi.org/10.1007/s10623-015-0094-2

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-015-0094-2

Keywords

Mathematics Subject Classification

Search

Navigation