You are looking at a specific version 20210621:075512 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2021
Keywords
Multiparty ComputationInformation-theoretic CryptographyCommunication 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.