On a variant of multilinear modular hashing with applications to authentication and secrecy codes

Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. As a well known family, one can mention MMH∗ which was shown to be Δ-universal by Halevi and Krawczyk in 1997. In this paper, we first introduce a variant of MMH∗ that we call GRDH. Then via a novel approach, namely, connecting the universal hashing problem to the number of solutions of (restricted) linear congruences, we investigate the e-almost-Δ — universality of GRDH. Finally, as an application of our results, we propose an authentication code with secrecy scheme which generalizes a recent construction.