An implementation of the Paillier crypto system with threshold decryption without a trusted dealer

Thijs Veugen, Thomas Attema, Gabriele Spini

Published Jan 1, 2019• 6 citations

Abstract

We consider the problem of securely generating the keys of the Paillier crypto system [11] with (t; n) threshold decryption, without a trusted dealer. Nishide and Sakurai [10] describe a solution, secure inthe malicious model. We use their ideas to make a simpler solution for the semi-honest model, and further introduce a few optimisations. We implement the secure key generation protocol on a single computer, andconsider its performance.

Related papers

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

Carmit Hazay, Gert Læssøe Mikkelsen, Tal Rabin +1 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 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.

Jan 1, 20110 citations

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

Fast Distributed RSA Key Generation for Semi-honest and Malicious Adversaries

Tore Kasper Frederiksen, Yehuda Lindell, Valery Osheter +1 more

We present two new, highly efficient, protocols for securely generating a distributed RSA key pair in the two-party setting. One protocol is semi-honestly secure and the other maliciously secure. Both are constant round and do not rely on any specific number-theoretic assumptions and improve significantly over the state-of-the-art by allowing a slight leakage (which we show to not affect security). For our maliciously secure protocol our most significant improvement comes from executing most of the protocol in a “strong” semi-honest manner and then doing a single, light, zero-knowledge argument of correct execution. We introduce other significant improvements as well. One such improvement arrives in showing that certain, limited leakage does not compromise security, which allows us to use lightweight subprotocols. Another improvement, which may be of independent interest, comes in our approach for multiplying two large integers using OT, in the malicious setting, without being susceptible to a selective-failure attack. Finally, we implement our malicious protocol and show that its performance is an order of magnitude better than the best previous protocol, which provided only semi-honest security. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Lecture notes in computer scienceJan 1, 201842 citations

An implementation of three-pass protocol on a Paillier cryptosystem

Ragdah Ahmed Qasim, Hamza B. Habib, Rifaat Z. Khalaf

This article proposes a new encryption algorithm based on two cryptographic techniques which are the three-pass protocol and the Paillier cryptosystem. Using the three-pass protocol makes it possible for one party to safely send a message to another party without exchanging or distributing encryption secrets. In each pass in the proposed algorithm, each party uses their private pair of prime numbers to calculate the modular number. That means they use their public and private keys to perform the encryption and decryption. Moreover, the encryption and the decryption on the sender side are performed by the Paillier cryptosystem which is based on the difficulty of finding the inverse modular of the public key. In the proposed algorithm, less information is shared between the two parties and that makes it more secure against attacks. The results show that the proposed algorithm needs less time to perform the encryption and decryption compared with the classic algorithm. Therefore, the proposed algorithm is more secure, fast and reliable for sending and receiving data compared with the classic algorithm.

AIP conference proceedingsJan 1, 20240 citations

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

A Note on the Relation between the Definitions of Security for Semi-Honest and Malicious Adversaries.

Carmit Hazay, Yehuda Lindell

In secure computation, a set of parties wish to jointly compute some function of their private inputs while preserving security properties like privacy, correctness and more. The two main adversary models that have been considered are semi-honest adversaries who follow the prescribed protocol but try to glean more information than allowed from the protocol transcript, and malicious adversaries who can run any efficient strategy in order to carry out their attack. As such they can deviate at will from the prescribed protocol. One would naturally expect that any protocol that is secure in the presence of malicious adversaries will automatically be secure in the presence of semi-honest adversaries. However, due to a technicality in the definition, this is not necessarily true. In this brief note, we explain why this is the case, and show that a slight modification to the definition of semi-honest adversaries (specifically, allowing a semi-honest adversary to change its received input) suffices for fixing this anomaly. Our aim in publishing this note is to make this curious fact more known to the wider cryptographic community. 1 Malicious Versus Semi-honest Adversaries

Jan 1, 201012 citations