nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Circuit Bootstrapping: Faster and Smaller

verfasst von : Ruida Wang, Yundi Wen, Zhihao Li, Xianhui Lu, Benqiang Wei, Kun Liu, Kunpeng Wang

Erschienen in: Advances in Cryptology – EUROCRYPT 2024

Verlag: Springer Nature Switzerland

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We present a novel circuit bootstrapping algorithm that outperforms the state-of-the-art TFHE method with 9.9\(\times \) speedup and 15.6\(\times \) key size reduction. These improvements can be attributed to two technical contributions. Firstly, we redesigned the circuit bootstrapping workflow to operate exclusively under the ring ciphertext type, which eliminates the need for conversion between LWE and RLWE ciphertexts. Secondly, we improve the LMKC+ blind rotation algorithm by reducing the number of automorphisms, then propose the first automorphism type multi-value functional bootstrapping. These automorphism-based techniques lead to further key size optimization, and are of independent interest besides circuit bootstrapping. Based on our new circuit bootstrapping we can evaluate AES-128 in 26.2 s (single thread), achieving 10.3\(\times \) speedup compared with the state-of-the-art TFHE-based approach.

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 Time-Lock Puzzles with Efficient Batch Solving

Nächstes Kapitel Registered Functional Encryptions from Pairings

Sample extraction is to extract LWE sample from RLWE, which is detailed in Sect. 2.4.

This results in a slight increase in circuit computation latency as we discussed in the full version of this paper [35], but allows for greater circuit depth and the batch processing of more ciphertexts at once (see TFHE horizontal/ vertical/mixed packing technology [11]).

They also propose a 4-minute variant without bootstrapping. However, it can not be used for transciphering since the ciphertext is too noisy to do further evaluation.

The parameters chosen for the TFHE circuit bootstrapping are listed in Table 6. Our new framework utilizes the parameter set \(\textsf{CMUX}_1\) recommended in Table 5.

LMKC+ has proposed an optimization to reduce the number of automorphisms by using additional storage. More details can be found in Sect. 4.2.

https://github.com/malb/lattice-estimator.

https://github.com/tfhe/experimental-tfhe.

We detailed this application scenario in the full version of this paper [35].

Al Badawi, A., et al.: Openfhe: open-source fully homomorphic encryption library. In: Proceedings of the 10th Workshop on Encrypted Computing and Applied Homomorphic Cryptography, pp. 53–63 (2022)

Alperin-Sheriff, J., Peikert, C.: Faster bootstrapping with polynomial error. In: Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology. CRYPTO 2014. LNCS, vol. 8616, pp. 297–314. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_17

Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology. CRYPTO 2012. LNCS, vol. 7417, pp. 868–886. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_50

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

Carpov, S., Izabachène, M., Mollimard, V.: New techniques for multi-value input homomorphic evaluation and applications. In: Matsui, M. (ed.) Topics in Cryptology, CT-RSA 2019. LNCS, vol. 11405, pp. 106–126. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_6

Chen, H., Dai, W., Kim, M., Song, Y.: Efficient homomorphic conversion between (ring) LWE ciphertexts. In: Sako, K., Tippenhauer, N.O. (eds.) Applied Cryptography and Network Security, ACNS 2021. LNCS, vol. 12726, pp. 460–479. Springer International Publishing, Cham (2021). https://doi.org/10.1007/978-3-030-78372-3_18

Cheon, J.H., et al.: Batch Fully Homomorphic Encryption over the Integers. In: Johansson, T., Nguyen, P.Q. (eds.) Advances in Cryptology. EUROCRYPT 2013. LNCS, vol. 7881, pp. 315–335. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-38348-9_20

Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology, ASIACRYPT 2017. LNCS, vol. 10624, pp. 409–437. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_15

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology. ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1

10.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: Takagi, T., Peyrin, T. (eds.) Advances in Cryptology, ASIACRYPT 2017. LNCS, vol. 10624, pp. 377–408. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_14

11.

Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption over the torus. J. Cryptol. 33(1), 34–91 (2020)

12.

Chillotti, I., Ligier, D., Orfila, J.-B., Tap, S.: Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In: Tibouchi, M., Wang, H. (eds.) Advances in Cryptology. ASIACRYPT 2021. LNCS, vol. 13092, pp. 670–699. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_23

13.

