Paper 2023/307

SUPERPACK: Dishonest Majority MPC with Constant Online Communication

Abstract

In this work we present a novel actively secure dishonest majority MPC protocol, \textsc{SuperPack}, whose efficiency improves as the number of \emph{honest} parties increases. Concretely, let $$ and consider an adversary that corrupts $$ out of $$ parties. \textsc{SuperPack} requires $$ field elements of online communication per multiplication gate across all parties, assuming circuit-dependent preprocessing, and $$ assuming circuit-independent preprocessing. In contrast, most of the previous works such as SPDZ (Damg\aa rd \emph{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 \emph{et al} (CRYPTO 2022), which achieves $$ field elements assuming circuit-independent preprocessing. Our work improves this result substantially by a factor of at least $$ in the circuit-independent preprocessing model. Practically, we also compare our work with the best concretely efficient online protocol Turbospeedz (Ben-Efraim \emph{et al}, ACNS 2019), which achieves $$ field elements per multiplication gate among all parties. Our online protocol improves over Turbospeedz as $$ grows, and as $$ approaches $$. For example, if there are $$ corruptions ($$), with $$ our online protocol is $$ better than Turbospeedz and with $$ this factor is $$, but for $$ corruptions ($$) with $$ our online protocol is $$ better, and for $$ this factor is $$. Our circuit-dependent preprocessing can be instantiated from OLE/VOLE. The amount of OLE/VOLE correlations required in our work is a factor of $$ 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 \textsc{TurboPack} (Escudero \emph{et al}, CCS 2022) protocol to achieve concrete efficiency for any circuit topology, not only SIMD. We implement both \textsc{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.