On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols

Zuzana Beerliova-Trubiniova, Martin Hirt, and Jesper Buus Nielsen

Proc. of the 2010 ACM Symposium on Principles of Distributed Computing — PODC '10, pp. 211–218, Jul 2010.

Multiparty computation (MPC) protocols among $n$ parties secure against $t$ active faults are known to exist if and only if

$t<n/\bf 2$, when the channels are synchronous, and
$t<n/\bf 3$, when the channels are 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 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$.

BibTeX Citation

@inproceedings{BeHiNi10,
    author       = {Zuzana {Beerliova-Trubiniova} and Martin Hirt and Jesper Buus Nielsen},
    title        = {On the Theoretical Gap Between Synchronous and Asynchronous MPC Protocols},
    booktitle    = {Proc. of the 2010 ACM Symposium on Principles of Distributed Computing --- PODC~'10},
    pages        = {211--218},
    year         = {2010},
    month        = {7},
}