Abstract
Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is \(\textsf {ECDSA}\) due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of \(\textsf {ECDSA}\) is comparatively sparse. In particular, all known security results for \(\textsf {ECDSA}\) rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.
In this work, we study the question whether these strong idealized models are necessary for proving the security of \(\textsf {ECDSA}\). Specifically, we focus on the programmability of \(\textsf {ECDSA}\) ’s “conversion function” which maps an elliptic curve point into its x-coordinate modulo the group order. Unfortunately, our main results are negative. We establish, by means of a meta reductions, that an algebraic security reduction for \(\textsf {ECDSA}\) can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for \(\textsf {ECDSA}\) is unlikely to exist without strong idealization.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
FIPS 186-5 from February 2023 does no longer approve \(\textsf {DSA}\) signatures for digital signature generation. However, \(\textsf {DSA}\) may still be used for signature verification.
- 2.
We stress that we do not question the modeling of \(\textsf {GenDSA}\) ’s hash function H as a programmable random oracle. Even though the programmable random oracle model has received valid criticism (e.g., [13]), it is generally viewed as a valid heuristic for a modern hash function which was designed to behave randomly.
- 3.
The \({ \textsf {SDLog}} \) assumption essentially says that it is hard to forge a \(\textsf {GenDSA}\) signature relative to a message m with \(H(m)=1\), see Definition 3.
- 4.
[22] consider a more general modeling where \(\mathcal {R}\) gets X before the query and can make its own oracle queries which could influence the response \({\bar{\textbf{O}}} (X)\). However, since such queries would never alter the behavior in all of our reductions, we only consider this simplified definition.
- 5.
This fixed embedding is not exploitable by \(\mathcal {R} \) since \(({\bar{\mathbf {\varPi }}},{\bar{\mathbf {\varPi }}}^{-1})\) is non-programmable.
References
Bauer, B., Fuchsbauer, G., Plouviez, A.: The one-more discrete logarithm assumption in the generic group model. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 587–617. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92068-5_20
Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. J. Cryptol. 16(3), 185–215 (2003)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS 93: 1st Conference on Computer and Communications Security, pp. 62–73. ACM Press, Fairfax (1993)
Blake-Wilson, S., Bolyard, N., Gupta, V., Hawk, C., Moeller, B.: Elliptic curve cryptography (ECC) cipher suites for transport layer security (TLS). RFC 4492, RFC Editor (2016)
Brickell, E., Pointcheval, D., Vaudenay, S., Yung, M.: Design validations for discrete logarithm based signature schemes. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 276–292. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46588-1_19
Brown, D.: On the Provable Security of ECDSA. London Mathematical Society Lecture Note Series, pp. 21–40. Cambridge University Press (2005)
Brown, D.R.L.: The exact security of ECDSA. Contributions to IEEE P1363a (2001). http://grouper.ieee.org/groups/1363/
Brown, D.R.L.: Generic groups, collision resistance, and ECDSA. Cryptology ePrint Archive, Report 2002/026 (2002). https://eprint.iacr.org/2002/026
Brown, D.R.L.: Generic groups, collision resistance, and ECDSA. Contributions to IEEE P1363a (2002). Updated version for “The Exact Security of ECDSA”. http://grouper.ieee.org/groups/1363/
Brzuska, C., Farshim, P., Mittelbach, A.: Random-oracle uninstantiability from indistinguishability obfuscation. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015, Part II. LNCS, vol. 9015, pp. 428–455. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_17
Camenisch, J., Piveteau, J.M., Stadler, M.: Blind signatures based on the discrete logarithm problem (rump session). In: Santis, A.D. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 428–432. Springer, Heidelberg (1995). https://doi.org/10.1007/bfb0053458
Canetti, R., Gennaro, R., Goldfeder, S., Makriyannis, N., Peled, U.: UC non-interactive, proactive, threshold ECDSA with identifiable aborts. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020: 27th Conference on Computer and Communications Security, pp. 1769–1787. ACM Press, Virtual Event (2020)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: 30th Annual ACM Symposium on Theory of Computing, pp. 209–218. ACM Press, Dallas (1998)
Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Two-party ECDSA from hash proof systems and efficient instantiations. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part III. LNCS, vol. 11694, pp. 191–221. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_7
Castagnos, G., Catalano, D., Laguillaumie, F., Savasta, F., Tucker, I.: Bandwidth-efficient threshold EC-DSA. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020, Part II. LNCS, vol. 12111, pp. 266–296. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45388-6_10
Dalskov, A., Orlandi, C., Keller, M., Shrishak, K., Shulman, H.: Securing DNSSEC keys via threshold ECDSA from generic MPC. In: Chen, L., Li, N., Liang, K., Schneider, S. (eds.) ESORICS 2020, Part II. LNCS, vol. 12309, pp. 654–673. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59013-0_32
Damgård, I., Jakobsen, T.P., Nielsen, J.B., Pagter, J.I., Østergaard, M.B.: Fast threshold ECDSA with honest majority. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 382–400. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_19
Doerner, J., Kondi, Y., Lee, E., shelat, a.: Secure two-party threshold ECDSA from ECDSA assumptions. In: 2018 IEEE Symposium on Security and Privacy, pp. 980–997. IEEE Computer Society Press, San Francisco (2018)
Doerner, J., Kondi, Y., Lee, E., Shelat, A.: Threshold ECDSA from ECDSA assumptions: the multiparty case. In: 2019 IEEE Symposium on Security and Privacy, pp. 1051–1066. IEEE Computer Society Press, San Francisco (2019)
Fersch, M., Kiltz, E., Poettering, B.: On the provable security of (EC)DSA signatures. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 2016: 23rd Conference on Computer and Communications Security, pp. 1651–1662. ACM Press, Vienna (2016)
Fersch, M., Kiltz, E., Poettering, B.: On the one-per-message unforgeability of (EC)DSA and its variants. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017, Part II. LNCS, vol. 10678, pp. 519–534. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_17
Fischlin, M., Lehmann, A., Ristenpart, T., Shrimpton, T., Stam, M., Tessaro, S.: Random oracles with(out) programmability. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 303–320. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_18
Fuchsbauer, G., Kiltz, E., Loss, J.: The Algebraic Group Model and its Applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2
Galbraith, S., Malone-Lee, J., Smart, N.: Public key signatures in the multi-user setting. Inf. Process. Lett. 83(5), 263–266 (2002). https://www.sciencedirect.com/science/article/pii/S0020019001003386
Gennaro, R., Goldfeder, S.: Fast multiparty threshold ECDSA with fast trustless setup. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018: 25th Conference on Computer and Communications Security, pp. 1179–1194. ACM Press, Toronto (2018)
Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 156–174. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_9
Groth, J., Shoup, V.: On the security of ECDSA with additive key derivation and presignatures. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13275, pp. 365–396. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-06944-4_13
Hartmann, D., Kiltz, E.: Limits in the provable security of ECDSA signatures. Cryptology ePrint Archive, Paper 2023/914 (2023). https://eprint.iacr.org/2023/914, https://eprint.iacr.org/2023/914
Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Secur. 1(1), 36–63 (2001)
Kiltz, E., Masny, D., Pan, J.: Optimal security proofs for signatures from identification schemes. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part II. LNCS, vol. 9815, pp. 33–61. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53008-5_2
Kondi, Y., Magri, B., Orlandi, C., Shlomovits, O.: Refresh when you wake up: proactive threshold wallets with offline devices. In: 2021 IEEE Symposium on Security and Privacy, pp. 608–625. IEEE Computer Society Press, San Francisco (2021)
Lindell, Y.: Fast secure two-party ECDSA signing. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part II. LNCS, vol. 10402, pp. 613–644. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_21
Lindell, Y., Nof, A.: Fast secure multiparty ECDSA with practical distributed key generation and applications to cryptocurrency custody. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018: 25th Conference on Computer and Communications Security, pp. 1837–1854. ACM Press, Toronto (2018)
Malone-Lee, J., Smart, N.P.: Modifications of ECDSA. In: Nyberg, K., Heys, H. (eds.) SAC 2002. LNCS, vol. 2595, pp. 1–12. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36492-7_1
National Institute of Standards and Technology: Digital signature standard (DSS) - FIPS 186–4. Technical report, U.S. Department of Commerce (2013)
Nguyen, P.Q., Shparlinski, I.: The insecurity of the digital signature algorithm with partially known nonces. J. Cryptol. 15(3), 151–176 (2002)
Paillier, P., Vergnaud, D.: Discrete-log-based signatures may not be equivalent to discrete log. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_1
Qin, X., Cai, C., Yuen, T.H.: One-more unforgeability of blind ECDSA. Cryptology ePrint Archive, Report 2021/1449 (2021). https://ia.cr/2021/1449
Reingold, O., Trevisan, L., Vadhan, S.: Notions of reducibility between cryptographic primitives. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 1–20. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24638-1_1
Stern, J., Pointcheval, D., Malone-Lee, J., Smart, N.P.: Flaws in applying proof methodologies to signature schemes. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 93–110. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_7
Vaudenay, S.: Hidden collisions on DSS. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 83–88. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_7
Vaudenay, S.: The security of DSA and ECDSA. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 309–323. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_23
Zhandry, M.: To label, or not to label (in generic groups). In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part IV. LNCS, vol. 13509, pp. 66–96. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15982-4_3
Zhang, C., Zhou, H.S., Katz, J.: An analysis of the algebraic group model. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 3794, pp. 310–322. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22972-5_11
Acknowledgments
Dominik Hartmann was supported by the European Union (ERC AdG REWORC - 101054911). Eike Kiltz was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2092 CASA - 390781972, and by the European Union (ERC AdG REWORC - 101054911).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 International Association for Cryptologic Research
About this paper
Cite this paper
Hartmann, D., Kiltz, E. (2023). Limits in the Provable Security of ECDSA Signatures. In: Rothblum, G., Wee, H. (eds) Theory of Cryptography. TCC 2023. Lecture Notes in Computer Science, vol 14372. Springer, Cham. https://doi.org/10.1007/978-3-031-48624-1_11
Download citation
DOI: https://doi.org/10.1007/978-3-031-48624-1_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-48623-4
Online ISBN: 978-3-031-48624-1
eBook Packages: Computer ScienceComputer Science (R0)