Robustness for Free in Unconditional Multi-Party Computation
Martin Hirt and Ueli Maurer
We present a very efficient multi-party computation protocol
unconditionally secure against an active adversary. The security is
maximal, i.e., active corruption of up to $t<n/3$ of the $n$ players
is tolerated. The communication complexity for securely evaluating a
circuit with $m$ multiplication gates over a finite field is
$\O(mn^2)$ field elements, including the communication required for
simulating broadcast, but excluding some overhead costs (independent
of $m$) for sharing the inputs and reconstructing the outputs.
This corresponds to the complexity of the best known protocols for the
passive model, where the corrupted players are guaranteed not to deviate
from the protocol. The complexity of our protocol may well be optimal.
The constant overhead factor for robustness is small and the protocol is
practical.