International Association for Cryptologic Research

International Association
for Cryptologic Research


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

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
Conference: CRYPTO 2021
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.
Video from CRYPTO 2021
  title={Unconditional Communication-Efficient MPC via Hall's Marriage Theorem},
  author={Vipul Goyal and Antigoni Polychroniadou and Yifan Song},