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.
Keywords: digital signatures, double signatures, forgeability, extractability, dishonest signer, two-to-one trapdoor functions
Bertram Poettering, Douglas Stebila. Double-authentication-preventing signatures. In Mirosław Kutyłowski, Jaideep Vaidya, editors, Proc. 19th European Symposium on Research in Computer Security (ESORICS) 2014, Part I, LNCS, vol. 8714, pp. 436-453. Springer, September 2014. Full version published in International Journal of Information Security. © Springer.
- C implementation source code (requires gcrypt library)
FundingThis research was supported by:
- Australian Research Council (ARC) Discovery Project grant DP130104304
- the Australian Technology Network and German Academic Exchange Service (ATN-DAAD) Joint Research Co-operation Scheme
- EPSRC Leadership Fellowship EP/H005455/1
- the European Community (FP7/2007-2013) under grant agreement number ICT-2007-216646 - European Network of Excellence in Cryptology II (ECRYPT II)