Unconditional Communication-Efficient MPC via Hall's Marriage Theorem

Vipul Goyal; Antigoni Polychroniadou; Yifan Song

Paper 2021/834

Unconditional Communication-Efficient MPC via Hall's Marriage Theorem

Vipul Goyal, Antigoni Polychroniadou, and Yifan Song

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 elements per gate.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in CRYPTO 2021
Keywords: Multiparty Computation Information-theoretic Cryptography Communication Complexity
Contact author(s): goyal @ cs cmu edu
antigonipoly @ gmail com
yifans2 @ andrew cmu edu
History: 2021-09-02: revised; 2021-06-21: received; See all versions
Short URL: https://ia.cr/2021/834
License: CC BY

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}
}