Higher Residuosity Attacks on Small RSA Subgroup Decision Problems

Xiaopeng Zhao, Zhenfu Cao, Xiaolei Dong, Zhusen Liu

TL;DR

This paper introduces novel "higher residuosity attacks" that break the security of two recently proposed secure two-party comparison protocols (CEK and BST). These attacks exploit a weakness in the underlying RSA subgroup decision problem when the prime base ($p_0$) is small, demonstrating that these protocols are not as secure as previously thought.

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 or relying on a trusted third party. While homomorphic encryption offers an elegant approach, recent protocols like CEK and BST, built upon RSA subgroup assumptions, have shown impressive performance. However, the security of these protocols hinges on the hardness of certain "small RSA subgroup decision problems." This paper investigates whether these problems are indeed as hard as assumed, particularly when certain parameters are small.

Methods

The core contribution of this paper is the development of "higher residuosity attacks." These attacks are an extension of classical residuosity attacks, specifically tailored to the small RSA subgroup decision problems that underpin the CEK and BST protocols. The authors leverage properties of Gaussian integers and quartic Jacobi symbols to efficiently solve these decision problems when the prime base ($p_0$) is small. They also extend these attacks to "higher" residuosity for odd prime bases. The attacks work by exploiting leakage from the RSA quintuple (a public key component) to partially factorize the RSA modulus $N$. This partial factorization then allows for the computation of power residue symbols, which are used to distinguish between the distributions that the protocols are designed to protect.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Small $p_0$ is a critical vulnerability: The paper reveals that the security of the CEK and BST protocols is significantly weakened when the prime base $p_0$ is small (e.g., $p_0 < 100$). This is a crucial parameter that was not adequately considered for its impact on security.
  • Higher Residuosity Attacks are powerful: The authors demonstrate that by extending classical residuosity attacks to "higher" orders, they can effectively break the underlying hardness assumptions of these protocols. This highlights the importance of considering higher-order residuosity in cryptographic design.
  • Gaussian Integers and Quartic Jacobi Symbols are key tools: The paper ingeniously uses the algebraic structure of Gaussian integers and the properties of the quartic Jacobi symbol to develop efficient algorithms for attacking the small RSA subgroup decision problems.
  • Practical implications for secure comparison: The attacks have direct implications for the security of practical secure two-party comparison protocols, showing that current implementations might be vulnerable to privacy leakage.

Key Results

  • The paper presents practical attacks that can solve the small RSA subgroup decision problems with a high success probability when $p_0$ is small.
  • Specifically, for $p_0 = 2$, the authors show that the SRSDP can be solved with an advantage of 1/2 using quartic residuosity.
  • For odd prime $p_0$, they describe a higher residuosity attack with a very high success probability, though its efficiency is limited by the computation of the $p_0$-th power residue symbol for large $p_0$.
  • The attacks demonstrate that the CEK and BST protocols can leak information about the private inputs, compromising the privacy of the participants.
  • The authors provide recommendations for mitigating these attacks, including using larger $p_0$ values or modifying the RSA quintuple structure.

Limitations and Future Work

  • Efficiency bottleneck for large $p_0$: While the higher residuosity attacks are effective, their practical implementation is hindered by the computational cost of computing power residue symbols for large prime bases $p_0$.
  • Limited scope of current attacks: The proposed attacks are effective against specific RSA subgroup decision problems. The paper notes that these attacks are currently ineffective against other "Gap 2k-residuosity" assumptions.
  • Future work directions:
    • Investigating more efficient algorithms for computing power residue symbols modulo two-element representation ideals.
  • Analyzing other number-theoretic hardness assumptions using higher residuosity attacks.
  • Developing protocols that are provably secure against these types of attacks, potentially by modifying the RSA quintuple structure or using larger $p_0$.

Summary updated

BibTeX
@article{zhao2025higher,
  author = {Xiaopeng Zhao and Zhenfu Cao and Xiaolei Dong and Zhusen Liu},
  title = {{Higher Residuosity Attacks on Small RSA Subgroup Decision Problems}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
  url = {https://openreview.net/forum?id=ZzEKG7rgry},
}

Loading related content...

Figure