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

所属专题: 网络空间安全

• 网络空间安全 • 上一篇    下一篇

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

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

  1. 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 Shangwen1, LIU Yao1, ZHOU Tanping1,2, YANG Xiaoyuan1,3   

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

摘要: 针对基于错误学习(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

中图分类号: