Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting.

Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin, Tomas Toft

Published Jan 1, 2011• 0 citations

Abstract

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is complete Paillier [Pai99] threshold encryption scheme in the two-party setting with security against malicious behavior. Furthermore, we describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation is comprised of the following: (i) a distributed protocol for generation of an RSA composite, and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite as public key and is comprised of: (i) a distributed generation of the corresponding secret-key shares and, (ii) a distributed decryption protocol for decrypting according to Paillier.

Related papers

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting

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

The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999 ) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: ( i ) a distributed protocol for generation of an RSA composite and ( ii ) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: ( i ) a distributed generation of the corresponding secret key shares and ( ii ) a distributed decryption protocol for decrypting according to Paillier.

Journal of CryptologyFeb 5, 201876 citations

Efficient threshold multiparty computation schemes

Schuyler Rosefield

Multiparty Computation (hereafter MPC) is a technique for allowing a set ofparticipants to run a secure computation with the assurance that the output is (1) correct, and (2) that a malicious party did not learn anything about the inputs of the honest parties besides what it can glean from the output. Impor- tantly much of cryptography is based on the assumption that an honest party has a private and secret input, and if the adversary learns this input the security of the scheme is broken. Then naturally the techniques of MPC can be applied to create threshold protocols for these cryptographic schemes to ensure that the secret inputs are not leaked and moreover that no group of parties smaller than the threshold know the input at all. While we have known how to generically evaluate MPC for any function since the 80s the question of efficiency still drives progress to this day. This thesis looks at two approaches for making secure com- putation more practical to deploy: developing specialized protocols for appli- cations such as distributed key generation and signing with RSA and ECDSA; and improving the state of the art of maliciously secure generic boolean-circuit MPC. We first look at work that produced a distributed key generation protocol for RSA that utilizes a novel candidate sampling mechanism to reduce waste in primality testing. The second work builds a threshold scheme for symmetric cryptographic primitives such as AES and SHA where there is limited algebraic structure to exploit by efficiently converting a generic n-of-n MPC protocol into a threshold t-of-n MPC protocol. Future directions in this thesis are in combin- ing techniques from the prior works to create a blind signature scheme for the Elliptic Curve Digital Signature Algorithm (ECDSA) that requires both alge- braic operations over elliptic curves and additionally symmetric evaluations of the SHA2 hash function.--Author's abstract

Jan 1, 20240 citations

The Return of Eratosthenes: Secure Generation of RSA Moduli using Distributed Sieving

Cyprien Delpech de Saint Guilhem, Eleftheria Makri, Dragos Rotaru +1 more

Secure multiparty generation of an RSA biprime is a challenging task, which increasingly receives attention, due to the numerous privacy-preserving applications that require it. In this work, we construct a new protocol for the RSA biprime generation task, secure against a malicious adversary, who can corrupt any subset of protocol participants. Our protocol is designed with generic multiparty computation (MPC), making it both platform-independent and allowing for weaker security models to be assumed (e.g., honest majority), should the application scenario require it. By carefully "postponing" the check of possible inconsistencies in the shares provided by malicious adversaries, we achieve noteworthy efficiency improvements. Concretely, we are able to produce additive sharings of the prime candidates, from multiplicative sharings via a semi-honest multiplication, without degrading the overall (active) security of our protocol. This is the core of our sieving technique, increasing the probability of our protocol sampling a biprime. Similarly, we perform the first biprimality test, requiring several repetitions, without checking input share consistency, and perform the more costly consistency check only in case of success of the Jacobi symbol based biprimality test. Moreover, we propose a protocol to convert an additive sharing over a ring, into an additive sharing over the integers. Besides being a necessary sub-protocol for the RSA biprime generation, this conversion protocol is of independent interest. The cost analysis of our protocol demonstrated that our approach improves the current state-of-the-art (Chen et al.-Crypto 2020), in terms of communication efficiency. Concretely, for the two-party case with malicious security, and primes of 2048bits, our protocol improves communication by a factor of ~37.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Nov 12, 20219 citations

Efficient generation of shared RSA keys

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

Journal of the ACMJul 1, 2001154 citations

Efficient and robust two-party RSA key generation

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.

Wuhan University Journal of Natural SciencesNov 1, 20061 citation

Threshold Fully Homomorphic Encryption and Secure Computation.

Steven Myers, Mona Sergi, Abhi A. Shelat

Cramer, Damgard, and Nielsen [CDN01] show how to construct an efficient secure multiparty computation scheme using a threshold homomorphic encryption scheme that has four properties i) a honest-verifier zero-knowledge proof of knowledge of encrypted values, ii) proving multiplications correct iii) threshold decryption and iv) trusted shared key setup. Naor and Nissim [NN01a] show how to construct secure multi-party protocols for a function f whose communication is proportional to the communication required to evaluate f without security, albeit at the cost of computation that might be exponential in the description of f . Gentry [Gen09a] shows how to combine both ideas with fully homomorphic encryption in order to construct secure multi-party protocol that allows evaluation of a function f using communication that is independent of the circuit description of f and computation that is polynomial in | f |. This paper addresses the major drawback’s of Gentry’s approach: we eliminate the use of non-black box methods that are inherent in Naor and Nissim’s compiler. To do this we show how to modify the fully homomorphic encryption construction of van Dijk et al. [vDGHV10] to be threshold fully homomorphic encryption schemes. We directly construct (information theoretically) secure protocols for sharing the secret key for our threshold scheme (thereby removing the setup assumptions) and for jointly decrypting a bit. All of these constructions are constant round and we thoroughly analyze their complexity; they address requirements (iii) and (iv). The fact that the encryption scheme is fully homomorphic addresses requirement (ii). To address the need for an honest-verifier zero-knowledge proof of knowledge of encrypted values, we instead argue that a weaker solution suffices. We provide a 2-round blackbox protocol that allows us to prove knowledge of encrypted bits. Our protocol is not zeroknowledge, but it provably does not release any information about the bit being discussed, and this is sufficient to prove the correctness of a simulation in a method similar to Cramer et al. Altogether, we construct the first black-box secure multi-party computation protocol that allows evaluation of a function f using communication that is independent of the circuit description of f .

Jan 1, 201130 citations