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

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

Abstract

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

CLC Number:

TP309

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.

Figures/Tables 6

符号	说明
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为常数

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

方案	格的维数	陷门尺寸/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

方案	陷门维数	用户公钥维数	陷门尺寸/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⁸

方案	陷门维数	用户公钥维数	陷门尺寸/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⁸

原像采样算法	陷门维数	陷门尺寸/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})$

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

Novel hierarchical identity-based encryption scheme from lattice

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 6

References 23

Related Articles 15

Metrics

Recommended 0

[1]	Huanhuan LIAN, Huiying HOU, Yunlei ZHAO. Post-quantum verifier-based three-party password authenticated key exchange protocol [J]. Journal on Communications, 2022, 43(4): 95-106.
[2]	Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices [J]. Journal on Communications, 2022, 43(12): 172-187.
[3]	Youheng DONG, Geng ZHAO, Yingjie MA. Two-dimensional pseudo-random coupled map lattices system based on partitioned elementary cellular automata and its dynamic properties [J]. Journal on Communications, 2022, 43(1): 71-82.
[4]	Hongxia HOU, Mingrui ZHANG, Yanqi ZHAO, Xiaoli DONG. ID-based ring signature on prime order group from asymmetric pairing [J]. Journal on Communications, 2021, 42(9): 155-164.
[5]	Miaomiao TIAN, Jing CHEN, Hong ZHONG. Identity-based incremental signature scheme from lattices [J]. Journal on Communications, 2021, 42(1): 108-117.
[6]	Zhen LIU,Yiliang HAN,Xiaoyuan YANG,Shuguang LIU. Provable security signcryption scheme based on RLWE without trapdoor [J]. Journal on Communications, 2020, 41(6): 14-25.
[7]	Xiaodong YANG,Yutong LI,Jinli WANG,Tingchun MA,Caifen WANG. Revocable identity-based proxy re-signature scheme in the standard model [J]. Journal on Communications, 2019, 40(5): 153-162.
[8]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[9]	Yatao YANG,Xinguang HAN,Jierun HUANG,Yang ZHAO. Bidirectional authentication key agreement protocol supporting identity’s privacy preservation based on RLWE [J]. Journal on Communications, 2019, 40(11): 180-186.
[10]	Qian MENG,Jianfeng MA,Kefei CHEN,Yinbin MIAO,Tengfei YANG. Data comparable encryption scheme based on cloud computing in Internet of things [J]. Journal on Communications, 2018, 39(4): 167-175.
[11]	Xixi YAN,Yuan LIU,Zichen LI,Yongli TANG,Qing YE. Privacy-preserving attribute-based encryption scheme on ideal lattices [J]. Journal on Communications, 2018, 39(3): 128-135.
[12]	Caifen WANG,Li CHEN. Three-party password authenticated key agreement protocol with user anonymity based on lattice [J]. Journal on Communications, 2018, 39(2): 21-30.
[13]	Xiaodong YANG,Chunlin CHEN,Ping YANG,Faying AN,Tingchun MA,Caifen WANG. Partially blind proxy re-signature scheme with proven security [J]. Journal on Communications, 2018, 39(2): 65-72.
[14]	Shao-bo YU,Ling-da WU,Xi-tao ZHANG. Research on space information representation model based on formal concept analysis [J]. Journal on Communications, 2017, 38(Z2): 78-85.
[15]	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.