Paper 2023/307

SUPERPACK: Dishonest Majority MPC with Constant Online Communication

Daniel Escudero, J.P. Morgan AI Research
Vipul Goyal, NTT Research
Antigoni Polychroniadou, J.P. Morgan AI Research
Yifan Song, Tsinghua University
Chenkai Weng, Northwestern University

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
MPCDishonest majorityConstant CommunicationConcrete EfficiencyPacked Secret-Sharing
Contact author(s)
daniel escudero @ protonmail com
vipul goyal @ gmail com
antigonipoly @ gmail com
yfsong1995 @ gmail com
chenkaiweng2024 @ u northwestern edu
2023-05-03: revised
2023-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Daniel Escudero and Vipul Goyal and Antigoni Polychroniadou and Yifan Song and Chenkai Weng},
      title = {SUPERPACK: Dishonest Majority MPC with Constant Online Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2023/307},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.