TL;DR
This paper introduces a new hash function family, GRDH, which generalizes the well-known MMH* family by using composite moduli instead of primes. They prove that GRDH achieves strong security properties (almost-universal and almost-Δ-universal) under specific conditions on the modulus and key, and demonstrate its application in constructing more general authentication and secrecy codes.
What Problem Does This Paper Address?
Universal hash functions are fundamental building blocks in computer science, with wide-ranging applications from data structures to cryptography. The MMH family, a prominent example, is known to be Δ-universal when using a prime modulus. However, many real-world applications require hash functions that can operate with composite moduli for efficiency or compatibility reasons. This paper addresses the challenge of understanding the security properties of hash functions when the modulus is composite, specifically by extending the MMH construction. They aim to determine the conditions under which such a generalized family (GRDH) still provides strong guarantees of "almost-universality" and "almost-Δ-universality," and how these properties translate to secure authentication and secrecy codes.
Methods
The core of the paper's methodology lies in connecting the analysis of hash function properties to the problem of counting solutions to "restricted linear congruences." The authors leverage a recently developed explicit formula for the number of solutions to these congruences, which itself relies on properties of Ramanujan sums and finite Fourier transforms.
Specifically, they:
- Generalize MMH* to GRDH: They replace the prime modulus $p$ in MMH* with an arbitrary integer $n > 1$, and relax the conditions on the key components $x_i$ from being arbitrary to satisfying $\gcd(x_i, n) = t_i$, where $t_i$ are given divisors of $n$.
- Connect Collisions to Congruences: A collision in the hash function $Y_x(m) = m \cdot x \pmod n$ occurs when $Y_x(m) = Y_x(m')$, which is equivalent to $x \cdot (m - m') \equiv 0 \pmod n$. This transforms the problem of analyzing hash collisions into counting solutions to a restricted linear congruence of the form $a_1x_1 + \dots + a_kx_k \equiv 0 \pmod n$, where $a_i = m_i - m'_i$ and the constraints on $x_i$ are $\gcd(x_i, n) = t_i$.
- Utilize Explicit Formula for Congruences: They apply Theorem 2.2, which provides an explicit formula for the number of solutions to such restricted linear congruences. This formula is crucial for deriving bounds on collision probabilities.
- Construct Authentication Codes: They build upon their GRDH results to generalize existing authentication code constructions, demonstrating how the properties of GRDH translate into security guarantees for these codes.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Composite Moduli Can Be Secure: The paper demonstrates that even with composite moduli, hash function families can achieve strong security properties (almost-universality and almost-Δ-universality), provided certain conditions are met. This is a significant finding as it expands the applicability of these cryptographic primitives beyond prime moduli.
- The Power of Restricted Linear Congruences: The novel application of counting solutions to restricted linear congruences to analyze hash function universality is a key methodological contribution. This approach provides a powerful tool for understanding collision probabilities in generalized hash functions.
- Tight Bounds: The paper not only proves that GRDH is $\epsilon$-almost-universal/Δ-universal under specific conditions but also shows that these bounds are tight, meaning they cannot be improved.
- Impossibility Results: A notable outcome is the demonstration that for composite moduli, strong collision bounds (like those achievable with prime moduli) are generally not possible unless specific, restrictive conditions are met (e.g., $k=1$ and $\gcd(x_1, n) = t_1 = 1$). This highlights the inherent limitations when moving away from prime moduli.
- Generalization of Authentication Codes: The work successfully generalizes existing constructions of authentication and secrecy codes, leading to more robust schemes that can handle a wider range of parameters.
Key Results
- GRDH is $\epsilon$-AU: The family GRDH is $\epsilon$-almost-universal for some $\epsilon < 1$ if and only if $n$ is odd and $\gcd(x_i, n) = t_i = 1$ for all $i$. Under these conditions, it is $\frac{1}{p-1}$-almost-universal, where $p$ is the smallest prime divisor of $n$. This bound is tight.
- GRDH is $\epsilon$-AΔU: Similarly, GRDH is $\epsilon$-almost-Δ-universal for some $\epsilon < 1$ if and only if $n$ is odd and $\gcd(x_i, n) = t_i = 1$ for all $i$. Under these conditions, it is $\frac{1}{p-1}$-almost-Δ-universal, where $p$ is the smallest prime divisor of $n$. This bound is also tight.
- Authentication Code Security: The paper proposes a generalized authentication code with secrecy scheme that is $\frac{1}{(p-1)n^{k-1}}$-secure against substitution attacks and $\frac{1}{(p-1)n^{k-1}}$-secret, where $n$ is odd and $p$ is the smallest prime divisor of $n$.
Limitations and Future Work
- Conditions for Security: The strong security properties of GRDH are contingent on $n$ being odd and $\gcd(x_i, n) = t_i = 1$. The paper implicitly suggests that for even $n$ or other choices of $t_i$, the security guarantees are significantly weaker or non-existent.
- Impossibility of Strong Bounds: The paper explicitly states that for composite moduli, achieving strong collision bounds (unless $k=1$ and $\gcd(x_1, n) = t_1 = 1$) is not possible. This is a fundamental limitation.
- Future Work: The authors believe their proof techniques, particularly the connection to restricted linear congruences, could motivate further research in universal hashing and related areas. They also mention that simpler proofs might exist, but their current approach offers a unified framework. The paper also hints at potential applications of their results to the generalized knapsack problem.
Summary updated