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.