Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer; Ivan Damgård; Jesper Buus Nielsen

Paper 2000/055

Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer, Ivan Damgård, and Jesper Buus Nielsen

Abstract

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$ players can be devised which are secure against an active adversary that corrupts any minority of the players. The total number of bits sent 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.

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. Unknown where it was published
Keywords: threshold cryptography
Contact author(s): buus @ brics dk
History: 2000-10-27: received
Short URL: https://ia.cr/2000/055
License: CC BY

BibTeX

@misc{cryptoeprint:2000/055,
      author = {Ronald Cramer and Ivan Damgård and Jesper Buus Nielsen},
      title = {Multiparty Computation from Threshold Homomorphic Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/055},
      year = {2000},
      url = {https://eprint.iacr.org/2000/055}
}