Paper 2021/834 Original: eprint.iacr.org/2021/834 ↗
Unconditional Communication-Efficient MPC via Hall's Marriage Theorem
Abstract
The best known $n$ party unconditional multiparty computation protocols with an optimal corruption threshold communicates $O(n)$ field elements per gate. This has been the case even in the semi-honest setting despite over a decade of research on communication complexity in this setting. Going to the slightly sub-optimal corruption setting, the work of Damgard, Ishai, and Kroigaard (EUROCRYPT 2010) provided the first protocol for a single circuit achieving communication complexity of $O(\log|C|)$ elements per gate. While a number of works have improved upon this result, obtaining a protocol with $O(1)$ field elements per gate has been an open problem. In this work, we construct the first unconditional multi-party computation protocol evaluating a single arithmetic circuit with amortized communication complexity of $O(1)$ elements per gate.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2021-09-02: last updated
- 2021-06-21: published
- Short URL
- https://ia.cr/2021/834
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2021/834,
author = {Vipul Goyal and Antigoni Polychroniadou and Yifan Song},
title = {Unconditional Communication-Efficient MPC via Hall's Marriage Theorem},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/834},
year = {2021},
url = {https://eprint.iacr.org/2021/834}
}