Top

Published in:

2019 | OriginalPaper | Chapter

Concrete Efficiency Improvements for Multiparty Garbling with an Honest Majority

Authors : Aner Ben-Efraim, Eran Omri

Published in: Progress in Cryptology – LATINCRYPT 2017

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

Secure multiparty computation is becoming a necessary component in many real-world systems. The efficiency of secure two-party protocols has improved tremendously in the last decade, making such protocols efficient enough for many real-world applications. Recently, much attention is being diverted to making secure multiparty computation (for more than two parties) truly practical as well. In particular, the last couple of years saw a resurgence of interest in constant round secure protocols, based on the multiparty garbling paradigm of Beaver et al. (STOC 1990). Such protocols generally offer improved performance in high latency networks, such as the internet.

In this paper we consider the case where a majority of the parties are honest, and construct highly efficient constant round protocols for both the semi-honest setting and the malicious setting. Our protocols in the semi-honest setting significantly improve over the recent multiparty garbling protocols for honest majority of Ben Efraim et al. (ACM CCS 2016), both in asymptotic complexity and in concrete running time.

In the malicious setting, we consider security with abort when assuming more than 2/3 of the parties are honest. We show that by assuming the existence of simple preprocessing primitives, which do not require knowledge of the computed function, we get malicious security at almost the same cost as semi-honest security. I.e., the function dependent preprocessing and the online phase are almost identical to the semi-honest setting.

We ran experiments to measure the effect of our optimizations and to show that our protocols compete with the state-of-the-art constant round protocols.

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 The Oblivious Machine

next chapter Homomorphic Rank Sort Using Surrogate Polynomials

This is to allow the garbled circuit to be revealed at the end of the offline phase.

Note that in our protocol, as well as in [24], this “share conversion” is done on multiplication of shares, so the resulting “shares” are not fully random. Nevertheless, they indeed sum to the secret, and the security is maintained by the masking.

An exception is [16] who used the outputs of PRGs for encrypting only, but they instead secret-shared 0’s of the same length using Shamir secret-sharing.

In fields of characteristic other than 2, party \(P_i\) computes the negation of the sum.

If there are redundant parties for interpolation, then these parties multiply by 0 instead.

We ignore NOT gates, as they can be eliminated by modifying the circuit, without enlarging the number of garbled gates.

We again assume that there are no NOT gates in the circuit.

This gives slightly less than 128 bits of security, see [2].

As mentioned, performing the reconstruction of the garbled circuit at the offline phase, before the inputs are given, requires assuming RO for proving security.

The work of [4] also presented the BGW protocols BGW2 and BGW3 along with their OT protocol. However, in their work they found that their OT protocol almost always significantly outperforms their BGW protocols for the same number of parties.

For fair comparison, we changed the code of [4] so only one party evaluates the circuit also there.

Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols. In: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing, STOC 1990, pp. 503–513. ACM, New York (1990). http://doi.acm.org/10.1145/100216.100287

Bellare, M., Hoang, V.T., Keelveedhi, S., Rogaway, P.: Efficient garbling from a fixed-key blockcipher. In: 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, 19–22 May 2013, pp. 478–492 (2013)

Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: Proceedings of the 15th ACM Conference on Computer and Communications Security, pp. 257–266. ACM (2008)

Ben-Efraim, A., Lindell, Y., Omri, E.: Optimizing semi-honest secure multiparty computation for the internet. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, 24–28 October 2016, pp. 578–590 (2016)

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 1–10 (1988)

Bertsekas, D., Özveren, C., Stamoulis, G., Tseng, P., Tsitsiklis, J.: Optimal communication algorithms for hypercubes. J. Parallel Distrib. Comput. 11(4), 263–275 (1991). http://www.sciencedirect.com/science/article/pii/0743731591900336CrossRef

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

Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03549-4_20CrossRef

Burkhart, M., Strasser, M., Many, D., Dimitropoulos, X.: SEPIA: privacy-preserving aggregation of multi-domain network events and statistics. Network 1, 101101 (2010)

10.

Chandran, N., Garay, J., Mohassel, P., Vusirikala, S.: Efficient, constant-round and actively secure MPC: beyond the three-party case. In: 24rd ACM Conference on Computer and Communications Security, CCS 2017. ACM (2017, to appear)

11.

Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 11–19 (1988)

12.

Choi, S.G., Hwang, K.-W., Katz, J., Malkin, T., Rubenstein, D.: Secure multi-party computation of boolean circuits with applications to privacy in on-line marketplaces. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 416–432. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27954-6_26CrossRefMATH

13.

Choi, S.G., Katz, J., Malozemoff, A.J., Zikas, V.: Efficient three-party computation from cut-and-choose. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8617, pp. 513–530. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44381-1_29CrossRef

14.

Cramer, R., Damgård, I., Ishai, Y.: Share conversion, pseudorandom secret-sharing and applications to secure computation. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 342–362. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_19CrossRef

