Paper 2022/831
Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing
Abstract
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).
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- A major revision of an IACR publication in CRYPTO 2022
- Keywords
- Information-theoretic Security Communication Complexity Multiparty Computation
- Contact author(s)
-
vipul @ cmu edu
antigonipoly @ gmail com
yifans2 @ andrew cmu edu - History
- 2022-06-27: approved
- 2022-06-23: received
- See all versions
- Short URL
- https://ia.cr/2022/831
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2022/831, 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}, url = {https://eprint.iacr.org/2022/831} }