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