**On an almost-universal hash function family with applications to authentication and secrecy codes**

*Khodakhast Bibak and Bruce M. Kapron and Venkatesh Srinivasan and László Tóth*

**Abstract: **Universal hashing, discovered by Carter and Wegman in 1979, has many important applications in computer science. MMH$^*$, which was shown to be $\Delta$-universal by Halevi and Krawczyk in 1997, is a well-known universal hash function family. We introduce a variant of MMH$^*$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $\mathbf{x}=\langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_n^k$ satisfy the conditions $\gcd(x_i,n)=t_i$ ($1\leq i\leq k$), where $t_1,\ldots,t_k$ are given positive divisors of $n$. Then via connecting the universal hashing problem to the number of solutions of restricted linear congruences, we prove that the family GRDH is an $\varepsilon$-almost-$\Delta$-universal family of hash functions for some $\varepsilon<1$ if and only if $n$ is odd and $\gcd(x_i,n)=t_i=1$ $(1\leq i\leq k)$. Furthermore, if these conditions are satisfied then GRDH is $\frac{1}{p-1}$-almost-$\Delta$-universal, where $p$ is the smallest prime divisor of $n$. Finally, as an application of our results, we propose an authentication code with secrecy scheme which strongly generalizes the scheme studied by Alomair et al. [{\it J. Math. Cryptol.} {\bf 4} (2010), 121--148], and [{\it J.UCS} {\bf 15} (2009), 2937--2956].

**Category / Keywords: **Universal hashing; authentication code with secrecy; restricted linear congruence

**Original Publication**** (in the same form): **International Journal of Foundations of Computer Science, to appear.

**Date: **received 11 Dec 2015, last revised 20 Apr 2017

**Contact author: **kbibak at uvic ca

**Available format(s): **PDF | BibTeX Citation

**Note: **Minor revision

**Version: **20170421:053620 (All versions of this report)

**Short URL: **ia.cr/2015/1187

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]