Recent Development of Theory and Application on Homomorphic Encryption

Yatao YANG; Yang ZHAO; Juanmei ZHANG; Jierun HUANG; Yuan GAO

doi:10.11999/JEIT191019

Volume 43 Issue 2

Feb. 2021

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2021 > 43(2): 475-487

Yatao YANG, Yang ZHAO, Juanmei ZHANG, Jierun HUANG, Yuan GAO. Recent Development of Theory and Application on Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(2): 475-487. doi: 10.11999/JEIT191019

Citation:

Yatao YANG, Yang ZHAO, Juanmei ZHANG, Jierun HUANG, Yuan GAO. Recent Development of Theory and Application on Homomorphic Encryption[J]. Journal of Electronics & Information Technology, 2021, 43(2): 475-487. doi: 10.11999/JEIT191019

Citation:

PDF( 544 KB)

Recent Development of Theory and Application on Homomorphic Encryption

doi: 10.11999/JEIT191019

1.
Department of Electronic and Communication Engineering, Beijing Electronic Science and Technology Institute, Beijing 100070, China
2.
Department of Cryptography Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100070, China
3.
School of Telecommunication Engineering, Xidian University, Xi’an 710071, China

Funds: The State Cryptography Development Fund of Thirteen Five-year(MMJJ20170110)

Received Date: 2019-12-23
Rev Recd Date: 2020-06-09

Available Online: 2020-07-17

Publish Date: 2021-02-23

Abstract

Abstract

With the popularization of various cloud services such as cloud computing and cloud storage, privacy preservation issues in the cloud environment have gradually become the focus of industrial applications. Homomorphic encryption has become an important method to solve this issue. Among them, how to construct an efficient fully homomorphic encryption scheme is one of the hotspots at present. Firstly, the development of homomorphic encryption is introduced. The homomorphic encryption schemes are analyzed and classified from different perspectives. The research progress of verifiable fully homomorphic encryption schemes is discussed in detail. By analyzing the property rights literature on homomorphic encryption that has been published in recent years, the progress in the theoretical research and application about homomorphic encryption are summarized. Secondly, the working performances of three typical homomorphic encryption libraries, Helib, SEAL and TFHE, are compared and analyzed. Finally, various application scenarios of homomorphic encryption technology are sorted out, and possible research and development directions in the future are proposed.
- Homomorphic Encryption(HE),
- Privacy preservation,
- Verifiable homomorphic encryption,
- Fully Homomorphic Encryption(FHE),
- Cryptographic application

FullText(HTML)

References(83)

References

RIVEST R L, ADLEMAN L, and DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169–180.

GENTRY C. A fully homomorphic encryption scheme[D]. [Ph. D. dissertation]. Stanford University, 2009.

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: 505–524. doi: 10.1007/978-3-642-22792-9_29.

BRAKERSKI Z and VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]. The 52nd IEEE Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011: 97–106. doi: 10.1109/FOCS.2011.12.

PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes[C]. International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, 1999: 223–238. doi: 10.1007/3-540-48910-X_16.

李增鹏, 马春光, 周红生. 全同态加密研究[J]. 密码学报, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208

LI Zengpeng, MA Chunguang, and ZHOU Hongsheng. Overview on fully homomorphic encryption[J]. Journal of Cryptologic Research, 2017, 4(6): 561–578. doi: 10.13868/j.cnki.jcr.000208

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: 75–92. doi: 10.1007/978-3-642-40041-4_5.

宋新霞, 陈智罡. 基于抽象解密结构的全同态加密构造方法分析[J]. 电子与信息学报, 2018, 40(7): 1669–1675. doi: 10.11999/JEIT170997

