nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Compiling Low Depth Circuits for Practical Secure Computation

verfasst von : Niklas Buescher, Andreas Holzer, Alina Weber, Stefan Katzenbeisser

Erschienen in: Computer Security – ESORICS 2016

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

With the rise of practical Secure Multi-party Computation (MPC) protocols, compilers have been developed that create Boolean or Arithmetic circuits for MPC from functionality descriptions in a high-level language. Previous compilers focused on the creation of size-minimal circuits. However, many MPC protocols, such as GMW and SPDZ, have a round complexity that is dependent on the circuit’s depth. When deploying these protocols in real world network settings, with network latencies in the range of tens or hundreds of milliseconds, the round complexity quickly becomes a significant performance bottleneck.

In this work, we present ShallowCC, a compiler extension that creates depth minimized Boolean circuits from ANSI-C. We first introduce novel optimized building blocks that are up to 50 % shallower than previous constructions. Second, we present multiple high- and low-level depth minimization techniques and implement these in the existing CBMC-GC compiler. Our experiments show significant depth reductions over hand-optimized constructions (for some applications up to 2.5\(\times \)), while maintaining a circuit size that is competitive with size-minimizing compilers. Evaluating exemplary functionalities in a GMW framework, we show that depth reductions lead to significant speed-ups in any real-world network setting. For an exemplary biometric matching application we report a \(400\times \) speed-up in comparison with a circuit generated from a size-minimizing compiler.

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 Robust Password-Protected Secret Sharing

Nächstes Kapitel Secure Computation of MIPS Machine Code

Even though, MPC is often benchmarked in a LAN setting, the WAN setting is the more natural deployment model of MPC.

Full version available at http://www.seceng.de/people/buescher/.

Amini, M., Creusillet, B., Even, S., Keryell, R., Goubier, O., Guelton, S., McMahon, J.O., Pasquier, F.-X., Péan, G., Villalon, P.: Par4All: from convex array regions to heterogeneous computing. In: Workshop on Polyhedral Compilation Techniques (2012)

Ben-David, A., Nisan, N., Pinkas, B.: Fairplaymp: a system for secure multi-party computation. In: ACM CCS (2008)

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

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

Buchfuhrer, D., Umans, C.: The complexity of boolean formula minimization. J. Comput. System Sci. 77, 1 (2011)MathSciNetCrossRefMATH

Büscher, N., Katzenbeisser, S.: Faster secure computation through automatic parallelization. In: USENIX Security (2015)

Clarke, E., Kroning, D., Lerda, F.: A tool for checking ANSI-C programs. In: Jensen, K., Podelski, A. (eds.) TACAS 2004. LNCS, vol. 2988, pp. 168–176. Springer, Heidelberg (2004)CrossRef

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

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

10.

Demmler, D., Dessouky, G., Koushanfar, F., Sadeghi, A., Schneider, T., Zeitouni, S.: Automated synthesis of optimized circuits for secure computation. In: ACM CCS (2015)

11.

Demmler, D., Schneider, T., Zohner, M.: ABY - a framework for efficient mixed-protocol secure two-party computation. In: NDSS (2015)

12.

Earle, J.: Latched carry-save adder. IBM Techn. Discl. Bull. 7(10), 909–910 (1965)

13.

Erkin, Z., Franz, M., Guajardo, J., Katzenbeisser, S., Lagendijk, I., Toft, T.: Privacy-preserving face recognition. In: Goldberg, I., Atallah, M.J. (eds.) PETS 2009. LNCS, vol. 5672, pp. 235–253. Springer, Heidelberg (2009)CrossRef

14.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: ACM STOC (1987)

15.

Harris, D.: A taxonomy of parallel prefix networks. In: IEEE ASILOMAR (2003)

16.

Henecka, W., Kögl, S., Sadeghi, A., Schneider, T., Wehrenberg, I.: TASTY: tool for automating secure two-party computations. In: ACM CCS (2010)

17.

Holzer, A., Franz, M., Katzenbeisser, S., Veith, H.: Secure two-party computations in ANSI C. In: ACM CCS (2012)

18.

Keller, M., Scholl, P.: Efficient, oblivious data structures for MPC. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 506–525. Springer, Heidelberg (2014)

19.

Kolesnikov, V., Sadeghi, A.-R., Schneider, T.: Improved garbled circuit building blocks and applications to auctions and computing minima. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 1–20. Springer, Heidelberg (2009)CrossRef

20.

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, Part II. LNCS, vol. 5126, pp. 486–498. Springer, Heidelberg (2008)CrossRef

21.

Kreuter, B., Shelat, A., Mood, B., Butler, K.: PCF: A portable circuit format for scalable two-party secure computation. In: USENIX Security (2013)

22.

Kreuter, B., Shelat, A., Shen, C.: Billion-gate secure computation with malicious adversaries. In: USENIX Security (2012)

23.

Liu, C., Huang, Y., Shi, E., Katz, J., Hicks, M.W.: Automating efficient ram-model secure computation. In: IEEE S&P (2014)

24.

Liu, C., Wang, X.S., Nayak, K., Huang, Y., Shi, E.: Oblivm: a programming framework for secure computation. In: IEEE S&P (2015)

25.

Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: USENIX Security (2004)

26.

Mood, B., Gupta, D., Carter, H., Butler, K., Traynor, P.: Frigate: a validated, extensible, and efficient compiler and interpreter for secure computation. In: IEEE European Symposium on Security and Privacy (2016)

27.

Mood, B., Letaw, L., Butler, K.: Memory-efficient garbled circuit generation for mobile devices. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 254–268. Springer, Heidelberg (2012)

28.

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

29.

Paterson, M.S., Pippenger, N., Zwick, U.: Optimal carry save networks

30.

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

31.

Songhori, E.M., Hussain, S.U., Sadeghi, A., Schneider, T., Koushanfar, F.: Tinygarble: Highly compressed and scalable sequential garbled circuits. In: IEEE S&P (2015)

32.

Wallace, C.S.: A suggestion for a fast multiplier. IEEE Trans. Electron. Comput. 13(1), 14–17 (1964)CrossRefMATH

33.

Yao, AC.-C.: Protocols for secure computations (Extended Abstract). In: Annual Symposium on Foundations of Computer Science, FOCS 1982 (1982)

34.

Zahur, S., Evans, D.: Circuit structures for improving efficiency of security and privacy tools. In: IEEE S&P (2013)

35.

Zahur, S., Evans, D.: Obliv-c: a language for extensible data-oblivious computation. IACR Cryptology ePrint Archive 2015 (2015)

36.

Zhang, Y., Steele, A., Blanton, M.: PICCO: a general-purpose compiler for private distributed computation. In: ACM CCS (2013)

Titel: Compiling Low Depth Circuits for Practical Secure Computation
verfasst von: Niklas Buescher
Andreas Holzer
Alina Weber
Stefan Katzenbeisser
Verlag: Springer International Publishing
Buch: Computer Security – ESORICS 2016
Print ISBN: 978-3-319-45740-6

Electronic ISBN: 978-3-319-45741-3

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-45741-3_5

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"

Premium Partner