CRC Seminar Series: Daniel Escudero

We present Turbopack (CCS 2022), 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 open-source implementation together with experimental results that show improvements in online phase runtimes that go up to 5X in certain settings (e.g. 45 parties, LAN network, circuit of depth 10 with 1M gates).

Finally, we also hint at Superpack (Eurocrypt 2023), which is a computationally secure protocol suitable for the setting where t<n*(1-eps), for any constant 0<eps<1. Superpack also achieves an online phase with O(|C|) communication. Note that, if 1/2<=eps<1, then there is an honest majority and Turbopack, which is information-theoretic secure and more lightweight, can be used. However, Superpack shines in the case in the dishonest majority case where 0<eps<1/2: prior dishonest majority works operate with only one honest party, and minor a few exceptions, no benefits are obtained by having more than one honest party; Superpack exploits the presence of a constant fraction of honest parties to enable O(|C|) communication in the online phase. We provide an open-source implementation and discuss concrete improvements through our extensive experiments.