Improved Distributed RSA Key Generation Using the Miller-Rabin Test

TY - GEN

T1 - Improved Distributed RSA Key Generation Using the Miller-Rabin Test

AU - Burkhardt, Jakob

AU - Damgård, Ivan

AU - Frederiksen, Tore Kasper

AU - Orlandi, Claudio

AU - Ghosh, Satrajit

PY - 2021/11/21

Y1 - 2021/11/21

N2 - 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.

AB - 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.

KW - RSA

KW - Secure multiparty computation

KW - threshold cryptography

UR - http://www.scopus.com/inward/record.url?scp=85179839848&partnerID=8YFLogxK

U2 - 10.1145/3576915.3623163

DO - 10.1145/3576915.3623163

M3 - Article in proceedings

SN - 979-8-4007-0050-7

SP - 2501

EP - 2515

BT - CCS '23

A2 - Meng, Weizhi

A2 - Jensen, Christian Damsgaard

A2 - Cremers, Cas

A2 - Kirda, Engin

PB - Association for Computing Machinery

CY - New York

ER -