An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem — Oak Academic Publishing
Research ArticleOpen AccessGoogle Scholar indexed
An Unbounded Fully Homomorphic Encryption Scheme Based on Ideal Lattices and Chinese Remainder Theorem
Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Henan Academy of Sciences, Renmin University of China, Beijing, China
,
Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Institute of Artificial Intelligence, Beijing, China
,
Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Henan Academy of Sciences, Renmin University of China, Beijing, China
1 Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Henan Academy of Sciences, Renmin University of China, Beijing, China
2 Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, Institute of Artificial Intelligence, Beijing, China
3 Engineering Research Center of Ministry of Education for Financial Computing and Digital Engineering, Henan Academy of Sciences, Renmin University of China, Beijing, China
We propose an unbounded fully homomorphic encryption scheme, i.e . a scheme that allows one to compute on encrypted data for any desired functions without needing to decrypt the data or knowing the decryption keys. This is a rational solution to an old problem proposed by Rivest, Adleman, and D ertouzos [1] in 1978, and to some new problems that appeared in Peikert [2] as open questions 10 and open questions 11 a few years ago. Our scheme is co mpletely different from the breakthrough work [3] of Gentry in 2009. Gentry ’ s bootstrapping technique constructs a fully homomorphic encryption (FHE) scheme from a somewhat homomorphic one that is powerful enough to evaluate its own decryption function. To date, it remains the only known way of obtaining unbounded FHE. Our construction of an unbounded FHE scheme is straightforward and can handle unbounded homomorphic computation on any refreshed ciphertexts without bootstrapping transformation technique.
KeywordsFully Homomorphic EncryptionIdeal LatticesChinese Remainder TheoremGeneral Compact Knapsacks Problem
Rivest, R.L., Adleman, L. and Dertouzos, M.L. (1978) On Data Banks and Privacy Homomorphisms. Foundations of Secure Computation, 4, 169-180.
Peikert, C. (2016) A Decade of Lattice Cryptography. Now Foundations and Trends, Boston, 1-90. https://doi.org/10.1561/9781680831139
Gentry, C. (2009) A Fully Homomorphic Encryption Scheme. Ph.D. Thesis, Stanford University, Stanford.
Gentry, C. (2009) Fully Homomorphic Encryption Using Ideal Lattices. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, Bethesda, 31 May-2 June 2009, 169-178. https://doi.org/10.1145/1536414.1536440
Brakerski, Z. (2012) Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Advances in Cryptology-CRYPTO 2012, Santa Barbara, 19-23 August 2012, 868-886. https://doi.org/10.1007/978-3-642-32009-5_50
Brakerski, Z., Gentry, C. and Vaikuntanathan, V. (2014) (Leveled) Fully Homomorphic Encryption without Bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, Cambridge, 8-10 January 2012, 309-325. https://doi.org/10.1145/2090236.2090262
Brakerski, Z. and Vaikuntanathan, V. (2011) Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Advances in Cryptology-CRYPTO 2011, Santa Barbara, 14-18 August 2011, 505-524. https://doi.org/10.1007/978-3-642-22792-9_29
Brakerski, Z. and Vaikuntanathan, V. (2014) Efficient Fully Homomorphic Encryption from (Standard) LWE. SIAM Journal on Computing, 43, 831-871. https://doi.org/10.1137/120868669
Cheon, J.H., Coron, J.-S., Kim, J., Lee, M.S., Lepoint, T., Tibouchi, M. and Yun, A. (2013) Batch Fully Homomorphic Encryption over the Integers. Advances in Cryptology-EUROCRYPT 2013, Athens, 26-30 May 2013, 315-335. https://doi.org/10.1007/978-3-642-38348-9_20
Coron, J.-S., Mandal, A., Naccache, D. and Tibouchi, M. (2011) Fully Homomorphic Encryption over the Integers with Shorter Public Keys. Advances in Cryptology-CRYPTO 2011, Santa Barbara, 14-18 August 2011, 487-504. https://doi.org/10.1007/978-3-642-22792-9_28
Coron, J.-S., Naccache, D. and Tibouchi, M. (2012) Public Key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers. Advances in Cryptology-EUROCRYPT 2012, Cambridge, 15-19 April 2012, 446-464. https://doi.org/10.1007/978-3-642-29011-4_27
Gentry, C. (2010) Computing Arbitrary Functions of Encrypted Data. Communications of the ACM, 53, 97-105. https://doi.org/10.1145/1666420.1666444
Gentry, C. (2010) Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness. Advances in Cryptology-CRYPTO 2010, Santa Barbara, 15-19 August 2010, 116-137. https://doi.org/10.1007/978-3-642-14623-7_7
Gentry, C., Halevi, S., Peikert, C. and Smart, N.P. (2012) Field Switching in BGV-Style Homomorphic Encryption. Journal of Computer Security, 21, 663-684. https://doi.org/10.3233/JCS-130480
Gentry, C., Halevi, S. and Smart, N.P. (2012) Fully Homomorphic Encryption with Polylog Overhead. Advances in Cryptology-EUROCRYPT 2012, Cambridge, 15-19 April 2012. 465-482. https://doi.org/10.1007/978-3-642-29011-4_28
Smart, N.P. and Vercauteren, F. (2014) Fully Homomorphic SIMD Operations. Designs, Codes and Cryptography, 71, 57-81. https://doi.org/10.1007/s10623-012-9720-4
Regev, O. (2009) On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. JOURNAL OF THE ACM, 56, Article No. 34. https://doi.org/10.1145/1568318.1568324
Regev, O. (2010) The Learning with Errors Problem. IEEE Conference on Computational Complexity, Cambridge, 9-11 June 2010, 191-204. https://doi.org/10.1109/CCC.2010.26
Gentry, C., Sahai, A. and Waters, B. (2013) Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. Advances in Cryptology-CRYPTO 2013, Santa Barbara, 18-22 August 2013, 75-92. https://doi.org/10.1007/978-3-642-40041-4_5
Zheng, Z. and Tian, K. (2022) On the LWE Cryptosystem with More General Disturbance. Journal of Information Security, 13, 127-139. https://doi.org/10.4236/jis.2022.133008
Alperin-Sheriff, J. and Peikert, C. (2013) Practical Bootstrapping in Quasilinear Time. Advances in Cryptology-CRYPTO 2013, Santa Barbara, 18-22 August 2013, 1-20. https://doi.org/10.1007/978-3-642-40041-4_1
Agrawal, S., Boneh, D. and Boyen, X. (2010) Efficient Lattice (H)IBE in the Standard Model. EUROCRYPT, Monaco, 30 May-3 June 2010, 553-572. https://doi.org/10.1007/978-3-642-13190-5_28
Ajtai, M. (1999) Generating Hard Instances of the Short Basis Problem. In: Wiedermann, J., Boas, P.E. and Nielsen, M., Eds., Automata, Languages and Programming, Springer, Berlin, 1-9. https://doi.org/10.1007/3-540-48523-6_1
Alwen, J. and Peikert, C. (2009) Generating Shorter Bases for Hard Random Lattices. Theory of Computing Systems, 48, 535-553. https://doi.org/10.1007/s00224-010-9278-3
Micciancio, D. and Peikert, C. (2012) Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. Advances in Cryptology-EUROCRYPT 2012, Cambridge, 15-19 April 2012, 700-718. https://doi.org/10.1007/978-3-642-29011-4_41
Peikert, C. and Waters, B. (2011) Lossy Trapdoor Functions and Their Applications. SIAM Journal on Computing, 40, 1803-1844. https://doi.org/10.1137/080733954
Chillotti, I., Gama, N., Georgieva, M. and Izabachene, M. (2016) Faster Fully Homomorphic Encryption: Bootstrapping in Less than 0.1 Seconds. Advances in Cryptology-ASIACRYPT 2016, Hanoi, 4-8 December 2016, 3-33. https://doi.org/10.1007/978-3-662-53887-6_1
Chillotti, I., Gama, N., Georgieva, M. and Izabachene, M. (2018) TFHE: Fast Fully Homomorphic Encryption over the Torus. Journal of Cryptology, 33, 34-91. https://doi.org/10.1007/s00145-019-09319-x
Chen, H., Laine, K. and Player, R. (2017) Simple Encrypted Arithmetic Library-SEAL v2.1. FC 2017 International Workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, 7 April 2017, 3-18. https://doi.org/10.1007/978-3-319-70278-0_1
Fan, J. and Vercauteren, F. (2012) Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive.
Cheon, J.H., Han, K., Kim, A., Kim, M. and Song, Y. (2018) Bootstrapping for Approximate Homomorphic Encryption. Advances in Cryptology-EUROCRYPT 2018, Tel Aviv, 29 April-3 May 2018, 360-384. https://doi.org/10.1007/978-3-319-78381-9_14
Cheon, J.H., Kim, A., Kim, M. and Song, Y.S. (2017) Homomorphic Encryption for Arithmetic of Approximate Numbers. Advances in Cryptology-ASIACRYPT 2017, Hong Kong, 3-7 December 2017, 409-437. https://doi.org/10.1007/978-3-319-70694-8_15
Boura, C., Gama, N., Georgieva, M. and Jetchev, D. (2020) CHIMERA: Combining Ring-LWE-Based Fully Homomorphic Encryption Schemes. Journal of Mathematical Cryptology, 14, 316-338. https://doi.org/10.1515/jmc-2019-0026
van Dijk, M., Gentry, C., Halevi, S. and Vaikuntanathan, V. (2010) Fully Homomorphic Encryption over the Integers. Advances in Cryptology-EUROCRYPT 2010, French Riviera, 30 May-3 June 2010, 24-43. https://doi.org/10.1007/978-3-642-13190-5_2
Kogos, K.G., Filippova, K.S. and Epishkina, A.V. (2017) Fully Homomorphic Encryption Schemes: The State of the Art. 2017 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering, St. Petersburg, 1-3 February 2017, 463-466. https://doi.org/10.1109/EIConRus.2017.7910591
Yagisawa, M. (2015) Fully Homomorphic Encryption without Bootstrapping. Cryptology ePrint Archive.
Yagisawa, M. (2015) Fully Homomorphic Encryption on Octonion Ring. Cryptology ePrint Archive.
Liu, D. (2015) Practical Fully Homomorphic Encryption without Noise Reduction. Cryptology ePrint Archive.
Li, J. and Wang, L. (2015) Noise-Free Symmetric Fully Homomorphic Encryption Based on Non-Commutative Rings. Cryptology ePrint Archive.
Zheng, Z. (2022) Modern Cryptography Volume 1—A Classical Introduction to Informational and Mathematical Principle. Springer, Berlin. https://doi.org/10.1007/978-981-19-0920-7
Ajtai, M. (1996) Generating Hard Instances of Lattice Problems. Quaderni di Matematica, 13, 99-108. https://doi.org/10.1145/237814.237838
Micciancio, D. (2002) Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. The 43rd Annual IEEE Symposium on Foundations of Computer Science, Vancouver, 16-19 November 2002, 356-365.
Zheng, Z., Liu, F. and Chen, M. (2022) On the High Dimensional RSA Algorithm—A Public Key Cryptosystem Based on Lattice and Algebraic Number Theory. International Journal of Latest Research in Engineering and Technology, 8, 1-16.
Zheng, , Z., Tian, K. and Liu, F. (2022) Modern Cryptography Volume 2—A Classical Introduction to Informational and Mathematical Principle. Springer, Berlin. https://doi.org/10.1007/978-981-19-7644-5
Lyubashevsky, V., Peikert, C. and Regev, O. (2010) On Ideal Lattices and Learning with Errors over Rings. Advances in Cryptology-EUROCRYPT 2010, French Riviera, 30 May-3 June 2010, 1-23. https://doi.org/10.1007/978-3-642-13190-5_1
Micciancio, D. and Regev, O. (2009) Lattice-Based Cryptography. In: Bernstein, D.J., Buchmann, J. and Dahmen, E., Eds., Post-Quantum Cryptography, Springer, Berlin, 147-191. https://doi.org/10.1007/978-3-540-88702-7_5
Zheng, Z., Liu, F., Huang, W., Xu, J. and Tian, K. (2022) A Generalization of NTRUEncrypt—Cryptosystem Based on Ideal Lattice. Journal of Information Security, 13, 165-180. https://doi.org/10.4236/jis.2022.133010
Zheng, Z., Liu, F., Lu, Y. and Tian, K. (2022) Cyclic Lattices, Ideal Lattices and Bounds for the Smoothing Parameter. Journal of Information Security, 13, 272-293. https://doi.org/10.4236/jis.2022.134015
Micciancio, D. and Regev, O. (2007) Worst-Case to Average-Case Reductions Based on Gaussian Measures. SIAM Journal on Computing, 37, 267-302. https://doi.org/10.1137/S0097539705447360
Washington, L.C. (1980) Graduate Texts in Mathematics—Introduction to Cyclotomic Fields. Springer-Verlag, New York.
Micciancio, D. (2001) Improving Lattice Based Cryptosystems Using the Hermite Normal Form. In: Silverman, J.H., Ed., Cryptography and Lattices, Springer, Berlin, 126-145. https://doi.org/10.1007/3-540-44670-2_11
Micciancio, D. and Peikert, C. (2013) Hardness of SIS and LWE with Small Parameters. Advances in Cryptology-CRYPTO 2013, Santa Barbara, 18-22 August 2013, 21-39. https://doi.org/10.1007/978-3-642-40041-4_2