Paper 2022/1316

TurboPack: Honest Majority MPC with Constant Online Communication

Daniel Escudero, J.P. Morgan AI Research
Vipul Goyal, NTT Research, Carnegie Mellon University
Antigoni Polychroniadou, J.P. Morgan AI Research
Yifan Song, Carnegie Mellon University
Abstract

We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires $12$ elements in total per multiplication gate with circuit-dependent preprocessing, or $20$ elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in $n$, the number of parties, with the best prior existing solution involving $1.5n$ elements per multiplication gate. Only one recent work (Goyal et al, CRYPTO'22) achieves constant online communication complexity, but the constants are large ($108$ elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties. The total end-to-end communication cost with the preprocessing phase is linear in $n$, i.e., $10n + 44$, which is larger than the $4n$ complexity of the state-of-the-art protocols. The gap is not significant when the online phase must be optimized as a priority and a reasonably large number of parties is involved. Unlike previous works based on packed secret-sharing to reduce communication complexity, we further reduce the communication by avoiding the use of complex and expensive network routing or permutations tools. Furthermore, we also allow for a maximal honest majority adversary, while most previous works require the set of honest parties to be strictly larger than a majority. Our protocol is simple and offers concrete efficiency. To illustrate this we present a full-fledged implementation together with experimental results that show improvements in online phase runtimes that go up to $5\times$ in certain settings (e.g. $45$ parties, LAN network, circuit of depth $10$ with $1$M gates).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. CCS'22
DOI
10.1145/3548606.3560633
Keywords
Secure Multiparty Computation Honest Majority Packed Secret-Sharing
Contact author(s)
daniel escudero @ protonmail com
vipul goyal @ gmail com
antigonipoly @ gmail com
yfsong1995 @ gmail com
History
2022-10-05: approved
2022-10-04: received
See all versions
Short URL
https://ia.cr/2022/1316
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1316,
      author = {Daniel Escudero and Vipul Goyal and Antigoni Polychroniadou and Yifan Song},
      title = {{TurboPack}: Honest Majority {MPC} with Constant Online Communication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1316},
      year = {2022},
      doi = {10.1145/3548606.3560633},
      url = {https://eprint.iacr.org/2022/1316}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.