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. MMH${}^{\ast }$, 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${}^{\ast }$, that we call GRDH, where we use an arbitrary integer $n>1$ instead of prime $p$ and let the keys $\mathbf{x}=⟨x_1,\dots ,x_k⟩\in {\mathbb{Z}}_n^k$ satisfy the conditions $\gcd (x_i,n)=t_i$ ($1\le i\le k$), where $t_1,\dots ,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 $\epsilon$-almost-$\Delta$-universal family of hash functions for some $\epsilon <1$ if and only if $n$ is odd and $\gcd (x_i,n)=t_i=1$ $(1\le i\le 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].

International Journal of Foundations of Computer Science, to appear

References in corpus (6)

• Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data
• Adding generators in cyclic groups
• Restricted linear congruences
• Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT
• MMH* with arbitrary modulus is always almost-universal
• On a restricted linear congruence

Cited by in corpus (3)

• Explicit Formulas for the Weight Enumerators of Some Classes of Deletion Correcting Codes
• Unweighted linear congruences with distinct coordinates and the Varshamov--Tenengolts codes
• A generalization of Schönemann's theorem via a graph theoretic method