Coron, J.S., Lepoint, T., Tibouchi, M.: Coron, JS., Lepoint, T., Tibouchi, M.: Scale-invariant fully homomorphic encryption over the integers. In: Krawczyk, H. (ed.) Public-Key Cryptography. PKC 2014. LNCS, vol. 8383, pp. 311–328. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54631-0_18

14.

De Micheli, G., Kim, D., Micciancio, D., Suhl, A.: Faster amortized fhew bootstrapping using ring automorphisms. Cryptology ePrint Archive (2023)

15.

Doröz, Y., Hu, Y., Sunar, B.: Homomorphic aes evaluation using the modified ltv scheme. Des. Codes Crypt. 80, 333–358 (2016)MathSciNetCrossRef

16.

Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology. EUROCRYPT 2015. LNCS, vol. 9056, pp. 617–640. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_24

17.

Gama, N., Izabachène, M., Nguyen, P.Q., Xie, X.: Structural lattice reduction: generalized worst-case to average-case reductions and homomorphic Cryptosystems. In: Fischlin, M., Coron, J.-S. (eds.) Advances in Cryptology. EUROCRYPT 2016. LNCS, vol. 9666, pp. 528–558. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_19

18.

Gentry, C.: A Fully Homomorphic Encryption Scheme. Stanford University (2009)

19.

Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) Advances in Cryptology. CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_49

20.

Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology. CRYPTO 2013. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5

21.

Guimarães, A., Borin, E., Aranha, D.F.: Revisiting the functional bootstrap in TFHE. In: IACR Transactions on Cryptographic Hardware and Embedded Systems, pp. 229–253 (2021)

22.

James, F.: Monte carlo theory and practice. Rep. Prog. Phys. 43(9), 1145 (1980)CrossRef

23.

Kim, A., Lee, Y., Deryabin, M., Eom, J., Choi, R.: LFHE: fully homomorphic encryption with bootstrapping key size less than a megabyte. Cryptology ePrint Archive (2023)

24.

Lee, Y., et al.: Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology, EUROCRYPT 2023. LNCS, vol. 14006, pp. 227–256. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30620-4_8

25.

Liu, F.-H., Wang, H.: Batch bootstrapping I:: a new framework for SIMD bootstrapping in polynomial modulus. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology, EUROCRYPT 2023. LNCS, vol. 14006, pp. 321–352. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30620-4_11

26.

Liu, F.H., Wang, H.: Batch bootstrapping II: bootstrapping in polynomial modulus only requires o\(^{\sim }\)(1) fhe multiplications in amortization. In: Advances in Cryptology, EUROCRYPT 2023. LNCS, vol. 14006. pp. 353–384. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_12

27.

López-Alt, A., Tromer, E., Vaikuntanathan, V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the Forty-Fourth annual ACM Symposium on Theory of Computing, pp. 1219–1234 (2012)

28.

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) Advances in Cryptology, EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_1

29.

Matsuoka, K., Banno, R., Matsumoto, N., Sato, T., Bian, S.: Virtual secure platform: a five-stage pipeline processor over TFHE. In: USENIX Security Symposium, pp. 4007–4024 (2021)

30.

Micciancio, D., Polyakov, Y.: Bootstrapping in fhew-like cryptosystems. In: Proceedings of the 9th on Workshop on Encrypted Computing and Applied Homomorphic Cryptography, pp. 17–28 (2021)

31.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 1–40 (2009)MathSciNetCrossRef

32.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1–34:40 (2009)

33.

Trama, D., Clet, P.E., Boudguiga, A., Sirdey, R.: At last! a homomorphic aes evaluation in less than 30 seconds by means of tfhe. Cryptology ePrint Archive (2023)

34.

Van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (eds.) Advances in Cryptology, EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_2

35.

Wang, R., et al.: Circuit bootstrapping: faster and smaller. Cryptology ePrint Archive, Paper 2024/323 (2024). https://eprint.iacr.org/2024/323

Titel: Circuit Bootstrapping: Faster and Smaller
verfasst von: Ruida Wang
Yundi Wen
Zhihao Li
Xianhui Lu
Benqiang Wei
Kun Liu
Kunpeng Wang
Verlag: Springer Nature Switzerland
Buch: Advances in Cryptology – EUROCRYPT 2024
Print ISBN: 978-3-031-58722-1

Electronic ISBN: 978-3-031-58723-8

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-58723-8_12

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