Gentry’s original blueprint for the construction of fully homomorphic encryption (FHE) starts from a somewhat homomorphic encryption scheme, that supports the homomorphic evaluation of arithmetic circuits of moderate multiplicative depth up to L, and whose decryption circuit itself can furthermore be “squashed” to a multiplicative depth less than L. Then, the homomorphic evaluation of this squashed decryption circuit, called bootstrapping, transforms any ciphertext into a ciphertext supporting at least one extra level of multiplication, enabling the homomorphic evaluation of arbitrary arithmetic circuits. Bootstrapping is the cornerstone of Gentry’s breakthrough. Unfortunately, it introduces substantial overhead that limits the efficiency of most FHE schemes so far. Consequently, numerous attempts have been made to circumvent the bottleneck of bootstrapping by directly constructing encryption schemes that support the evaluation of circuits of unbounded depth, e.g., by avoiding ciphertext noise, the randomness present in Gentry-like somewhat homomorphic schemes that grows after each homomorphic multiplication. Noise effectively limits the depths of supported circuits, as ciphertexts fail to correctly decrypt when noise size exceeds a certain threshold. Most attempts to achieve noiseless FHE schemes have proved insecure, however. In this paper, we take a closer look at a recent construction along those lines due to Zheng et al.’s unbounded FHE scheme, and show that it is no exception. We show that it is susceptible to an efficient full key recovery attack, and moreover that ciphertexts can be decrypted faster with the public parameters alone than the time it takes to generate the public key.
- Open Access
- Article
Cryptanalysis of an Unbounded Fully Homomorphic Encryption Scheme †
- Hyewon Sung 1,*,‡,
- Mehdi Tibouchi 2,*,‡
Author Information
Received: 09 Jul 2026 | Revised: 13 Aug 2026 | Accepted: 14 Aug 2026 | Published: 09 Sep 2026
Abstract
References
- 1.
Rivest, R.L.; Adleman, L.; Dertouzos, M.L. On Data Banks and Privacy Homomorphisms. In Foundations of Secure Computation; Academic Press: New York, NY, USA, 1978; pp. 165–179.
- 2.
Rabin, M.O. Digitalized Signatures and Public-Key Functions as Intractable as Factorization; Report MIT/LCS/TR-212; Massachusetts Institute of Technology, Laboratory for Computer Science: Cambridge, MA, USA, 1979.
- 3.
Paillier, P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Advances in Cryptology — EUROCRYPT'99, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 2–6 May 1999; Springer: Berlin/Heidelberg, Germany, 1999; pp. 223–238. https://doi.org/10.1007/3-540-48910-X_16.
- 4.
Boneh, D.; Goh, E.J.; Nissim, K. Evaluating 2-DNF Formulas on Ciphertexts. In Theory of Cryptography, Proceedings of the Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, 10–12 February 2005; Springer: Berlin/Heidelberg, Germany, 2005; pp. 325–341.
- 5.
Cocks, C. An Identity Based Encryption Scheme Based on Quadratic Residues. In Cryptography and Coding, Proceedings of the 8th IMA International Conference, Cirencester, UK, 17–19 December 2001; Springer: Berlin/Heidelberg, Germany, 2001; pp. 360–363. https://doi.org/10.1007/3-540-45325-3_32.
- 6.
Gentry, C. Fully Homomorphic Encryption Using Ideal Lattices. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA, 31 May–2 June 2009; pp. 169–178. https://doi.org/10.1145/1536414.1536440.
- 7.
Brakerski, Z.; Gentry, C.; Vaikuntanathan, V. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, MA, USA, 8–10 January 2012; pp. 309–325. https://doi.org/10.1145/2090236.2090262.
- 8.
Fan, J.; Vercauteren, F. Somewhat Practical Fully Homomorphic Encryption. 2012. Available online: https://eprint.iacr.org/2012/144 (accessed on 13 August 2026).
- 9.
Cheon, J.H.; Kim, A.; Kim, M.; et al. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Advances in Cryptology—ASIACRYPT 2017, Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 3–7 December 2017; Springer: Cham, Switzerland, 2017; Volume 10624, pp. 409–437. https://doi.org/10.1007/978-3-319-70694-8_15.
- 10.
Chillotti, I.; Gama, N.; Georgieva, M.; et al. Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds. In Advances in Cryptology—ASIACRYPT 2016, Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016; Springer: Berlin/Heidelberg, Germany, 2016; pp. 3–33. https://doi.org/10.1007/978-3-662-53887-6_1.
- 11.
Gentry, C.; Sahai, A.; Waters, B. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Advances in Cryptology—CRYPTO 2013, Proceedings of the 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, 18–22 August 2013; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8042, pp. 75–92. https://doi.org/10.1007/978-3-642-40041-4_5.
- 12.
Ducas, L.; Micciancio, D. FHEW: Bootstrapping Homomorphic Encryption in Less than a Second. In Advances in Cryptology—EUROCRYPT 2015, Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26–30 April 2015; Springer: Berlin/Heidelberg, Germany, 2015; Volume 9056, pp. 617–640. https://doi.org/10.1007/978-3-662-46800-5_24.
- 13.
Kipnis, A.; Hibshoosh, E. Efficient Methods for Practical Fully Homomorphic Symmetric-Key Encryption, Randomization and Verification. 2012/637. Available online: https://eprint.iacr.org/2012/637 (accessed on 13 August 2026).
- 14.
Tsaban, B.; Lifshitz, N. Cryptanalysis of the MORE Symmetric Key Fully Homomorphic Encryption Scheme. J. Math. Cryptol. 2015, 9, 75–78. https://doi.org/10.1515/jmc-2014-0013.
- 15.
Vizár, D.; Vaudenay, S. Cryptanalysis of EnhancedMore. Tatra Mt. Math. Publ. 2019, 73, 163–178. https://doi.org/10.2478/tmmp-2019-0012.
- 16.
Alex, S.; Yang, B. Cryptanalysis and Modification of a Variant of Matrix Operation for Randomization or Encryption (V-MORE). In Data and Applications Security and Privacy XXXIX, Proceedings of the 39th IFIP WG 11.3 Annual Conference on Data and Applications Security and Privacy, DBSec 2025, Gjøvik, Norway, 23–24 June 2025; Springer Nature: Cham, Switzerland, 2025; pp. 439–455.
- 17.
Li, J.; Wang, L. Noise-Free Symmetric Fully Homomorphic Encryption Based on Non-Commutative Rings. 2015/641. Available online: https://eprint.iacr.org/2015/641 (accessed on 13 August 2026).
- 18.
Barenghi, A.; Mainardi, N.; Pelosi, G. Comparison-Based Attacks against Noise-Free Fully Homomorphic Encryption Schemes. In Information and Communications Security, Proceedings of the 20th International Conference, ICICS 2018, Lille, France, 29–31 October 2018; Springer: Cham, Switzerland, 2018; pp. 177–191. https://doi.org/10.1007/978-3-030-01950-1_11.
- 19.
Yagisawa, M. Fully Homomorphic Encryption without Bootstrapping. 2015/474. Available online: https://eprint.iacr.org/2015/474 (accessed on 13 August 2026).
- 20.
Wang, Y. Octonion Algebra and Noise-Free Fully Homomorphic Encryption (FHE) Schemes. ArXiv 2016, arXiv:1601.06744.
- 21.
Nuida, K. Towards Constructing Fully Homomorphic Encryption without Ciphertext Noise from Group Theory. In International Symposium on Mathematics, Quantum Theory, and Cryptography; Springer: Singapore, 2021; pp. 57–78.
- 22.
Zheng, Z.; Liu, F.; Tian, K. An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem. J. Inf. Secur. 2023, 14, 366–395. https://doi.org/10.4236/jis.2023.144021.
- 23.
Chun, J.; Han, H.; Kang, S.V.; et al. Noiseless Homomorphic Encryption for Complex Numbers and Fully Homomorphic Encryption with Modular Arithmetic. J. Algebra Its Appl. 2026, 25, 2650060. https://doi.org/10.1142/s021949882650060x.
- 24.
Chun, J.; Han, H.; Kang, S.V.; et al. Construction of Noiseless Leveled Fully Homomorphic Encryption Scheme. J. Algebra Its Appl. 2026, 25, 2650183. https://doi.org/10.1142/s0219498826501835.
- 25.
van Dijk, M.; Gentry, C.; Halevi, S.; et al. Fully Homomorphic Encryption over the Integers. In Advances in Cryptology—EUROCRYPT 2010, Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, 30 May–3 June 2010; Springer: Berlin/Heidelberg, Germany, 2010; pp. 24–43. https://doi.org/10.1007/978-3-642-13190-5_2.
- 26.
Nuida, K.; Kurosawa, K. (Batch) Fully Homomorphic Encryption over Integers for Non-Binary Message Spaces. In Advances in Cryptology—EUROCRYPT 2015, Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 26–30 April 2015; Springer: Berlin/Heidelberg, Germany, 2015; pp. 537–555. https://doi.org/10.1007/978-3-662-46800-5_21.
- 27.
Kim, E.; Tibouchi, M. FHE over the Integers and Modular Arithmetic Circuits. IET Inf. Secur. 2018, 12, 257–264. https://doi.org/10.1049/iet-ifs.2017.0024.
- 28.
Koseki, R.; Ito, A.; Ueno, R.; et al. Homomorphic Encryption for Stochastic Computing. J. Cryptogr. Eng. 2023, 13, 251–263. https://doi.org/10.1007/s13389-022-00299-6.
- 29.
Micciancio, D. Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, BC, Canada, 16–19 November 2002; pp. 356–365.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com