Welcome to the resource topic for 2024/432
Title:
Perfect Asynchronous MPC with Linear Communication Overhead
Authors: Ittai Abraham, Gilad Asharov, Shravani Patil, Arpita Patra
Abstract: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).
ePrint: https://eprint.iacr.org/2024/432
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .