Paper 2018/790

Generic Double-Authentication Preventing Signatures and a Post-Quantum Instantiation

David Derler, Sebastian Ramacher, and Daniel Slamanig


Double-authentication preventing signatures (DAPS) are a variant of digital signatures which have received considerable attention recently (Derler et al. EuroS&P 2018, Poettering AfricaCrypt 2018). They are unforgeable signatures in the usual sense and sign messages that are composed of an address and a payload. Their distinguishing feature is the property that signing two different payloads with respect to the same address allows to publicly extract the secret signing key from two such signatures. DAPS are known in the factoring, the discrete logarithm and the lattice setting. The majority of the constructions are ad-hoc. Only recently, Derler et al. (EuroS&P 2018) presented the first generic construction that allows to extend any discrete logarithm based secure signatures scheme to DAPS. However, their scheme has the drawback that the number of potential addresses (the address space) used for signing is polynomially bounded (and in fact small) as the size of secret and the public keys of the resulting DAPS are linear in the address space. In this paper we overcome this limitation and present a generic construction of DAPS with constant size keys and signatures. Our techniques are not tailored to a specific algebraic setting and in particular allow us to construct the first DAPS without structured hardness assumptions, i.e., from symmetric key primitives, yielding a candidate for post-quantum secure DAPS.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MAJOR revision.ProvSec 2018
digital signaturesdouble-authentication preventionShamir secret sharingprovable-securitygeneric constructionexponential size address space
Contact author(s)
sebastian ramacher @ iaik tugraz at
2018-09-01: received
Short URL
Creative Commons Attribution


      author = {David Derler and Sebastian Ramacher and Daniel Slamanig},
      title = {Generic Double-Authentication Preventing Signatures and a Post-Quantum Instantiation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/790},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.