## CryptoDB

### Paper: Unconditional Communication-Efficient MPC via Hall's Marriage Theorem

Authors: Vipul Goyal , CMU and NTT Research Antigoni Polychroniadou , J.P. Morgan AI Research Yifan Song , Carnegie Mellon University DOI: 10.1007/978-3-030-84245-1_10 (login may be required) Search ePrint Search Google CRYPTO 2021 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.
##### BibTeX
@inproceedings{crypto-2021-31117,
title={Unconditional Communication-Efficient MPC via Hall's Marriage Theorem},
publisher={Springer-Verlag},
doi={10.1007/978-3-030-84245-1_10},
author={Vipul Goyal and Antigoni Polychroniadou and Yifan Song},
year=2021
}