Paper 2017/1203

Short Double- and N-Times-Authentication-Preventing Signatures from ECDSA and More

David Derler, Sebastian Ramacher, and Daniel Slamanig

Abstract

Double-authentication-preventing signatures (DAPS) are signatures designed with the aim that signing two messages with an identical first part (called address) but different second parts (called payload) allows to publicly extract the secret signing key from two such signatures. A prime application for DAPS is disincentivizing and/or penalizing the creation of two signatures on different payloads within the same address, such as penalizing double spending of transactions in Bitcoin by the loss of the double spender's money. So far DAPS have been constructed from very specific signature schemes not used in practice and using existing techniques it has proved elusive to construct DAPS schemes from signatures widely used in practice. This, unfortunately, has prevented practical adoption of this interesting tool so far. In this paper we ask whether one can construct DAPS from signature schemes used in practice. We affirmatively answer this question by presenting novel techniques to generically construct provably secure DAPS from a large class of discrete logarithm based signatures. This class includes schemes like Schnorr, DSA, EdDSA, and, most interestingly for practical applications, the widely used ECDSA signature scheme. The resulting DAPS are highly efficient and the shortest among all existing DAPS schemes. They are nearly half of the size of the most efficient factoring based schemes (IACR PKC'17) and improve by a factor of 100 over the most efficient discrete logarithm based ones (ACM CCS'15). Although this efficiency comes at the cost of a reduced address space, i.e., size of keys linear in the number of addresses, we will show that this is not a limitation in practice. Moreover, we generalize DAPS to any N>2, which we denote as N-times-authentication-preventing signatures (NAPS). Finally, we also provide an integration of our ECDSA-based DAPS into the OpenSSL library and perform an extensive comparison with existing approaches.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. IEEE EuroS&P 2018
Keywords
signaturesECDSASchnorrEdDSAverifiable secret sharingprovable-securitydouble-spending preventionnon-equivocation contractscertificate subversioncode-signing
Contact author(s)
sebastian ramacher @ iaik tugraz at
History
2018-02-28: revised
2017-12-18: received
See all versions
Short URL
https://ia.cr/2017/1203
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1203,
      author = {David Derler and Sebastian Ramacher and Daniel Slamanig},
      title = {Short Double- and N-Times-Authentication-Preventing Signatures from ECDSA and More},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1203},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1203}},
      url = {https://eprint.iacr.org/2017/1203}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.