Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience

Vipul Goyal; Chen-Da Liu-Zhang; Yifan Song

Paper 2024/243

Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience

Vipul Goyal, NTT Research, Carnegie Mellon University

Chen-Da Liu-Zhang

, Lucerne University of Applied Sciences and Arts, Web3 Foundation

Yifan Song, Tsinghua University, Shanghai Qi Zhi Institute

Abstract

Secure multi-party computation (MPC) allows a set of $n$ parties to jointly compute a function over their private inputs. The seminal works of Ben-Or, Canetti and Goldreich [STOC '93] and Ben-Or, Kelmer and Rabin [PODC '94] settled the feasibility of MPC over asynchronous networks. Despite the significant line of work devoted to improving the communication complexity, current protocols with information-theoretic security and optimal resilience $t<n/3$ communicate $\Omega(n^4C)$ field elements for a circuit with $C$ multiplication gates. In contrast, synchronous MPC protocols with $O(nC)$ communication have long been known. In this work we make progress towards closing this gap. We provide a novel MPC protocol in the asynchronous setting with statistical security that makes black-box use of an asynchronous complete secret-sharing (ACSS) protocol. The cost per multiplication reduces to the cost of distributing a constant number of sharings via ACSS, improving a linear factor over the state of the art by Choudhury and Patra [IEEE Trans. Inf. Theory '17]. With a recent concurrent work achieving ACSS with linear cost per sharing, we achieve an MPC with ${O}(nC)$ communication and optimal resilience.

Note: Added a solution for asynchronous MPC with smaller field size.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in CRYPTO 2024
Keywords: Secure Multiparty Computation Information-theoretic Security Asynchronous Network Communication Complexity
Contact author(s): vipul @ cmu edu
chendaliu @ gmail com
yfsong @ mail tsinghua edu cn
History: 2024-07-10: last of 2 revisions; 2024-02-15: received; See all versions
Short URL: https://ia.cr/2024/243
License: CC BY

BibTeX

@misc{cryptoeprint:2024/243,
      author = {Vipul Goyal and Chen-Da Liu-Zhang and Yifan Song},
      title = {Towards Achieving Asynchronous {MPC} with Linear Communication and Optimal Resilience},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/243},
      year = {2024},
      url = {https://eprint.iacr.org/2024/243}
}