[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1007/978-3-031-15985-5_1guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing

Published: 15 August 2022 Publication History

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).

References

[1]
Abspoel M et al. Moriai S, Wang H, et al. Asymptotically good multiplicative LSSS over galois rings and applications to MPC over Z/pkZ Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 151-180
[2]
Bendlin R, Damgård I, Orlandi C, and Zakarias S Paterson KG Semi-homomorphic encryption and multiparty computation Advances in Cryptology – EUROCRYPT 2011 2011 Heidelberg Springer 169-188
[3]
Beaver D Feigenbaum J Efficient multiparty protocols using circuit randomization Advances in Cryptology — CRYPTO ’91 1992 Heidelberg Springer 420-432
[4]
Boyle E, Gilboa N, Ishai Y, and Nof A Moriai S and Wang H Efficient fully secure computation via distributed zero-knowledge proofs Advances in Cryptology – ASIACRYPT 2020 2020 Cham Springer 244-276
[5]
Boyle E, Gilboa N, Ishai Y, and Nof A Malkin T and Peikert C Sublinear GMW-style compiler for MPC with preprocessing Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 457-485
[6]
Beck G, Goel A, Jain A, and Kaptchuk G Canteaut A and Standaert F-X Order-C secure multiparty computation for highly repetitive circuits Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 663-693
[7]
Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 1–10. ACM (1988)
[8]
Cascudo I, Cramer R, Xing C, and Yuan C Shacham H and Boldyreva A Amortized complexity of information-theoretically secure MPC revisited Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 395-426
[9]
Chida K et al. Shacham H, Boldyreva A, et al. Fast large-scale honest-majority MPC for malicious adversaries Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 34-64
[10]
Couteau G Ishai Y and Rijmen V A note on the communication complexity of multiparty computation in the correlated randomness model Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 473-503
[11]
Cramer R, Rambaud M, and Xing C Malkin T and Peikert C Asymptotically-good arithmetic secret sharing over Z/pZ with strong multiplication and its applications to efficient MPC Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 656-686
[12]
Damgård I, Ishai Y, and Krøigaard M Gilbert H Perfectly secure multiparty computation and the computational overhead of cryptography Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 445-465
[13]
Damgård I and Nielsen JB Menezes A Scalable and unconditionally secure multiparty computation Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 572-590
[14]
Damgård I, Nielsen JB, Polychroniadou A, and Raskin M Robshaw M and Katz J On the communication required for unconditionally secure multiplication Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 459-488
[15]
Damgård I, Pastro V, Smart N, and Zakarias S Safavi-Naini R and Canetti R Multiparty computation from somewhat homomorphic encryption Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 643-662
[16]
Franklin, M., Yung, M.: Communication complexity of secure computation (Extended Abstract). In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC 1992, pp. 699–710. Association for Computing Machinery, New York (1992)
[17]
Genkin D, Ishai Y, and Polychroniadou A Gennaro R and Robshaw M Efficient multi-party computation: from passive to active security via secure SIMD circuits Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 721-741
[18]
Goyal V, Li H, Ostrovsky R, Polychroniadou A, and Song Y Malkin T and Peikert C ATLAS: efficient and scalable MPC in the honest majority setting Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 244-274
[19]
Goyal V, Polychroniadou A, and Song Y Malkin T and Peikert C Unconditional communication-efficient MPC via hall’s marriage theorem Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 275-304
[20]
Goyal, V., Polychroniadou, A., Song, Y.: Sharing transformation and dishonest majority MPC with packed secret sharing. Cryptology ePrint Archive (2022)
[21]
Gordon SD, Starin D, and Yerukhimovich A Canteaut A and Standaert F-X The more the merrier: reducing the cost of large scale MPC Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 694-723
[22]
Polychroniadou A and Song Y Canteaut A and Standaert F-X Constant-overhead unconditionally secure multiparty computation over binary fields Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 812-841
[23]
Shamir A How to share a secret Commun. ACM 1979 22 11 612-613

Cited By

View all

Index Terms

  1. Sharing Transformation and Dishonest Majority MPC with Packed Secret Sharing
      Index terms have been assigned to the content through auto-classification.

      Recommendations

      Comments

      Please enable JavaScript to view thecomments powered by Disqus.

      Information & Contributors

      Information

      Published In

      cover image Guide Proceedings
      Advances in Cryptology – CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV
      Aug 2022
      589 pages
      ISBN:978-3-031-15984-8
      DOI:10.1007/978-3-031-15985-5

      Publisher

      Springer-Verlag

      Berlin, Heidelberg

      Publication History

      Published: 15 August 2022

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 28 Jan 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2024)Perfectly-Secure MPC with Constant Online Communication ComplexityTheory of Cryptography10.1007/978-3-031-78023-3_11(329-361)Online publication date: 2-Dec-2024
      • (2024)Towards Achieving Asynchronous MPC with Linear Communication and Optimal ResilienceAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_6(170-206)Online publication date: 18-Aug-2024
      • (2024)Scalable Multiparty Computation from Non-linear Secret SharingAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68397-8_12(384-417)Online publication date: 18-Aug-2024
      • (2024)SPRINT: High-Throughput Robust Distributed Schnorr SignaturesAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_3(62-91)Online publication date: 26-May-2024
      • (2023)Experimenting with Zero-Knowledge Proofs of TrainingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623202(1880-1894)Online publication date: 15-Nov-2023
      • (2023)Linear Communication in Malicious Majority MPCProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623162(2173-2187)Online publication date: 15-Nov-2023
      • (2023)Scalable Multiparty GarblingProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623132(2158-2172)Online publication date: 15-Nov-2023

      View Options

      View options

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media