Homomorphic encryption: a mathematical survey. (English) Zbl 07821731

Gentry, Craig

Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 2. Plenary lectures. Berlin: European Mathematical Society (EMS). 956-1006 (2023).

Summary: If the first thing that comes to mind when you hear the word “encryption” is the Enigma machine, you might think that encryption is complicated and mathematically uninteresting. In fact, many modern encryption systems are quite simple from a mathematical point of view, especially encryption systems that are homomorphic. In these systems, the starting point is a homomorphism that respects some binary operation(s), such as \(+\) or \(\times\). Depicting this homomorphism with a rectangular commutative diagram, the objects on the top level of the diagram are called ciphertexts, and the objects on the bottom level are called messages or plaintexts. The downward arrows in the diagram are the homomorphism, which we call decryption. The rightward arrows are the operation(s). Decryption commutes with the operations. To the commutative diagram we add one extra ingredient, computational complexity. Specifically, we need for it to be easy (in the sense of polynomial-time) for anyone to compute the rightward arrows in the diagram, but hard to learn how to compute the downward (decryption) arrows except with some special information that we will call a “secret key.” In short, homomorphic encryption is simply a homomorphism that has been “hardened” in the complexity-theoretic sense.
Homomorphic encryption allows anyone to compute on encrypted data, without needing (or being able) to decrypt, has many exciting applications. Fully homomorphic encryption (FHE) systems, which allow a rich (functionally complete) set of operations, were finally discovered in 2009. But all of the FHE systems that we have discovered so far follow the same blueprint, and we still wonder whether there are other ways to build FHE.
This survey presents homomorphic encryption from a mathematical point of view, illustrating with several examples how to start from a homomorphism and harden it to make it suitable for cryptography, pointing out pitfalls and attacks to avoid, laying out the current blueprint for FHE, and (I hope) serving as an inspiration and useful guide in the development of new approaches to FHE.
For the entire collection see [Zbl 1532.00036].

MSC:

68P25	Data encryption (aspects in computer science)
68Q17	Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
14G50	Applications to coding theory and cryptography of arithmetic geometry
94A60	Cryptography

Keywords:

homomorphism; cryptography; encryption; complexity theory

Software:

TFHE; NTRU; FHEW

References:

