Paper 2013/333

Double-authentication-preventing signatures

Bertram Poettering and Douglas Stebila


Digital signatures are often used by trusted authorities to make unique bindings between a subject and a digital object; for example, certificate authorities certify a public key belongs to a domain name, and time-stamping authorities certify that a certain piece of information existed at a certain time. Traditional digital signature schemes however impose no uniqueness conditions, so a trusted authority could make multiple certifications for the same subject but different objects, be it intentionally, by accident, or following a (legal or illegal) coercion. We propose the notion of a double-authentication-preventing signature, in which a value to be signed is split into two parts: a subject and a message. If a signer ever signs two different messages for the same subject, enough information is revealed to allow anyone to compute valid signatures on behalf of the signer. This double-signature forgeability property discourages signers from misbehaving---a form of self-enforcement---and would give binding authorities like CAs some cryptographic arguments to resist legal coercion. We give a generic construction using a new type of trapdoor functions with extractability properties, which we show can be instantiated using the group of sign-agnostic quadratic residues modulo a Blum integer.

Note: A preliminary version of this paper appears in the proceedings of ESORICS 2014. The full version appears in the International Journal of Information Security. This is the author's copy of the full version. The final publication is available at Springer via

Available format(s)
Publication info
Published elsewhere. MAJOR revision.ESORICS 2014
digital signaturesdouble signaturesdishonest signercoercioncompelled certificate creation attackself-enforcementtwo-to-one trapdoor functions
Contact author(s)
stebila @ qut edu au
2016-01-18: last of 3 revisions
2013-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Bertram Poettering and Douglas Stebila},
      title = {Double-authentication-preventing signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2013/333},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.