In classical cryptography, universal hash functions—the building blocks of Message Authentication Codes (MACs)—are almost always defined over finite fields. By choosing a prime number $p$ as a modulus, researchers ensure that every non-zero element has an inverse, making the analysis of collision probabilities straightforward.
However, real-world hardware is not optimized for arbitrary primes. It is optimized for powers of two or other composite numbers that allow for efficient bit-shifting and modular reduction. This creates a tension: the mathematical "cleanliness" of primes versus the computational efficiency of composite moduli.
Recent research led by Khodakhast Bibak, Bruce M. Kapron, and Venkatesh Srinivasan has bridged this gap by providing a rigorous number-theoretic framework for hashing over arbitrary integer rings.
The Smallest Prime Factor Bottleneck
The central intuition of this research direction is that the security of a hash function over a composite modulus $n$ is only as strong as the "weakest link" in its prime factorization.
In MMH* with arbitrary modulus is always almost-universal, Bibak and his colleagues prove that for the Multilinear Modular Hashing (MMH*) family, the maximum collision probability is exactly $1/p$, where $p$ is the smallest prime factor of the modulus $n$.
This explains why using a power-of-two modulus ($n = 2^k$) is disastrous for security: the smallest prime factor is 2, leading to a collision probability of $1/2$, regardless of how large $k$ is. To maintain security while using composite numbers, one must ensure that all prime factors of the modulus are sufficiently large.
Counting Solutions via Ramanujan Sums
To prove these bounds, researchers had to solve a fundamental problem in combinatorial number theory: counting the number of solutions to restricted linear congruences. These are equations of the form: $$a_1x_1 + \dots + a_kx_k \equiv b \pmod n$$ where each $x_i$ must satisfy a specific constraint, such as being coprime to $n$.
In Restricted linear congruences and an authenticated encryption scheme, Bibak, Tauraso, and Tóth introduced a method to solve these using Ramanujan sums—a type of trigonometric sum used in signal processing and number theory. By applying the Finite Fourier Transform (DFT) of arithmetic functions, they derived explicit formulas that allow cryptographers to calculate exact collision probabilities rather than relying on loose upper bounds.
This approach was extended in On an almost-universal hash function family with applications to authentication and secrecy codes, where the authors introduced GRDH (Generalized Restricted Dot Product Hashing). They showed that even when keys are restricted to specific sets (like elements sharing divisors with the modulus), the security remains predictable as long as the modulus is odd.
Smoothness and the Geometry of Moduli
The "quality" of a modulus isn't just about its smallest factor; it's also about its smoothness—how many small prime factors it has. This concept appears in both the design of new hash functions and the destruction of old ones.
- Path-finding Resistance: In A Cryptographic Hash Function from Markoff Triples, Elena Fuchs and Kristin E. Lauter explore hash functions based on walks on graphs. They find that the security (resistance to path-finding attacks) is sensitive to the smoothness of $p^2-1$. If this value has many small factors, the graph's structure becomes easier to navigate, highlighting that prime selection is a subtle art.
- Cryptanalysis: Conversely, Duhyeong Kim uses the probability of GCDs being "$B$-smooth" to formalize attacks on multilinear maps. By calculating the likelihood that a greatest common divisor consists only of small primes, Kim provides a theoretical basis for why certain lattice-based primitives fail.
Why It Works
The shift from prime fields to arbitrary rings works because the underlying "hardness" of the collision problem is redistributed across the prime factors of the modulus. By using Ramanujan sums and the properties of the Riemann zeta function, researchers have turned what was once a heuristic "engineering hack" (using composite moduli) into a precise science. We now know that we can trade the mathematical elegance of a prime field for the hardware efficiency of a composite ring, provided we respect the bottleneck imposed by the smallest prime factor.