Paper 2015/1187

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. The following family, called MMH$^*$ by Halevi and Krawczyk in 1997, is well known: Let $p$ be a prime and $k$ be a positive integer. Define \begin{align*} \text{MMH}^*:=\lbrace g_{\mathbf{x}} \; : \; \mathbb{Z}_p^k \rightarrow \mathbb{Z}_p \; | \; \mathbf{x}\in \mathbb{Z}_p^k \rbrace, \end{align*} where \begin{align*} g_{\mathbf{x}}(\mathbf{m}) := \mathbf{m} \cdot \mathbf{x} \pmod{p} = \sum_{i=1}^k m_ix_i \pmod{p}, \end{align*} for any $\mathbf{x}=\langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_p^k$, and any $\mathbf{m}=\langle m_1, \ldots, m_k \rangle \in \mathbb{Z}_p^k$. In this paper, we first give a new proof for the $\triangle$-universality of MMH$^*$, shown by Halevi and Krawczyk in 1997, via connecting the universal hashing problem to the number of solutions of (restricted) linear congruences. We then introduce a new hash function family --- 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$. Applying our aforementioned approach, we prove that the family GRDH is an $\varepsilon$-almost-$\triangle$-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-$\triangle$-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 generalizes a recent construction.

Note: Minor revision