新的格上基于身份的全同态加密方案

doi:10.11959/j.issn.1000-436x.2017098

通信学报 ›› 2017, Vol. 38 ›› Issue (5): 39-47.doi: 10.11959/j.issn.1000-436x.2017098

新的格上基于身份的全同态加密方案

汤永利,胡明星,刘琨,叶青,闫玺玺

河南理工大学计算机科学与技术学院，河南焦作 454000

修回日期:2017-03-29 出版日期:2017-05-01 发布日期:2017-05-28
作者简介:汤永利（1972-），男，河南孟州人，博士后，河南理工大学教授、硕士生导师，主要研究方向为信息安全、密码学。|胡明星（1994-），男，河南鹿邑人，河南理工大学硕士生，主要研究方向为密码学。|刘琨（1978-），女，河南焦作人，河南理工大学副教授、硕士生导师，主要研究方向为信息安全、密码学。|叶青（1981-），女，辽宁营口人，博士，河南理工大学讲师、硕士生导师，主要研究方向为密码学。|闫玺玺（1985-），女，河南灵宝人，河南理工大学讲师、硕士生导师，主要研究方向为密码学。
基金资助:
国家自然科学基金资助项目(61300216);河南省科技厅基金资助项目(142300410147);河南省教育厅基金资助项目(12A520021);河南省教育厅基金资助项目(16A520013);河南理工大学博士基金资助项目(B2014-044);河南理工大学博士基金资助项目(B2013-043)

Novel identity-based fully homomorphic encryption scheme from lattice

Yong-li TANG,Ming-xing HU,Kun LIU,Qing YE,Xi-xi YAN

College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo 454000,China

Revised:2017-03-29 Online:2017-05-01 Published:2017-05-28
Supported by:
The National Natural Science Foundation of China(61300216);The Project of Science and Technology Department of Henan Province(142300410147);The Project of Education Department of Henan Province(12A520021);The Project of Education Department of Henan Province(16A520013);Doctoral Fund of Henan Polytechnic University(B2014-044);Doctoral Fund of Henan Polytechnic University(B2013-043)

摘要/Abstract

摘要：

分析以往格上基于身份的全同态加密方案，指出方案效率低的根本原因在于陷门生成和原像采样过程的复杂度过高，为此提出一种新的解决方案。先将新型陷门函数与对偶容错学习（LWE，learning with errors）算法有机结合，构造一种新的格上基于身份的加密方案；再利用特征向量方法转化为格上基于身份的全同态加密方案。对比分析表明，所提方案的陷门生成复杂度显著降低，原像采样复杂度约降低为以往方案的 $\frac{1}{3}$ ，SIVP 近似因子缩小为以往方案的 $\frac{1}{\sqrt{m}}$ 。在标准模型下，方案安全性归约至判定性LWE的难解性，并包含严格的安全性证明。

关键词: 格, 全同态加密, 基于身份加密, 标准模型, 密码学

Abstract:

