On the construction of digest functions for manual authentication protocols

Abstract

A digest function is a sort of universal hash that takes a key and a message as its inputs. This paper will study these functions' properties and design in the context of their application in manual authentication technology. Frequently a digest function needs to have a very short output (e.g. 16–32 bits) and no key is used to digest more than one message. These together with other characteristics represent a new kind of game played between an attacker and honest parties, which is very different from other authentication mechanisms, notably message authentication codes or MACs. Short digests can be constructed directly or by "condensing" longer functions. We offer an improved method for the latter but concentrate mainly on direct constructions. We propose a digest algorithm which uses word multiplications to obtain a very fast implementation. This digest scheme enjoys strong and provable security properties, namely for a single-word or b-bit output digest function the collision probability is 2^1-b on equal and arbitrarily length inputs. The scheme is based on the multiplicative universal hash function of Dietzfelbinger et al., and it improves on several well-studied and efficient universal hashing algorithms, including MMH and NH.