Multiparty Computation from Threshold Homomorphic Encryption

By Ronald Cramer, Ivan Bjerre Damgård, Jesper Buus Nielsen. 2000

669 citations recorded by the source corpus.

We introduce a new approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. We show that given keys for any sufficiently efficient system of this type, general MPC protocols for n parties can be devised which are secure against an active adversary that corrupts any minority of the parties. The total number of bits broadcast is O(nk|C|), where k is the security parameter and |C| is the size of a (Boolean) circuit computing the function to be securely evaluated. An earlier proposal by Franklin and Haber with the same complexity was only secure for passive adversaries, while all earlier protocols with active security had complexity at least quadratic in n. We give two examples of threshold cryptosystems that can support our construction and lead to the claimed complexities.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, methodology): “To compute secure sum,we applied efficient techniques based on threshold homomorphic functions [17] and Fig.”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “Interestingly, threshold decryption of homomorphic encryption can be used as a primitive for constructing a very efficient generic protocol for secure multiparty computation, with a communication overhead of only O(mk|C|) bits (see (16) for a construction secure against semi-honest adversaries, and ”
TACKing Together Efficient Authentication, Revocation, and Privacy in VANETs (2009, methodology): “During simulation, we divide each area into regions based on the dotted lines in Figure 2 (1 kilometer square regions in the city and a boundary bisecting the highway loop).”
Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation (2005, background): “Applications of such functionalities range from emulating a trusted poker dealer to providing players with correlated resources for general MPC protocols (e.g., [14, 16]).”
Privacy-Preserving Face Recognition (2009, methodology): “The problem considered in this paper is an instance of a secure two-party problem; thus standard methods of Secure Multiparty Computation [38,7] can be applied.”
Differentially private aggregation of distributed time-series with transformation and encryption (2010, positive): “However, if the function to be evaluated is a sum function, then efficient techniques using threshold homomorphic functions have been proposed [4,13].”
Secure two-party computations in ANSI C (2012, background): “…General— security and protection General Terms Security, Programming Languages Keywords Secure Computations, Privacy, Model Checking, Compilers Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are…”
Semi-Homomorphic Encryption and Multiparty Computation (2011, methodology): “k ·EV (rk ,t k), where ak is the value contained in Ψk and rk is the value in Φk. Since all commitments and ciphertexts live in the same group Z ∗2 ,w herepkV = N , we can do this efficiently using a variant of a protocol from [ CDN01 ].”
Secure multiparty aggregation with differential privacy: a comparative study (2013, methodology): “For computing sum, we use efficient techniques based on threshold homomorphic functions [12] and random shares [42].”
Distributed Paillier Cryptosystem without Trusted Dealer (2010, background): “Many multiparty computation (MPC) protocols using threshold homomorphic cryptosystems are Paillier-based [32] construnctions (e.g., [ 13 ,3,28,36,26]).”
Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting (2012, background): “• This step differs significantly; obtaining gN could easily be done [11]; however, Ñ cannot be computed as in the two-party case, hence we would have to obtain the solution to the DL problem differently.”
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE (2012, background): “The works of [12,15,6,13] use additively and somewhat homomorphic encryption to get some of the most practically efficient MPC implementations.”
Improved Primitives for Secure Multiparty Integer Computation (2010, background): “The protocols can be instantiated using secret sharing [8] or homomorphic encryption [9].”
Private Similarity Computation in Distributed Systems: From Cryptography to Differential Privacy (2011, methodology): “Formally, the similarity metric eﬀectively used in ThresholdCosine is On one hand for obtaining the numerator, we square the output of the scalar product by applying the multiplication gate from [6] to multiply it by itself.”
Privacy-Preserving Set Operations (2005, background): “Note that Paillier’s cryptosystem [23] satisfies each of our requirements: it is additively homomorphic, supports ciphertexts re-randomization and threshold decryption (secure in the malicious case) [10,11], and allows certain efficient zero-knowledge proofs (standard constructions from [5,3], and p”