新的格上基于身份的分级加密方案

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

通信学报 ›› 2017, Vol. 38 ›› Issue (11): 54-64.doi: 10.11959/j.issn.1000-436x.2017219

新的格上基于身份的分级加密方案

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

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

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

Novel hierarchical identity-based encryption scheme from lattice

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

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

Revised:2017-06-05 Online:2017-11-01 Published:2017-12-13
Supported by:
The “13th Five-Year” National Crypto Development Foundation(MMJJ20170122);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(18A413001);The Project of Education Department of Henan Province(16A520013);Doctoral Fund of Henan Polytechnic University(B2014-044);Doctoral Fund of Henan Polytechnic University(B2016-36)

摘要/Abstract

摘要：

针对格上基于身份的分级加密（HIBE,hierarchical identity-based encryption）体制中用户密钥提取算法复杂度过高和陷门尺寸膨胀率大的问题，提出一种新的HIBE方案。首先，利用隐式扩展法对HIBE方案中的原像采样算法优化，然后，结合MP12陷门派生算法提出一种高效的HIBE用户密钥提取算法，并基于该算法结合对偶 LWE 算法完成 HIBE 方案构造。对比分析表明，所提方案的效率较同类方案在系统建立和用户密钥提取阶段均有提升，陷门尺寸与系统分级深度仅成线性增长关系，且优化后的原像采样算法一定程度上可解决MP12陷门派生算法在陷门派生后高斯参数增长的问题。在标准模型下，方案安全性归约至判定性 LWE 问题的难解性，并包含严格的安全性证明。

关键词: 格, 基于身份的分级加密, 陷门派生, 标准模型, 容错学习

Abstract:

Aiming at the high complexity in user’s private key extraction and large expansion ratio of trapdoor size in previous hierarchical identity-based encryption (HIBE) schemes,a new HIBE scheme was proposed.The implicit extension method to improve preimage sampling algorithm was used,and then combined the improved algorithm with MP12 trapdoor delegation algorithm to construct an efficient HIBE user’s private key extraction algorithm.Finally,the new extraction algorithm and the Dual-LWE algorithm was integrated to complete the scheme.Compared with the similar schemes,the efficiency of the proposed scheme was improved in system establishment and user’s private key extraction stage,the trapdoor size grows only linearly with the system hierarchical depth,and the improved preimage sample algorithm partly solves the Gaussian parameter increasing problem induced by MP12 trapdoor delegation.The security of the proposed scheme strictly reduces to the hardness of decisional learning with errors problem in the standard model.

Key words: lattice, hierarchical identity-based encryption, trapdoor delegation, standard model, learning with error

中图分类号:

TP309

叶青,胡明星,汤永利,刘琨,闫玺玺. 新的格上基于身份的分级加密方案[J]. 通信学报, 2017, 38(11): 54-64.

Qing YE,Ming-xing HU,Yong-li TANG,Kun LIU,Xi-xi YAN. Novel hierarchical identity-based encryption scheme from lattice[J]. Journal on Communications, 2017, 38(11): 54-64.

图/表 6

表1

符号说明"

符号	说明
A ^m×n	m 行n列矩阵
A_i	矩阵A的第i行
u	向量，默认为列向量形式
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

参数设定"

参数	值
m	2nlbq
σ_e	$w ω (\sqrt{lb n})$
α_e	${[w m ω (\sqrt{lb n})]}^{- 1}$
q	$w \sqrt{m^{3}} ω (\sqrt{lb n})$

表2

表3

IBE方案效率分析对比"

方案	格的维数	陷门尺寸/MB	陷门生成复杂度（ $ℤ_{q}$ 乘加次数）	原像采样复杂度（ $ℤ_{q}$ 乘加次数）	用户公钥尺寸/MB	用户私钥尺寸/KB
文献[5]方案	13 632	22.15	乘≈64.65×10¹⁰加≈64.64×10¹⁰	乘≈55.75×10⁷加≈74.33×10⁷	22.15	79.92
文献[6]方案	40 896	199.38	乘≈15.31×10¹²加≈15.30×10¹²	乘≈50.17×10⁸加≈66.90×10⁸	66.72	239.52
本文方案	13 632	5.54	乘≈13.74×10⁹加≈13.73×10⁹	乘≈96.87×10⁶加≈96.87×10⁶	11.08	39.84

表3

表4

HIBE方案派生前效率分析对比"

