Paper 2024/2072

Beyond the 1/2 Bound: On the Theory and Practice of Biprimality Tests

Abstract

The Boneh-Franklin (BF) biprimality test, a cornerstone of distributed RSA key generation, has a universally accepted worst-case soundness error of $1/2$. We show that this two-decade-old bound is not tight and present a collection of results that refine and generalize this fundamental test. Our contributions are threefold: \textbf{(1) A Tight Soundness Bound for the BF Test:} Our primary contribution is a rigorous proof that the worst-case acceptance probability of the BF test for a non-RSA modulus is at most $1/4$, not the long-accepted $1/2$. By constructing cases that meet this bound, we establish that it is tight. This fundamental result allows existing protocols to halve the required iterations, thereby improving the efficiency of verifying valid moduli while maintaining the same security level. \textbf{(2) A Generalized Test for Universal Applicability and a Nuanced Verdict:} We introduce a versatile Lucas-sequence-based test that resolves the long-standing limitation of the BF test to Blum integers. While we prove its soundness error is theoretically and empirically superior in the vast majority of cases, our analysis, based on a performance model parameterized by simulation, indicates a trade-off. For the specific task of generating Blum integers, the exceptional local computation speed of the BF test suggests it maintains a practical advantage in latency-sensitive environments. This nuanced finding underscores the interplay between theoretical soundness error and real-world performance. \textbf{(3) New Protocols for an Expanded Design Space:} We construct new distributed verification protocols that realize our foundational insights. Our Lucas-based protocol provides the first efficient, provably secure solution for generating all standard RSA moduli in the semi-honest model, alongside a maliciously secure variant for Blum integers. This fills a gap for applications requiring generality and, combined with our comparative analysis, provides a clearer and more complete toolkit for protocol designers. Overall, our work refines the theoretical bounds of biprimality testing and provides a more efficient and versatile foundation for distributed RSA key generation.

Note: Minor revisions. 3/13