Welcome to the resource topic for 2001/023
Robustness for Free in Unconditional Multi-Party Computation
Authors: Martin Hirt, Ueli MaurerAbstract:
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.
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. Even in this model, it seems to be unavoidable that
for every multiplication gate every player must send a value to every
other player, and hence the complexity of our protocol may well be
optimal. The constant overhead factor for robustness is small and the
protocol is practical.
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .