Multiparty Computation from Threshold Homomorphic Encryption

Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen

BRICS Report Series · 2000 · 42 citations · 7 references

DOIFull text

Open access

Concepts

Abstract

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

References

7