Name
Title | ||
|---|---|---|
On an almost-universal hash function family with applications to authentication and secrecy codes. |
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1142/s0129054118500089 | IACR Cryptology ePrint Archive |
Field | DocType | Volume |
Prime (order theory),Integer,Universal hashing,Theoretical computer science,Hash function,Prime factor,Divisor,Congruence relation,Mathematics | Journal | 2015 |
Issue | Citations | PageRank |
3 | 1 | 0.39 |
References | Authors | |
31 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Khodakhast Bibak | 1 | 13 | 6.63 |
| Bruce M. Kapron | 2 | 308 | 26.02 |
| Srinivasan Venkatesh | 3 | 136 | 10.67 |
| László Tóth | 4 | 3 | 1.43 |