Paper 2023/914

Limits in the Provable Security of ECDSA Signatures

Dominik Hartmann, Ruhr University Bochum
Eike Kiltz, Ruhr University Bochum

Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for 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 ECDSA. Specifically, we focus on the programmability of 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 ECDSA can only exist if the security reduction is allowed to program the conversion function. As a consequence, a meaningful security proof for ECDSA is unlikely to exist without strong idealization.

Available format(s)
Publication info
ECDSArandom oracle modelprogrammabilitymeta reductions
Contact author(s)
dominik hartmann @ rub de
eike kiltz @ rub de
2023-06-14: approved
2023-06-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dominik Hartmann and Eike Kiltz},
      title = {Limits in the Provable Security of {ECDSA} Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2023/914},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.