SuperPack: Dishonest Majority MPC with Constant Online Communication

In this work we present a novel actively secure dishonest majority MPC protocol, SuperPack, whose efficiency improves as the number of honest parties increases. Concretely, let $0<\epsilon<1/2$ and consider an adversary that corrupts $t<n(1-\epsilon)$ out of $n$ parties. SuperPack requires $6/\epsilon$ field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and $10/\epsilon$ assuming circuit-independent preprocessing. In contrast, most of the previous works such as SPDZ (Damgrd et al, ESORICS 2013) and its derivatives perform the same regardless of whether there is only one honest party or a constant (non-majority) fraction of honest parties. A notable exception is due to Goyal et al (CRYPTO 2022), which achieves $58/\epsilon + 96/\epsilon^2$ field elements assuming circuit-independent preprocessing. Our work improves this result substantially by a factor of at least $25$ in the circuit-independent preprocessing model.

Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim *et al*, ACNS 2019), which achieves $2(1-\epsilon)n$ field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as $n$ grows, and as $\epsilon$ approaches $1/2$.
For example, if there are $90\%$ corruptions ($\epsilon=0.1$), with $n=50$ our online protocol is $1.5\times$ better than Turbospeedz and with $n=100$ this factor is $3\times$, but for $70\%$ corruptions ($\epsilon=0.3$) with $n=50$ our online protocol is $3.5\times$ better, and for $n=100$ this factor is $7\times$.

Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of $\approx \epsilon n/2$ smaller than these required by Le Mans (Rachuri and Scholl, CRYPTO 2022) leveraged to instantiate the preprocessing of Turbospeedz. 

Our dishonest majority protocol relies on packed secret-sharing and leverages ideas from the honest majority TurboPack (Escudero *et al*, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD.
We implement both SuperPack and Turbospeedz and verify with experimental results that our approach indeed leads to more competitive runtimes in distributed environments with a moderately large number of parties.