Paper 2020/1437

Round-Optimal and Communication-Efficient Multiparty Computation

Michele Ciampi
Rafail Ostrovsky
Hendrik Waldner
Vassilis Zikas

Typical approaches for minimizing the round complexity of multiparty computation (MPC) come at the cost of increased communication complexity (CC) or the 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 a 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 protocols that are secure against malicious adversaries in the plain model, which we present in this work. Concretely, our two main contributions are: 1) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-scalable maliciously secure MPC protocols in the plain model, assuming (succinct) FE combiners. 2) We provide a round-preserving black-box compiler that compiles a wide class of MPC protocols into circuit-independent— i.e., with a CC that depends only on the input-output length of the circuit—maliciously secure MPC protocols in the plain model, assuming Multi-Key Fully-Homomorphic Encryption (MFHE). Our constructions are based on a new compiler that turns a wide class of MPC protocols into k-delayed-input function MPC protocols (a notion we introduce), where the function that is being computed is specified only in the k-th round of the protocol. As immediate corollaries of our two compilers, we derive (1) the first round-optimal and circuit-scalable maliciously secure MPC protocol, and (2) the first round-optimal and circuit-independent maliciously secure MPC protocol in the plain model. The latter achieves the best to-date CC for a round-optimal maliciously secure MPC protocol. In fact, it is even communication-optimal when the output size of the function being evaluated is smaller than its input size (e.g., for boolean functions). All of our results are based on standard polynomial time assumptions.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
multiparty computation functional encryption fully homomorphic encryption communication efficient
Contact author(s)
michele ciampi @ ed ac uk
rafail @ cs ucla edu
hendrik waldner @ ed ac uk
vzikas @ cs purdue edu
2022-05-25: last of 2 revisions
2020-11-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Rafail Ostrovsky and Hendrik Waldner and Vassilis Zikas},
      title = {Round-Optimal and Communication-Efficient Multiparty Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1437},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.