## CryptoDB

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

Authors: Vipul Goyal Yanyi Liu Yifan Song DOI: 10.1007/978-3-030-26951-7_4 Search ePrint Search Google 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.
##### BibTeX
@article{crypto-2019-29883,
title={Communication-Efficient Unconditional MPC with Guaranteed Output Delivery},
booktitle={Advances in Cryptology – CRYPTO 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11693},
pages={85-114},
doi={10.1007/978-3-030-26951-7_4},
author={Vipul Goyal and Yanyi Liu and Yifan Song},
year=2019
}