Paper 2019/200

Degree 2 is Complete for the Round-Complexity of Malicious MPC

Benny Applebaum, Zvika Brakerski, and Rotem Tsabary

Abstract

We show, via a non-interactive reduction, that the existence of a secure multi-party computation (MPC) protocol for degree-$2$ functions implies the existence of a protocol with the same round complexity for general functions. Thus showing that when considering the round complexity of MPC, it is sufficient to consider very simple functions. Our completeness theorem applies in various settings: information theoretic and computational, fully malicious and malicious with various types of aborts. In fact, we give a master theorem from which all individual settings follow as direct corollaries. Our basic transformation does not require any additional assumptions and incurs communication and computation blow-up which is polynomial in the number of players and in $S,2^D$, where $S,D$ are the circuit size and depth of the function to be computed. Using one-way functions as an additional assumption, the exponential dependence on the depth can be removed. As a consequence, we are able to push the envelope on the state of the art in various settings of MPC, including the following cases. * $3$-round perfectly-secure protocol (with guaranteed output delivery) against an active adversary that corrupts less than a quarter of the parties. * $2$-round statistically-secure protocol that achieves security with ``selective abort'' against an active adversary that corrupts less than half of the parties. * Assuming one-way functions, $2$-round computationally-secure protocol that achieves security with (standard) abort against an active adversary that corrupts less than half of the parties. This gives a new and conceptually simpler proof to the recent result of Ananth et al. (Crypto 2018). Technically, our non-interactive reduction draws from the encoding method of Applebaum, Brakerski and Tsabary (TCC 2018). We extend these methods to ones that can be meaningfully analyzed even in the presence of malicious adversaries.