Optimized CKKS scheme based on learning with errors problem

doi:10.11772/j.issn.1001-9081.2020091447

Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (6): 1723-1728.DOI: 10.11772/j.issn.1001-9081.2020091447

Special Issue: 网络空间安全

• Cyber security • Previous Articles Next Articles

Optimized CKKS scheme based on learning with errors problem

ZHENG Shangwen¹, LIU Yao¹, ZHOU Tanping^1,2, YANG Xiaoyuan^1,3

1. College of Cryptographic Engineering, Engineering University of PAP, Xi'an Shaanxi 710086, China;
2. Institute of Software, Chinese Academy of Sciences, Beijing 100090, China;
3. Key Laboratory of Network and Information Security of PAP;(Engineering University of PAP), Xi'an Shaanxi 710086, China

Received:2020-09-17 Revised:2020-11-30 Online:2021-06-10 Published:2020-12-14
Supported by:
This work is partially supported by the National Key Research and Development Program of China (2017YFB0802000), the National Natural Science Foundation of China (U1636114, 61872384), the Natural Science Foundation of Shaanxi Province (2020JQ-492), the Project of Innovative Research Team in Engineering University of PAP (KYTD201805), the Fundamental Research Funds of Engineering University of PAP (WJY201910, WJY201914, WJY201912).

优化的基于错误学习问题的CKKS方案

郑尚文¹, 刘尧¹, 周潭平^1,2, 杨晓元^1,3

1. 武警工程大学密码工程学院, 西安 710086;
2. 中国科学院软件研究所, 北京 100090;
3. 网络和信息安全武警部队重点实验室(武警工程大学), 西安 710086

通讯作者: 周潭平
作者简介:郑尚文(1998-),男,湖南宁乡人,硕士研究生,主要研究方向:同态密码、信息安全;刘尧(1993-),男,山东聊城人,硕士研究生,主要研究方向:同态密码、信息安全;周潭平(1989-),男,江西鹰潭人,讲师,博士,主要研究方向:同态密码、信息安全;杨晓元(1959-),湖南湘潭人,教授,博士生导师,硕士,主要研究方向:密码学、信息安全。
基金资助:
国家重点研发计划项目（2017YFB0802000）；国家自然科学基金资助项目（U1636114，61872384）；陕西省自然科学基金资助项目（2020JQ-492）；武警工程大学科研创新团队项目（KYTD201805）；武警工程大学基础基金资助项目（WJY201910，WJY201914，WJY201912）。

Abstract

Abstract: Focused on the issue that the CKKS (Cheon-Kim-Kim-Song) homomorphic encryption scheme based on the Learning With Errors (LWE) problem has large ciphertext, complicated calculation key generation and low homomorphic calculation efficiency in the encrypted data calculation, an optimized scheme of LWE type CKKS was proposed through the method of bit discarding and homomorphic calculation key reorganization. Firstly, the size of the ciphertext in the homomorphic multiplication process was reduced by discarding part of the low-order bits of the ciphertext vector and part of the low-order bits of the ciphertext tensor product in the homomorphic multiplication. Secondly, the method of bit discarding was used to reorganize and optimize the homomorphic calculation key, so as to remove the irrelevant extension items in powersof2 during the key exchange procedure and reduce the scale of the calculation key as well as the noise increase in the process of homomorphic multiplication. On the basis of ensuring the security of the original scheme, the proposed optimized scheme makes the dimension of the calculation key reduced, and the computational complexity of the homomorphic multiplication reduced. The analysis results show that the proposed optimized scheme reduces the computational complexity of the homomorphic calculation and calculation key generation process to a certain extent, so as to reduce the storage overhead and improve the efficiency of the homomorphic multiplication operation.

Key words: homomorphic encryption, Learning With Errors (LWE) problem, low-order bits discarding, calculation key, computational complexity

摘要： 针对基于错误学习（LWE）问题的CKKS同态加密方案在密态数据计算中存在的密文大、计算密钥生成复杂以及同态计算效率低的缺陷，运用比特丢弃和同态计算密钥重组的方法，提出了一种优化的LWE型CKKS方案。首先，丢弃密文向量的部分低位比特和同态乘法计算中密文张量积的部分低位比特，从而减小了同态乘法过程中的密文规模；其次，针对比特丢弃对同态计算密钥进行重组和优化，从而去除密钥交换过程中powersof2含有的无关扩展项并降低计算密钥的规模和同态乘法过程中的噪声增长规模。在保证原有方案安全性的基础上，所提优化方案使得计算密钥的维度减少，使得同态乘法的计算复杂性降低。分析结果表明，所提出的优化方案在一定程度上降低了同态计算及计算密钥生成过程的计算复杂性，从而降低了存储开销并提升了同态乘法运算的效率。

