Paper 2019/646

Communication-Efficient Unconditional MPC with Guaranteed Output Delivery

Vipul Goyal, Yanyi Liu, and Yifan Song


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)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2019
Multiparty ComputationInformation-theoretic CryptographyCommunication Complexity
Contact author(s)
vipul @ cmu edu
yl2866 @ cornell edu
yifans2 @ andrew cmu edu
2019-06-04: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.