Paper 2015/1187

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

Khodakhast Bibak, Bruce M. Kapron, 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].

Note: Minor revision

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. International Journal of Foundations of Computer Science, to appear.
Keywords
Universal hashingauthentication code with secrecyrestricted linear congruence
Contact author(s)
kbibak @ uvic ca
History
2017-04-21: last of 2 revisions
2015-12-13: received
See all versions
Short URL
https://ia.cr/2015/1187
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1187,
      author = {Khodakhast Bibak and Bruce M.  Kapron and Venkatesh Srinivasan and László Tóth},
      title = {On an almost-universal hash function family with applications to authentication and secrecy codes},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1187},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1187}},
      url = {https://eprint.iacr.org/2015/1187}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.