Top

Published in:

2022 | OriginalPaper | Chapter

Secure Multiparty Computation with Sublinear Preprocessing

Authors : Elette Boyle, Niv Gilboa, Yuval Ishai, Ariel Nof

Published in: Advances in Cryptology – EUROCRYPT 2022

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A common technique for enhancing the efficiency of secure multiparty computation (MPC) with dishonest majority is via preprocessing: In an offline phase, parties engage in an input-independent protocol to securely generate correlated randomness. Once inputs are known, the correlated randomness is consumed by a “non-cryptographic” and highly efficient online protocol.

The correlated randomness in such protocols traditionally comes in two flavors: multiplication triples (Beaver, Crypto ’91), which suffice for security against semi-honest parties, and authenticated multiplication triples (Bendlin et al., Eurocrypt ’11, Damgård et al., Crypto ’12) that yield efficient protocols against malicious parties.

Recent constructions of pseudorandom correlation generators (Boyle et al., Crypto ’19, ’20) enable concretely efficient secure generation of multiplication triples with sublinear communication complexity. However, these techniques do not efficiently apply to authenticated triples, except in the case of secure two-party computation of arithmetic circuits over large fields.

In this work, we propose the first concretely efficient approach for (malicious) MPC with preprocessing in which the offline communication is sublinear in the circuit size. More specifically, the offline communication scales with the square root of the circuit size.

From a feasibility point of view, our protocols can make use of any secure protocol for generating (unauthenticated) multiplication triples together with any additive homomorphic encryption. We propose concretely efficient instantiations (based on strong but plausible “linear-only” assumptions) from existing homomorphic encryption schemes and pseudorandom correlation generators.

Our technique is based on a variant of a recent protocol of Boyle et al. (Crypto ’21) for MPC with preprocessing. As a result, our protocols inherit the succinct correlated randomness feature of the latter protocol.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Secure Multiparty Computation with Free Branching

next chapter Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties

This can be formalized by requiring the existence of alternative correlated randomness, which is computationally indistinguishable from the one generated by the offline protocol, and given which the entire protocol is information-theoretically secure.

While these limitations can in some cases be circumvented [9, 25, 40], this comes at a big additional cost.

Implied, e.g., by any of the Quadratic Residuosity, Learning with Errors, or Decisional Composite Residuosity assumptions.

Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34CrossRef

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: STOC (1988)

Bendlin, R., Damgård, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 169–188. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20465-4_11CrossRef

Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Theory of Cryptography Conference, pp. 315–333 (2013)

Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation with constant communication overhead using multiplication embeddings. In: Chakraborty, D., Iwata, T. (eds.) Progress in Cryptology - INDOCRYPT, vol. 11356 of Lecture Notes in Computer Science, pp. 375–398 (2018)

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

Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Lattice-based SNARGs and their application to more efficient obfuscation. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 247–277 (2017)

Boyle, E., et al.: Efficient two-round OT extension and silent non-interactive secure computation. In: ACM CCS (2019)

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators: silent OT extension and more. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 489–518. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_16CrossRef

10.

Boyle, E., Couteau, G., Gilboa, N., Ishai, Y., Kohl, L., Scholl, P.: Efficient pseudorandom correlation generators from Ring-LPN. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 387–416. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_14CrossRef

11.

Boyle, E., Gilboa, N., Ishai, Y.: Secure computation with preprocessing via function secret sharing. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11891, pp. 341–371. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-36030-6_14CrossRef

12.

Boyle, E., Gilboa, N., Ishai, Y., Nof, A.: Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs. In: ACM CCS (2019)

13.

Boyle, E., Gilboa, N., Ishai, Y., Nof, A.: Efficient fully secure computation via distributed zero-knowledge proofs. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12493, pp. 244–276. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_9CrossRef

14.

Boyle, E., Gilboa, N., Ishai, Y., Nof, A.: Sublinear GMW-Style compiler for MPC with preprocessing. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12826, pp. 457–485. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84245-1_16CrossRef

15.

Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory (TOCT) 6(3), 1–36 (2014)MathSciNetCrossRef

16.

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

17.

Catalano, D., Raimondo, M.D., Fiore, D., Giacomelli, I.: Monz2ka: fast maliciously secure two party computation on z2k. IACR Cryptology ePrint Archive (2019)

18.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols (extended abstract). In: STOC (1988)

19.

Cohen, J.D., Fischer, M.J.: A robust and verifiable cryptographically secure election scheme (extended abstract). In: FOCS 1985, pp. 372–382 (1985)

20.

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

21.

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

22.

Damgård, I., Nielsen, J.B., Nielsen, M., Ranellucci, S.: The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 167–187. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63688-7_6CrossRef

23.

Damgård, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_38CrossRef

24.

Damgård, I., Zakarias, S.: Constant-overhead secure computation of Boolean circuits using preprocessing. In: TCC (2013)

25.

Abram, D., Scholl, P.: Low-communication multiparty triple generation for SPDZ from ring-LPN. In: PKC 2022 (2022)

26.

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

27.

Goldreich, O.: The Foundations of Cryptography - volume 2, Basic Applications. Cambridge University Press (2004)

28.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987)

29.

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRef

30.

Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T., Nicolosi, A.A.: Efficient RSA key generation and threshold Paillier in the two-party setting. J. Cryptol. 32(2), 265–323 (2019)MathSciNetCrossRef

31.

Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600–620. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_34CrossRefMATH

32.

Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Sufficient conditions for collision-resistant hashing. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 445–456. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_24CrossRef

33.

Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.P.: GAZELLE: A low latency framework for secure neural network inference. In: USENIX Security 2018, pp. 1651–1669 (2018)

34.

Katz, J., Yung, M.: Threshold cryptosystems based on factoring. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 192–205 (2002)

35.

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: ACM CCS (2016)

36.

Keller, M., Pastro, V., Rotaru, D.: Overdrive: making SPDZ great again. In: EUROCRYPT (2018). https://doi.org/10.1007/978-3-319-78372-7_6

37.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: ACM STOC, pp. 723–732 (1992)

38.

Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: ACM STOC, pp. 590–599 (2001)

39.

Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_40CrossRef

40.

Orlandi, C., Scholl, P., Yakoubov, S.: The rise of Paillier: homomorphic secret sharing and public-key silent OT. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 678–708. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_24CrossRef

41.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 223–238 (1999)

42.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC 2005, pp. 84–93 (2005)

43.

Shoup, V.: Arithmetic software libraries. https://www.shoup.net/papers/akl-chapter.pdf

44.

Yao, A.C.: How to generate and exchange secrets (extended abstract). In: FOCS (1986)

Title: Secure Multiparty Computation with Sublinear Preprocessing
Authors: Elette Boyle
Niv Gilboa
Yuval Ishai
Ariel Nof
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2022
Print ISBN: 978-3-031-06943-7

Electronic ISBN: 978-3-031-06944-4

Copyright Year: 2022
DOI: https://doi.org/10.1007/978-3-031-06944-4_15

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner