Paper 2022/831

Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing

Vipul Goyal, Carnegie Mellon University, NTT Research
Antigoni Polychroniadou, J.P. Morgan AI Research
Yifan Song, Carnegie Mellon University

In the last few years, the efficiency of secure multi-party computation (MPC) in the dishonest majority setting has increased by several orders of magnitudes starting with the SPDZ protocol family which offers a speedy information-theoretic online phase in the prepossessing model. However, state-of-the-art $n$-party MPC protocols in the dishonest majority setting incur online communication complexity per multiplication gate which is linear in the number of parties, i.e. $O(n)$, per gate across all parties. In this work, we construct the first MPC protocols in the preprocessing model for dishonest majority with sub-linear communication complexity per gate in the number of parties $n$. To achieve our results, we extend the use of packed secret sharing to the dishonest majority setting. For a constant fraction of corrupted parties (i.e. if 99 percent of the parties are corrupt), we can achieve a communication complexity of $O(1)$ field elements per multiplication gate across all parties. At the crux of our techniques lies a new technique called sharing transformation. The sharing transformation technique allows us to transform shares under one type of linear secret sharing scheme into another, and even perform arbitrary linear maps on the secrets of (packed) secret sharing schemes with optimal communication complexity. This technique can be of independent interest since transferring shares from one type of scheme into another (e.g., for degree reduction) is ubiquitous in MPC. Furthermore, we introduce what we call sparsely packed Shamir sharing which allows us to address the issue of network routing efficiently, and packed Beaver triples which is an extension of the widely used technique of Beaver triples for packed secret sharing (for dishonest majority).

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2022
Information-theoretic Security Communication Complexity Multiparty Computation
Contact author(s)
vipul @ cmu edu
antigonipoly @ gmail com
yifans2 @ andrew cmu edu
2022-06-27: approved
2022-06-23: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Vipul Goyal and Antigoni Polychroniadou and Yifan Song},
      title = {Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/831},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.