Paper 2023/644

Improved Distributed RSA Key Generation Using the Miller-Rabin Test

Jakob Burkhardt, Aarhus University
Ivan Damgård, Aarhus University
Tore Frederiksen, Zama
Satrajit Ghosh, Indian Institute of Technology Kharagpur
Claudio Orlandi, Aarhus University

Secure distributed generation of RSA moduli (e.g., generating $N=pq$ where none of the parties learns anything about $p$ or $q$) is an important cryptographic task, that is needed both in threshold implementations of RSA-based cryptosystems and in other, advanced cryptographic protocols that assume that all the parties have access to a trusted RSA modulo. In this paper, we provide a novel protocol for secure distributed RSA key generation based on the Miller-Rabin test. Compared with the more commonly used Boneh-Franklin test (which requires many iterations), the Miller-Rabin test has the advantage of providing negligible error after even a single iteration of the test for large enough moduli (e.g., $4096$ bits). From a technical point of view, our main contribution is a novel divisibility test which allows to perform the primality test in an efficient way, while keeping $p$ and $q$ secret. Our semi-honest RSA generation protocol uses any underlying secure multiplication protocol in a black-box way, and our protocol can therefore be instantiated in both the honest or dishonest majority setting based on the chosen multiplication protocol. Our semi-honest protocol can be upgraded to protect against active adversaries at low cost using existing compilers. Finally, we provide an experimental evaluation showing that for the honest majority case, our protocol is much faster than Boneh-Franklin.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. CCS 2023
secure multiparty computationthreshold cryptographyRSA
Contact author(s)
jakob @ cs au dk
ivan @ cs au dk
tore frederiksen @ zama ai
satrajit @ cse iitkgp ac in
orlandi @ cs au dk
2023-11-16: revised
2023-05-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jakob Burkhardt and Ivan Damgård and Tore Frederiksen and Satrajit Ghosh and Claudio Orlandi},
      title = {Improved Distributed RSA Key Generation Using the Miller-Rabin Test},
      howpublished = {Cryptology ePrint Archive, Paper 2023/644},
      year = {2023},
      doi = {10.1145/3576915.3623163},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.