Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / multiparty computation, functional encryption, fully homomorphic encryption, communication efficient

Date: received 15 Nov 2020, last revised 17 Nov 2020

Contact author: micheleciampi1990 at gmail com,rafail@cs ucla edu,hendrik waldner@ed ac uk,vzikas@inf ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20201117:115436 (All versions of this report)

Short URL: ia.cr/2020/1437


[ Cryptology ePrint archive ]