Dishonest Majority Constant-Round MPC with Linear Communication from DDH
Vipul Goyal, NTT Research, Carnegie Mellon University
Junru Li, Tsinghua University
Ankit Kumar Misra, University of California, Los Angeles
Rafail Ostrovsky, University of California, Los Angeles
Yifan Song, Tsinghua University
Chenkai Weng, Arizona State University
Abstract
In this work, we study constant round multiparty computation (MPC) for Boolean circuits against a fully malicious adversary who may control up to out of parties. Without relying on fully homomorphic encryption (FHE), the best-known results in this setting are achieved by Wang et al. (CCS 2017) and Hazay et al. (ASIACRYPT 2017) based on garbled circuits, which require a quadratic communication in the number of parties . In contrast, for non-constant round MPC, the recent result by Rachuri and Scholl (CRYPTO 2022) has achieved linear communication .
In this work, we present the first concretely efficient constant round MPC protocol in this setting with linear communication in the number of parties . Our construction can be based on any public-key encryption scheme that is linearly homomorphic for public keys. Our work gives a concrete instantiation from a variant of the El-Gamal Encryption Scheme assuming the DDH assumption. The analysis shows that when the computational security parameter and statistical security parameter , our protocol achieves a smaller communication than Wang et al. (CCS 2017) when there are parties for AES circuit and parties for general Boolean circuits (where we assume that the numbers of AND gates and XOR gates are the same). When comparing with the recent work by Beck et al. (CCS 2023) that achieves constant communication complexity in the strong honest majority setting ( where is a constant), our protocol is better as long as (when for their work).
@misc{cryptoeprint:2024/1466,
author = {Vipul Goyal and Junru Li and Ankit Kumar Misra and Rafail Ostrovsky and Yifan Song and Chenkai Weng},
title = {Dishonest Majority Constant-Round {MPC} with Linear Communication from {DDH}},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1466},
year = {2024},
url = {https://eprint.iacr.org/2024/1466}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.