A New Family of Authentication Protocols

R.J. Anderson¹, F. Bergadano², B. Crispo¹ J.H. Lee¹,
C. Manifavas¹ and R.M. Needham³

¹ University of Cambridge, UK
² Università di Torino, Italy
³ Microsoft Research, UK


We present a related family of authentication and digital signature protocols based on symmetric cryptographic primitives which perform substantially better than previous contructions. Previously, one-time digital signatures based on hash functions involved hundreds of hash function computations for each signature; we show that given online access to a timestamping service, we can sign messages using only two computations of a hash function. Previously, techniques to sign infinite streams involved one such one-time signature for each message block; we show that in many realistic scenarios a small number of hash function computations is sufficient. Previously the Diffie-Hellman protocol enabled two principals to create a confidentiality key from scratch; we provide an equivalent protocol for integrity, which enables two people who do not share a secret to set up a securely serialised channel into which attackers cannot subsequently intrude. In addition to being of potential use in real applications our contructions also arise interesting questions about the definition of a digital signature, and the relationship between integrity and authenticity.

Here the full paper in poscript format.

This paper has been published in the ACM Operating Systems Review, vol. 32, n. 4, pp. 9-20, October 1998, ACM Press.