Generation of Shared RSA Keys by Two Parties

Guillaume Poupard, Jacques Stern

Simon R. Blackburn⋆, Mike V. D. Burmester, Steven D. Galbraith⋆ +1 more

Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin +1 more

Yang Muxiang, Hong Mei Fan, Minghui Zheng +1 more

An efficient two party RSA secret key sharing generation scheme based on a homomorphic encryption, which is semantically secure under the prime residuosity assumption, is proposed in this paper. At the stage of computing RSA modulo N , an initial distributed primality test protocol is used to reduce the computation complexity and increase the probability of N being a two-prime product. On the other aspect, the homomorphic encryption based sharing conversion protocols is devised and adopted in multi-party computing modulus N and secret key d . Comparing to any sharing conversion protocols based on oblivious transfer protocol, the homomorphic encryption based sharing conversion protocols are of high performance. Our scheme resists the passive attack and since a method of verifying the sharing was introduced in, the scheme can resists any cheating behaviors too. Security proof, computation complexity and communication complexity analysis are given at last.

Dan Boneh, Matthew Franklin

We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N . In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication. All results are presented in the honest but curious scenario (passive adversary).

Ed Blakey