Paper 2021/1174

On Communication-Efficient Asynchronous MPC with Adaptive Security

Annick Chopard, Martin Hirt, and Chen-Da Liu-Zhang


Secure multi-party computation (MPC) allows a set of $n$ parties to jointly compute an arbitrary computation over their private inputs. Two main variants have been considered in the literature according to the underlying communication model. Synchronous MPC protocols proceed in rounds, and rely on the fact that the communication network provides strong delivery guarantees within each round. Asynchronous MPC protocols achieve security guarantees even when the network delay is arbitrary. While the problem of MPC has largely been studied in both variants with respect to both feasibility and efficiency results, there is still a substantial gap when it comes to communication complexity of adaptively secure protocols. Concretely, while adaptively secure synchronous MPC protocols with linear communication are known for a long time, the best asynchronous protocol communicates $\mathcal{O}(n^4 \kappa)$ bits per multiplication. In this paper, we make progress towards closing this gap by providing two protocols. First, we present an adaptively secure asynchronous protocol with optimal resilience $t<n/3$ and $\mathcal{O}(n^2 \kappa)$ bits of communication per multiplication, improving over the state of the art protocols in this setting by a quadratic factor in the number of parties. The protocol has cryptographic security and follows the CDN approach [Eurocrypt'01], based on additive threshold homomorphic encryption. Second, we show an optimization of the above protocol that tolerates up to $t<(1-\epsilon)n/3$ corruptions and communicates $\mathcal{O}(n\cdot \poly(\kappa))$ bits per multiplication under stronger assumptions.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2021
Multi-party computationasynchronousadaptive security
Contact author(s)
achopard @ ethz ch
hirt @ ethz ch
cliuzhan @ andrew cmu edu
2021-11-08: revised
2021-09-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Annick Chopard and Martin Hirt and Chen-Da Liu-Zhang},
      title = {On Communication-Efficient Asynchronous {MPC} with Adaptive Security},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1174},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.