## TFHE: fast fully homomorphic encryption over the torus.(English)Zbl 1455.94141

Summary: This work describes a fast fully homomorphic encryption scheme over the torus (TFHE) that revisits, generalizes and improves the fully homomorphic encryption (FHE) based on GSW and its ring variants. The simplest FHE schemes consist in bootstrapped binary gates. In this gate bootstrapping mode, we show that the scheme FHEW of L. Ducas and D. Micciancio [Eurocrypt 2015, Lect. Notes Comput. Sci. 9056, 617–640 (2015; Zbl 1370.94509)] can be expressed only in terms of external product between a GSW and an LWE ciphertext. As a consequence of this result and of other optimizations, we decrease the running time of their bootstrapping from 690 to 13 ms single core, using 16 MB bootstrapping key instead of 1 GB, and preserving the security parameter. In leveled homomorphic mode, we propose two methods to manipulate packed data, in order to decrease the ciphertext expansion and to optimize the evaluation of lookup tables and arbitrary functions in RingGSW-based homomorphic schemes. We also extend the automata logic, introduced in [N. Gama et al., Eurocrypt 2016, Lect. Notes Comput. Sci. 9666, 528–558 (2016; Zbl 1371.94635)], to the efficient leveled evaluation of weighted automata, and present a new homomorphic counter called TBSR, that supports all the elementary operations that occur in a multiplication. These improvements speed up the evaluation of most arithmetic functions in a packed leveled mode, with a noise overhead that remains additive. We finally present a new circuit bootstrapping that converts LWE ciphertexts into low-noise RingGSW ciphertexts in just 137 ms, which makes the leveled mode of TFHE composable and which is fast enough to speed up arithmetic functions, compared to the gate bootstrapping approach. Finally, we provide an alternative practical analysis of LWE based schemes, which directly relates the security parameter to the error rate of LWE and the entropy of the LWE secret key, and we propose concrete parameter sets and timing comparison for all our constructions.

### MSC:

 94A60 Cryptography

### Citations:

Zbl 1370.94509; Zbl 1371.94635

### Software:

TFHE; FFTW; HElib; BKZ; GitHub; FHEW
Full Text:

