Paper 2024/2072

Advancements in Distributed RSA Key Generation: Enhanced Biprimality Tests

Abstract

RSA is widely used in modern cryptographic practice, with certain RSA-based protocols relying on the secrecy of $p$ and $q$. A common approach is to use secure multiparty computation to address the privacy concerns of $p$ and $q$. Specifically constrained to distributed RSA modulus generation protocols, the biprimality test for Blum integers $N=pq$, where $p\equiv q\equiv 3 \mod4$ are two primes, proposed by Boneh and Franklin ($2001$) is the most commonly used. Over the past $20 $ years, the worst-case acceptance rate of this test has been consistently assumed to be $1/2$ under the condition $\gcd(pq,p+q-1)=1$. In this paper, we demonstrate that for the Boneh-Franklin test, the acceptance probability is at most $1/4$, rather than $1/2$, except in the specific case where $p = q = 3$. We establish that the value of $1/4$ represents the tightest upper bound. This finding significantly enhances the practical effectiveness of the Boneh-Franklin test: achieving equivalent soundness for the RSA modulus now requires only half the number of iterations previously deemed necessary. Furthermore, we propose a generalized biprimality test based on the Lucas sequence. In the worst case, the acceptance rate of the proposed test is at most $1/4 + 1.25/(p_{\min} -3)$, where $p_{\min}$ is the smallest prime factors of $N$. Simulation study suggests that this test is generally more efficient than the Boneh-Franklin test for detecting when $N$ is not an RSA modulus. Additionally, this test is applicable to generating arbitrary RSA moduli for arbitrary odd primes $p,q$. A corresponding protocol is developed for this test, validated for resilience against semi-honest adversaries, and shown to be applicable to most known distributed RSA modulus generation protocols. After thoroughly analyzing and comparing well-known protocols for Blum integers, including the variant Miller-Rabin test used by Burkhardt et al. (CCS 2023), the Boneh-Franklin test, and our proposed Lucas-type test, our proposed protocol test is also highly competitive in verifying whether $N$ is an RSA modulus.