Higher Residuosity Attacks on Small RSA Subgroup Decision Problems

Secure two-party comparison, known as Yao’s millionaires’ problem, has been a fundamental challenge in privacy-preserving compu-tation. It enables two parties to compare their inputs without revealing the exact values of those inputs or relying on any trusted third party. One elegant approach to secure computation is based on homomorphic encryption. Recently, building on this approach, Carlton et al. (CT-RSA 2018) and Bourse et al. (CT-RSA 2020) presented novel solutions for the problem of secure integer comparison. These protocols have demon-strated significantly improved performance compared to the well-known and frequently used DGK protocol (ACISP 2007 and Int. J. Appl. Cryp-togr. 1(4),323-324, 2009). In this paper, we introduce a class of higher residuosity attacks, which can be regarded as an extension of the clas-sical quadratic residuosity attack on the decisional Diffie-Hellman prob-lem. We demonstrate that the small RSA subgroup decision problems, upon which both the CEK and BST protocols are based, are not difficult to solve when the prime base p_0 p0 is small (e.g., $ p_0 < 100 p0 < 100). Under these conditions, the protocols achieve optimal overall performance. Further-more, we offer recommendations for precluding such attacks, including one approach that does not adversely affect performance. We hope that these attacks can be applied to analyze other number-theoretic hardness assumptions.