### TurboPack: Honest Majority MPC with Constant Online Communication

##### 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).

Available format(s)
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
See all versions
Short URL
https://ia.cr/2022/1316

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},
note = {\url{https://eprint.iacr.org/2022/1316}},
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.