### References:

 [1] M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, V. Vaikuntanathan, Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, (November 2018) [2] Albrecht, Martin R., On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL, Lecture Notes in Computer Science, 103-129 (2017), Cham: Springer International Publishing, Cham · Zbl 1415.94402 [3] Albrecht, Mr; Cid, C.; Faugère, J.; Fitzpatrick, R.; Perret, L., On the complexity of the BKW algorithm on LWE, Designs, Codes and Cryptography, 74, 2, 325-354 (2015) · Zbl 1331.94051 [4] M. R. Albrecht, B. R. Curtis, A. Deo, A. Davidson, R. Player, E. Postlethwaite, F. Virdia, T. Wunderer, Estimate all the $$\{$$ LWE, NTRU $$\}$$ schemes. https://estimate-all-the-lwe-ntru-schemes.github.io/docs, (2017) · Zbl 06957562 [5] M. R. Albrecht, A. Deo, Large modulus ring-lwe $$>=$$ module-lwe, in ASIACRYPT 2017, 2017 · Zbl 1420.94033 [6] Albrecht, Mr; Player, R.; Scott, S., On the concrete hardness of learning with errors, J. Mathematical Cryptology, 9, 3, 169-203 (2015) · Zbl 1352.94023 [7] E. Alkim, L. Ducas, T. Pöppelmann, P. Schwabe, Post-quantum key exchange - A new hope, in 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, pp. 327-343, 2016 [8] Alperin-Sheriff, Jacob; Peikert, Chris, Faster Bootstrapping with Polynomial Error, Advances in Cryptology - CRYPTO 2014, 297-314 (2014), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1336.94034 [9] J.-C. Bajard, J. Eynard, A. Hasan, V. Zucca, A full rns variant of fv like somewhat homomorphic encryption schemes, in SAC 2016, volume 10532 of LNCS, pp. 423-442, 2016 · Zbl 1418.94029 [10] D. Benarroch, Z. Brakerski, T. Lepoint, Fhe over the integers: Decomposed and batched in the post-quantum regime. Cryptology ePrint Archive, 2017/065 · Zbl 1400.94118 [11] Blum, A.; Kalai, A.; Wasserman, H., Noise-tolerant learning, the parity problem, and the statistical query model, J. of ACM, 50, 4, 506-519 (2003) · Zbl 1325.68114 [12] Z. Brakerski, C. Gentry, V. Vaikuntanathan, (leveled) fully homomorphic encryption without bootstrapping, in ITCS, pp. 309-325, 2012 · Zbl 1347.68120 [13] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, D.Stehlé, Classical hardness of learning with errors, in Proc. of 45th STOC, pp. 575-584 (ACM, 2013) · Zbl 1293.68159 [14] Z. Brakerski, R. Perlman, Lattice-based fully dynamic multi-key FHE with short ciphertexts, in Crypto’2016, volume 9814, pp. 190-213, 2016 · Zbl 1351.94029 [15] Z. Brakerski, V. Vaikuntanathan, Lattice-based FHE as secure as PKE, in ITCS, pp. 1-12, 2014 · Zbl 1364.94528 [16] Buchsbaum, Al; Giancarlo, R.; Westbrook, Jr, On the determinization of weighted finite automata, SIAM Journal on Computing, 30, 5, 1502-1531 (2000) · Zbl 0980.68065 [17] Chen, Yuanmi; Nguyen, Phong Q., BKZ 2.0: Better Lattice Security Estimates, Lecture Notes in Computer Science, 1-20 (2011), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1227.94037 [18] Cheon, Jung Hee; Coron, Jean-Sébastien; Kim, Jinsu; Lee, Moon Sung; Lepoint, Tancrède; Tibouchi, Mehdi; Yun, Aaram, Batch Fully Homomorphic Encryption over the Integers, Advances in Cryptology - EUROCRYPT 2013, 315-335 (2013), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1306.94040 [19] Cheon, Jung Hee; Han, Kyoohyung; Kim, Andrey; Kim, Miran; Song, Yongsoo, A Full RNS Variant of Approximate Homomorphic Encryption, Selected Areas in Cryptography - SAC 2018, 347-368 (2019), Cham: Springer International Publishing, Cham · Zbl 1447.94026 [20] J. H. Cheon, A. Kim, M. Kim, Y. Song, Homomorphic encryption for arithmetic of approximate numbers, in Asiacrypt 2017, 2016. http://eprint.iacr.org/2016/421 · Zbl 1420.94051 [21] J. H. Cheon, D. Stehlé, Fully homomophic encryption over the integers revisited, in EUROCRYPT 2015 (Springer, 2015), pp. 513-536 · Zbl 1370.94496 [22] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds, in Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I (Springer, 2016), pp. 3-33 · Zbl 1384.94044 [23] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, A homomorphic lwe based e-voting scheme, in PQ Cryptography (Springer, 2016), pp. 245-265 · Zbl 1405.81024 [24] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE, in Advances in Cryptology - ASIACRYPT 2017 (Springer, 2017) · Zbl 1420.94052 [25] I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, TFHE: Fast fully homomorphic encryption library. https://tfhe.github.io/tfhe/ (August 2016) · Zbl 1384.94044 [26] Coron, Jean-Sébastien; Lepoint, Tancrède; Tibouchi, Mehdi, Scale-Invariant Fully Homomorphic Encryption over the Integers, Public-Key Cryptography - PKC 2014, 311-328 (2014), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1335.94041 [27] R. Cramer, L. Ducas, B. Wesolowski, Short stickelberger class relations and application to ideal-svp, in Eurocrypt 2017, 2016 · Zbl 1411.94057 [28] M. Droste, P. Gastin, Weighted automata and weighted logics, in Handbook of weighted automata (Springer, 2009), pp. 175-211 · Zbl 1084.03036 [29] L. Ducas, D. Micciancio, FHEW: Bootstrapping homomorphic encryption in less than a second, in Eurocrypt, pp. 617-640, 2015 · Zbl 1370.94509 [30] Frigo, M.; Johnson, S. G., The Design and Implementation of FFTW3, Proceedings of the IEEE, 93, 2, 216-231 (2005) [31] N. Gama, M. Izabachène, P. Q. Nguyen, X. Xie, Structural lattice reduction: Generalized worst-case to average-case reductions. ePrint Archive, 2014/283, 2016 · Zbl 1371.94635 [32] N. Gama, P. Q. Nguyen, Predicting Lattice Reduction, in Eurocrypt, 2008 · Zbl 1149.94314 [33] C. Gentry, Fully homomorphic encryption using ideal lattices, in STOC, 2009 · Zbl 1304.94059 [34] C. Gentry, A. Sahai, B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, in Crypto’13, 2013 · Zbl 1310.94148 [35] Gorbunov, S.; Vaikuntanathan, V.; Wee, H., Attribute-based encryption for circuits, Journal of the ACM (JACM), 62, 6, 45 (2015) · Zbl 1426.68082 [36] S. Halevi, I. V. Shoup, Helib - an implementation of homomorphic encryption. https://github.com/shaih/HElib/ (September 2014) · Zbl 1343.94061 [37] Halevi, Shai; Shoup, Victor, Algorithms in HElib, Advances in Cryptology - CRYPTO 2014, 554-571 (2014), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1343.94061 [38] N. Howgrave-Graham, Approximate integer common divisors, in CaLC, volume 1 (Springer, 2001), pp. 51-66 · Zbl 1006.94528 [39] Langlois, A.; Stehlé, D., Worst-case to average-case reductions for module lattices, Designs, Codes and Cryptography, 75, 3, 565-599 (2015) · Zbl 1361.94043 [40] M. Liu, P. Q. Nguyen, Solving bdd by enumeration: An update, in Proc. of CT-RSA, volume 7779 of LNCS (Springer, 2013), pp. 293-309 · Zbl 1312.94070 [41] Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded, On Ideal Lattices and Learning with Errors over Rings, Advances in Cryptology - EUROCRYPT 2010, 1-23 (2010), Berlin, Heidelberg: Springer Berlin Heidelberg, Berlin, Heidelberg · Zbl 1279.94099 [42] Micciancio, D., On the hardness of learning with errors with binary secrets, Theory of Computing, 14, 1, 1-17 (2018) · Zbl 1412.68072 [43] D. Micciancio, C. Peikert, Trapdoors for lattices: Simpler, tighter, faster, smaller, in Eurocrypt ’12, LNCS (Springer, 2012) · Zbl 1297.94090 [44] D. Micciancio, M. Walter, Practical, predictable lattice basis reduction, in Proc. of Eurocrypt 2016, volume 9665 of LNCS (Springer, 2016), pp. 820-849 · Zbl 1385.94062 [45] A. I. R. V. of the BFV Homomorphic Encryption Scheme. Shai halevi and yuriy polyakov and victor shoup. In CT-RSA 2019, volume 11405 of LNCS (Springer, 2019), pp. 83-105 [46] M. A. R. Hiromasa, T. Okamoto, Packing messages and optimizing bootstrapping in gsw-fhe, in PKC ’15, pp. 699-715, 2015 · Zbl 1345.94068 [47] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in STOC, pp. 84-93, 2005 · Zbl 1192.94106 [48] N. Smart, F. Vercauteren, Fully homomorphic simd operations. Cryptology ePrint Archive, Report 2011/133, 2011. https://eprint.iacr.org/2011/133 · Zbl 1323.94140 [49] N. P. Smart, F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes, in Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings, pp. 420-443, 2010 · Zbl 1281.94055 [50] Smart, Np; Vercauteren, F., Fully homomorphic SIMD operations, Des. Codes Cryptography, 71, 1, 57-81 (2014) · Zbl 1323.94140 [51] D. Stehlé, R. Steinfeld, K. Tanaka, K. Xagawa, Efficient public key encryption based on ideal lattices, in Advances in Cryptology - ASIACRYPT 2009, 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings, pp. 617-635, 2009 · Zbl 1267.94132 [52] M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully homomorphic encryption over the integers, in Eurocrypt, pp. 24-43, 2010 · Zbl 1279.94130
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.