Paper 2020/370

Multiparty Generation of an RSA Modulus

Megan Chen, Ran Cohen, Jack Doerner, Yashvanth Kondi, Eysa Lee, Schuyler Rosefield, and abhi shelat


We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring. Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto'18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt'19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2020
threshold cryptographymultiparty computationRSAbiprime samplingconcrete efficiency
Contact author(s)
j @ ckdoerner net
2021-11-27: last of 4 revisions
2020-04-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Megan Chen and Ran Cohen and Jack Doerner and Yashvanth Kondi and Eysa Lee and Schuyler Rosefield and abhi shelat},
      title = {Multiparty Generation of an RSA Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2020/370},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.