On almost-universal multilinear modular hashing with composite moduli

Khodakhast Bibak, Bruce M. Kapron, S. VenkatesharXiv 2015 · arXiv · OpenReview

Abstract

Universal hashing, introduced by Carter and Wegman in 1979, is a fundamental tool in computer science with applications ranging from data structures to cryptography. A well-known family in this domain is MMH$^*$, shown to be $\Delta$-universal by Halevi and Krawczyk. This paper introduces GRDH (Generalized Restricted Dot Product Hashing), a variant of MMH$^*$ that utilizes an arbitrary composite modulus $n > 1$ rather than a prime $p$. By establishing a novel connection between universal hashing and the number of solutions to restricted linear congruences, we prove that GRDH is an $\epsilon$-almost-$\Delta$-universal family if and only if $n$ is odd and the keys are coprime to $n$. Under these conditions, we demonstrate that the collision probability is bounded by $1/(p-1)$, where $p$ is the smallest prime divisor of $n$. Finally, we apply these results to construct a generalized authentication code with secrecy.

Introduction

Universal hashing is a cornerstone of modern cryptography, particularly in the construction of Message Authentication Codes (MACs). The efficiency of these schemes often depends on the underlying hash function family. The Multilinear Modular Hashing (MMH$^*$) family is highly regarded for its performance, but its standard formulation relies on a prime modulus $p$.

In practical implementations, there is often a desire to use composite moduli $n$ for greater flexibility or to align with specific hardware architectures. However, moving from a prime to a composite modulus introduces significant mathematical complexity regarding collision probabilities. This research addresses this gap by introducing the GRDH family and providing a rigorous number-theoretic analysis of its security properties.

The GRDH Family

The GRDH family is defined by the function: $$gx(m) := \sum_{i=1}^{k} m_i x_i \pmod n$$ where the keys $\mathbf{x} = \langle x_1, \ldots, x_k \rangle \in \mathbb{Z}_n^k$ are subject to specific constraints. Specifically, we require $\gcd(x_i, n) = t_i$ for given positive divisors $t_1, \ldots, t_k$ of $n$.

This formulation generalizes the standard MMH$^*$ by allowing for any integer $n > 1$ and incorporating these greatest common divisor (GCD) conditions into the key space. The primary challenge addressed in this work is determining the conditions under which this family remains "almost-universal."

Methodology: Hashing and Linear Congruences

The core innovation of this paper is the bridge built between hashing theory and the study of restricted linear congruences. The authors demonstrate that calculating the probability of a hash collision (or a specific difference in hash values) is equivalent to counting the number of solutions to a linear equation of the form: $$\sum_{i=1}^{k} a_i x_i \equiv b \pmod n$$ where the variables $x_i$ are restricted by GCD conditions.

To solve this counting problem, the research employs several advanced tools from analytic number theory:

  • Ramanujan Sums: Used to represent the properties of integers modulo $n$ in a way that simplifies the counting of solutions.
  • Finite Fourier Transforms: Applied over cyclic groups to handle the modular arithmetic constraints.
  • Explicit Solution Formulas: The authors utilize a recently derived formula for the number of solutions to restricted linear congruences to provide an exact, rather than approximate, collision probability $\epsilon$.

Key Theoretical Insights

1. The Necessity of Odd Moduli

A striking result of the analysis is that GRDH is only effective as a universal hash family when the modulus $n$ is odd. If $n$ is even, the authors prove that there exist cases where the collision probability reaches 1, rendering the family insecure for cryptographic purposes.

2. The Smallest Prime Factor Rule

For an odd modulus $n$, the security of the hash family—defined by the bound $\epsilon$—is determined entirely by the smallest prime divisor $p$ of $n$. The research proves that GRDH is $\frac{1}{p-1}$-almost-$\Delta$-universal. This implies that the "weakest link" in a composite modulus is its smallest prime factor; to maintain high security, one must ensure that even the smallest factor of $n$ is sufficiently large.

3. Tightness of the Bound

The authors do not merely provide an upper bound; they demonstrate that this bound is tight. By identifying specific instances where the collision probability exactly equals $1/(p-1)$, they show that the analysis provides the best possible guarantee for this family of functions.

Applications: Authentication with Secrecy

Beyond the theoretical bounds, the paper proposes a practical application: an authentication code with secrecy scheme. This scheme is designed for scenarios where a sender needs to provide both integrity (ensuring the message wasn't altered) and secrecy (ensuring the message remains private).

This construction generalizes previous models in the literature, such as those by Alomair et al. The authors prove that their GRDH-based scheme provides quantifiable resistance to substitution attacks, where an adversary attempts to replace a valid message-tag pair with a fraudulent one.

Conclusion and Future Work

This research provides a comprehensive characterization of multilinear modular hashing over composite moduli. While the requirement for an odd modulus $n$ may limit some hardware-specific optimizations (such as those favoring powers of 2), the use of Ramanujan sums and restricted congruences offers a powerful new framework for analyzing hash functions.

Future work may involve relaxing the assumption of uniform message distribution in the authentication scheme or exploring whether similar number-theoretic techniques can be applied to other classes of non-linear hash functions.

Summary updated

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].
BibTeX
@misc{bibak2015almost,
  author = {Khodakhast Bibak and Bruce M. Kapron and S. Venkatesh},
  title = {{On almost-universal multilinear modular hashing with composite moduli}},
  year = {2015},
  eprint = {1507.02331},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1507.02331},
}

Loading related content...

Figure