2017 年 5 月 Journal on Communications May 2017
2017098-1
第 38 卷第 5 期 通 信 学 报 Vol.38
No.5
新的格上基于身份的全同态加密方案
汤永利,胡明星,刘琨,叶青,闫玺玺
(河南理工大学计算机科学与技术学院,河南 焦作 454000)
摘 要:分析以往格上基于身份的全同态加密方案,指出方案效率低的根本原因在于陷门生成和原像采样过程的
复杂度过高,为此提出一种新的解决方案。先将新型陷门函数与对偶容错学习(LWE,learning with errors)算法
有机结合,构造一种新的格上基于身份的加密方案;再利用特征向量方法转化为格上基于身份的全同态加密方案。
对比分析表明,所提方案的陷门生成复杂度显著降低,原像采样复杂度约降低为以往方案的
1
3
,SIVP 近似因子
缩小为以往方案的
1
m
。在标准模型下,方案安全性归约至判定性 LWE 的难解性,并包含严格的安全性证明。
关键词:格;全同态加密;基于身份加密;标准模型;密码学
中图分类号:TP309 文献标识码:A
Novel identity-based fully homomorphic
encryption scheme from lattice
TANG Yong-li, HU Ming-xing, LIU Kun, YE Qing, YAN Xi-xi
(College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo 454000, China)
Abstract: The previous identity-based homomorphic encryption schemes from lattice was analyzed. That the high com-
plexity in previous schemes was mainly caused by trapdoor generation and preimage sampling was pointed out. A new
solution was proposed. A novel identity-based encryption scheme from lattice by combining new trapdoor function and
dual-LWE algorithm organically was constructed, and it was transformed to an identity-based fully homomorphic encryp-
tion scheme from lattice by employing the idea of eigenvector. Comparative analysis shows that the scheme’s complexity
of trapdoor generation has a significant reduction, the complexity of preimage sampling has a nearly three-fold reduction,
and the SIVP approximation factor has a
m times reduction. The security of the proposed scheme strictly reduces to the
hardness of decisional learning with errors problem in the standard model.
Key words: lattice, fully homomorphic encryption, identity-based encryption, standard model, cryptography
1 引言
近几年,云计算在实现中遇到的问题之一就是
如何保证数据的私密性,全同态加密可以很好地解
决这个技术难题。1978 年,Rivest 等
[1]
最早提出利
用同态加密来保护数据私密性的想法。直到 2009
年,IBM 研究员 Gentry
[2]
基于理想格提出第一个全
同态加密方案,此后全同态加密方案的设计成为密
码学研究领域的热点。
全同态加密作为公钥加密的一种,需要考虑在
云环境和安全多方计算中身份认证的问题,一般方
法是引入公钥证书,但证书中心的存在也为整个密
收稿日期:2016-11-07;修回日期:2017-03-29
通信作者:叶青,yeqing@hpu.edu.cn
基金项目:国家自然科学基金资助项目(No.61300216);河南省科技厅基金资助项目(No.142300410147);河南省教育厅基
金资助项目(No.12A520021, No.16A520013);河南理工大学博士基金资助项目(No.B2014-044, No.B2013-043)
Foundation Items: The National Natural Science Foundation of China (No.61300216), The Project of Science and Technology De-
artment of Henan Province (No.142300410147), The Project of Education Department of Henan Province (No.12A520021,
o.16A520013), Doctoral Fund of Henan Polytechnic University (No.B2014-044, No.B2013-043)
doi:10.11959/j.issn.1000-436x.2017098