TL;DR
This paper introduces a new class of "higher residuosity attacks" that can break the security of recent protocols designed for secure two-party comparison (Yao's millionaires' problem). The attacks exploit a weakness when a specific parameter, the prime base $p_0$, is small, demonstrating that these protocols are not as secure as previously thought under certain conditions.
What Problem Does This Paper Address?
The paper tackles the challenge of secure two-party comparison, famously known as Yao's millionaires' problem. This problem allows two parties to compare their private numerical inputs without revealing the actual values to each other, a crucial task in privacy-preserving computation. While homomorphic encryption offers an elegant solution, recent protocols like CEK and BST have shown impressive performance improvements over older methods. However, their security relies on the hardness of "small RSA subgroup decision problems." This paper investigates whether these problems are truly hard, especially under specific parameter choices, and if not, how this impacts the security of the CEK and BST protocols.
Methods
The core of this paper is the introduction of "higher residuosity attacks." These attacks are an extension of the classical quadratic residuosity attack, but instead of dealing with squares, they generalize to higher powers. The authors leverage properties of number fields, specifically Gaussian integers (Z[i]) for the $p_0=2$ case and cyclotomic fields for odd $p_0$, to develop these attacks. They introduce and utilize concepts like the quartic Jacobi symbol and the general power residue symbol. The attacks work by exploiting the leakage of information about the order of elements in specific subgroups of $\mathbb{Z}_N^*$, which can then be used to partially factorize the RSA modulus $N$. This factorization breaks the underlying hardness assumption of the protocols.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Small $p_0$ is a vulnerability: The most significant insight is that the security of the CEK and BST protocols is compromised when the prime base $p_0$ is small (e.g., less than 100). This is because it becomes computationally feasible to solve the underlying "small RSA subgroup decision problems."
- Higher Residuosity Attacks are powerful: The paper demonstrates that extending classical residuosity attacks to higher powers can be effective against cryptographic assumptions. This suggests a broader applicability of these techniques to analyze other number-theoretic hardness assumptions.
- Leakage of Order is Critical: The attacks exploit the leakage of an element's order within a specific subgroup. This leakage allows for partial factorization of the RSA modulus, which is the key to breaking the protocols.
- Practical Implications for Secure Comparison: The findings directly impact the practical security of secure two-party comparison protocols, showing that careful parameter selection is crucial for maintaining privacy.
Key Results
- The paper presents a quartic residuosity attack that efficiently solves the small RSA subgroup decision problem when $p_0 = 2$.
- It also introduces a general higher residuosity attack for odd prime $p_0$, which is highly successful when $p_0$ is small.
- These attacks demonstrate that the CEK and BST protocols are not semantically secure when $p_0$ is small, as they can leak information about the private inputs. Specifically, they can reveal whether an input is zero.
- The authors provide recommendations for mitigating these attacks, including using larger $p_0$ values or modifying the protocols to satisfy specific conditions related to the prime factors of $N$.
Limitations and Future Work
- Efficiency Bottleneck for Large $p_0$: While the attacks are highly successful for small $p_0$, computing the $p_0$-th power residue symbol becomes computationally expensive for large $p_0$. This limits the direct applicability of these specific attacks to scenarios with very large $p_0$.
- Analysis of Other Assumptions: The authors express hope that their work can be applied to analyze other number-theoretic hardness assumptions beyond the small RSA subgroup decision problem.
- Further Research on Power Residue Symbols: The paper suggests investigating more efficient algorithms for computing power residue symbols modulo two-element representation ideals.
- Improving Protocol Security: The paper offers concrete suggestions for improving the security of the CEK and BST protocols, such as choosing larger $p_0$ or modifying the RSA quintuple structure. Future work could focus on formally proving the security of these modified protocols under the proposed assumptions.
Summary updated