关键词: 同态加密, 错误学习问题, 低位比特丢弃, 计算密钥, 计算复杂性

CLC Number:

TP309

ZHENG Shangwen, LIU Yao, ZHOU Tanping, YANG Xiaoyuan. Optimized CKKS scheme based on learning with errors problem[J]. Journal of Computer Applications, 2021, 41(6): 1723-1728.

郑尚文, 刘尧, 周潭平, 杨晓元. 优化的基于错误学习问题的CKKS方案[J]. 计算机应用, 2021, 41(6): 1723-1728.

References

[1] GENTRY C. Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 200941st ACM Symposium on Theory of Computing. New York:ACM,2009:169-178.
[2] VAN DIJK M,GENTRY C,HALEVI S,et al. Fully homomorphic encryption over the integers[C]//Proceedings of the 2010 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 6110. Berlin:Springer,2010:24-43.
[3] BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]//Proceedings of the 2012 3rd Innovations in Theoretical Computer Science Conference. New York:ACM,2012:309-325.
[4] GENTRY C,SAHAI A,WATERS B. Homomorphic encryption from learning with errors:conceptually-simpler, asymptoticallyfaster,attribute-based[C]//Proceedings of the 2013 33rd Annual Cryptology Conference, LNCS 8042. Berlin:Springer, 2013:75-92.
[5] LÓPEZ-ALT A,TROMER E,VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multi-key fully homomorphic encryption[C]//Proceedings of the 2012 44th Annual ACM Symposium on Theory of Computing. New York:ACM, 2012:1219-1234.
[6] CHILLOTTI I,GAMA N,GEORGIEVA M,et al. Faster fully homomorphic encryption:bootstrapping in less than 0.1 seconds[C]//Proceedings of the 201622nd International Conference on the Theory and Application of Cryptology and Information Security, LNCS 10031. Berlin:Springer,2016:3-33.
[7] CHEON J H,KIM A,KIM M,et al. Homomorphic encryption for arithmetic of approximate numbers[C]//Proceedings of the 2017 23rd International Conference on the Theory and Applications of Cryptology and Information Security, LNCS 10624. Cham:Springer,2017:409-437.
[8] LAUTER K,LÓPEZ-ALT A,NAEHRIG M. Private computation on encrypted genomic data[C]//Proceedings of the 2014 3rd International Conference on Cryptology and Information Security in Latin America,LNCS 8895. Cham:Springer,2014:3-27.
[9] WANG S,ZHANG Y,DAI W,et al. HEALER:Homomorphic computation of ExAct Logistic rEgRession for secure rare disease variants analysis in GWAS[J]. Bioinformatics,2016,32(2):211-218.
[10] CHEON J H,KIM M,LAUTER K. Homomorphic computation of edit distance[C]//Proceedings of the 2015 International Conference on Financial Cryptography and Data Security,LNCS 8976. Berlin:Springer,2015:194-212.
[11] HAMLIN A,SHELAT A,WEISS M,et al. Multi-key searchable encryption,revisited[C]//Proceedings of the 201821st IACR International Conference on Practice and Theory of Public-Key Cryptography,LNCS 10769. Cham:Springer,2018:95-124.
[12] 王永建, 张健, 程少豫, 等. 面向云计算的同态加密改进设计[J]. 信息网络安全, 2017, 17(3):21-26.(WANG Y J,ZHANG J,CHENG S Y,et al. An improved design of homomorphic encryption for cloud computing[J]. Netinfo Security,2017,17(3):21-26.)
[13] CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[C]//Proceedings of the 2018 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 10820. Cham:Springer,2018:360-384.
[14] CHEON J H,HAN K,KIM A,et al. A full RNS variant of approximate homomorphic encryption[C]//Proceedings of the 2018 25th International Conference on Selected Areas in Cryptography,LNCS 11349. Cham:Springer,2018:347-368.
[15] CHEN H,CHILLOTTI I,SONG Y. Improved bootstrapping for approximate homomorphic encryption[C]//Proceedings of the 2019 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques,LNCS 11477. Cham:Springer,2019:34-54.
[16] CHEN H, DAI W, KIM M, et al. Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York:ACM,2019:395-412.
[17] BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from(standard) LWE[C]//Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. Piscataway:IEEE,2011:97-106.
[18] ZHOU T,YANG X,LIU L,et al. Faster bootstrapping with multiple addends[J]. IEEE Access,2018,6:49868-49876.
[19] REGEV O. On lattices, learning with errors, random linear codes,and cryptography[J]. Journal of the ACM,2009,56(6):Article No. 34.
[20] 车小亮, 周昊楠, 周潭平, 等. 基于NTRU的多密钥同态加密方案解密结构[J]. 计算机应用, 2020, 40(7):1959-1964.(CHE X L,ZHOU H N,ZHOU T P,et al. Decryption structure of multikey homomorphic encryption scheme based on NTRU[J]. Journal of Computer Applications,2020,40(7):1959-1964.)
[21] GENTRY C,HALEVI S,SMART N P. Homomorphic evaluation of the AES circuit[C]//Proceedings of the 201232nd Annual Cryptology Conference,LNCS 7417. Berlin:Springer,2012:850-867.

