Welcome to the resource topic for 2024/242
Title:
Perfectly-Secure MPC with Constant Online Communication Complexity
Authors: Yifan Song, Xiaxi Ye
Abstract:In this work, we study the communication complexity of perfectly secure MPC protocol with guaranteed output delivery against t=(n-1)/3 corruptions. The previously best-known result in this setting is due to Goyal, Liu, and Song (CRYPTO, 2019) which achieves O(n) communication per gate, where n is the number of parties.
On the other hand, in the honest majority setting, a recent trend in designing efficient MPC protocol is to rely on packed Shamir sharings to speed up the online phase. In particular, the work by Escudero et al. (CCS 2022) gives the first semi-honest protocol that achieves a constant communication overhead per gate across all parties in the online phase while maintaining overall O(n) communication per gate. We thus ask the following question: ``Is it possible to construct a perfectly secure MPC protocol with GOD such that the online communication per gate is O(1) while maintaining overall O(n) communication per gate?‘’
In this work, we give an affirmative answer by providing an MPC protocol with communication complexity O(|C|+\mathsf{Depth}\cdot n+n^5) elements for the online phase, and O(|C|\cdot n+\mathsf{Depth}\cdot n^2 + n^4) elements for the preprocessing phase, where |C| is the circuit size and \mathsf{Depth} is the circuit depth.
ePrint: https://eprint.iacr.org/2024/242
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 .