Paper 2022/1316

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 $$ elements in total per multiplication gate with circuit-dependent preprocessing, or $$ elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in $$, the number of parties, with the best prior existing solution involving $$ elements per multiplication gate. Only one recent work (Goyal et al, CRYPTO'22) achieves constant online communication complexity, but the constants are large ($$ 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 $$, i.e., $$, which is larger than the $$ 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 $$ in certain settings (e.g. $$ parties, LAN network, circuit of depth $$ with $$M gates).