Homomorphic encryption plays a crucial role in the challenging problem of privacy preservation. In this survey, we describe a number of homomorphic schemes providing the relevant definitions to make the topic accessible to both cryptographers and mathematicians. We classify the schemes according to the timeline of appearance and, for some of them, we verify that they are correct with respect to decryption and evaluation, providing proofs or references. Recent research directions are also briefly discussed in this context.
Citation: Valentina Grazian, Antonio Tortora, Maria Tota. For what algebraic systems does a useful privacy homomorphism exist?[J]. AIMS Mathematics, 2025, 10(4): 9539-9562. doi: 10.3934/math.2025440
Homomorphic encryption plays a crucial role in the challenging problem of privacy preservation. In this survey, we describe a number of homomorphic schemes providing the relevant definitions to make the topic accessible to both cryptographers and mathematicians. We classify the schemes according to the timeline of appearance and, for some of them, we verify that they are correct with respect to decryption and evaluation, providing proofs or references. Recent research directions are also briefly discussed in this context.
| [1] | J. Alperin-Sheriff, C. Peikert, Faster bootstrapping with polynomial error, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8616 LNCS (PART 1), (2014), 297–314. https://doi.org/10.1007/978-3-662-44371-2_17 |
| [2] | G. Asharov, A. Jain, A. López-Alt, E. Tromer, V. Vaikuntanathan, D. Wichs, Multiparty computation with low communication, computation and interaction via threshold FHE, In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology – EUROCRYPT 2012, (2012), 483–501, Berlin, Heidelberg. |
| [3] | Y. Bae, J. H. Cheon, J. Kim, J. H. Park, D. Stehlé, Hermes: Efficient ring packing using mlwe ciphertexts and application to transciphering, In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, (2023), 37–69. Cham: Springer Nature Switzerland. https://doi.org/10.1007/978-3-031-38551-3_2 |
| [4] |
L. Bergerat, A. Boudi, Q. Bourgerie, I. Chillotti, D. Ligier, J. B. Orfila, et al., Parameter optimization and larger precision for (T)FHE, J. Cryptol., 36 (2023), 28. https://doi.org/10.1007/s00145-023-09463-5 doi: 10.1007/s00145-023-09463-5
|
| [5] | K. Boudgoust, P. Scholl, Simple threshold (fully homomorphic) encryption from lwe with polynomial modulus, International Conference on the Theory and Application of Cryptology and Information Security, (2023), 371–404. |
| [6] | Z. Brakerski, Fully homomorphic encryption without modulus switching from classical GapSVP, In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, (2012), 868–886. Springer. |
| [7] | D. Boneh, E. J. Goh, K. Nissim, Evaluating 2-dnf formulas on ciphertexts, In Joe Kilian, editor, Theory of Cryptography, Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005, Proceedings, volume 3378 of Lecture Notes in Computer Science, (2005), 325–341. Springer. https://doi.org/10.1007/978-3-540-30576-7_18 |
| [8] |
C. Boura, N. Gama, M. Georgieva, D. Jetchev, CHIMERA: combining ring-lwe-based fully homomorphic encryption schemes, J. Math. Cryptol., 14 (2020), 316–338. https://doi.org/10.1515/jmc-2019-0026 doi: 10.1515/jmc-2019-0026
|
| [9] | Z. Brakerski, C. Gentry, V. Vaikuntanathan, Fully homomorphic encryption without bootstrapping, Cryptology ePrint Archive, Paper 2011/277, 2011. https://eprint.iacr.org/2011/277 |
| [10] | Z. Brakerski, C. Gentry, V. Vaikuntanathan, (leveled) fully homomorphic encryption without bootstrapping, In Shafi Goldwasser, editor, Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, (2012), 309–325. ACM. https://doi.org/10.1145/2090236.2090262 |
| [11] |
Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory, 6 (2014), 1–36. https://doi.org/10.1145/2633600 doi: 10.1145/2633600
|
| [12] | Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, In Rafail Ostrovsky, editor, IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, (2011), 97–106. IEEE Computer Society. https://doi.org/10.1109/FOCS.2011.12 |
| [13] | Z. Brakerski, V. Vaikuntanathan, Fully homomorphic encryption from ring-lwe and security for key dependent messages, In Phillip Rogaway, editor, Advances in Cryptology - CRYPTO 2011 - 31st Annual Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2011. Proceedings, volume 6841 of Lecture Notes in Computer Science, (2011), 505–524. Springer. https://doi.org/10.1007/978-3-642-22792-9_29 |
| [14] |
Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, SIAM J. Comput., 43 (2014), 831–871. https://doi.org/10.1137/120868669 doi: 10.1137/120868669
|
| [15] |
I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, TFHE: fast fully homomorphic encryption over the torus, J. Cryptol., 33 (2020), 34–91. https://doi.org/10.1007/s00145-019-09319-x doi: 10.1007/s00145-019-09319-x
|
| [16] | J. H. Cheon, K. Han, A. Kim, M. Kim, Y. Song, Bootstrapping for approximate homomorphic encryption, In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018 Proceedings, Part I, volume 10820 of Lecture Notes in Computer Science, (2018), 360–384. Springer. https://doi.org/10.1007/978-3-319-78381-9_14 |
| [17] | J. H. Cheon, A. Kim, M. Kim, Y. Song, Homomorphic encryption for arithmetic of approximate numbers, In Tsuyoshi Takagi and Thomas Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017 - 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I, volume 10624 of Lecture Notes in Computer Science, (2017), 409–437. Springer. https://doi.org/10.1007/978-3-319-70694-8_15 |
| [18] | J. Cho, J. Ha, S. Kim, B. Lee, J. Lee, J. Lee, et al., Transciphering framework for approximate homomorphic encryption, In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, (2021), 640–669. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-030-92078-4_22 |
| [19] | R. Cramer, L. Ducas, C. Peikert, O. Regev, Recovering short generators of principal ideals in cyclotomic rings, In Advances in cryptology – EUROCRYPT 2016. Part II, volume 9666 of Lecture Notes in Comput. Sci., (2016), 559–585. Springer, Berlin. https://doi.org/10.1007/978-3-662-49896-5_20 |
| [20] | L. Ducas, D. Micciancio, FHEW: bootstrapping homomorphic encryption in less than a second, In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, (2015), 617–640. Springer. https://doi.org/10.1007/978-3-662-46800-5_24 |
| [21] | T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, In Advances in cryptology (Santa Barbara, Calif., 1984), volume 196 of Lecture Notes in Comput. Sci., (1985), 10–18. Springer, Berlin. https://doi.org/10.1007/3-540-39568-7_2 |
| [22] | M. Ferrara, A. Tortora, M. Tota, An overview of torus fully homomorphic encryption, International Journal of Group Theory, Proceedings of Ischia Group Theory 2022, 14 (2025), 59–73. |
| [23] |
M. Ferrara, A. Tortora, M. Tota, A data aggregation protocol based on TFHE, International Journal of Computer Mathematics: Computer Systems Theory, 9 (2024), 243–252. https://doi.org/10.1080/23799927.2024.2415034 doi: 10.1080/23799927.2024.2415034
|
| [24] | J. Fan, F. Vercauteren, Somewhat practical fully homomorphic encryption, IACR Cryptol. ePrint Arch., (2012), 144. |
| [25] | C. Gentry, Fully homomorphic encryption using ideal lattices, In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, (2009), 169–178. ACM. https://doi.org/10.1145/1536414.1536440 |
| [26] | C. Gentry, S. Halevi, Implementing gentry's fully-homomorphic encryption scheme, Annual international conference on the theory and applications of cryptographic techniques, (2011), 129–148. https://doi.org/10.1007/978-3-642-20465-4_9 |
| [27] | C. Gentry, S. Halevi, N. P. Smart, Fully homomorphic encryption with polylog overhead, Annual International Conference on the Theory and Applications of Cryptographic Techniques, (2012), 465–482. https://doi.org/10.1007/978-3-642-29011-4_28 |
| [28] | C. Gentry, S. Halevi, N. P. Smart, Better bootstrapping in fully homomorphic encryption, In Marc Fischlin, Johannes Buchmann, and Mark Manulis, editors, Public Key Cryptography - PKC 2012 - 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, May 21-23, 2012. Proceedings, volume 7293 of Lecture Notes in Computer Science, (2012), 1–16. Springer. |
| [29] | C. Gentry, S. Halevi, N. P. Smart, Homomorphic evaluation of the AES circuit, In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, (2012), 850–867. Springer. |
| [30] | C. Gentry, A. Sahai, B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, (2013), 75–92. Springer. https://doi.org/10.1007/978-3-642-40041-4_5 |
| [31] | N. Gama, M. Izabachène, P. Q. Nguyen, X. Xie, Structural lattice reduction: Generalized worst-case to average-case reductions and homomorphic cryptosystems, In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, (2016), 528–558. https://doi.org/10.1007/978-3-662-49896-5_19 |
| [32] | J. Ha, S. Kim, B. Lee, J. Lee, M. Son, Rubato: Noisy ciphers for approximate homomorphic encryption, In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, (2022), 581–610. Springer International Publishing. https://doi.org/10.1007/978-3-031-06944-4_20 |
| [33] | R. Hiromasa, M. Abe, T. Okamoto, Packing messages and optimizing bootstrapping in GSW-FHE, In Public-key cryptography—PKC 2015, volume 9020 of Lecture Notes in Comput. Sci., (2015), 699–715. Springer, Heidelberg. https://doi.org/10.1007/978-3-662-46447-2_31 |
| [34] | HEaaN Private AI Homomorphic Encryption Library. https://heaan.it/, January 2023. Crypto Lab, Korea. |
| [35] | S. Halevi, V. Shoup, Design and implementation of helib: a homomorphic encryption library, Cryptology ePrint Archive, Paper 2020/1481, 2020. https://eprint.iacr.org/2020/1481 |
| [36] | J. W. Lee, E. Lee, Y.-S. Kim, J. S. No, Rotation key reduction for client-server systems of deep neural network on fully homomorphic encryption, In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, (2023), 36–68. Springer Nature Singapore. https://doi.org/10.1007/978-981-99-8736-8_2 |
| [37] | A. Kim, A. Papadimitriou, Y. Polyakov, Approximate homomorphic encryption with reduced approximation error, In Topics in cryptology—CT-RSA 2022, volume 13161 of Lecture Notes in Comput. Sci., (2022), 120–144. Springer. https://doi.org/10.1007/978-3-030-95312-6_6 |
| [38] | A. Kim, Y. Polyakov, V. Zucca, Revisiting homomorphic encryption schemes for finite fields, In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, (2021), 608–639. Springer International Publishing. https://doi.org/10.1007/978-3-030-92078-4_21 |
| [39] | R. Ko, S. G. Lee, V. Rajan, Cloud computing vulnerability incidents: A statistical overview, Technical report, Cloud Vulnerabilities Working Group, Bellingham, WA, USA, 2013. |
| [40] | B. Li, D. Micciancio, On the security of homomorphic encryption on approximate numbers, In Advances in cryptology – EUROCRYPT 2021. Part I, volume 12696 of Lecture Notes in Comput. Sci., (2021), 648–677. https://doi.org/10.1007/978-3-030-77870-5_23 |
| [41] | Y. Lee, D. Micciancio, A. Kim, R. Choi, M. Deryabin, J. Eom, et al., Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption, In Advances in cryptology – EUROCRYPT 2023. Part III, volume 14006 of Lecture Notes in Comput. Sci., (2023), 227–256. Springer, Cham. https://doi.org/10.1007/978-3-031-30620-4_8 |
| [42] | H. Okada, R. Player, S. Pohmann, Homomorphic polynomial evaluation using galois structure and applications to bfv bootstrapping, In Jian Guo and Ron Steinfeld, editors, Advances in Cryptology – ASIACRYPT 2023, (2023), 69–100. Springer Nature Singapore. https://doi.org/10.1007/978-981-99-8736-8_3 |
| [43] | P. Paillier, Public-key cryptosystems based on composite degree residuosity classes, In Advances in cryptology – EUROCRYPT '99 (Prague), volume 1592 of Lecture Notes in Comput. Sci., (1999), 223–238. Springer, Berlin. https://doi.org/10.1007/3-540-48910-X_16 |
| [44] | Palisade homomorphic encryption software library. https://palisade-crypto.org/, December 2022. Crypto Lab, Korea. |
| [45] | C. Peikert, Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. STOC'09–Proceedings of the 2009 ACM International Symposium on Theory of Computing, 333–342. Association for Computing Machinery (ACM), New York, 2009. https://doi.org/10.1145/1536414.1536461 |
| [46] |
O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, 56 (2009), 1–40. https://doi.org/10.1145/1568318.1568324 doi: 10.1145/1568318.1568324
|
| [47] | R. Podschwadt, D. Takabi, P. Hu, Privacy-preserving Deep Learning with Homomorphic Encryption, arXiv: 2112.12855 [cs.CR] arXiv: 2112.12855v2 [cs.CR]. |
| [48] | R. L. Rivest, L. Adleman, M. L. Dertouzos, On data banks and privacy homomorphisms, In Foundations of secure computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977), (1978), 169–179. Academic Press. |
| [49] | Microsoft SEAL (release 4.1), https://github.com/Microsoft/SEAL, January 2023. Microsoft Research, Redmond, WA. |
| [50] | A. Silverberg, Fully homomorphic encryption for mathematicians, In Women in numbers 2: research directions in number theory, volume 606 of Contemp. Math., (2013), 111–123. Amer. Math. Soc., Providence, RI. https://doi.org/10.1090/conm/606/12143 |
| [51] | N. P. Smart, F. Vercauteren, Fully homomorphic encryption with relatively small key and ciphertext sizes, In Phong Q. Nguyen and David Pointcheval, editors, Public Key Cryptography - PKC 2010, 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010. Proceedings, volume 6056 of Lecture Notes in Computer Science, (2010), 420–443. Springer. https://doi.org/10.1007/978-3-642-13013-7_25 |
| [52] | M. van Dijk, C. Gentry, S. Halevi, V. Vaikuntanathan, Fully homomorphic encryption over the integers, In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, (2010), 24–43. Springer. https://doi.org/10.1007/978-3-642-13190-5_2 |
Figures(4)
Valentina Grazian, Antonio Tortora, Maria Tota. For what algebraic systems does a useful privacy homomorphism exist?[J]. AIMS Mathematics, 2025, 10(4): 9539-9562. doi: 10.3934/math.2025440
DownLoad: