nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

LLVM-Based Circuit Compilation for Practical Secure Computation

verfasst von : Tim Heldmann, Thomas Schneider, Oleksandr Tkachenko, Christian Weinert, Hossein Yalame

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

Multi-party computation (MPC) allows two or more parties to jointly and securely compute functions over private inputs. Cryptographic protocols that realize MPC require functions to be expressed as Boolean or arithmetic circuits. Deriving such circuits is either done manually, or with hardware synthesis tools and specialized MPC compilers. Unfortunately, such existing tools compile only from a single front-end language and neglect decades of research for optimizing regular compilers.

In this paper, we make MPC practical for developers by automating circuit compilation based on the compiler toolchain LLVM. For this, we develop an LLVM optimizer suite consisting of multiple transform passes that operate on the LLVM intermediate representation (IR) and gradually lower functions to circuit level. Our approach supports various front-end languages (currently C, C++, and Fortran) and takes advantage of powerful source code optimizations built into LLVM. We furthermore make sure to produce circuits that are optimized for MPC, and even offer fully automated post-processing for efficient post-quantum MPC.

We empirically measure the quality of our compilation results and compare them to the state-of-the-art specialized MPC compiler HyCC (Büscher et al. CCS’2018). For all benchmarked HyCC example applications (e.g., biomatch and linear equation solving), our highly generalizable approach achieves similar quality in terms of gate count and composition.

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 Privacy-Preserving Data Aggregation with Probabilistic Range Validation

Nächstes Kapitel An Efficient Passive-to-Active Compiler for Honest-Majority MPC over Rings

Nur mit Berechtigung zugänglich

ABC: A system for sequential synthesis and verification. http://www.eecs.berkeley.edu/~alanmi/abc/

Aly, A., et al.: SCALE-MAMBA v1. 10: Documentation (2020)

Archer, D., et al.: Bristol Fashion MPC circuits (2020). https://homes.esat.kuleuven.be/~nsmart/MPC/

Barrio, P., Carruth, C., Molloy, J.: Recursion inlining in LLVM (2015). https://www.llvm.org/devmtg/2015-04/slides/recursion-inlining-2015.pdf

Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: STOC (1990)

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

Boemer, F., Cammarota, R., Demmler, D., Schneider, T., Yalame, H.: MP2ML: a mixed-protocol machine learning framework for private inference. In: ARES (2020)

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

Boston University: JIFF: JavaScript implementation of federated functionalities (2015). https://github.com/multiparty/jiff/

10.

Boyar, J., Damgård, I., Peralta, R.: Short non-interactive cryptographic proofs. J. Cryptol. 13, 449–472 (2000)

11.

Braun, L., Demmler, D., Schneider, T., Tkachenko, O.: MOTION - A framework for mixed-protocol multi-party computation. ePrint (2020). https://ia.cr/2020/1137

12.

Büscher, N., et al.: Secure two-party computation in a quantum world. In: Conti, M., Zhou, J., Casalicchio, E., Spognardi, A. (eds.) ACNS 2020. LNCS, vol. 12146, pp. 461–480. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57808-4_23CrossRef

13.

Büscher, N., Demmler, D., Katzenbeisser, S., Kretzmer, D., Schneider, T.: HyCC: compilation of hybrid protocols for practical secure computation. In: CCS (2018)

14.

Chandran, N., Gupta, D., Rastogi, A., Sharma, R., Tripathi, S.: EzPC: programmable, efficient, and scalable secure two-party computation for machine learning. In: EuroS&P (2019)

15.

Clarke, E., Kroening, 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). https://doi.org/10.1007/978-3-540-24730-2_15CrossRefMATH

16.

Coussy, P., Morawiec, A.: High-Level Synthesis: From Algorithm to Digital Circuit. Springer, Dordrecht (2008). https://doi.org/10.1007/978-1-4020-8588-8

17.

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

18.

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

19.

Dessouky, G., Koushanfar, F., Sadeghi, A.R., Schneider, T., Zeitouni, S., Zohner, M.: Pushing the communication barrier in secure computation using lookup tables. In: NDSS (2017)

20.

Fereidooni, H., et al.: SAFELearn: secure aggregation for private federated learning. In: Deep Learning and Security Workshop (2021)

21.

Fowler, D., Robson, E.: Square root approximations in old Babylonian mathematics: YBC 7289 in context. Historia Mathematica (1998)

22.

Fraser, C.W., Hanson, D.R.: A Retargetable C Compiler: Design and Implementation. Addison-Wesley (1995)

23.

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

24.

Gueron, S., Lindell, Y., Nof, A., Pinkas, B.: Fast garbling of circuits under standard assumptions. In: CCS, pp. 567–578. ACM (2015)

25.

Hastings, M., Hemenway, B., Noble, D., Zdancewic, S.: SoK: general purpose compilers for secure multi-party computation. In: S&P (2019)

26.

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

