Multiparty Computation from Threshold Homomorphic Encryption

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.