Cryptology ePrint Archive: Report 2013/333
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 15 Jun 2015
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. This is the revised full version.
Version: 20150616:002330 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]