| Zuzana Beerliova |
 |
 |
Date de l'exposé : 1 juillet 2005
Efficient Multi-Party Computation with Dispute Control
Secure multi-party computation (MPC) allows a set of $n$
players to securely compute an agreed function of their inputs, even
when up to $t$ of the players are under complete adversarial
control. We consider secure MPC in the information-theoretic model
with broadcast channels (PKI setup) and present an efficient protocol
with optimal resilience ($t< n/2$), using a new technique technique
called dispute control: During the course of the protocol, the players
keep track of disputes that arise among them, and the ongoing
computation is adjusted such that known disputes cannot arise
again. This prevents the faulty players from intervening too often,
which again allows the honest players to reduce the frequency of
expensive verifications. This way, we can securely (for some security
parameter $\kappa$) compute a circuit with $m$ gates with
communication complexity $O(m n^2 \kappa)$ bits (plus some overhead
independent of $m$). This is to be compared with $\Omega(m n^{22}
\kappa)$ -- the communication complexity of the best known protocol in
the same model.
