Paper 2020/1437

Round-Optimal and Communication-Efficient Multiparty Computation

Michele Ciampi and Rafail Ostrovsky and Hendrik Waldner and Vassilis Zikas

Abstract

Typical approaches for minimizing the round complexity of multi-party computation (MPC) do so at the cost of increased communication complexity (CC) or reliance on setup assumptions. A notable exception is the recent work of Ananth et al. [TCC 2019], which used Functional Encryption (FE) combiners to obtain a round optimal (two-round) semi-honest MPC in the plain model with CC proportional to the depth and input-output length of the circuit being computed---we refer to such protocols as circuit scalable. This leaves open the question of obtaining communication efficient malicious security in the plain model which we answer in this work: 1) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into a circuit-scalable maliciously secure MPC in the plain model, assuming a (succinct) FE combiner. By using our compiler with a round-optimal MPC, we derive the first round-optimal and circuit-scalable maliciously secure MPC in the plain model. 2) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into a circuit-independent---i.e., with CC that depends only on the input-output length of the circuit---maliciously secure MPC in the plain model, assuming Multi-Key Fully-Homomorphic Encryption (MFHE). Again, by using this second compiler with a round-optimal MPC, we derive the first round-optimal and circuit-independent maliciously secure MPC in the plain model. This is the best to-date CC for a round-optimal malicious MPC protocol, which is even communication-optimal when the output size of the function being evaluated is smaller than its input size (e.g., for boolean functions). Our compilers assume the existence of four-round maliciously secure oblivious transfer which can be obtained from standard cryptographic assumptions.