Linkable Message Tagging: Solving the Key Distribution Problem of Signature Schemes

Felix Günther; Bertram Poettering

Paper 2014/014

Linkable Message Tagging: Solving the Key Distribution Problem of Signature Schemes

Felix Günther and Bertram Poettering

Abstract

Digital signatures are one of the most extensively used cryptographic primitives today. It is well-understood that they guarantee practical security only if the corresponding verification keys are distributed authentically; however, arguably, satisfying solutions for the latter haven't been found yet, or at least aren't in large-scale deployment. This paper introduces a novel approach for cryptographic message authentication where this problem does not arise: A linkable message tagging scheme (LMT) identifies pairs of messages and accompanying authentication tags as related if and only if these tags were created using the same secret key. In other words, in contrast to signature schemes, our primitive does not aim at detecting whether individually considered messages originate from an explicitly specified entity, but instead decides whether all messages from a given collection originate from the same (possibly anonymous) source. The appealing consequence is that our primitive fully avoids public keys and hence elegantly sidesteps the key distribution problem of signature schemes. As an interesting application of LMT we envision an email authentication system with minimal user interaction. Email clients could routinely generate a secret LMT key upon their first invocation, and then equip all outgoing messages with corresponding tags. On the receiver's side, client software could automatically verify for incoming messages whether they indeed originate from the same entity as previously or subsequently received messages with identical sender address. Although this form of authentication does not provide as strong guarantees of message's origin as signature schemes would do, we do believe that trading the apparently discouraging obstacles implied by the authentic distribution of signature verification keys for the assumption that an attacker does not forge every message exchanged between parties is quite attractive. As technical contributions we formalize the notions of LMT and its (more efficient) variant CMT (classifiable message tagging), including corresponding notions of unforgeability. For both variants we propose a range of provably secure constructions, basing on different hardness assumptions, with and without requiring random oracles.

Note: A preliminary version of this paper appears in the proceedings of ACISP 2015. This is the full version.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Major revision. 20th Australasian Conference on Information Security and Privacy (ACISP 2015)
DOI: 10.1007/978-3-319-19962-7_12
Keywords: message authentication key distribution problem message tagging digital signatures
Contact author(s): guenther @ cs tu-darmstadt de
History: 2015-06-18: revised; 2014-01-07: received; See all versions
Short URL: https://ia.cr/2014/014
License: CC BY

BibTeX

@misc{cryptoeprint:2014/014,
      author = {Felix Günther and Bertram Poettering},
      title = {Linkable Message Tagging: Solving the Key Distribution Problem of Signature Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/014},
      year = {2014},
      doi = {10.1007/978-3-319-19962-7_12},
      url = {https://eprint.iacr.org/2014/014}
}