Optimized CKKS scheme based on learning with errors problem

优化的基于错误学习问题的CKKS方案

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	MA Minyao, LIU Zhuo, XU Yi, WU Lian. Private-preserving determination problem of integer-interval positional relationship [J]. Journal of Computer Applications, 2020, 40(9): 2657-2664.
[2]	MA Minyao, WU Lian, LIU Zhuo, XU Yi. Privacy-preserving determination of integer point-interval relationship [J]. Journal of Computer Applications, 2020, 40(7): 1983-1988.
[3]	CHE Xiaoliang, ZHOU Haonan, ZHOU Tanping, LI Ningbo, YANG Xiaoyuan. Decryption structure of multi-key homomorphic encryption scheme based on NTRU [J]. Journal of Computer Applications, 2020, 40(7): 1959-1964.
[4]	MA Minyao, XU Yi, LIU Zhuo. Privacy preserving Hamming distance computing problem of DNA sequences [J]. Journal of Computer Applications, 2019, 39(9): 2636-2640.
[5]	YU Qingfei, TU Guangsheng, LI Ningbo, ZHOU Tanping. Multi-hop multi-policy attributed-based fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(8): 2326-2332.
[6]	TU Guangsheng, YANG Xiaoyuan, ZHOU Tanping. Efficient identity-based multi-identity fully homomorphic encryption scheme [J]. Journal of Computer Applications, 2019, 39(3): 750-755.
[7]	ZHANG En, JIN Ganggang. Cloud outsourcing multiparty private set intersection protocol based on homomorphic encryption and Bloom filter [J]. Journal of Computer Applications, 2018, 38(8): 2256-2260.
[8]	BAI Ping, ZHANG Wei. Fully homomorphic encryption scheme based on learning with errors under multi-attribute environment [J]. Journal of Computer Applications, 2018, 38(5): 1377-1382.
[9]	DAI Xiaokang, CHEN Changbo, WU Wenyuan. New voting protocol based on homomorphic threshold cryptography [J]. Journal of Computer Applications, 2018, 38(4): 1036-1040.
[10]	LUO Xiaoshuang, YANG Xiaoyuan, LI Cong, WANG Xu'an. Publicly verifiable outsourced computation scheme for multivariate polynomial based on two-server model [J]. Journal of Computer Applications, 2018, 38(2): 321-326.
[11]	ZHOU Wei, GUO Mengyu, XIANG Danlei. Improved QRD-M detection algorithm for spatial modulation system [J]. Journal of Computer Applications, 2018, 38(10): 2950-2954.
[12]	LI Zhenlin, ZHANG Wei, BAI Ping, WANG Xu'an. BGN type outsourcing the decryption of attribute-based encryption ciphertexts [J]. Journal of Computer Applications, 2017, 37(8): 2287-2291.
[13]	LI Zhenlin, ZHANG Wei, DAI Xiaoming. Predicate encryption scheme supporting secure multi-party homomorphic multiplicative computation [J]. Journal of Computer Applications, 2017, 37(4): 999-1003.
[14]	LI Mingxiang, LIU Zhao, ZHANG Mingyan. Fully homomorphic encryption scheme without Gaussian noise [J]. Journal of Computer Applications, 2017, 37(12): 3430-3434.
[15]	WANG Jie, LU Jianzhu, ZENG Xiaofei. Data aggregation scheme for wireless sensor network to timely determine compromised nodes [J]. Journal of Computer Applications, 2016, 36(9): 2432-2437.