SONG Xinxia and CHEN Zhigang. Analysis of constructing fully homomorphic encryption based on the abstract decryption structure[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1669–1675. doi: 10.11999/JEIT170997

李宗育, 桂小林, 顾迎捷, 等. 同态加密技术及其在云计算隐私保护中的应用[J]. 软件学报, 2018, 29(7): 1830–1851. doi: 10.13328/j.cnki.jos.005354

LI Zongyu, GUI Xiaolin, GU Yingjie, et al. Survey on homomorphic encryption algorithm and its application in the privacy-preserving for cloud computing[J]. Journal of Software, 2018, 29(7): 1830–1851. doi: 10.13328/j.cnki.jos.005354

李子臣, 张卷美, 杨亚涛, 等. 基于NTRU的全同态加密方案[J]. 电子学报, 2018, 46(4): 938–944. doi: 10.3969/j.issn.0372-2112.2018.04.023

LI Zichen, ZHANG Juanmei, YANG Yatao, et al. A fully homomorphic encryption scheme based on NTRU[J]. Acta Electronica Sinica, 2018, 46(4): 938–944. doi: 10.3969/j.issn.0372-2112.2018.04.023

杨亚涛, 刘博雅, 孙亚飞, 等. NTRU全同态掩码防御方案[J]. 计算机学报, 2019, 42(12): 2742–2753. doi: 10.11897/SP.J.1016.2019.02742

YANG Yatao, LIU Boya, SUN Yafei, et al. Fully homomorphic masking defense scheme based on NTRU[J]. Chinese Journal of Computers, 2019, 42(12): 2742–2753. doi: 10.11897/SP.J.1016.2019.02742

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.

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: 3–33. doi: 10.1007/978-3-662-53887-6_1.

CHEN Hao and HAN K. Homomorphic lower digits removal and improved FHE bootstrapping[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 315–337. doi: 10.1007/978-3-319-78381-9_12.

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

CASTRYCK W, ILIASHENKO I, and VERCAUTEREN F. Homomorphic SIM²D operations: Single instruction much more data[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018: 338–359. doi: 10.1007/978-3-319-78381-9_13.

王励成, 李婧. 无噪声全同态加密浅析[J]. 密码学报, 2017, 4(6): 579–595. doi: 10.13868/j.cnki.jcr.000209

WANG Licheng and LI Jing. Simple analysis on noiseless fully homomorphic encryptions[J]. Journal of Cryptologic Research, 2017, 4(6): 579–595. doi: 10.13868/j.cnki.jcr.000209

KIPNIS A and HIBSHOOSH E. Efficient methods for practical fully-homomorphic symmetric-key encryption, randomization, and verification[J]. Urban Research & Practice, 2012, 7(3): 255–257.

NUIDA K. A simple framework for noise-free construction of fully homomorphic encryption from a special class of non-commutative groups[J]. IACR Cryptology ePrint Archive, 2014, 2017: 97.

GENTRY C. Computing on the edge of chaos: Structure and randomness in encrypted computation[J]. Electronic Colloquium on Computational Complexity, 2014, 21: 106.

LIU Dongxi. Practical fully homomorphic encryption without noise reduction[J]. IACR Cryptology ePrint Archive, 2015, 2015: 468.

YAGISAWA M. Improved fully homomorphic encryption without bootstrapping[J]. IACR Cryptology ePrint Archive, 2017, 2017: 763.

LI Jing and WANG Licheng. Noise-free symmetric fully homomorphic encryption based on noncommutative rings[J]. IACR Cryptology ePrint Archive, 2015, 2015: 641.

施佺, 韩赛飞, 黄新明, 等. 面向全同态加密的有限域FFT算法FPGA设计[J]. 电子与信息学报, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312

SHI Quan, HAN Saifei, HUANG Xinming, et al. Design of finite field FFT for fully homomorphic encryption based on FPGA[J]. Journal of Electronics &Information Technology, 2018, 40(1): 57–62. doi: 10.11999/JEIT170312

谢星, 黄新明, 孙玲, 等. 大整数乘法器的FPGA设计与实现[J]. 电子与信息学报, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836

XIE Xing, HUANG Xinming, SUN Ling, et al. FPGA design and implementation of large integer multiplier[J]. Journal of Electronics &Information Technology, 2019, 41(8): 1855–1860. doi: 10.11999/JEIT180836

SMART P N and VERCAUTEREN F. Fully homomorphic encryption with relatively small key and ciphertext sizes[C]. The 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, 2010: 420–443. doi: 10.1007/978-3-642-13013-7_25.

VAN DIJK M, GENTRY C, HALEVI S, et al. Fully homomorphic encryption over the integers[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Riviera, France, 2010: 24–43. doi: 10.1007/978-3-642-13190-5_2.

CHEON J H, CORON J, KIM J, et al. Batch fully homomorphic encryption over the integers[C]. The 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 315–335. doi: 10.1007/978-3-642-38348-9_20.

NUIDA K and KUROSAWA K. (Batch) Fully homomorphic encryption over integers for non-binary message spaces[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 537–555. doi: 10.1007/978-3-662-46800-5_21.

HOWGRAVE-GRAHAM N. Approximate integer common divisors[C]. International Cryptography and Lattices Conference, Providence, USA, 2001: 51–56. doi: 10.1007/3-540-44670-2_6.

CHEON J H and STEHLÉ D. Fully homomophic encryption over the integers revisited[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 513–536. doi: 10.1007/978-3-662-46800-5_20.

王彩芬, 成玉丹, 刘超, 等. 基于整数的多对一全同态加密方案[J]. 电子与信息学报, 2018, 40(9): 2119–2126. doi: 10.11999/JEIT171194

WANG Caifen, CHENG Yudan, LIU Chao, et al. Multiple to one fully homomorphic encryption scheme over the integers[J]. Journal of Electronics &Information Technology, 2018, 40(9): 2119–2126. doi: 10.11999/JEIT171194

JASCHKE A and ARMKNECHT F. Accelerating homomorphic computations on rational numbers[C]. The 14th International Conference on Applied Cryptography and Network Security, Guildford, UK, 2016: 405–423. doi: 10.1007/978-3-319-39555-5_22.

DOWLIN N, GILAD-BACHRACH R, LAINE K, et al. Manual for using homomorphic encryption for bioinformatics[J]. Proceedings of the IEEE, 2017, 105(3): 552–567. doi: 10.1109/JPROC.2016.2622218

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: 409–437. doi: 10.1007/978-3-319-70694-8_15.

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: 360–384. doi: 10.1007/978-3-319-78381-9_14.

MÉAUX P, JOURNAULT A, STANDAERT F X, et al. Towards stream ciphers for efficient FHE with low-noise ciphertexts[C]. The 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016: 311–343. doi: 10.1007/978-3-662-49890-3_13.

BROADBENT A and JEFFERY S. Quantum homomorphic encryption for circuits of low T-gate complexity[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 609–629. doi: 10.1007/978-3-662-48000-7_30.

DULEK Y, SCHAFFNER C, and SPEELMAN F. Quantum homomorphic encryption for polynomial-sized circuits[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 3–32. doi: 10.1007/978-3-662-53015-3_1.

薛锐, 吴迎, 刘牧华, 等. 可验证计算研究进展[J]. 中国科学: 信息科学, 2015, 45(11): 1370–1388. doi: 10.1360/N112014-00336

XUE Rui, WU Ying, LIU Muhua, et al. Progress in verifiable computation[J]. Scientia Sinica Informationis, 2015, 45(11): 1370–1388. doi: 10.1360/N112014-00336

JOHNSON R, MOLNAR D, SONG D, et al. Homomorphic signature schemes[C]. Cryptographers’ Track at the RSA Conference, San Jose, USA, 2002: 244–262. doi: 10.1007/3-540-45760-7_17.

BONEH D and FREEMAN D M. Homomorphic signatures for polynomial functions[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011: 149–168. doi: 10.1007/978-3-642-20465-4_10.

GENNARO R and WICHS D. Fully homomorphic message authenticators[C]. The 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 2013: 301–320. doi: 10.1007/978-3-642-42045-0_16.

CATALANO D and FIORE D. Practical homomorphic MACs for arithmetic circuits[C]. The 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, 2013: 336–352. doi: 10.1007/978-3-642-38348-9_21.

白平, 张薇, 李聪. 云环境下运用基于编号Merkle Hash Tree的同态认证方案[J]. 中国科技论文, 2018, 13(2): 181–185. doi: 10.3969/j.issn.2095-2783.2018.02.013

BAI Ping, ZHANG Wei, and LI Cong. Using rank-based Merkle Hash Tree into homomorphic authentication during cloud[J]. China Sciencepaper, 2018, 13(2): 181–185. doi: 10.3969/j.issn.2095-2783.2018.02.013

CATALANO D, MARCEDONE A, and PUGLISI O. Authenticating computation on groups: New homomorphic primitives and applications[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taipei, China, 2014: 193–212. doi: 10.1007/978-3-662-45608-8_11.

BONEH D, FREEMAN D, KATZ J, et al. Signing a linear subspace: Signature schemes for network coding[C]. The 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, USA, 2009: 68–87. doi: 10.1007/978-3-642-00468-1_5.

JOO C and YUN A. Homomorphic authenticated encryption secure against chosen-ciphertext attack[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taipei, China, 2014: 173–192. doi: 10.1007/978-3-662-45608-8_10.

YANG Yatao, ZHANG Shuang, YANG Junming, et al. Targeted fully homomorphic encryption based on a double decryption algorithm for polynomials[J]. Tinghua Science and Technology, 2014, 19(05):478–485. doi: 10.1109/TST.2014.6919824.

FIORE D, MITROKOTSA A, NIZZARDO L, et al. Multi-key homomorphic authenticators[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 499–530. doi: 10.1007/978-3-662-53890-6_17.

LAI R W F, TAI R K H, WONG H W H, et al. Multi-key homomorphic signatures unforgeable under insider corruption[C]. The 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, Australia, 2018: 465–492. doi: 10.1007/978-3-030-03329-3_16.

ALAGIC G, DULEK Y, SCHAFFNER C, et al. Quantum fully homomorphic encryption with verification[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 438–467. doi: 10.1007/978-3-319-70694-8_16.

UNIV SEOUL NAT R and DB FOUND. Additive homomorphic encryption and decryption method based on the CO-ACD problem and apparatus using the same[P]. South Korea, KR20160017226A, 2016.

CAMENISCH J L and LEHMANN A. Signature scheme for homomorphic message encoding functions[P]. US, 20180234254, 2018.

CHEN Wenbin, LEI Hao, and YANG Qinqin. Method, apparatus, and system for authenticating fully homomorphic message[P]. US, 20160119346, 2016.

UNIV MOHAMMED V RABAT. Quaternion-based, efficient fully-homomorphic cryptosystem[P]. Morocco, WO2018124869A1, 2018.

LAINE K, PLAYER R L, and CHEN Hao. Rational number arithmetic in homomorphic encryption[P]. US, 20180131506, 2018.

GENTRY C B, HALEVI S, and SMART N P. Homomorphic evaluation including key switching, modulus switching, and dynamic noise management[P]. US, 10057057, 2018.

MANIATAKOS M, KONSTANTINOU C, and KELIRIS A. Systems and methods for privacy-preserving functional IP verification utilizing fully homomorphic encryption[P]. US, 20160254912A1, 2016.

HOFFSTEIN J and SILVERMAN J H. Homomorphic encryption[P]. US, 20180212750, 2018.

西安电子科技大学. 基于同态加密算法的个人图像安全检索方法[P]. 中国, 108418995A, 2018.

Xidian University. Homomorphic encryption algorithm-based individual image safe retrieving method[P]. China, 108418995A, 2018.

南京邮电大学, 江苏省新通智能交通科技发展有限公司. 一种云存储中基于同态加密的密文检索方法[P]. 中国, 108011713A, 2018.

Nanjing University of Posts and Telecommunications, Jiangsu Xintong Intelligent Transportation Technology Development Co., Ltd. Ciphertext retrieval method based on homomorphic encryption in cloud storage[P]. China, 108011713A, 2018.

深圳市全同态科技有限公司, 胡和平. 一种全同态加密的密文查询方法和系统[P]. 中国, 106953722A, 2017.

Shenzhen Quantong Technology Co., Ltd and HU Heping. Fully homomorphic encryption cryptograph query method and system[P]. China, 106953722A, 2017.

HUAWEI TECH CO LTD. System and method for searching over encrypted data using homomorphic encryption[P]. China, EP3264669A1, 2018.

电子科技大学. 一种基于向量同态加密的隐私保护的线性SVM模型训练算法[P]. 中国, 108521326A, 2018.

University of Electronic Science and Technology of China. Linear SVM model training algorithm for privacy protection based on vector homomorphic encryption[P]. China, 108521326A, 2018.

陈智罡. 基于全同态加密的认证方法和用户设备以及认证服务器[P]. 中国, 107819587A, 2018.

CHEN Zhigang. Authentication method based on homomorphic encryption, user equipment and authentication server[P]. China, 107819587A, 2018.

GILAD-BACHRACH R, DOWLIN N, LAINE K, et al. CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy[C]. The 33rd International Conference on Machine Learning, New York City, USA, 2016: 201–210.

上海凭安征信服务有限公司. 一种基于加法同态加密的隐藏分散贷款额获取贷款总和的方法[P]. 中国, 107330678A, 2017.

Shanghai Ping An Credit Service Co., Ltd. Method of hiding scattered loan sum and acquiring loan sum based on based on addition homomorphic encryption[P]. China, 107330678A, 2017.

PATEL S and YUNG M M M. Systems and methods for a multiple value packing scheme for homomorphic encryption[P]. US, 20160359617, 2016.

BACON D F, BENT G A, BERGAMASCHI F A, et al. Efficient two party oblivious transfer using a leveled fully homomorphic encryption[P]. US, 20170147835, 2017.

UNIV SEOUL NAT R and DB FOUND. Method for calculating edit distance between DNA genomic sequence through homomorphic encryption[P]. South Korea, KR20170096387A, 2017.

西安邮电大学. 一种基于同态加密的智能电网用户售电方法[P]. 中国, 107172043A, 2017.

Xi’an University of Posts & Telecommunications. Intelligent power grid user power-selling method based on homomorphic encryption[P]. China, 107172043A, 2017.

DOW A, DOW E M, GILCHRIST J P, et al. Distributed computing utilizing homomorphic encryption[P]. US, 20160380761A1, 2016.

SAMSUNG SDS CO LTD. Apparatus for generating barcode using homomorphic encryption and method thereof[P]. South Korea, KR20170048767A, 2017.

北京洋浦伟业科技发展有限公司. 基于同态加密算法保护程序代码安全的方法和装置[P]. 中国, 107124261A, 2017.

Beijing Yangpu Weiye Technology Development Co., Ltd. Method and apparatus for protecting security of program code based on homomorphic encryption algorithm[P]. China, 107124261A, 2017.

南京汽车集团有限公司. 基于同态加密的信息安全传输装置、传输方法及存储方法[P]. 中国, 107682379A, 2018.

Nanjing Automobile Group. Information safety transmission device and method based on homomorphic encryption and storage method[P]. China, 107682379A, 2018.

BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 13. doi: 10.1145/2633600

HALEVI S and SHOUP V. HElib—An implementation of homomorphic encryption[EB/OL]. https://github.com/shaih/HElib/.

GENTRY C, HALEVI S, and SMART N P. Homomorphic evaluation of the AES circuit[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 850–867. doi: 10.1007/978-3-642-32009-5_49.

FAN J and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[J]. IACR Cryptology ePrint Archive, 2012, 2012: 144.

BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 868–886. doi: 10.1007/978-3-642-32009-5_50.

BAJARD J C, EYNARD J, HASAN M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[C]. The 3rd International Conference on Selected Areas in Cryptography, St. John’s, Canada, 2016: 423–442. doi: 10.1007/978-3-319-69453-5_23.

CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 377–408. doi: 10.1007/978-3-319-70694-8_14.

Relative Articles

Supplements(0)

Cited By

Proportional views