Welcome to the resource topic for 2015/1187
Title:
On an almost-universal hash function family with applications to authentication and secrecy codes
Authors: Khodakhast Bibak, Bruce M. Kapron, Venkatesh Srinivasan, 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].
ePrint: https://eprint.iacr.org/2015/1187
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .