### Communication-Efficient Unconditional MPC with Guaranteed Output Delivery

Vipul Goyal, Yanyi Liu, and Yifan Song

##### Abstract

We study the communication complexity of unconditionally secure MPC with guaranteed output delivery over point-to-point channels for corruption threshold $t < n/3$. We ask the question: “is it possible to construct MPC in this setting s.t. the communication complexity per multiplication gate is linear in the number of parties?” While a number of works have focused on reducing the communication complexity in this setting, the answer to the above question has remained elusive for over a decade. We resolve the above question in the affirmative by providing an MPC with communication complexity $O(Cn\kappa + n^3\kappa)$ where $\kappa$ is the size of an element in the field, $C$ is the size of the (arithmetic) circuit, and, $n$ is the number of parties. This represents a strict improvement over the previously best known communication complexity of $O(Cn\kappa+D_Mn^2\kappa+ n^3\kappa)$ where $D_M$ is the multiplicative depth of the circuit. To obtain this result, we introduce a novel technique called 4-consistent tuples of sharings which we believe to be of independent interest.

Available format(s)
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Keywords
Multiparty ComputationInformation-theoretic CryptographyCommunication Complexity
Contact author(s)
vipul @ cmu edu
yl2866 @ cornell edu
yifans2 @ andrew cmu edu
History
Short URL
https://ia.cr/2019/646

CC BY

BibTeX

@misc{cryptoeprint:2019/646,
author = {Vipul Goyal and Yanyi Liu and Yifan Song},
title = {Communication-Efficient Unconditional MPC with Guaranteed Output Delivery},
howpublished = {Cryptology ePrint Archive, Paper 2019/646},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/646}},
url = {https://eprint.iacr.org/2019/646}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.