On the Communication Complexity of Secure Computation

In this talk, we will discuss our recent lower bounds on the communication and round complexity of secure Multi-Party Computation (MPC) protocols. In the information theoretic setting, we show that protocols based on the traditional secret-sharing design paradigm cannot be significantly improved with respect to the round and communication complexity even in the preprocessing model. In the computational setting, we revisit the exact round complexity of two-party as well as multi-party computation protocols in the simultaneous message exchange model since there was no known lower bound in the multi-party setting without trusted setup. In particular, we establish a lower bound on the round complexity connected to the round complexity of non-malleable commitments.

This talk is based on joint works with Ivan Damgård, Jesper B. Nielsen, Michael Raskin and Sanjam Garg, Pratyay Mukherjee, Omkant Pandey