Secure Distributed RSA Modulus Generation Revisited: A Faster and More Communication-Efficient Construction

Securely generating an RSA modulus N = pq in a distributed n-party setting while keeping its factors private is a core challenge in threshold cryptography. This paper revisits this problem and improves the state-of-the-art distributed Miller-Rabin primality test by replacing its core component-the divisibility test-with a novel zero-testing protocol.

Our key innovation is an elegant distributed design of Montgomery reduction, which transforms checking δ mod f = 0 (given shares of δ and f ) into testing whether a product equals zero. This approach enables efficient distributed evaluation and offers: (1) Perfect correctness. Unlike prior approaches that are probabilistic or require impractically large shares, our zero test decides δ mod f = 0 deterministically. (2) Improved efficiency. Our zero test runs in only 7 rounds and uses 5 secure multiplications, improving over previous divisibility tests that require either 3 + log 2 n rounds with n + 3 multiplications or 8 rounds with 5n -1 multiplications. Extensive experiments under honest-majority settings show increasing speedups for n ≥ 9, with the efficiency advantage growing as the number of parties increases. Moreover, our semi-honest protocol supports both honest-and dishonest-majority settings via appropriate secure multiplication primitives, and can be upgraded to malicious security with standard compilers.