The previous identity-based homomorphic encryption schemes from lattice was analyzed.That the high complexity 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 encryption 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 $\sqrt{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

中图分类号:

TP309

汤永利,胡明星,刘琨,叶青,闫玺玺. 新的格上基于身份的全同态加密方案[J]. 通信学报, 2017, 38(5): 39-47.

Yong-li TANG,Ming-xing HU,Kun LIU,Qing YE,Xi-xi YAN. Novel identity-based fully homomorphic encryption scheme from lattice[J]. Journal on Communications, 2017, 38(5): 39-47.

图/表 3

表1

符号说明"

符号	意义
A^m×n	m行n列矩阵
A _i	矩阵A的第i行
u	向量，默认为列向量形式
u[i]	向量u的第i个分量
u^T	向量u的转置
$‖ S ‖$	向量集合S 的长度，等于其中所有向量欧几里得范数的最大值
$‖ \tilde{S} ‖$	向量集合S 的Gram-Schmidt范数的最大值
s ₁ (R)	矩阵R的最大奇异值
negl(n)	n的可忽略函数：f(n)＜(n^?c)，c 为常数
poly (n)	n的多项式函数：f(n)=O(n^c)，c 为常数

表1

表2

IBE方案性能分析对比"

比较参数	Agrawal 2010方案	Agrawal 2012方案	Wang方案	本文方案
m	6nlbq	5nlbq	6nlbq	2nlbq
σ	$m ω (\sqrt{lb n})$	mlbmω (lbn )	(m+6)ω (lbn )	$\sqrt{m} ω (\sqrt{lb n})$
q	$\sqrt{n m^{3}} ω (lb n)$	$\sqrt{n m^{3}} lb m ω {(lb n)}^{\frac{3}{2}}$	$(\sqrt{n m^{3}} + 6 \sqrt{n m}) ω {(lb n)}^{\frac{3}{2}}$	$m \sqrt{n} ω (lb n)$
β	$\sqrt{m^{3}} ω (\sqrt{lb n})$	$\sqrt{m^{3}} lb m ω (lb n)$	$(\sqrt{n m^{3}} + 6 \sqrt{n m}) ω (lb n)$	$m ω (\sqrt{lb n})$
α	${(\sqrt{m^{3}} ω (lb n))}^{- 1}$	${(\sqrt{m^{3}} lb m ω {(lb n)}^{\frac{3}{2}})}^{- 1}$	${((\sqrt{m^{3}} + 6 \sqrt{n m}) ω {(lb n)}^{\frac{3}{2}})}^{- 1}$	${(m ω (lb n))}^{- 1}$

表2

表3

参考文献 21

[1]	RIVEST R , ADLEMAN L , DERTOUZOS M . On data banks and privacy homomorphisms[C]// IEEE 17nd Annual Symposium on Foundations of Computer Science (FOCS1978). 1978: 169-177.
[2]	GENTRY C , . Fully homomorphic encryption using ideal lattices[C]// The 41rd ACM Symposium on Theory of Computing (STOC2009). 2009: 169-178.
[3]	DUCAS L , MICCIANCIO D.FHEW . Bootstrapping homomorphic encryption in less than a second[C]// Advances in Cryptology EUROCRYPT 2016. 2015: 617-640.
[4]	BRAKERSKI Z , PERLMAN R . Lattice-based fully dynamic multi-key FHE with short ciphertexts[C]// Advances in Cryptology CRYPTO 2016. 2016: 190-213.
[5]	NUIDA K , KUROSAWA K . (Batch) Fully homomorphic encryption over integers for non-binary message spaces[C]// Advances in Cryptology EUROCRYPT 2015. 2015: 537-555.
[6]	光焱, 祝跃飞, 费金龙 ,等. 利用容错学习问题构造基于身份的全同态加密体制[J]. 通信学报, 2014,35(2): 111-117.
	GUANG Y , ZHU Y F , FEI J L ,et al. Identity-based fully homomorphic encryption from learning with error problem[J]. Journal on Communications, 2014,35(2): 111-117.
[7]	康元基, 顾纯祥, 郑永辉 ,等. 利用特征向量构造基于身份的全同态加密体制[J]. 软件学报, 2016,27(6): 1487-1497.
	KANG Y J , GU C X , ZHENG Y H ,et al. Identity-based fully homomorphic encryption from eigenvector[J]. Journal of Software, 2016,27(6): 1487-1497.
[8]	GENTRY C , SAHAI A , WATERS B.Homomorphic encryption from learning with errors . Conceptually-simpler,asymptotically-faster,attribute-based[C]// Advances in Cryptology CRYPTO 2013. 2013: 75-92.
[9]	CLEAR M , MCGOLDRICK C . Multi-identity and multi-key leveled FHE from learning with errors[C]// Advances in Cryptology CRYPTO 2015. 2015: 630-656.
[10]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[C]// The 40th ACM Symposium on Theory of Computing(STOC2008). 2008: 197-206.
[11]	AJTAIM . Generating hard instances of the short basis problem[C]// Automata,Languages and Programming(ICALP1999). 1999: 1-9.
[12]	AGRAWAL S , BONEHD , BOYEN X . Efficient lattice (H)IBE in the standard model[C]// Advances in Cryptology EUROCRYPT2010. 2010: 553-572.
[13]	APON D , FAN X , LIU F H . Fully-secure lattice-based IBE as compact as PKE[R]. IACRePrint Cryptography Archive, 2016.
[14]	YAMADA S , . Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters[C]// Advances in Cryptology EUROCRYPT 2016. 2016: 32-62.
[15]	ALWEN J , PEIKERT C . Generating shorter bases for hard random lattices[C]// The 26th International Symposium on Theoretical Aspects of Computer Science. 2009: 535-553.
[16]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices,simpler,tighter,faster,smaller[C]// Advances in Cryptology EUROCRYPT 2012. 2012: 700-718.
[17]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. The Annual ACM Symposium on Theory of Computing, 2009,56(6): 84-93.
[18]	AGRAWAL S , BOYEN X , VAIKUNTANATHAN V ,et al. Functional encryption for threshold functions(or fuzzy IBE) from lattices[C]// The 15th International Conference on Practice and Theory in Public Key Cryptography. 2012: 280-297.
[19]	WANG F H , LIU Z H , WANG C X . Full secure identity-based encryption scheme with short public key size over lattices in the standard model[J]. The International Journal of Computer Mathematics, 2016,93(6): 854-863.
[20]	DODIS Y , OSTROVSKY R , REYZIN L . Fuzzy extractors.How to generate strong keys from biometrics and other noisy data[J]. The Society for Industrial and Applied Mathematics (SIAM), 2008,38(1): 97-139.
[21]	PEIKERT C , . An efficient and parallel gaussian sampler for lattices[C]// Advances in Cryptology CRYPTO 2010. 2010: 80-97.

IBFHE方案	标准模型	运算密钥	陷门生成复杂度(×10¹⁰)	原像采样复杂度(×10¹⁰)	公钥尺寸/MB	私钥尺寸/KB
GY方案	否	有	乘次数64.65加次数64.65	乘次数69.04加次数68.80	50.4	76.2
Clear方案	否	无	乘次数64.65加次数64.65	乘次数69.04加次数68.80	472.6	1.66
本文方案	是	无	乘次数1.374加次数1.374	乘次数23.15加次数23.15	472.5	1.66

新的格上基于身份的全同态加密方案

Novel identity-based fully homomorphic encryption scheme from lattice

在线阅读

PDF下载

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 3

参考文献 21

相关文章 15

Metrics

推荐阅读 0

[1]	陈晓玉, 孙连峰, 张钇涵. 具有大零相关区宽度的Ⅱ型偶长Z-互补对构造方法[J]. 通信学报, 2023, 44(6): 167-174.
[2]	杨亚涛, 刘德莉, 刘培鹤, 曾萍, 肖嵩. BFV-Blockchainvoting：支持BFV全同态加密的区块链电子投票系统[J]. 通信学报, 2022, 43(9): 100-111.
[3]	廉欢欢, 侯慧莹, 赵运磊. 后量子基于验证元的三方口令认证密钥交换协议[J]. 通信学报, 2022, 43(4): 95-106.
[4]	曹阳, 钟烨, 彭醇陵, 彭小峰. 基于混合供能和能量协作的异构网络能量效率优化算法[J]. 通信学报, 2022, 43(3): 135-147.
[5]	毛伊敏, 甘德瑾, 廖列法, 陈志刚. 基于Spark框架和ASPSO的并行划分聚类算法[J]. 通信学报, 2022, 43(3): 148-163.
[6]	郭渊博, 尹安琪. 基于格的口令认证密钥交换协议综述[J]. 通信学报, 2022, 43(12): 172-187.
[7]	郭红伟, 朱策, 杨栩, 罗雷. 基于失真反向传播的时域依赖率失真优化[J]. 通信学报, 2022, 43(12): 222-232.
[8]	董有恒, 赵耿, 马英杰. 基于分区初等元胞自动机的二维伪随机耦合映像格系统及其动态特性[J]. 通信学报, 2022, 43(1): 71-82.
[9]	田有亮, 蒋小霞. 通用可组合框架下的公平理性委托计算[J]. 通信学报, 2021, 42(9): 106-119.
[10]	侯红霞, 张明瑞, 赵艳琦, 董晓丽. 素数阶群上基于非对称对的身份基环签名[J]. 通信学报, 2021, 42(9): 155-164.
[11]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[12]	王宏禹,邱天爽. 特征算子谱表示与特征展开的研究[J]. 通信学报, 2020, 41(5): 1-8.
[13]	于斌, 黄海, 刘志伟, 赵石磊, 那宁. 面向多椭圆曲线的高速标量乘法器设计与实现[J]. 通信学报, 2020, 41(12): 100-109.
[14]	杜蛟,刘春红,庞善起. 4t-1元旋转对称2-弹性函数的构造[J]. 通信学报, 2020, 41(11): 169-175.
[15]	房礼国,付正欣,胡浩,沈刚,郁滨. 基于区域递增式彩色视觉密码的栅格地图多级分存算法研究[J]. 通信学报, 2019, 40(9): 24-32.