A new multi-linear universal hash family

A new universal hash family is described which generalises a previously known multi-linear hash family. Messages are sequences over a finite field ${\mathbb{F}_q}$ while keys are sequences over an extension field ${\mathbb{F}_{q^n}}$ . A linear map ${\psi}$ from ${\mathbb{F}_{q^n}}$ to itself is used to compute the output digest. Of special interest is the case q = 2. For this case, we show that there is an efficient way to implement ${\psi}$ using a tower field representation of ${\mathbb{F}_{q^n}}$ . From a practical point of view, the focus of our constructions is small hardware and other resource constrained applications. For such platforms, our constructions compare favourably to previous work.