On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols

Zuzana Beerliova-Trubiniova and Martin Hirt and Jesper Buus Nielsen

Multiparty computation (MPC) protocols among $n$ parties secure against
$t$ active faults are known to exist if and only if
\item $t<n/2$, when the channels are \emph{synchronous}, and
\item $t<n/3$, when the channels are \emph{asynchronous}, respectively.
In this work we analyze the gap between these bounds, and show that
in the cryptographic setting (with setup), the sole reason for it is the
\emph{distribution of inputs}: given an oracle for input
distribution, cryptographically-secure asynchronous MPC is possible
with the very same condition as synchronous MPC, namely $t<n/2$. We
do not know whether the gaps in other security models (perfect,
statistical) have the same cause. We stress that all previous
asynchronous MPC protocols inherently require $t<n/3$, even once inputs
are distributed. In particular, all published asynchronous
multiplication sub-protocols inherently require $t<n/3$ and cannot be
used in our setting.

Furthermore, we show that such an input-distribution oracle can be
reduced to an oracle that allows each party to synchronously broadcast
one single message. This means that when one single round of synchronous
broadcast is available, then asynchronous MPC is possible at the same
condition as synchronous MPC, namely $t<n/2$. If such a round cannot be
used, then MPC (and even Byzantine agreement) requires $t<n/3$.