Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Of Crypto Seminar: Perfect Asynchronous MPC with Linear Communication Overhead
event speaker icon
Gilad Asharov (Bar Ilan University)
event date icon
Thursday, 01.02.2024, 11:30
event location icon
Taub 401
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 $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 $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., $O(1)$-overhead per secret).

To achieve this goal, we develop new techniques for the asynchronous setting, including the use of \emph{trivariate polynomials} (as opposed to bivariate polynomials).

Joint work with Ittai Abraham, Shravani Patil, and Arpita Patra