Bootstrapping fully homomorphic encryption over the integers in less than one second. (English) Zbl 1479.94242
Garay, Juan A. (ed.), Public-key cryptography – PKC 2021. 24th IACR international conference on practice and theory of public key cryptography, virtual event, May 10–13, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12710, 331-359 (2021).
Summary: One can bootstrap LWE-based fully homomorphic encryption (FHE) schemes in less than one second, but bootstrapping AGCD-based FHE schemes, also known as FHE over the integers, is still very slow. In this work we propose a fast bootstrapping method for FHE over the integers, closing thus this gap between these two types of schemes. We use a variant of the AGCD problem to construct a new GSW-like scheme that can natively encrypt polynomials, then, we show how the single-gate bootstrapping method proposed by L. Ducas and D. Micciancio [Lect. Notes Comput. Sci. 9056, 617–640 (2015; Zbl 1370.94509)] can be adapted to FHE over the integers using our scheme, and we implement a bootstrapping that, using around 400 MB of key material, runs in less than one second in a common personal computer.
For the entire collection see [Zbl 1476.94003].
For the entire collection see [Zbl 1476.94003].
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1370.94509References:
| [1] | Alperin-Sheriff, J.; Peikert, C.; Garay, JA; Gennaro, R., Faster bootstrapping with polynomial error, Advances in Cryptology - CRYPTO 2014, 297-314 (2014), Heidelberg: Springer, Heidelberg · Zbl 1336.94034 · doi:10.1007/978-3-662-44371-2_17 |
| [2] | Benarroch, D.; Brakerski, Z.; Lepoint, T.; Fehr, S., FHE over the Integers: decomposed and Batched in the Post-Quantum Regime, Public-Key Cryptography - PKC 2017, 271-301 (2017), Heidelberg: Springer, Heidelberg · Zbl 1400.94118 · doi:10.1007/978-3-662-54388-7_10 |
| [3] | Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS 2012, pp. 309-325. ACM, New York (2012) · Zbl 1347.68120 |
| [4] | Brakerski, Z.; Safavi-Naini, R.; Canetti, R., Fully homomorphic encryption without modulus switching from classical GapSVP, Advances in Cryptology - CRYPTO 2012, 868-886 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94091 · doi:10.1007/978-3-642-32009-5_50 |
| [5] | Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 97-106, October 2011 · Zbl 1292.94038 |
| [6] | Cheon, JH; Johansson, T.; Nguyen, PQ, Batch fully homomorphic encryption over the integers, Advances in Cryptology - EUROCRYPT 2013, 315-335 (2013), Heidelberg: Springer, Heidelberg · Zbl 1306.94040 · doi:10.1007/978-3-642-38348-9_20 |
| [7] | Chillotti, I.; Gama, N.; Georgieva, M.; Izabachène, M.; Cheon, JH; Takagi, T., Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds, Advances in Cryptology - ASIACRYPT 2016, 3-33 (2016), Heidelberg: Springer, Heidelberg · Zbl 1384.94044 · doi:10.1007/978-3-662-53887-6_1 |
| [8] | Chen, Y.; Nguyen, PQ; Lee, DH; Wang, X., BKZ 2.0: better lattice security estimates, Advances in Cryptology - ASIACRYPT 2011, 1-20 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94037 · doi:10.1007/978-3-642-25385-0_1 |
| [9] | Coron, J-S; Naccache, D.; Tibouchi, M.; Pointcheval, D.; Johansson, T., Public key compression and modulus switching for fully homomorphic encryption over the integers, Advances in Cryptology - EUROCRYPT 2012, 446-464 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94062 · doi:10.1007/978-3-642-29011-4_27 |
| [10] | Coron, J.-S., Pereira, H.V.L.: On Kilian’s randomization of multilinear map encodings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11922, pp. 325-355. Springer, Cham (2019). doi:10.1007/978-3-030-34621-8_12, https://eprint.iacr.org/2018/1129 · Zbl 1455.94144 |
| [11] | Cheon, JH; Stehlé, D.; Oswald, E.; Fischlin, M., Fully homomophic encryption over the integers revisited, Advances in Cryptology - EUROCRYPT 2015, 513-536 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94496 · doi:10.1007/978-3-662-46800-5_20 |
| [12] | van Dijk, M.; Gentry, C.; Halevi, S.; Vaikuntanathan, V.; Gilbert, H., Fully homomorphic encryption over the integers, Advances in Cryptology - EUROCRYPT 2010, 24-43 (2010), Heidelberg: Springer, Heidelberg · Zbl 1279.94130 · doi:10.1007/978-3-642-13190-5_2 |
| [13] | Ducas, L.; Micciancio, D.; Oswald, E.; Fischlin, M., FHEW: bootstrapping homomorphic encryption in less than a second, Advances in Cryptology - EUROCRYPT 2015, 617-640 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94509 · doi:10.1007/978-3-662-46800-5_24 |
| [14] | Gentry, C.: A fully homomorphic encryption scheme. Ph.D. thesis, Stanford University (2009). https://crypto.stanford.edu/craig/ · Zbl 1304.94059 |
| [15] | Galbraith, SD; Gebregiyorgis, SW; Murphy, S., Algorithms for the approximate common divisor problem, LMS J. Comput. Math., 19, A, 58-72 (2016) · Zbl 1404.11142 · doi:10.1112/S1461157016000218 |
| [16] | Gentry, C.; Halevi, S.; Smart, NP; Pointcheval, D.; Johansson, T., Fully homomorphic encryption with polylog overhead, Advances in Cryptology - EUROCRYPT 2012, 465-482 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94071 · doi:10.1007/978-3-642-29011-4_28 |
| [17] | Gentry, C.; Sahai, A.; Waters, B.; Canetti, R.; Garay, JA, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology - CRYPTO 2013, 75-92 (2013), Heidelberg: Springer, Heidelberg · Zbl 1310.94148 · doi:10.1007/978-3-642-40041-4_5 |
| [18] | Howgrave-Graham, N.; Silverman, JH, Approximate integer common divisors, Cryptography and Lattices, 51-66 (2001), Heidelberg: Springer, Heidelberg · Zbl 1006.94528 · doi:10.1007/3-540-44670-2_6 |
| [19] | Lee, HT; Seo, JH; Garay, JA; Gennaro, R., Security analysis of multilinear maps over the integers, Advances in Cryptology - CRYPTO 2014, 224-240 (2014), Heidelberg: Springer, Heidelberg · Zbl 1343.94069 · doi:10.1007/978-3-662-44371-2_13 |
| [20] | Pereira, H.V.L.: Efficient AGCD-based homomorphic encryption for matrix and vector arithmetic. Cryptology ePrint Archive, Report 2020/491 (2020). https://eprint.iacr.org/2020/491 · Zbl 07314279 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
