Paper 2024/2072

Advancements in Distributed RSA Key Generation: Enhanced Biprimality Tests

Abstract

This work re-evaluates the soundness guarantees of the Boneh-Franklin biprimality test ($2001$) for Blum integers. Under the condition $\gcd(pq, p + q - 1) = 1$, we show that the test accepts a non-RSA modulus with probability at most $1/4$. This is a refinement of the previously established $1/2$ bound and holds for all cases except the specific instance where $p=q=3$. We further demonstrate that this $1/4$ bound is tight, thereby halving the number of test iterations required to achieve equivalent soundness. This directly reduces computational and communication overhead in distributed RSA generation protocols. Additionally, we propose a generalized biprimality test based on the Lucas sequence. In the worst case, the acceptance probability of the proposed test is at most $1/4 + 1.25/(p_{\min} -3)$, where $p_{\min}$ is the smallest prime factor of $N$. To validate our approach, we implemented the variant Miller-Rabin test, the Boneh-Franklin test, and our proposed test, performing pairwise comparisons of their effectiveness. Both theoretical analysis and simulations indicate that the proposed test is generally more efficient than the Boneh-Franklin test in detecting cases where $N$ is not an RSA modulus. Furthermore, this test is applicable to generating RSA moduli for arbitrary odd primes. A distributed RSA modulus verification protocol that incorporates our test is also introduced. The protocol is secure against semi-honest adversaries for general odd primes. For Blum integers, it also offers security against malicious adversaries. We analyze its efficiency and compatibility with existing distributed RSA protocols, including those of Boneh-Franklin and Burkhardt et al. (CCS 2023). Our protocol offers competitive performance while enhancing soundness and generality in cryptographic applications.