Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology

DAI Yiran; ZHANG Jiang; XIANG Binwu; DENG Yi

doi:10.11999/JEIT230703

Volume 46 Issue 5

May 2024

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2024 > 46(5): 1774-1789

DAI Yiran, ZHANG Jiang, XIANG Binwu, DENG Yi. Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703

Citation:

DAI Yiran, ZHANG Jiang, XIANG Binwu, DENG Yi. Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703

Citation:

PDF( 1018 KB)

Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology

doi: 10.11999/JEIT230703

DAI Yiran^{1, 2, 3},
ZHANG Jiang²,
XIANG Binwu^{1, 2, 3},
DENG Yi^{1, 3
,
,}

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China
2.
State Key Laboratory of Cryptology, Beijing 100878, China
3.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China

Funds: The National Key Research and Development Project of China (2023YFB4503203), The National Natural Science Foundation of China (62372447, 61932019)

Received Date: 2023-09-28
Rev Recd Date: 2024-01-22

Available Online: 2024-05-12

Publish Date: 2024-05-30

Abstract

Abstract

With the application and popularization of IoT, cloud computing, and artificial intelligence, data security and privacy protection have become the focus of attention. Fully homomorphic encryption, as an effective solution to the privacy security problem, allows performing arbitrary homomorphic computation on encrypted data, and is a powerful encryption tool with a wide range of potential applications. The paper summarizes the proposed fully homomorphic encryption schemes since 2009, and divides them into four technical routes based on the core technologies of the schemes, analyzes and discusses the key constructs, algorithm optimization processes, and future development directions of each type of scheme. The paper firstly introduces fully homomorphic encryption-related mathematical principles, covering the basic assumptions and security features of fully homomorphic encryption schemes. Subsequently, according to the technical routes of the four fully homomorphic encryption schemes, it summarizes the structural general formulas of the encryption schemes, summarizes the core steps of the bootstrap algorithms, discusses the latest research progress, and on the basis of this, comprehensively analyzes and compares the storage efficiencies and computing speeds of various schemes. The paper finally shows the application implementation of homomorphic algorithm library for encryption schemes under each technical route, analyzes the opportunities and challenges of fully homomorphic encryption schemes in the current era, and makes an outlook on the future research prospects.
- Fully Homomorphic Encryption,
- Bootstrapping,
- BGV,
- GSW,
- CKKS

FullText(HTML)

References(67)

References

