Douglas Stebila

Double-authentication-preventing signatures

Our DAPS construction relies on two-to-one trapdoor functions.

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.

Keywords: digital signatures, double signatures, forgeability, extractability, dishonest signer, two-to-one trapdoor functions

Reference

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.

Download

Code

• C implementation source code (requires gcrypt library)

BibTeX

@inproceedings{ESORICS:PoeSte14,
 	Author = {Bertram Poettering and Douglas Stebila},
 	Booktitle = {Proc. 19th European Symposium on Research in Computer Security (ESORICS) 2014, Part I},
 	Editor = {Miros{\l}aw Kuty{\l}owski and Jaideep Vaidya},
 	Month = {September},
 	Pages = {436--453},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Double-authentication-preventing signatures},
 	Volume = {8714},
 	Year = {2014}
 }

Funding

• 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)