Efficient Multi-Party Computation with Dispute Control

Zuzana Beerliova-Trubiniova and Martin Hirt

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$
players are under the control of an (active or passive) adversary. In the
information-theoretic model MPC is possible if and only if $t<n/2$ (where
active security with $t\ge n/3$ requires a trusted key setup).

Known passive MPC protocols require a communication of $\O(n^2)$ field
elements per multiplication. Recently, the same communication complexity
was achieved for active security with $t<n/3$. It remained an open
question whether $\O(n^2)$ complexity is achievable for $n/3\le t<n/2$.

We answer this question in the affirmative by presenting an active MPC
protocol that provides optimal ($t<n/2$) security and communicates only
$\O(n^2)$ field elements per multiplication. Additionally the protocol
broadcasts $\O(n^3)$ field elements \emph{overall}, for the whole
computation. 

The communication complexity of the new protocol is to be compared with
the most efficient previously known protocol for the same model, which
requires \emph{broadcasting} $\Omega(n^5)$ field elements per
multiplication. This substantial reduction in communication is mainly
achieved by applying a new technique called \emph{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. Dispute control is inspired by the
player-elimination framework. However, player elimination is not suited
for models with $t\ge n/3$.