Paper 2024/243
Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience
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 $\Omega(nC)$ communication have long been known. In this work we make progress towards closing this gap. We provide a novel MPC protocol that makes black-box use of an asynchronous complete secret-sharing (ACSS) protocol, where 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]. Instantiating ACSS with the protocol by Choudhury and Patra [J. Crypto '23] we achieve an MPC protocol with $\mathcal{O}(n^3C)$ communication. Moreover, with a recent concurrent work achieving ACSS with linear cost per sharing, we achieve an MPC with $\mathcal{O}(nC)$ communication.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2024
- Keywords
- Secure Multiparty ComputationInformation-theoretic SecurityAsynchronous NetworkCommunication Complexity
- Contact author(s)
-
vipul @ cmu edu
chendaliu @ gmail com
yfsong @ mail tsinghua edu cn - History
- 2024-05-26: revised
- 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}, note = {\url{https://eprint.iacr.org/2024/243}}, url = {https://eprint.iacr.org/2024/243} }