Paper 2022/781

Linear Communication in Malicious Majority MPC

S. Dov Gordon, George Mason University
Phi Hung Le, George Mason University
Daniel McVicker, George Mason University
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)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.