方案	陷门维数	用户公钥维数	陷门尺寸/MB	陷门质量	用户公钥尺寸/MB	用户私钥尺寸/KB	明文—密文扩展率	计算效率（ $ℤ_{q}$ 乘加次数）
方案	陷门维数	用户公钥维数	陷门尺寸/MB	陷门质量	用户公钥尺寸/MB	用户私钥尺寸/KB	明文—密文扩展率	陷门生成	原像采样	加密＆解密
CHKP方案	40 896	81 792	199.38	$O (\sqrt{n lb q})$	66.48	9.98	1 963 032	乘≈15.31×10¹²	乘≈50.17×10⁸	乘≈65.97×10⁸
CHKP方案	40 896	81 792	199.38	$O (\sqrt{n lb q})$	66.48	9.98	1 963 032	加≈15.30×10¹²	加≈66.90×10⁸	加≈65.74×10⁸
ABB方案	34 080	68 160	138.46	$O (\sqrt{n lb q})$	55.44	8.32	1 635 864	乘≈12.75×10¹²	乘≈34.84×10⁸	乘≈54.98×10⁸
ABB方案	34 080	68 160	138.46	$O (\sqrt{n lb q})$	55.44	8.32	1 635 864	加≈12.74×10¹²	加≈46.46×108	加≈54.78×10⁸
YZWLY方案	13 632	27 264	22.15	$O (\sqrt{n \ln q})$	22.08	3.33	654 360	乘≈64.65×10¹⁰	乘≈55.75×10⁷	乘≈21.99×10⁸
YZWLY方案	13 632	27 264	22.15	$O (\sqrt{n \ln q})$	22.08	3.33	654 360	加≈64.64×10¹⁰	加≈74.33×10⁷	加≈21.91×10⁸
WWL方案	40 896	40 896	199.38	$O (n^{2} {lb}^{2} n \cdot {lb}^{2} q)$	33.23	4.99	981 528	乘≈15.31×10¹²	乘≈50.17×108	乘≈32.99×10⁸
WWL方案	40 896	40 896	199.38	$O (n^{2} {lb}^{2} n \cdot {lb}^{2} q)$	33.23	4.99	981 528	加≈15.30×10¹²	加≈66.90×10⁸	加≈32.87×10⁸
本文方案	6 816	13 632	5.54	$O (\sqrt{\bar{m}} + \sqrt{w})$	11.08	1.66	327 192	乘≈13.74×10⁹	乘≈96.87×10⁶	乘≈11.00×10⁸
本文方案	6 816	13 632	5.54	$O (\sqrt{\bar{m}} + \sqrt{w})$	11.08	1.66	327 192	加≈13.73×10⁹	加≈96.87×10⁶	加≈10.96×10⁸

表4

表5

HIBE方案派生后效率分析对比"

方案	陷门维数	用户公钥维数	陷门尺寸/MB	陷门质量	用户公钥尺寸/MB	用户私钥尺寸/kB	明文—密文扩展率	计算效率（ $ℤ_{q}$ 乘加次数）
方案	陷门维数	用户公钥维数	陷门尺寸/MB	陷门质量	用户公钥尺寸/MB	用户私钥尺寸/kB	明文—密文扩展率	陷门派生	原像采样	加密＆解密
CHKP方案	81 792	122 688	797.50	$O (\sqrt{n \ln q})$	99.69	14.98	2 944 536	乘≈16.42×10¹⁴	乘≈20.07×10⁹	乘≈98.96×10⁸
CHKP方案	81 792	122 688	797.50	$O (\sqrt{n \ln q})$	99.69	14.98	2 944 536	加≈21.89×10¹⁴	加≈26.76×10⁹	加≈98.61×10⁸
ABB方案	68 160	102 240	553.82	$O (\sqrt{n \ln q})$	83.04	12.48	2 453 784	乘≈95.00×10¹³	乘≈13.94×10⁹	乘≈82.46×10⁸
ABB方案	68 160	102 240	553.82	$O (\sqrt{n \ln q})$	83.04	12.48	2 453 784	加≈12.67×10¹⁴	加≈18.58×10⁹	加≈82.17×10⁸
YZWLY方案	27 264	40 896	88.61	$O (\sqrt{n \ln q})$	33.12	4.99	98 1528	乘≈60.80×10¹²	乘≈22.30×10⁸	乘≈32.99×10⁸
YZWLY方案	27 264	40 896	88.61	$O (\sqrt{n \ln q})$	33.12	4.99	98 1528	加≈81.06×10¹²	加≈29.73×10⁸	加≈32.87×10⁸
WWL方案	40 896	40 896	199.38	$O (n^{3} {lb}^{3} n \cdot {lb}^{3} q)$	33.23	4.99	981 528	乘≈27.36×10¹³	乘≈50.17×10⁸	乘≈68.40×10¹²
WWL方案	40 896	40 896	199.38	$O (n^{3} {lb}^{3} n \cdot {lb}^{3} q)$	33.23	4.99	981 528	加≈34.20×10¹³	加≈66.90×10⁸	加≈68.40×10¹²
本文方案	13 632	20 448	11.08	$O (\sqrt{m} + \sqrt{w})$	16.61	2.50	490 776	乘≈19.80×10¹¹	乘≈14.53×10⁷	乘≈16.49×10⁸
本文方案	13 632	20 448	11.08	$O (\sqrt{m} + \sqrt{w})$	16.61	2.50	490 776	加≈19.80×10¹¹	加≈14.53×10⁷	加≈16.43×10⁸

