Welcome to the resource topic for 2024/2072
Title:
Advancements in Distributed RSA Key Generation: Enhanced Biprimality Tests
Authors: ChihYun Chuang, IHung Hsu, TingFang Lee
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 \mod 4 are two primes, proposed by Boneh and Franklin in 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 show that for the Boneh-Franklin test, its acceptance probability is at most 1/4 rather than 1/2,
except in the case where p = q = 3. At the same time, 1/4 is also the tightest upper bound. Enhance the effectiveness of applying the Boneh-Franklin test in this result: achieving the same soundness for the RSA modulus requires only half the number of iterations commonly recognized.
Furthermore, we propose two types of Lucas biprimality tests. In the worst case, one of proposed tests acceptance rate is at most 1/4 + 1.25/(p_{\min} -3), where p_{\min} is the smallest prime factors of N. However, simulation study suggests that this test is generally more efficient than the Boneh-Franklin test for detecting when N is not an RSA modulus.
The second type of Lucas test, though less efficient, can be applied to arbitrary RSA moduli p and q. Nevertheless, if the soundness error for generating an RSA modulus is set at approximately 2^{-80}, it leaks at most 46 quadratic symbol values, regardless of the public key length. We also design corresponding protocols for both tests and validate their resilience against semi-honest adversaries, which can be applied to most known distributed RSA modulus generation protocols. After thoroughly analyzing and comparing well-known protocols, including the variant Miller-Rabin test used by Burkhardt et al. (CCS 2023), the Boneh-Franklin test, and our proposed Lucas-type tests, our proposed Lucas test is also highly competitive in verifying whether N is an RSA modulus.
ePrint: https://eprint.iacr.org/2024/2072
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .