Paper 2004/368

Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience

Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek


We consider secure multi-party computation in the asynchronous model and present an efficient protocol with optimal resilience. For $n$ parties, up to $t<n/3$ of them being corrupted, and security parameter $\kappa$, a circuit with $c$ gates can be securely computed with communication complexity $O(c n^3 \kappa)$ bits. In contrast to all previous asynchronous protocols with optimal resilience, our protocol requires access to an expensive broadcast primitive only $O(n)$ times --- independently of the size $c$ of the circuit. This results in a practical protocol with a very low communication overhead. One major drawback of a purely asynchronous network is that the inputs of up to $t$ honest parties cannot be considered for the evaluation of the circuit. Waiting for all inputs could take infinitely long when the missing inputs belong to corrupted parties. Our protocol can easily be extended to a hybrid model, in which we have one round of synchronicity at the end of the input stage, but are fully asynchronous afterwards. In this model, our protocol allows to evaluate the circuit on the inputs of every honest party.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. An extended abstract of this paper appeared in Eurocrypt 2005, pp. 322--340
Contact author(s)
przydatek @ inf ethz ch
2005-06-03: revised
2004-12-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin Hirt and Jesper Buus Nielsen and Bartosz Przydatek},
      title = {Cryptographic Asynchronous Multi-Party Computation with Optimal Resilience},
      howpublished = {Cryptology ePrint Archive, Paper 2004/368},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.