Cryptology ePrint Archive: Report 2013/333

Double-authentication-preventing signatures

Bertram Poettering and Douglas Stebila

Abstract: 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.

Category / Keywords: digital signatures, double signatures, dishonest signer, coercion, compelled certificate creation attack, self-enforcement, two-to-one trapdoor functions

Original Publication (with major differences): ESORICS 2014

Date: received 29 May 2013, last revised 17 Jan 2016

Contact author: stebila at qut edu au

Available format(s): PDF | BibTeX Citation

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

Version: 20160118:053446 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]