Communication-Efficient Unconditional MPC with Guaranteed Output Delivery

Vipul Goyal; Yanyi Liu; Yifan Song

Paper 2019/646

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 . 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 where is the size of an element in the field, is the size of the (arithmetic) circuit, and, is the number of parties. This represents a strict improvement over the previously best known communication complexity of where 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A minor revision of an IACR publication in CRYPTO 2019
Keywords: Multiparty Computation Information-theoretic Cryptography Communication Complexity
Contact author(s): vipul @ cmu edu
yl2866 @ cornell edu
yifans2 @ andrew cmu edu
History: 2019-06-04: received
Short URL: https://ia.cr/2019/646
License: 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},
      url = {https://eprint.iacr.org/2019/646}
}