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 moduli generation protocols, the biprimality test for Blum integers $N=pq$, where $p\equiv q\equiv 3\mathrm{mod}4$ are two primes, proposed by Boneh and Franklin ($$) is the most commonly used. Over the past $$ years, the acceptance of this test with a probability in the worst-case for non-RSA moduli has been consistently assumed to be $$ under the condition $$. This paper demonstrates that the acceptance with a probability for the Boneh-Franklin test is at most $$, rather than $$, except in the specific case where $$. Notably, $$ is shown to be the tightest upper bound. This result substantially improves the practical effectiveness of the Boneh-Franklin test: achieving the same level of soundness for the RSA moduli now requires only half the iterations previously considered necessary. Furthermore, we propose a generalized biprimality test based on the Lucas sequence. In the worst case, the acceptance with a probability of the proposed test is at most $$, where $$ is the smallest prime factors of $$. 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. Simulations indicate that the proposed test is generally more efficient than the Boneh-Franklin test in detecting cases where $$ is not an RSA modulus. Additionally, this test is applicable to generating RSA moduli for arbitrary odd primes $$. 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 moduli generation protocols. After thoroughly analyzing and comparing well-known protocols for Blum integers, including Burkhardt et al.'s protocol (CCS 2023), and the Boneh-Franklin protocol, our protocol is competitive for generating distributed RSA moduli.