Benny Applebaum: The Round Complexity of Perfectly-Secure Multiparty Computation

Thursday, June 11, 2020 - 12:00pm to 1:30pm
Zoom Link:
Benny Applebaum


We study the round complexity of general secure multiparty computation (MPC) in the classical information-theoretic model of Ben-Or, Goldwasser, and Wigderson [BGW88]. That is, we strive for perfect, information-theoretic and error-free, security against any coalition of at most t computationally-unbounded corrupted parties. Classical feasibility results show that this is possible for any t<n/2 in the passive setting, when the parties follow the protocol, and up to t<n/3 in the active (aka Byzantine) setting when the parties may deviate from the protocol.

I will survey a recent line of works that settles the round complexity of perfect-MPC with optimal security threshold for general functions. In particular, we show that 2 rounds are sufficient and necessary in the passive setting and 4 rounds are sufficient and necessary in the active setting.
Based on joint works with Zvika Brakerski, Eliran Kachlon, Arpita Ptra, and Rotem Tsabary. 
The talk will be over zoom --- connection information below.