[1]	BRICKELL E F and YACOBI Y. On privacy homomorphisms (Extended Abstract)[C]. The Workshop on the Theory and Application of Cryptographic Techniques, Amsterdam, The Netherlands, 1988: 117–125. doi: 10.1007/3-540-39118-5_12.
[2]	CRAMER R, DAMGÅRD I, and NIELSEN J B. Multiparty computation from threshold homomorphic encryption[C]. The International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, 2001: 280–300. doi: 10.1007/3-540-44987-6_18.
[3]	RIVEST R L, ADLEMAN L, and DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169–179.
[4]	ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[M]. BLAKLEY G R and CHAUM D. Advances in Cryptology. Berlin Heidelberg: Springer, 1985: 10–18. doi: 10.1007/3-540-39568-7_2.
[5]	RIVEST R L, SHAMIR A, and ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120–126. doi: 10.1145/359340.359342.
[6]	BONEH D, GOH E J, and NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]. The Second Theory of Cryptography Conference, Cambridge, USA, 2005: 325–341. doi: 10.1007/978-3-540-30576-7_18.
[7]	BEHERA S and PRATHURI J R. Design of novel hardware architecture for fully homomorphic encryption algorithms in FPGA for real-time data in cloud computing[J]. IEEE Access, 2022, 10: 131406–131418. doi: 10.1109/ACCESS.2022.3229892.
[8]	LI Juyan, QIAO Zhiqi, ZHANG Kejia, et al. A lattice-based homomorphic proxy re-encryption scheme with strong anti-collusion for cloud computing[J]. Sensors, 2021, 21(1): 288. doi: 10.3390/s21010288.
[9]	LEE J W, KANG H, LEE Y, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network[J]. IEEE Access, 2022, 10: 30039–30054. doi: 10.1109/ACCESS.2022.3159694.
[10]	李腾, 方保坤, 马卓, 等. 基于同态加密的医疗数据密文异常检测方法[J]. 中国科学: 信息科学, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214. LI Teng, FANG Baokun, MA Zhuo, et al. Homomorphic encryption-based ciphertext anomaly detection method for e-health records[J]. Scientia Sinica Informationis, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214.
[11]	GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The 41st Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–169. doi: 10.1145/1536414.1536440.
[12]	PEREIRA H V L. Bootstrapping fully homomorphic encryption over the integers in less than one second[C/OL]. The 24th IACR International Conference on Practice and Theory of Public Key Cryptography, 2021. doi: 10.1007/978-3-030-75245-3_13.
[13]	BONTE C, ILIASHENKO I, PARK J, et al. FINAL: Faster FHE instantiated with NTRU and LWE[C]. The 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, China, 2022. doi: 10.1007/978-3-031-22966-4_7.
[14]	KLUCZNIAK K. NTRU-v-um: Secure fully homomorphic encryption from NTRU with small modulus[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 1783–1797. doi: 10.1145/3548606.3560700.
[15]	XIANG Binwu, ZHANG Jiang, DENG Yi, et al. Fast blind rotation for bootstrapping FHEs[C]. The 43rd Annual International Cryptology Conference, Santa Barbara, USA, 2023. doi: 10.1007/978-3-031-38551-3_1.
[16]	STEHLÉ D, STEINFELD R, TANAKA K, et al. Efficient public key encryption based on ideal lattices[C]. The 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 2009. doi: 10.1007/978-3-642-10366-7_36.
[17]	SVP challenge[EB/OL]. https://www.latticechallenge.org/svp-challenge/.
[18]	REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.
[19]	BLUM A, FURST M, KEARNS M, et al. Cryptographic primitives based on hard learning problems[C]. The 13th Annual International Cryptology Conference, Santa Barbara, USA, 1994. doi: 10.1007/3-540-48329-2_24.
[20]	BRAKERSKI Z and VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]. The 31st Annual Cryptology Conference, Santa Barbara, USA, 2011. doi: 10.1007/978-3-642-22792-9_29.
[21]	GENTRY C, HALEVI S, and VAIKUNTANATHAN V. i-Hop homomorphic encryption and rerandomizable Yao circuits[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010. doi: 10.1007/978-3-642-14623-7_9.
[22]	KITAGAWA F and MATSUDA T. Circular security is complete for KDM security[C]. The 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 2020. doi: 10.1007/978-3-030-64837-4_9.
[23]	BRAKERSKI Z and VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011: 97–106. doi: 10.1109/FOCS.2011.12.
[24]	GENTRY C, SAHAI A, and WATERS B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013. doi: 10.1007/978-3-642-40041-4_5.
[25]	CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017. doi: 10.1007/978-3-319-70694-8_15.
[26]	GENTRY C. Computing arbitrary functions of encrypted data[J]. Communications of the ACM, 2010, 53(3): 97–105. doi: 10.1145/1666420.1666444.
[27]	GENTRY C and HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011: 129–148. doi: 10.1007/978-3-642-20465-4_9.
[28]	GENTRY C and HALEVI S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011. doi: 10.1109/FOCS.2011.94.
[29]	GENTRY C, HALEVI S, and SMART N P. Better bootstrapping in fully homomorphic encryption[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 1–16. doi: 10.1007/978-3-642-30057-8_1.
[30]	BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]. The 3rd Innovations in Theoretical Computer Science Conference, Cambridge, USA, 2012. doi: 10.1145/2090236.2090262.
[31]	CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018. DOI: 10.1007/978-3-319-78381-9_14.
[32]	LEE J W, LEE E, LEE Y, et al. High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_22.
[33]	JUTLA C S and MANOHAR N. Sine series approximation of the mod function for bootstrapping of approximate HE[R]. Paper 2021/572, 2021.
[34]	BAE Y, CHEON J H, CHO W, et al. META-BTS: Bootstrapping precision beyond the limit[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 223–234. doi: 10.1145/3548606.3560696.
[35]	LI Baiyu and MICCIANCIO D. On the security of homomorphic encryption on approximate numbers[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_23.
[36]	LI Baiyu, MICCIANCIO D, SCHULTZ M, et al. Securing approximate homomorphic encryption using differential privacy[R]. Paper 2022/816, 2022.
[37]	FAN Junfeng and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[R]. Paper 2012/144, 2012.
[38]	GENTRY C, HALEVI S, and SMART N P. Fully homomorphic encryption with polylog overhead[C]. The 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012. doi: 10.1007/978-3-642-29011-4_28.
[39]	GENTRY C, HALEVI S, and SMART N P. Homomorphic evaluation of the AES circuit[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012. doi: 10.1007/978-3-642-32009-5_49.
[40]	HALEVI S and SHOUP V. Algorithms in HElib[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014. doi: 10.1007/978-3-662-44371-2_31.
[41]	HALEVI S and SHOUP V. Design and implementation of HElib: A homomorphic encryption library[R]. Paper 2020/1481, 2020.
[42]	HALEVI S and SHOUP V. Bootstrapping for HElib[J]. Journal of Cryptology, 2021, 34(1): 7. doi: 10.1007/s00145-020-09368-7.
[43]	KIM A, POLYAKOV Y, and ZUCCA V. Revisiting homomorphic encryption schemes for finite fields[C]. Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2021. DOI: 10.1007/978-3-030-92078-4_21.
[44]	ALPERIN-SHERIFF J and PEIKERT C. Faster bootstrapping with polynomial error[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014: 297–314. doi: 10.1007/978-3-662-44371-2_17.
[45]	DUCAS L and MICCIANCIO D. FHEW: Bootstrapping homomorphic encryption in less than a second[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 617–640. doi: 10.1007/978-3-662-46800-5_24.
[46]	CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016. DOI: 10.1007/978-3-662-53887-6_1.
[47]	MYERS S and SHULL A. Practical revocation and key rotation[C]. The Cryptographers’ Track at the RSA Conference 2018, San Francisco, USA, 2018. DOI: 10.1007/978-3-319-76953-0_9.
[48]	LIU Fenghao and WANG Han. Batch bootstrapping II: Bootstrapping in polynomial modulus only requires $ O(1) $ FHE multiplications in amortization[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 353–384. doi: 10.1007/978-3-031-30620-4_12.
[49]	LIU Fenghao and WANG Han. Batch bootstrapping I: A new framework for SIMD bootstrapping in polynomial modulus[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 321–352. doi: 10.1007/978-3-031-30620-4_11.
[50]	MICCIANCIO D and REGEV O. Lattice-based cryptography[M]. BERNSTEIN D J, BUCHMANN J, and DAHMEN E. Post-Quantum Cryptography. Berlin, Heidelberg: Springer, 2009. doi: 10.1007/978-3-540-88702-7_5.
[51]	AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 99–108. doi: 10.1145/237814.237838.
[52]	LYUBASHEVSKY V, PEIKERT C, and REGEV O. On ideal lattices and learning with errors over rings[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010. doi: 10.1007/978-3-642-13190-5_1.
[53]	DUCAS L and DURMUS A. Ring-LWE in polynomial rings[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 34–51. doi: 10.1007/978-3-642-30057-8_3.
[54]	SMART N P and VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57–81. doi: 10.1007/s10623-012-9720-4.
[55]	Homenc. HElib[EB/OL].https://github.com/homenc/HElib.
[56]	Microsoft. SEAL[EB/OL]. https://github.com/microsoft/SEAL.
[57]	Openfheorg. Openfhe-development[EB/OL]. https://github.com/openfheorg/openfhe-development.
[58]	Tfhe. Tfhe[EB/OL].https://github.com/tfhe/tfhe.
[59]	Snucrypto. HEAAN[EB/OL]. https://github.com/snucrypto/HEAAN.
[60]	CHOWDHURY S, SINHA S, SINGH A, et al. Efficient threshold FHE with application to real-time systems[R]. Paper 2022/1625, 2022.
[61]	YUAN Minghao, WANG Dongdong, ZHANG Feng, et al. An examination of multi-key fully homomorphic encryption and its applications[J]. Mathematics, 2022, 10(24): 4678. doi: 10.3390/math10244678.
[62]	PARK J and ROVIRA S. Efficient TFHE bootstrapping in the multiparty setting[R]. Paper 2023/759, 2023.
[63]	DI GIUSTO A and MARCOLLA C. Breaking the power-of-two barrier: Noise estimation for BGV in NTT-friendly rings[R]. Paper 2023/783, 2023.
[64]	CHEN Hao, ILIASHENKO I, and LAINE K. When HEAAN Meets FV: A new somewhat homomorphic encryption with reduced memory overhead[C]. The 18th IMA International Conference, 2021. doi: 10.1007/978-3-030-92641-0_13.
[65]	AUNG K M M, LIM E, SIM J J, et al. Field instruction multiple data[R]. Paper 2022/771, 2022.
[66]	LI Zengpeng and WANG Ding. Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2022, 15(1): 308–321. doi: 10.1109/TSC.2019.2939836.
[67]	WANG Qingxuan, WANG Ding, CHENG Chi, et al. Quantum2FA: Efficient quantum-resistant two-factor authentication scheme for mobile devices[J]. IEEE Transactions on Dependable and Secure Computing, 2023, 20(1): 193–208. doi: 10.1109/TDSC.2021.3129512.