Perfect Asynchronous MPC with Linear Communication Overhead

ePrint Report: Perfect Asynchronous MPC with Linear Communication Overhead

Ittai Abraham, Gilad Asharov, Shravani Patil, Arpita Patra

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 …

asynchronous can communication computation eprint report function linear malicious mpc perfect report resilience secure multiparty computation security study