15.

Damgård, I., Geisler, M., Krøigaard, M., Nielsen, J.B.: Asynchronous multiparty computation: theory and implementation. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 160–179. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00468-1_10CrossRef

16.

Damgård, I., Ishai, Y.: Constant-round multiparty computation using a black-box pseudorandom generator. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 378–394. Springer, Heidelberg (2005). https://doi.org/10.1007/11535218_23CrossRef

17.

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

18.

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

19.

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

20.

Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fast-track multiparty computations with applications to threshold cryptography. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1998, pp. 101–111. ACM (1998)

21.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the 19th ACM Symposium on the Theory of Computing, pp. 218–229 (1987)

22.

Gueron, S., Kounavis, M.E.: Efficient implementation of the galois counter mode using a carry-less multiplier and a fast reduction algorithm. Inf. Process. Lett. 110(14–15), 549–553 (2010)MathSciNetCrossRef

23.

Hazay, C., Scholl, P., Soria-Vazquez, E.: Low cost constant round MPC combining BMR and oblivious transfer. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 598–628. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_21CrossRef

24.

Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 294–304 (2000)

25.

Keller, M., Orsini, E., Rotaru, D., Scholl, P., Soria-Vazquez, E., Vivek, S.: Faster secure multi-party computation of AES and DES using lookup tables. In: Gollmann, D., Miyaji, A., Kikuchi, H. (eds.) ACNS 2017. LNCS, vol. 10355, pp. 229–249. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-61204-1_12CrossRef

26.

Keller, M., Orsini, E., Scholl, P.: MASCOT: faster malicious arithmetic secure computation with oblivious transfer. In: Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 830–842. ACM (2016)

27.

Kolesnikov, V., Schneider, T.: Improved garbled circuit: free XOR gates and applications. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70583-3_40CrossRefMATH

28.

Kreuter, B., Shelat, A., Shen, C.H.: Billion-gate secure computation with malicious adversaries. In: USENIX Security Symposium, pp. 285–300 (2012)

29.

Lindell, Y., Pinkas, B., Smart, N.P., Yanai, A.: Efficient constant round multi-party computation combining BMR and SPDZ. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 319–338. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48000-7_16CrossRef

30.

Lindell, Y., Riva, B.: Blazing fast 2PC in the offline/online setting with security for malicious adversaries. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 579–590. ACM, New York (2015). http://doi.acm.org/10.1145/2810103.2813666

31.

Lindell, Y., Smart, N.P., Soria-Vazquez, E.: More efficient constant-round multi-party computation from BMR and SHE. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9985, pp. 554–581. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53641-4_21CrossRef

32.

Malkhi, D., Nisan, N., Pinkas, B., Sella, Y., et al.: Fairplay-secure two-party computation system. In: USENIX Security Symposium, vol. 4, San Diego, CA, USA (2004)

33.

Mohassel, P., Rosulek, M., Zhang, Y.: Fast and secure three-party computation: the garbled circuit approach. In: Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 591–602. ACM, New York(2015). http://doi.acm.org/10.1145/2810103.2813705

34.

Nielsen, J.B., Orlandi, C.: LEGO for two-party secure computation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 368–386. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-00457-5_22CrossRef

35.

Nielsen, J.B., Schneider, T., Trifiletti, R.: Constant round maliciously secure 2PC with function-independent preprocessing using LEGO. In: Network and Distributed System Security Symposium, NDSS (2017)

36.

Pinkas, B., Schneider, T., Smart, N.P., Williams, S.C.: Secure two-party computation is practical. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 250–267. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_15CrossRef

37.

Schneider, T., Zohner, M.: GMW vs. Yao? Efficient secure two-party computation with low depth circuits. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 275–292. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39884-1_23CrossRef

38.

Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)MathSciNetCrossRef

39.

Wang, X., Ranellucci, S., Katz, J.: Authenticated garbling and efficient maliciously secure two-party computation. In: 24rd ACM Conference on Computer and Communications Security, CCS 2017. ACM (2017, to appear)

40.

Wang, X., Ranellucci, S., Katz, J.: Global-scale secure multiparty computation. In: 24rd ACM Conference on Computer and Communications Security, CCS 2017. ACM (2017, to appear)

41.

Yao, A.C.: Protocols for secure computations. In: Proceedings of the 23th IEEE Symposium on Foundations of Computer Science, pp. 160–164 (1982)

42.

Zahur, S., Rosulek, M., Evans, D.: Two halves make a whole - reducing data transfer in garbled circuits using half gates. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 220–250. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_8CrossRefMATH

Title: Concrete Efficiency Improvements for Multiparty Garbling with an Honest Majority
Authors: Aner Ben-Efraim
Eran Omri
Publisher: Springer International Publishing
Book: Progress in Cryptology – LATINCRYPT 2017
Print ISBN: 978-3-030-25282-3

Electronic ISBN: 978-3-030-25283-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-25283-0_16

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