[1]	A. Acar, H. Aksu, A. S. Uluagac, and M. Conti, A survey on homomorphic encryption schemes: Theory and implementation. ACM Comput. Surv. 51 (2018), no. 4, 1-35.
[2]	C. Aguilar-Melchor, S. Fau, C. Fontaine, G. Gogniat, and R. Sirdey, Recent advances in homomorphic encryption: a possible future for signal processing in the encrypted domain. IEEE Signal Process. Mag. 30 (2013), no. 2, 108-117.
[3]	M. Ajtai, Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on theory of computing, pp. 99-108, ACM, 1996. · Zbl 0921.11071
[4]	M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/average-case equivalence. In Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp. 284-293, ACM, 1997. · Zbl 0962.68055
[5]	G. Alagic, Z. Brakerski, Y. Dulek, and C. Schaffner, Impossibility of quantum virtual black-box obfuscation of classical circuits. 2020, arXiv:2005.06432.
[6]	M. R. Albrecht, P. Farshim, J.-C. Faugere, and L. Perret, Polly cracker, revisited. In International conference on the theory and application of cryptology and infor-mation security, pp. 179-196, Springer, 2011. · Zbl 1227.94025
[7]	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. M. T. Morrison, A. Sahai, and V. Vaikuntanathan, Homomorphic encryption standard. Available at http://homomorphicencryption.org/, accessed February 2019, November 2018.
[8]	J. Alperin-Sheriff and C. Peikert, Faster bootstrapping with polynomial error. In Advances in cryptology-CRYPTO 2014, Part I, edited by J. A. Garay and R. Gennaro, pp. 297-314, Springer, 2014. · Zbl 1336.94034
[9]	B. Applebaum, D. Cash, C. Peikert, and A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In Advances in cryptology-CRYPTO 2009, 29th annual international cryptology confer-ence, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings, pp. 595-618, Springer, 2009. · Zbl 1252.94044
[10]	F. Armknecht, T. Gagliardoni, S. Katzenbeisser, and A. Peter, General impossi-bility of group homomorphic encryption in the quantum world. In International workshop on public key cryptography, pp. 556-573, Springer, 2014. · Zbl 1335.94028
[11]	F. Armknecht, C. Boyd, C. Carr, K. Gjøsteen, A. Jäschke, C. A. Reuter, and M. Strand, A guide to fully homomorphic encryption. IACR Cryptol. ePrint Arch. 2015 (2015), 1192.
[12]	S. Arora and R. Ge, New algorithms for learning in presence of errors. In ICALP (1), pp. 403-415, Lecture Notes in Comput. Sci. 6755, Springer, 2011. · Zbl 1332.68099
[13]	B. Barak and Z. Brakerski, Building the Swiss Army Knife. https://windowsontheory.org/2012/05/02/building-the-swiss-army-knife/, May 2, 2012.
[14]	B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S. Vadhan, and K. Yang, On the (im) possibility of obfuscating programs. In Annual international cryptology conference, pp. 1-18, Springer, 2001.
[15]	M. Bellare, A. Desai, E. Jokipii, and P. Rogaway, A concrete security treatment of symmetric encryption. In Proceedings 38th annual symposium on foundations of computer science, pp. 394-403, IEEE, 1997.
[16]	A. Blum, M. Furst, M. Kearns, and R. J. Lipton, Cryptographic primitives based on hard learning problems. In Annual international cryptology conference, pp. 278-291, Springer, 1993. · Zbl 0870.94021
[17]	D. Boneh and M. Franklin, Identity-based encryption from the weil pairing. In Annual international cryptology conference, pp. 213-229, Springer, 2001. · Zbl 1002.94023
[18]	D. Boneh and R. J. Lipton, Algorithms for black-box fields and their application to cryptography. In Annual international cryptology conference, pp. 283-297, Springer, 1996. · Zbl 1329.94053
[19]	D. Boneh and A. Silverberg, Applications of multilinear forms to cryptography. Contemp. Math. 324 (2003), no. 1, 71-90. · Zbl 1030.94032
[20]	Z. Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP. In Annual cryptology conference, pp. 868-886, Springer, 2012. · Zbl 1296.94091
[21]	Z. Brakerski, When homomorphism becomes a liability. In Theory of cryptog-raphy conference, pp. 143-161, Springer, 2013. · Zbl 1310.94133
[22]	Z. Brakerski, Fundamentals of fully homomorphic encryption. In Providing sound foundations for cryptography: on the work of Shafi Goldwasser and Silvio Micali, pp. 543-563, ACM, 2019.
[23]	Z. Brakerski, C. Gentry, and V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory 6 (2014), no. 3, 13. · Zbl 1347.68121
[24]	Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) lwe. SIAM J. Comput. 43 (2014), no. 2, 831-871. · Zbl 1302.94037
[25]	Z. Brakerski and V. Vaikuntanathan, Lattice-based FHE as secure as PKE. In Innovations in theoretical computer science, ITCS’14, edited by M. Naor, pp. 1-12, ACM, 2014. · Zbl 1364.94528
[26]	R. Canetti, H. Lin, S. Tessaro, and V. Vaikuntanathan, Obfuscation of proba-bilistic circuits and applications. In Theory of cryptography conference, pp. 468-497, Springer, 2015. · Zbl 1382.94078
[27]	J. H. Cheon, A. Kim, M. Kim, and Y. S. Song, Homomorphic encryption for arithmetic of approximate numbers. In ASIACRYPT (1), pp. 409-437, Lecture Notes in Comput. Sci. 10624, Springer, 2017. · Zbl 1420.94051
[28]	J. H. Cheon and D. Stehlé, Fully homomophic encryption over the integers revis-ited. In Annual international conference on the theory and applications of crypto-graphic techniques, pp. 513-536, Springer, 2015. · Zbl 1370.94496
[29]	I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, Faster fully homo-morphic encryption: bootstrapping in less than 0.1 seconds. In Advances in cryptology-ASIACRYPT 2016. ASIACRYPT 2016, pp. 3-33, Lecture Notes in Comput. Sci. 10031, Springer, 2016. · Zbl 1384.94044
[30]	I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, Faster packed homomor-phic operations and efficient circuit bootstrapping for TFHE. In ASIACRYPT (1), pp. 377-408, Lecture Notes in Comput. Sci. 10624, Springer, 2017. · Zbl 1420.94052
[31]	W. Diffie and M. Hellman, New directions in cryptography. IEEE Trans. Inf. Theory 22 (1976), no. 6, 644-654. · Zbl 0435.94018
[32]	D. Dolev, C. Dwork, and M. Naor, Nonmalleable cryptography. SIAM Rev. 45 (2003), no. 4, 727-784. · Zbl 1043.94009
[33]	L. Ducas and D. M. FHEW, bootstrapping homomorphic encryption in less than a second. In EUROCRYPT (1), pp. 617-640, Lecture Notes in Comput. Sci. 9056, Springer, 2015. · Zbl 1370.94509
[34]	L. Ducas and D. Stehlé, Sanitization of fhe ciphertexts. In Proceedings, Part I, of the 35th annual international conference on advances in cryptology-EUROCRYPT 2016, pp. 294-310, Lecture Notes in Comput. Sci. 9665, Springer, 2016. · Zbl 1384.94057
[35]	T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31 (1985), no. 4, 469-472. · Zbl 0571.94014
[36]	A. Feldmann, N. Samardzic, A. Krastev, S. Devadas, R. Dreslinski, K. Eldefrawy, N. Genise, C. Peikert, and D. Sanchez, F1: A fast and programmable accelerator for fully homomorphic encryption (extended version). 2021, arXiv:2109.05371.
[37]	M. Fellows and N. Koblitz, Combinatorial cryptosystems galore! Contemp. Math. 168 (1994), 51-51.
[38]	S. Garg, C. Gentry, and S. Halevi, Candidate multilinear maps from ideal lattices. In Annual international conference on the theory and applications of crypto-graphic techniques, pp. 1-17, Springer, 2013. · Zbl 1300.94055
[39]	S. Garg, C. Gentry, S. Halevi, M. Raykova, A. Sahai, and B. Waters, Candidate indistinguishability obfuscation and functional encryption for all circuits. SIAM J. Comput. 45 (2016), no. 3, 882-929. · Zbl 1348.94048
[40]	C. Gentry, A fully homomorphic encryption scheme. Stanford university, 2009.
[41]	C. Gentry, Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st ACM symposium on theory of computing-STOC 2009, pp. 169-178, ACM, 2009. · Zbl 1304.94059
[42]	C. Gentry, Computing arbitrary functions of encrypted data. Commun. ACM 53 (2010), no. 3, 97-105. · Zbl 1315.94074
[43]	C. Gentry, Computing on the edge of chaos: Structure and randomness in encrypted computation. In Proceedings of the international congress of math-ematicians (ICM), pp. 609-632, Kyung Moon SA, Seoul, 2014. · Zbl 1373.68225
[44]	C. Gentry, S. Halevi, M. Raykova, and D. Wichs, Outsourcing private RAM com-putation. In 2014 IEEE 55th annual symposium on foundations of computer sci-ence, pp. 404-413, IEEE, 2014.
[45]	C. Gentry, S. Halevi, and N. Smart, Fully homomorphic encryption with polylog overhead. In Advances in cryptology-EUROCRYPT 2012, pp. 465-482, Lecture Notes in Comput. Sci. 7237, Springer, 2012. Full version at http://eprint.iacr.org/ 2011/566. · Zbl 1297.94071
[46]	C. Gentry, A. Sahai, and B. Waters, Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster. In Advances in cryptology-CRYPTO 2013, Part I, edited by R. Canetti, and J. A. Garay, pp. 75-92, Springer, 2013. · Zbl 1310.94148
[47]	S. Goldwasser and S. Micali, Probabilistic encryption. J. Comput. System Sci. 28 (1984), no. 2, 270-299. · Zbl 0563.94013
[48]	S. Halevi, Homomorphic encryption. In Tutorials on the foundations of cryptog-raphy, pp. 219-276, Springer, 2017. · Zbl 1481.94106
[49]	D. Harvey and J. Van Der Hoeven, Integer multiplication in time o.n log n/. Ann. of Math. 193 (2021), no. 2, 563-617. · Zbl 1480.11162
[50]	J. Hoffstein, J. Pipher, and J. H. Silverman NTRU, A ring-based public key cryp-tosystem. In ANTS, edited by J. Buhler, pp. 267-288, Lecture Notes in Comput. Sci. 1423, Springer, 1998. · Zbl 1067.94538
[51]	Homomorphic Encryption Standardization. 2021, https://homomorphicencryption. org. · Zbl 1483.94003
[52]	N. Howgrave-Graham, Approximate integer common divisors. In International cryptography and lattices conference, pp. 51-66, Springer, 2001. · Zbl 1006.94528
[53]	A. Jain, H. Lin, and A. Sahai, Indistinguishability obfuscation from well-founded assumptions. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pp. 60-73, ACM, 2021. · Zbl 07765153
[54]	A. Joux, A one round protocol for tripartite Diffie-Hellman. In International algo-rithmic number theory symposium, pp. 385-393, Springer, 2000. · Zbl 1029.94026
[55]	W. Jung, S. Kim, J. H. Ahn, J. H. Cheon, and Y. Lee, Over 100 faster bootstrap-ping in fully homomorphic encryption through memory-centric optimization with gpus. IACR Cryptol. ePrint Arch. 2021 (2021), 508.
[56]	R. M. Karp and V. Ramachandran, A survey of parallel algorithms for shared-memory machines. United States: N. p., 1989.
[57]	A. K. Lenstra, H. W. Jr. Lenstra, M. S. Manasse, and J. M. Pollard, The number field sieve. In Proceedings of the twenty-second annual ACM symposium on theory of computing, pp. 564-572, ACM, 1990.
[58]	N. Linial, Y. Mansour, and N. Nisan, Constant depth circuits, Fourier transform, and learnability. J. ACM 40 (1993), no. 3, 607-620. · Zbl 0781.94006
[59]	A. López-Alt, E. Tromer, and V. Vaikuntanathan, On-the-fly multiparty com-putation on the cloud via multikey fully homomorphic encryption. In STOC, pp. 1219-1234, ACM, 2012. · Zbl 1286.68114
[60]	V. Lyubashevsky, C. Peikert, and O. Regev, On ideal lattices and learning with errors over rings. In Advances in cryptology-EUROCRYPT’10, edited by H. Gilbert, pp. 1-23, Lecture Notes in Comput. Sci. 6110, Springer, 2010. · Zbl 1279.94099
[61]	U. Mahadev, Classical homomorphic encryption for quantum circuits. SIAM J. Comput. (0):FOCS18-189 (2020). · Zbl 1457.81026
[62]	P. Martins, L. Sousa, and A. Mariano, A survey on fully homomorphic encryp-tion: an engineering perspective. ACM Comput. Surv. 50 (2017), no. 6, 1-33.
[63]	K. Nuida, Towards constructing fully homomorphic encryption without ciphertext noise from group theory. In International symposium on mathematics, quantum theory, and cryptography, pp. 57-78, Springer, Singapore, 2021. · Zbl 1459.94136
[64]	B. Reagen, W.-S. Choi, Y. Ko, V. T. Lee, H.-H. S. Lee, G.-Y. Wei, and D. B. Cheetah, Optimizing and accelerating homomorphic encryption for pri-vate inference. In IEEE international symposium on high-performance computer architecture (HPCA), pp. 26-39, IEEE, 2021.
[65]	O. Regev, On lattices, learning with errors, random linear codes, and cryptog-raphy. In Proceedings of the thirty-seventh annual ACM symposium on theory of computing, pp. 84-93, ACM, 2005. Full version in [66]. · Zbl 1192.94106
[66]	O. Regev, On lattices, learning with errors, random linear codes, and cryptog-raphy. J. ACM 56 (2009), no. 6, 34:1-34:40. · Zbl 1325.68101
[67]	R. Rivest, L. Adleman, and M. Dertouzos, On data banks and privacy homomor-phisms. In Foundations of secure computation, pp. 169-177, Academic Press, 1978.
[68]	R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signa-tures and public-key cryptosystems. Commun. ACM 21 (1978), no. 2, 120-126. · Zbl 0368.94005
[69]	R. Rothblum, Homomorphic encryption: from private-key to public-key. In Theory of cryptography conference, pp. 219-234, Springer, 2011. · Zbl 1295.94139
[70]	C.-P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms. Theoret. Comput. Sci. 53 (1987), no. 2-3, 201-224. · Zbl 0642.10030
[71]	P. W. Shor, Polynomial-time algorithms for prime factorization and discrete loga-rithms on a quantum computer. SIAM Rev. 41 (1999), no. 2, 303-332. · Zbl 1005.11507
[72]	A. Silverberg, Fully homomorphic encryption for mathematicians. In Women in numbers 2: research directions in number theory, p. 111, Contemp. Math. 606, AMS, 2013. 1005 Homomorphic encryption: a mathematical survey · Zbl 1297.94103
[73]	N. P. Smart and F. Vercauteren, Fully homomorphic SIMD operations. Des. Codes Cryptogr. 71 (2014), no. 1, 57-81. Early version at http://eprint.iacr.org/2011/133. · Zbl 1323.94140
[74]	V. Vaikuntanathan, Computing blindfolded: new developments in fully homo-morphic encryption. In 2011 IEEE 52nd annual symposium on foundations of computer science, pp. 5-16, IEEE, 2011. · Zbl 1292.94145
[75]	L. G. Valiant, A theory of the learnable. Commun. ACM 27 (1984), no. 11, 1134-1142. · Zbl 0587.68077
[76]	M. van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan, Fully homomorphic encryption over the integers. In Advances in cryptology-EUROCRYPT 2010, 29th annual international conference on the theory and applications of cryp-tographic techniques, French Riviera, May 30-June 3, 2010. Proceedings, pp. 24-43, Springer, 2010. · Zbl 1279.94130
[77]	W. Van Dam, S. Hallgren, and L. Ip, Quantum algorithms for some hidden shift problems. SIAM J. Comput. 36 (2006), no. 3, 763-778. · Zbl 1126.81019
[78]	J. Watrous, Quantum algorithms for solvable groups. In Proceedings of the thirty-third annual ACM symposium on theory of computing, pp. 60-67, ACM, 2001. Craig Gentry Algorand Foundation, New York, NY, USA, [e-mail] · Zbl 1323.68289