Multiparty Computation from Threshold Homomorphic Encryption

We introduce a new approach to multiparty computation (MPC) basingit on homomorphic threshold crypto-systems. We show that givenkeys for any sufficiently efficient system of this type, general MPC protocolsfor n players can be devised which are secure against an activeadversary that corrupts any minority of the players. The total number ofbits sent is O(nk|C|), where k is the security parameter and |C| is the sizeof a (Boolean) circuit computing the function to be securely evaluated.An earlier proposal by Franklin and Haber with the same complexity wasonly secure for passive adversaries, while all earlier protocols with activesecurity had complexity at least quadratic in n. We give two examplesof threshold cryptosystems that can support our construction and leadto the claimed complexities