International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Badger - A Fast and Provably Secure MAC

Martin Boesgaard
Ove Scavenius
Thomas Pedersen
Thomas Christensen
Erik Zenner
Search ePrint
Search Google
Abstract: We present Badger, a new fast and provably secure MAC based on universal hashing. In the construction, a modified tree hash that is more efficient than standard tree hash is used and its security is being proven. Furthermore, in order to derive the core hash function of the tree, we use a novel technique for reducing $\Delta$-universal function families to universal families. The resulting MAC is very efficient on standard platforms both for short and long messages. As an example, for a $64$-bit tag, it achieves performances up to 2.2 and 1.2 clock cycles per byte on a Pentium III and Pentium 4 processor, respectively. The forgery probability is at most $2^{-52.2}$.
  title={Badger - A Fast and Provably Secure MAC},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / message authentication codes, universal hash, tree, pseudo-random generator},
  note={ACNS 2005 (Springer LNCS) 13028 received 19 Nov 2004, last revised 2 Sep 2005},
  author={Martin Boesgaard and Ove Scavenius and Thomas Pedersen and Thomas Christensen and Erik Zenner},