27.

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

28.

Huang, Y., Evans, D., Katz, J.: Private set intersection: are garbled circuits better than custom protocols? In: NDSS (2012)

29.

Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: USENIX Security (2011)

30.

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9CrossRef

31.

Ishaq, M., Milanova, A.L., Zikas, V.: Efficient MPC via program analysis: a framework for efficient optimal mixing. In: CCS (2019)

32.

Javadi, M., Yalame, H., Mahdiani, H.: Small constant mean-error imprecise adder/multiplier for efficient VLSI implementation of MAC-based applications. IEEE Trans. Comput. (2020)

33.

Keller, M.: MP-SPDZ: a versatile framework for multi-party computation. In: CCS (2020)

34.

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). https://doi.org/10.1007/978-3-642-10433-6_1CrossRefMATH

35.

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

36.

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

37.

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

38.

Lattner, C., Adve, V.S.: LLVM: a compilation framework for lifelong program analysis & transformation. In: Code Generation and Optimization (2004)

39.

LLVM Community: CIRCT / Circuit IR compilers and tools (2020). https://github.com/llvm/circt

40.

LLVM Project: LLVM’s analysis and transform passes (2020). https://llvm.org/docs/Passes.html

41.

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

42.

Mantel, H., Scheidel, L., Schneider, T., Weber, A., Weinert, C., Weißmantel, T.: RiCaSi: rigorous cache side channel mitigation via selective circuit compilation. In: Krenn, S., Shulman, H., Vaudenay, S. (eds.) CANS 2020. LNCS, vol. 12579, pp. 505–525. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65411-5_25CrossRef

43.

Mohassel, P., Rindal, P.: ABY3: a mixed protocol framework for machine learning. In: CCS (2018)

44.

Mood, B., Gupta, D., Carter, H., Butler, K.R.B., Traynor, P.: Frigate: a validated, extensible, and efficient compiler and interpreter for secure computation. In: Euro S&P (2016)

45.

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). https://doi.org/10.1007/978-3-642-32946-3_19CrossRef

46.

Nguyen, T.D., et al.: FLGUARD: secure and private federated learning. ePrint (2021). https://ia.cr/2021/025

47.

Nielsen, J.D., Schwartzbach, M.I.: A domain-specific programming language for secure multiparty computation. In: Workshop on Programming Languages and Analysis for Security (2007)

48.

Patra, A., Schneider, T., Suresh, A., Yalame, H.: ABY2.0: improved mixed-protocol secure two-party computation. In: USENIX Security (2020)

49.

Pinkas, B., Rosulek, M., Trieu, N., Yanai, A.: PSI from PaXoS: fast, malicious private set intersection. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12106, pp. 739–767. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_25CrossRef

50.

Rastogi, A., Hammer, M.A., Hicks, M.: Wysteria: a programming language for generic, mixed-mode multiparty computations. In: S&P (2014)

51.

Robertson, J.E.: A new class of digital division methods. Trans. Electron. Comput. (1958)

52.

Rotaru, D.: awesome-mpc (2020). https://github.com/rdragos/awesome-mpc#frameworks

53.

Rugina, R., Rinard, M.: Recursion unrolling for divide and conquer programs. In: Midkiff, S.P., et al. (eds.) LCPC 2000. LNCS, vol. 2017, pp. 34–48. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45574-4_3CrossRefMATH

54.

Schoenmakers, B.: MPyC: secure multiparty computation in Python (2018). https://github.com/lschoe/mpyc/blob/master/README.md

55.

Schropfer, A., Kerschbaum, F., Muller, G.: L1 - an intermediate language for mixed-protocol secure computation. In: Computer Software and Applications Conference (2011)

56.

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

57.

Synopsis: DC Ultra (2020). https://www.synopsys.com/implementation-and-signoff/rtl-synthesis-test/dc-ultra.html

58.

Tatsuoka, M., et al.: Physically aware high level synthesis design flow. In: DAC (2015)

59.

Tillich, S., Smart, N.: (Bristol Format) Circuits of basic functions suitable for MPC and FHE (2020). https://homes.esat.kuleuven.be/~nsmart/MPC/old-circuits.html

60.

Verilog.com: Verilog Resources (2020). https://verilog.com/

61.

Wang, X., Malozemoff, A.J., Katz, J.: EMP-toolkit: Efficient multiparty computation toolkit (2016). https://github.com/emp-toolkit

62.

Wolf, C.: Yosys open synthesis suite. http://www.clifford.at/yosys/

63.

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

64.

Zahur, S., Evans, D.: Obliv-C: a language for extensible data-oblivious computation. ePrint (2015). https://ia.cr/2015/1153

65.

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

66.

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

Titel: LLVM-Based Circuit Compilation for Practical Secure Computation
verfasst von: Tim Heldmann
Thomas Schneider
Oleksandr Tkachenko
Christian Weinert
Hossein Yalame
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_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"