表5

表6

HIBE方案原像采样算法优化前后效率分析对比"

原像采样算法	陷门维数	陷门尺寸/MB	原像采样复杂度（ $ℤ_{q}$ 乘加次数）	高斯参数
优化前算法	13 632	11.08	乘≈14.53×10⁷	$s_{1} (R^{'}) ω (\sqrt{lb n})$
优化前算法	13 632	11.08	加≈14.53×10⁷	$s_{1} (R^{'}) ω (\sqrt{lb n})$
优化后算法	6 816	5.54	乘≈96.87×10⁶	$s_{1} (R) ω (\sqrt{lb n})$
优化后算法	6 816	5.54	加≈96.87×10⁶	$s_{1} (R) ω (\sqrt{lb n})$

表6

参考文献 23

[1]	GENTRY C , SILVERBERG A . Hierarchical id-based cryptography,advances in cryptology[C]// ASIACRYPT 2002. 2002: 548-566.
[2]	HORWITZ J , LYNN B . Toward hierarchical identity-based encryption[C]// EUROCRYPT. 2002: 466-481.
[3]	BONEH D , FRANKLIN M . Identity-based encryption from theweil pairing[C]// Advances in Cryptology CRYPTO 2001. 2001: 213-229.
[4]	LAI J , DENG R H , LIU S ,et al. Identity-based encryption secure against selective opening chosen-ciphertextattack[C]// Advances in Cryptology EUROCRYPT 2012. 2012: 77-92.
[5]	YAMADA S , . Adaptively secure identity-based encryption from lattices with asymptotically shorter public parameters[C]// Advances in Cryptology EUROCRYPT2016. 2016: 32-62.
[6]	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.
[7]	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.
[8]	NGUYEN P , ZHANG J , ZHANG Z F . Simpler efficient group signatures from lattices[C]// Public-Key Cryptography. 2015: 401-426.
[9]	BRAKERSKI Z , PERLMAN R . Lattice-based fully dynamic multi-key FHE with short ciphertexts[C]// CRYPTO2016. 2016: 190-213.
[10]	LIBERT B , LING S , NGUYEN K ,et al. Zero-knowledge arguments for lattice-based accumulators,logarithmic-size ring signatures and group signatures without trapdoors[C]// Advances in Cryptology EUROCRYPT 2016. 2016: 1-31.
[11]	段然, 顾纯祥, 祝跃飞 ,等. NTRU 格上高效的基于身份的全同态加密体制[J]. 通信学报, 2017,38(1): 66-75.
	DUAN R , GU C X , ZHU Y F ,et al. Efficient identity-based fully homomorphic encryption over NTRU[J]. Journal on Communications, 2017,38(1): 66-75.
[12]	CASH D , HOFHEINZ D , KILTZ E ,et al. Bonsai trees,or how to delegate lattice basis[C]// Advances in Cryptology EUROCRYPT 2010. 201025(4): 523-552.
[13]	GENTRY C , PEIKERT C , VAIKUNTANATHAN V . Trapdoors for hard lattices and new cryptographic constructions[C]// The 40th ACM Symposium on Theory of Computing. 2008: 197-206.
[14]	AGRAWAL S , BONEH D , BOYEN X . Efficient lattice (H)IBE in the standard model[C]// Advances in Cryptology EUROCRYPT2010, 2010: 553-572.
[15]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller[C]// Advances in Cryptology EUROCRYPT2012. 2012: 700-718.
[16]	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.
[17]	PEIKERT C , . An efficient and parallel Gaussian sampler for lattices[C]// Advances in Cryptology CRYPTO 2010. 2010: 80-97.
[18]	AGRAWAL S , BOYEN X , VAIKUNTANATHAN V ,et al. Functional encryption for threshold functions(or fuzzy IBE) from lattices[C]// 15th International Conference on Practice and Theory in Public Key Cryptography. 2012: 280-297.
[19]	YANG C , ZHENG S , WANG L ,et al. Hierarchical identity-based broadcast encryption scheme from LWE[J]. Journal of Communications ＆ Networks, 2014,16(3): 258-263.
[20]	KATSUMATA S , YAMADA S . Partitioning via non-linear polynomial functions:more compact IBEs from ideal lattices and bilinear maps[C]// Advances in Cryptology ASIACRYPT 2016. 2016: 682-712.
[21]	ZHANG J , CHEN Y , ZHANG Z . Programmable hash functions from lattices:short signatures and IBEs with small key sizes[C]// Advances in Cryptology CRYPTO 2016. 2016: 302-332.
[22]	WANG F H , WANG C X , LIU Z H . Efficient hierarchical identity based encryption scheme in the standard model over lattices[J]. Frontiers of Information Technology ＆ Electronic Engineering, 2016,17(8): 781-791.
[23]	DODIS Y , OSTROVSKY R , REYZIN L ,et al. 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.

新的格上基于身份的分级加密方案

Novel hierarchical identity-based encryption scheme from lattice

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 23

相关文章 15

Metrics

推荐阅读 0

[1]	陈晓玉, 孙连峰, 张钇涵. 具有大零相关区宽度的Ⅱ型偶长Z-互补对构造方法[J]. 通信学报, 2023, 44(6): 167-174.
[2]	廉欢欢, 侯慧莹, 赵运磊. 后量子基于验证元的三方口令认证密钥交换协议[J]. 通信学报, 2022, 43(4): 95-106.
[3]	曹阳, 钟烨, 彭醇陵, 彭小峰. 基于混合供能和能量协作的异构网络能量效率优化算法[J]. 通信学报, 2022, 43(3): 135-147.
[4]	毛伊敏, 甘德瑾, 廖列法, 陈志刚. 基于Spark框架和ASPSO的并行划分聚类算法[J]. 通信学报, 2022, 43(3): 148-163.
[5]	郭渊博, 尹安琪. 基于格的口令认证密钥交换协议综述[J]. 通信学报, 2022, 43(12): 172-187.
[6]	郭红伟, 朱策, 杨栩, 罗雷. 基于失真反向传播的时域依赖率失真优化[J]. 通信学报, 2022, 43(12): 222-232.
[7]	董有恒, 赵耿, 马英杰. 基于分区初等元胞自动机的二维伪随机耦合映像格系统及其动态特性[J]. 通信学报, 2022, 43(1): 71-82.
[8]	侯红霞, 张明瑞, 赵艳琦, 董晓丽. 素数阶群上基于非对称对的身份基环签名[J]. 通信学报, 2021, 42(9): 155-164.
[9]	田苗苗, 陈静, 仲红. 格上基于身份的增量签名方案[J]. 通信学报, 2021, 42(1): 108-117.
[10]	王宏禹,邱天爽. 特征算子谱表示与特征展开的研究[J]. 通信学报, 2020, 41(5): 1-8.
[11]	房礼国,付正欣,胡浩,沈刚,郁滨. 基于区域递增式彩色视觉密码的栅格地图多级分存算法研究[J]. 通信学报, 2019, 40(9): 24-32.
[12]	王天荆,李秀琴,白光伟,沈航. 无线传感器网络中基于自适应网格的多目标定位算法[J]. 通信学报, 2019, 40(7): 197-207.
[13]	杨小东,李雨潼,王晋利,麻婷春,王彩芬. 标准模型下可撤销的基于身份的代理重签名方案[J]. 通信学报, 2019, 40(5): 153-162.
[14]	田苗苗,高闯,陈洁. 格上基于身份的云存储完整性检测方案[J]. 通信学报, 2019, 40(4): 128-139.
[15]	曾锋,王润华,彭佳,陈志刚. 口碑参与模式下移动众包网络的用户博弈研究[J]. 通信学报, 2019, 40(3): 125-138.