Multiparty Computation from Threshold Homomorphic Encryption
Ronald Cramer
June 2000 |
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
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
, where is the security parameter and 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 . We give two examples of threshold
cryptosystems that can support our construction and lead to the claimed
complexities.
Available as PostScript, PDF, DVI. |