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

doi:10.11772/j.issn.1001-9081.2020091447

计算机应用 ›› 2021, Vol. 41 ›› Issue (6): 1723-1728.DOI: 10.11772/j.issn.1001-9081.2020091447

所属专题：网络空间安全

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

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

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

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

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).

摘要/Abstract

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

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

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

中图分类号:

TP309

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

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.

参考文献

[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.

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

Optimized CKKS scheme based on learning with errors problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	马敏耀, 刘卓, 徐艺, 吴恋. 隐私保护整数区间位置关系判定问题[J]. 计算机应用, 2020, 40(9): 2657-2664.
[2]	马敏耀, 吴恋, 刘卓, 徐艺. 隐私保护整数点和区间关系判定问题[J]. 计算机应用, 2020, 40(7): 1983-1988.
[3]	车小亮, 周昊楠, 周潭平, 李宁波, 杨晓元. 基于NTRU的多密钥同态加密方案解密结构[J]. 计算机应用, 2020, 40(7): 1959-1964.
[4]	马敏耀, 徐艺, 刘卓. 隐私保护DNA序列汉明距离计算问题[J]. 计算机应用, 2019, 39(9): 2636-2640.
[5]	余卿斐, 涂广升, 李宁波, 周潭平. 多跳多策略属性基全同态加密方案[J]. 计算机应用, 2019, 39(8): 2326-2332.
[6]	涂广升, 杨晓元, 周潭平. 高效的身份基多用户全同态加密方案[J]. 计算机应用, 2019, 39(3): 750-755.
[7]	张恩, 金刚刚. 基于同态加密和Bloom过滤器的云外包多方隐私集合比较协议[J]. 计算机应用, 2018, 38(8): 2256-2260.
[8]	白平, 张薇. 多属性环境下基于容错学习的全同态加密方案[J]. 计算机应用, 2018, 38(5): 1377-1382.
[9]	代小康, 陈长波, 吴文渊. 基于同态门限密码体制的投票协议[J]. 计算机应用, 2018, 38(4): 1036-1040.
[10]	罗小双, 杨晓元, 李聪, 王绪安. 基于双服务器模型的可公开验证多元多项式外包计算方案[J]. 计算机应用, 2018, 38(2): 321-326.
[11]	李镇林, 张薇, 白平, 王绪安. 基于属性的BGN型密文解密外包方案[J]. 计算机应用, 2017, 37(8): 2287-2291.
[12]	李镇林, 张薇, 戴晓明. 支持安全多方同态乘积计算的谓词加密方案[J]. 计算机应用, 2017, 37(4): 999-1003.
[13]	李明祥, 刘照, 张明艳. 无高斯噪声的全同态加密方案[J]. 计算机应用, 2017, 37(12): 3430-3434.
[14]	王洁, 卢建朱, 曾小飞. 可及时确定受攻击节点的无线传感器网络数据聚合方案[J]. 计算机应用, 2016, 36(9): 2432-2437.
[15]	戴晓明, 张薇, 郑志恒, 李镇林. 基于容错学习的GSW-型全同态层次型IBE方案[J]. 计算机应用, 2016, 36(7): 1856-1860.