Top

Published in:

2021 | OriginalPaper | Chapter

Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys

Authors : Jean-Philippe Bossuat, Christian Mouchet, Juan Troncoso-Pastoriza, Jean-Pierre Hubaux

Published in: Advances in Cryptology – EUROCRYPT 2021

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

We present a bootstrapping procedure for the full-RNS variant of the approximate homomorphic-encryption scheme of Cheon et al., CKKS (Asiacrypt 17, SAC 18). Compared to the previously proposed procedures (Eurocrypt 18 & 19, CT-RSA 20), our bootstrapping procedure is more precise, more efficient (in terms of CPU cost and number of consumed levels), and is more reliable and 128-bit-secure. Unlike the previous approaches, it does not require the use of sparse secret-keys. Therefore, to the best of our knowledge, this is the first procedure that enables a highly efficient and precise bootstrapping with a low probability of failure for parameters that are 128-bit-secure under the most recent attacks on sparse R-LWE secrets.

We achieve this efficiency and precision by introducing three novel contributions: (i) We propose a generic algorithm for homomorphic polynomial-evaluation that takes into account the approximate rescaling and is optimal in level consumption. (ii) We optimize the key-switch procedure and propose a new technique for linear transformations (double hoisting). (iii) We propose a systematic approach to parameterize the bootstrapping, including a precise way to assess its failure probability.

We implemented our improvements and bootstrapping procedure in the open-source Lattigo library. For example, bootstrapping a plaintext in \(\mathbb {C}^{32768}\) takes 18 s, has an output coefficient modulus of 505 bits, a mean precision of 19.1 bits, and a failure probability of \(2^{-15.58}\). Hence, we achieve 14.1\(\times \) improvement in bootstrapped throughput (plaintext-bit per second), with respect to the previous best results, and we have a failure probability 468\(\times \) smaller and ensure 128-bit security.

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 On the Ideal Shortest Vector Problem over Random Rational Primes

next chapter High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function

SwitchKey does not act directly in a ciphertext; instead, we define it as a generalized intermediate function used as a building block that takes a polynomial as input.

Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNetCrossRef

Albrecht, M., et al.: Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, November 2018

Bajard, J.-C., Eynard, J., Hasan, M.A., Zucca, V.: A full RNS variant of FV like somewhat homomorphic encryption schemes. In: Avanzi, R., Heys, H. (eds.) SAC 2016. LNCS, vol. 10532, pp. 423–442. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69453-5_23CrossRef

Bossuat, J.-P., et al.: Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys. Cryptology ePrint Archive, Report 2020/1203 (2020). https://eprint.iacr.org/2020/1203

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

Chen, H., Chillotti, I., Song, Y.: Improved bootstrapping for approximate homomorphic encryption. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 34–54. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_2CrossRef

Cheon, J.H., Han, K., Hhan, M.: Faster Homomorphic Discrete Fourier Transforms and Improved FHE Bootstrapping. IACR Cryptology ePrint Archive 2018/1073 (2018)

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: A full RNS variant of approximate homomorphic encryption. In: Cid, C., Jacobson, M. (eds.) SAC 2018. LNCS, vol. 11349, pp. 347–368. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-10970-7_16CrossRef

Cheon, J.H., et al.: A hybrid of dual and meet-in-the-middle attack on sparse and ternary secret LWE. IEEE Access 7, 89497–89506 (2019)CrossRef

10.

Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 360–384. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_14CrossRef

11.

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

12.

Curtis, B.R., Player, R.: On the feasibility and impact of standardising sparse-secret LWE parameter sets for homomorphic encryption. In: Proceedings of the 7th Workshop on Encrypted Computing and Applied Homomorphic Cryptography (2019)

13.

Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive 2012/144 (2012)

14.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 169–178 (2009)

15.

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

16.

Halevi, S., Polyakov, Y., Shoup, V.: An improved RNS variant of the BFV homomorphic encryption scheme. In: Matsui, M. (ed.) CT-RSA 2019. LNCS, vol. 11405, pp. 83–105. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12612-4_5CrossRef

17.

Halevi, S., Shoup, V.: Algorithms in HElib. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 554–571. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_31CrossRefMATH

18.

Halevi, S., Shoup, V.: Bootstrapping for HElib. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 641–670. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46800-5_25CrossRef

19.

Halevi, S., Shoup, V.: Faster homomorphic linear transformations in HElib. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 93–120. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_4CrossRefMATH

20.

Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 364–390. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40186-3_16CrossRef

21.

HEAAN. https://github.com/snucrypto/HEAAN

22.

Kim, A., Papadimitriou, A., Polyakov, Y.: Approximate Homomorphic Encryption with Reduced Approximation Error. Cryptology ePrint Archive, Report 2020/1118 (2020). https://eprint.iacr.org/2020/1118

23.

Kim, M., et al.: Ultra-fast homomorphic encryption models enable secure outsourcing of genotype imputation. bioRxiv (2020). https://doi.org/10.1101/2020.07.02.183459

24.

Lattigo 2.0.0. EPFL-LDS, September 2020. https://github.com/ldsec/lattigo

25.

Lee, J.-W., et al.: High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function. Cryptology ePrint Archive, Report 2020/552 (2020). https://eprint.iacr.org/2020/552. Accepted to Eurocrypt 2021

26.

Masters, O., et al.: Towards a Homomorphic Machine Learning Big Data Pipeline for the Financial Services Sector. IACR Cryptology ePrint Archive 2019/1113 (2019)

27.

Sav, S., et al.: POSEIDON: Privacy-Preserving Federated Neural Network Learning. arXiv preprint (2020). arXiv:2009.00349

28.

Microsoft SEAL (release 3.6). Microsoft Research, Redmond, WA, November 2020. https://github.com/Microsoft/SEAL

29.

Son, Y., Cheon, J.H.: Revisiting the Hybrid attack on sparse and ternary secret LWE. In: IACR Cryptology ePrint Archive 2019/1019 (2019)

30.

The Go Programming Language, September 2020. https://golang.org/

Title: Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys
Authors: Jean-Philippe Bossuat
Christian Mouchet
Juan Troncoso-Pastoriza
Jean-Pierre Hubaux
Publisher: Springer International Publishing
Book: Advances in Cryptology – EUROCRYPT 2021
Print ISBN: 978-3-030-77869-9

Electronic ISBN: 978-3-030-77870-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-77870-5_21

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