Paper 2020/189

Guaranteed Output Delivery Comes Free in Honest Majority MPC

Vipul Goyal, Yifan Song, and Chenzhi Zhu


We study the communication complexity of unconditionally secure MPC with guaranteed output delivery over point-to-point channels for corruption threshold t < n/2, assuming the existence of a public broadcast channel. 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 until now. We also focus on the concrete communication complexity of evaluating each multiplication gate. We resolve the above question in the affirmative by providing an MPC with communication complexity O(Cn\phi) bits (ignoring fixed terms which are independent of the circuit) where \phi is the length of an element in the field, C is the size of the (arithmetic) circuit, n is the number of parties. This is the first construction where the asymptotic communication complexity matches the best-known semi-honest protocol. This represents a strict improvement over the previously best-known communication complexity of O(C(n\phi+\kappa)+D_Mn^2\kappa) bits, where \kappa is the security parameter and D_M is the multiplicative depth of the circuit. Furthermore, the concrete communication complexity per multiplication gate is 5.5 field elements per party in the best case and 7.5 field elements in the worst case when one or more corrupted parties have been identified. This also roughly matches the best-known semi-honest protocol, which requires 5.5 field elements per gate.

Available format(s)
Publication info
Preprint. MINOR revision.
Multiparty ComputationInformation-theoretic CryptographyCommunication Complexity
Contact author(s)
vipul @ cmu edu
yifans2 @ andrew cmu edu
mrbrtpt @ gmail com
2020-02-18: received
Short URL
Creative Commons Attribution


      author = {Vipul Goyal and Yifan Song and Chenzhi Zhu},
      title = {Guaranteed Output Delivery Comes Free in Honest Majority MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2020/189},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.