nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings

verfasst von : Mark Abspoel, Anders Dalskov, Daniel Escudero, Ariel Nof

Erschienen in: Applied Cryptography and Network Security

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Multiparty computation (MPC) over rings such as \(\mathbb {Z}_{2^{32}}\) or \(\mathbb {Z}_{2^{64}}\) has received a great deal of attention recently due to its ease of implementation and attractive performance. Several actively secure protocols over these rings have been implemented, for both the dishonest majority setting and the setting of three parties with one corruption. However, in the honest majority setting, no concretely efficient protocol for arithmetic computation over rings has yet been proposed that allows for an arbitrary number of parties.

We present a novel compiler for MPC over the ring \(\mathbb {Z}_{2^{k}}\) in the honest majority setting that turns a semi-honest protocol into an actively secure protocol with very little overhead. The communication cost per multiplication is only twice that of the semi-honest protocol, making the resultant actively secure protocol almost as fast.

To demonstrate the efficiency of our compiler, we implement both an optimized 3-party variant (based on replicated secret-sharing), as well as a protocol for n parties (based on a recent protocol from TCC 2019). For the 3-party variant, we obtain a protocol which outperforms the previous state of the art that we can experimentally compare against. Our n-party variant is the first implementation for this particular setting, and we show that it performs comparably to the current state of the art over fields.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel LLVM-Based Circuit Compilation for Practical Secure Computation

Nächstes Kapitel Experimental Review of the IKK Query Recovery Attack: Assumptions, Recovery Rate and Improvements

This reduction uses the identity \(x\cdot y = a2^n+b\equiv a+b\bmod 2^n-1\) for some a, b. However this requires computing and storing the product \(x\cdot y\) without overflow.

If all the shares \([\![x ]\!]_{\ell }\) are even then these shares may be written as \([\![x ]\!]_{\ell } = 2\cdot [\![y ]\!]_{\ell }\), which, by the homomorphism property, are shares of \(2\cdot y\). Since these are shares of x as well, this shows that \(x\equiv _{\ell } 2\cdot y\), so x is even.

