Cryptology ePrint Archive: Report 2021/834

Unconditional Communication-Efficient MPC via Hall's Marriage Theorem

Vipul Goyal and 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 $O(1)$ elements per gate.

Category / Keywords: cryptographic protocols / Multiparty Computation, Information-theoretic Cryptography, Communication Complexity

Original Publication (with major differences): IACR-CRYPTO-2021

Date: received 18 Jun 2021, last revised 1 Sep 2021

Contact author: goyal at cs cmu edu, antigonipoly at gmail com, yifans2 at andrew cmu edu

Available format(s): PDF | BibTeX Citation

Version: 20210902:002711 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]