Simple and Efficient Perfectly-Secure Asynchronous MPC

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 adversary.
Known \emph{asynchronous} MPC protocols require communication of at least
$\Omega(n^3)$ (with cryptographic security), respectively $\Omega(n^4)$
(with information-theoretic security, but with error probability and
non-optimal resilience) field elements per multiplication.
We present an asynchronous MPC protocol communicating $\O(n^3)$ field
elements per multiplication. Our protocol provides perfect security
against an active, adaptive adversary corrupting $t<n/4$ players, which
is optimal.
This communication complexity is to be compared with the most efficient
previously known protocol for the same model, which requires
$\Omega(n^5)$ field elements of communication (i.e., $\Omega(n^3)$
broadcasts). Our protocol is as efficient as the most efficient perfectly
secure protocol for the synchronous model and the most efficient
asynchronous protocol with cryptographic security.

Furthermore, we enhance our MPC protocol for a hybrid model. In the fully
asynchronous model, up to $t$ honest players might not be able to provide
their input in the computation. In the hybrid model, all players are able
to provide their input, given that the very first round of communication
is synchronous. We provide an MPC protocol with communicating $\O(n^3)$
field elements per multiplication, where all players can provide their
input if the first communication round turns out to be synchronous, and
all but at most $t$ players can provide their input if the communication
is fully asynchronous. The protocol does not need to know whether or not
the first communication round is synchronous, thus combining the
advantages of the synchronous world and the asynchronous world. The
proposed MPC protocol is the first protocol with this property.