On the theoretical gap between synchronous and asynchronous MPC protocols

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Zuzana Beerliová-Trubíniová, ETH Zürich, Switzerland
  • Martin Hirt, ETH Zürich, Switzerland
  • Jesper Buus Nielsen
  • Department of Computer Science

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

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

Original languageEnglish
Title of host publicationProceeding of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. PODC '10
EditorsAndrea Richa , Rachid Guerraoui
Number of pages8
PublisherAssociation for Computing Machinery
Publication year2010
ISBN (print)978-1-60558-888-9
Publication statusPublished - 2010
Event29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. - Zurich, Switzerland
Duration: 25 Jul 201028 Jul 2010


Conference29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing.

See relations at Aarhus University Citationformats

ID: 22304434