Welcome to the resource topic for 2023/307
Title:
SUPERPACK: Dishonest Majority MPC with Constant Online Communication
Authors: Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, Yifan Song, Chenkai Weng
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 0<\epsilon<1/2 and consider an adversary that corrupts t<n(1-\epsilon) out of n parties.
\textsc{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 (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 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 \emph{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 \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.
ePrint: https://eprint.iacr.org/2023/307
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .