计算机应用 ›› 2016, Vol. 36 ›› Issue (4): 962-965.DOI: 10.11772/j.issn.1001-9081.2016.04.0962

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

基于环上容错学习和GSW的层次型全同态加密方案

王曌1,2, 丁勇1,2, 王会勇1,3   

  1. 1. 桂林电子科技大学 数学与计算科学学院, 广西 桂林 541004;
    2. 桂林电子科技大学 广西信息科学实验中心, 广西 桂林 541004;
    3. 中国科学院 成都计算机应用研究所, 四川 成都 610041
  • 收稿日期:2015-09-21 修回日期:2015-11-23 出版日期:2016-04-10 发布日期:2016-04-08
  • 通讯作者: 丁勇
  • 作者简介:王曌(1990-),女,山西太原人,硕士研究生,主要研究方向:全同态加密; 丁勇(1975-),男,重庆人,教授,博士,CCF会员,主要研究方向:信息安全、密码学; 王会勇(1977-),男,山东诸城人,讲师,博士研究生,主要研究方向:公钥密码学、网络信息安全。
  • 基金资助:
    广西自然科学基金资助项目(2013GXNSFBB053005);广西科学研究与技术开发计划项目(14124004-4-10);广西研究生教育创新计划项目(XJYC2012020);广西信息科学实验中心项目(2015-12)。

Leveled fully homomorphic encryption scheme based on Ring-LWE-GSW

WANG Zhao1,2, DING Yong1,2, WANG Huiyong1,3   

  1. 1. School of Mathematics and Computing Science, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
    2. Guangxi Experiment Center of Information Technology, Guilin University of Electronic Technology, Guilin Guangxi 541004, China;
    3. Chengdu Institute of Computer Applications, Chinese of Academy of Sciences, Chengdu Sichuan 610041, China
  • Received:2015-09-21 Revised:2015-11-23 Online:2016-04-10 Published:2016-04-08
  • Supported by:
    This work is partially supported by the Guangxi Natural Science Foundation (2013GXNSFBB053005), the Guangxi Development Plan of Science and Technology (14124004-4-10), the Innovation Project of Guangxi Graduate Education (XJYC2012020), the Project of Guangxi Information and Science Center (201512).

摘要: 针对目前全同态加密方案效率不高的问题,对GSW同态加密方案进行改进,提出基于环上容错学习和GSW的层次型全同态加密方案。首先,构造基于环上容错学习困难问题的基本公钥加密方案,利用近似特征向量方法使其具有加法、乘法同态性,进一步为简化噪声增长过程的分析而引入随机化函数技术;其次,证明了基本加密方案的正确性、安全性,并详细分析了同态加法、同态乘法和同态与非门操作的正确性;最后,根据密文对应噪声项的增长情况及困难问题的安全性设置方案安全参数,并利用快速傅里叶变换降低多项式乘法运算的计算复杂度,构造出层次型(Leveled)全同态加密方案。与GSW方案相比,新方案具有更小的公钥尺寸,且同态计算每个与非门的复杂度从Õ((nL)2.37)降低到Õ(nL2)。

关键词: 全同态加密, 环上容错学习, 随机化函数, 噪声增长, 层次型全同态

Abstract: Focusing on the issue that current fully homomorphic encryption schemes are not practical, Gentry-Sahai-Waters (GSW) homomorphic encryption scheme was improved and a leveled fully homomorphic encryption scheme based on Ring Learning with Error (Ring-LWE) and GSW was proposed. Firstly, a basic public key encryption scheme was constructed on Ring-LWE problem, the approximate eigenvector method was used to make it have homomorphic addition and multiplication properties, and the randomized function technique was introduced to simplify the analysis of noise blow-up. Secondly, the correctness and security of the proposed scheme was proved, the correctness of homomorphic addition, multiplication and NAND operation was analyzed in detail. Finally, security parameter was set in accordance with the noise blow-up with homomorphic evaluation and the security of Ring-LWE problem, fast Fourier transformation was adopted to reduce the computational complexity of polynomial multiplication, then a leveled fully homomorphic encryption scheme was given. The size of the pubic key in new scheme is shorter than that in GSW and the computational complexity of NAND gate is reduced from Õ((nL)2.37) to Õ(nL2).

Key words: fully homomorphic encryption, Ring Learning with Error (Ring-LWE), randomized function, noise blow-up, leveled fully homomorphic encryption

中图分类号: