Welcome to the resource topic for 2022/781
Title:
Linear Communication in Malicious Majority MPC
Authors: S. Dov Gordon, Phi Hung Le, and Daniel McVicker
Abstract:The SPDZ multiparty computation protocol allows n parties to securely compute arithmetic circuits over a finite field, while tolerating up to n − 1 active corruptions. A line of work building upon SPDZ have made considerable improvements to the protocol’s performance, typically focusing on concrete efficiency. However, the communication complexity of each of these protocols is \Omega(n^2 |C|). In this paper, we present a protocol that achieves O(n|C|) communication. Our construction is very similar to those in the SPDZ family of protocols, but for one modular sub-routine for computing a verified sum. There are a handful of times in the SPDZ protocols in which the n parties wish to sum n public values. Rather than requiring each party to broadcast their input to all other parties, clearly it is cheaper to use some designated “dealer” to compute and broadcast the sum. In prior work, it was assumed that the cost of verifying the correctness of these sums is O(n^2 ), erasing the benefit of using a dealer. We show how to amortize this cost over the computation of multiple sums, resulting in linear communication complexity whenever the circuit size is |C| > n.
ePrint: https://eprint.iacr.org/2022/781
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 .