Although attacks in previous gates may be carried out on both multiplications, the idea is here is to fix \(x_{i}\) which is shared by \([\![x_{i} ]\!]_{k+s}\) at the current value on the wire, and then given the randomized sharing \([\![x_{i'} ]\!]_{k+s}\), define \(\epsilon _{i}=x_{i'}-r\cdot x_{i}\) as the accumulated error on the input wire.

Technically, an element of R is a residue class modulo the ideal (h(X)), but we omit this for simplicity of notation.

Over fields this can be a general Vandermonde matrix, but this is not sufficient over R.

In general, any R-linear code with good distance and dimension suffices to get O(n) complexity in the protocol, but the Vandermonde construction is optimal.

We may just use \((\beta _{1}, \dots , \beta _{n}) = (\alpha _{1}, \dots , \alpha _{n})\).

Depending on the privacy threshold the constraints may fully determine the shares.

Indeed, while a multiplication in \({\mathbb {Z}}_{2^{64}}\) is one unsigned 64-bit multiplication, a multiplication on 128-bit types compile to three \({\mathbb {Z}}_{2^{64}}\) multiplications. That the overhead is less than \(\times 3\) can be attributed to the compiler being able to easier vectorize 64-bit multiplications in the \({\mathbb {Z}}_{2^{128}}\) case.

We thank the authors of [21] for giving us the tikzcode of their graph, as well as their raw experimental data which allows us to make a fair comparison in this section.

Fast large-scale honest-majority MPC for malicious adversaries (2017). https://github.com/cryptobiu/MPCHonestMajorityNoTriples

Abspoel, M., Cramer, R., Damgård, I., Escudero, D., Yuan, C.: Efficient information-theoretic secure multiparty computation over \(\mathbb{Z}/p^k\mathbb{Z}\) via Galois rings. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11891, pp. 471–501. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36030-6_19CrossRef

Araki, T., et al.: Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier, pp. 843–862 (2017)

Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority, pp. 805–817 (2016)

Beerliová-Trubíniová, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 305–328. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_16CrossRef

Ben-Sasson, E., Fehr, S., Ostrovsky, R.: Near-linear unconditionally-secure multiparty computation with a dishonest minority. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 663–680. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_39CrossRef

Bogdanov, D., Laur, S., Willemson, J.: Sharemind: a framework for fast privacy-preserving computations. In: Jajodia, S., Lopez, J. (eds.) ESORICS 2008. LNCS, vol. 5283, pp. 192–206. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-88313-5_13CrossRef

Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., Ishai, Y.: Zero-knowledge proofs on secret-shared data via fully linear PCPs. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 67–97. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_3CrossRef

Boyle, E., Gilboa, N., Ishai, Y., Nof, A.: Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs, pp. 869–886 (2019)

10.

Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)MathSciNetCrossRef

11.

Cascudo, I., Cramer, R., Xing, C., Yuan, C.: Amortized complexity of information-theoretically secure MPC revisited. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 395–426. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_14CrossRef

12.

Catrina, O., de Hoogh, S.: Improved primitives for secure multiparty integer computation. In: Garay, J.A., De Prisco, R. (eds.) SCN 2010. LNCS, vol. 6280, pp. 182–199. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15317-4_13CrossRefMATH

13.

Chaudhari, H., Choudhury, A., Patra, A., Suresh, A.: ASTRA: high throughput 3PC over rings with application to secure prediction. In: Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop, CCSW@CCS 2019, London, UK, November 11, 2019, pp. 81–92 (2019)

14.

Chida, K., et al.: Fast large-scale honest-majority MPC for malicious adversaries. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 34–64. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96878-0_2CrossRef

15.

Cramer, R., Damgård, I., Escudero, D., Scholl, P., Xing, C.: SPD\(\mathbb{Z}_{2^k}\): efficient MPC mod \(2^k\) for dishonest majority. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 769–798. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_26CrossRef

16.

Dalskov, A.P.K., Escudero, D., Keller, M.: Secure evaluation of quantized neural networks, vol. 2020, no. 4, pp. 355–375 (2020)

17.

Damgård, I., Escudero, D., Frederiksen, T.K., Keller, M., Scholl, P., Volgushev, N.: New primitives for actively-secure MPC over rings with applications to private machine learning, pp. 1102–1120 (2019)

18.

Damgård, I., Keller, M., Larraia, E., Pastro, V., Scholl, P., Smart, N.P.: Practical covertly secure MPC for dishonest majority – or: breaking the SPDZ limits. In: Crampton, J., Jajodia, S., Mayes, K. (eds.) ESORICS 2013. LNCS, vol. 8134, pp. 1–18. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40203-6_1CrossRef

19.

Damgård, I., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572–590. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_32CrossRef

20.

Damgård, I., Orlandi, C., Simkin, M.: Yet another compiler for active security or: efficient MPC over arbitrary rings. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 799–829. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_27CrossRef

21.

Eerikson, H., Keller, M., Orlandi, C., Pullonen, P., Puura, J., Simkin, M.: Use your brain! Arithmetic 3PC for any modulus with active security, pp. 5:1–5:24 (2020)

22.

Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 225–255. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_8CrossRef

23.

Genkin, D., Ishai, Y., Polychroniadou, A.: Efficient multi-party computation: from passive to active security via secure SIMD circuits. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 721–741. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_35CrossRef

24.

Genkin, D., Ishai, Y., Prabhakaran, M., Sahai, A., Tromer, E.: Circuits resilient to additive attacks with applications to secure computation, pp. 495–504 (2014)

25.

Goldreich, O.: Foundations of Cryptography: Basic Applications, vol. 2. Cambridge University Press, Cambridge (2004)CrossRef

26.

Goldwasser, S., Lindell, Y.: Secure multi-party computation without agreement. J. Cryptol. 18(3), 247–287 (2005)MathSciNetCrossRef

27.

Goyal, V., Liu, Y., Song, Y.: Communication-efficient unconditional MPC with guaranteed output delivery. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 85–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26951-7_4CrossRef

28.

Goyal, V., Song, Y., Zhu, C.: Guaranteed output delivery comes free in honest majority MPC. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 618–646. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_22CrossRef

29.

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer, pp. 830–842 (2016)

30.

Kikuchi, R., et al.: Field extension in secret-shared form and its applications to efficient secure computation. In: Jang-Jaccard, J., Guo, F. (eds.) ACISP 2019. LNCS, vol. 11547, pp. 343–361. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-21548-4_19CrossRef

31.

Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority, pp. 259–276 (2017)

32.

Mohassel, P., Rindal, P.: ABY\(^3\): a mixed protocol framework for machine learning, pp. 35–52 (2018)

33.

Nordholt, P.S., Veeningen, M.: Minimising communication in honest-majority MPC by batchwise multiplication verification. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 321–339. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93387-0_17CrossRef

34.

Patra, A., Suresh, A.: BLAZE: blazing fast privacy-preserving machine learning (2020)

Titel: An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings
verfasst von: Mark Abspoel
Anders Dalskov
Daniel Escudero
Ariel Nof
Verlag: Springer International Publishing
Buch: Applied Cryptography and Network Security
Print ISBN: 978-3-030-78374-7

Electronic ISBN: 978-3-030-78375-4

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-78375-4_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"