[Resource Topic] 2019/646: Communication-Efficient Unconditional MPC with Guaranteed Output Delivery

Welcome to the resource topic for 2019/646

Title:
Communication-Efficient Unconditional MPC with Guaranteed Output Delivery

Authors: Vipul Goyal, Yanyi Liu, 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.

ePrint: https://eprint.iacr.org/2019/646

Talk: https://www.youtube.com/watch?v=X1GOKXc2G38

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .