Paper 2022/781
Linear Communication in Malicious Majority MPC
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$.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Multiparty computation Dishonest majority Arithmetic circuits
- Contact author(s)
-
gordon @ gmu edu
ple13 @ gmu edu
dmcvicke @ gmu edu - History
- 2022-06-20: approved
- 2022-06-17: received
- See all versions
- Short URL
- https://ia.cr/2022/781
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/781, author = {S. Dov Gordon and Phi Hung Le and Daniel McVicker}, title = {Linear Communication in Malicious Majority {MPC}}, howpublished = {Cryptology {ePrint} Archive, Paper 2022/781}, year = {2022}, url = {https://eprint.iacr.org/2022/781} }