International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Dishonest Majority Constant-Round MPC with Linear Communication from DDH

Authors:
Vipul Goyal , NTT Research and 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 and Shanghai Qi Zhi Institute
Chenkai Weng , Arizona State University
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: In this work, we study constant round multiparty computation (MPC) for Boolean circuits against a fully malicious adversary who may control up to $n-1$ out of $n$ 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 $O(|C|\cdot n^2)$. In contrast, for non-constant round MPC, the recent result by Rachuri and Scholl (CRYPTO 2022) has achieved linear communication $O(|C|\cdot n)$. In this work, we present the first concretely efficient constant round MPC protocol in this setting with linear communication in the number of parties $O(|C|\cdot n)$. 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 $\lambda=128$ and statistical security parameter $\kappa=80$, our protocol achieves a smaller communication than Wang et al. (CCS 2017) when there are $16$ parties for AES circuit, and $8$ 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 $O(|C|)$ in the strong honest majority setting ($t<(1/2-\epsilon)n$ where $\epsilon$ is a constant), our protocol is better as long as $n<3500$ (when $t=n/4$ for their work).
BibTeX
@inproceedings{asiacrypt-2024-34700,
  title={Dishonest Majority Constant-Round MPC with Linear Communication from DDH},
  publisher={Springer-Verlag},
  author={Vipul Goyal and Junru Li and Ankit Kumar Misra and Rafail Ostrovsky and Yifan Song and Chenkai Weng},
  year=2024
}