Paper 2024/432

Perfect Asynchronous MPC with Linear Communication Overhead

Ittai Abraham, Intel Labs
Gilad Asharov, Bar-Ilan University
Shravani Patil, Indian Institute of Science, Bangalore
Arpita Patra, Indian Institute of Science, Bangalore

We study secure multiparty computation in the asynchronous setting with perfect security and optimal resilience (less than one-fourth of the participants are malicious). It has been shown that every function can be computed in this model [Ben-OR, Canetti, and Goldreich, STOC'1993]. Despite 30 years of research, all protocols in the asynchronous setting require $\Omega(n^2C)$ communication complexity for computing a circuit with $C$ multiplication gates. In contrast, for nearly 15 years, in the synchronous setting, it has been known how to achieve $\mathcal{O}(nC)$ communication complexity (Beerliova and Hirt; TCC 2008). The techniques for achieving this result in the synchronous setting are not known to be sufficient for obtaining an analogous result in the asynchronous setting. We close this gap between synchronous and asynchronous secure computation and show the first asynchronous protocol with $\mathcal{O}(nC)$ communication complexity for a circuit with $C$ multiplication gates. Linear overhead forms a natural barrier for general secret-sharing-based MPC protocols. Our main technical contribution is an asynchronous weak binding secret sharing that achieves rate-1 communication (i.e., $\mathcal{O}(1)$-overhead per secret). To achieve this goal, we develop new techniques for the asynchronous setting, including the use of trivariate polynomials (as opposed to bivariate polynomials).

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2024
Perfect Secure ComputationAsynchronous networksSecret sharing
Contact author(s)
ittai abraham @ intel com
Gilad Asharov @ biu ac il
shravanip @ iisc ac in
arpita @ iisc ac in
2024-03-15: approved
2024-03-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Gilad Asharov and Shravani Patil and Arpita Patra},
      title = {Perfect Asynchronous {MPC} with Linear Communication Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2024/432},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.