Welcome to the resource topic for 2024/243
Title:
Towards Achieving Asynchronous MPC with Linear Communication and Optimal Resilience
Authors: Vipul Goyal, Chen-Da Liu-Zhang, Yifan Song
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.
ePrint: https://eprint.iacr.org/2024/243
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .