基于容错学习的属性基加密方案的具体安全性分析

赵建; 高海英; 胡斌

doi:10.11999/JEIT180824

基于容错学习的属性基加密方案的具体安全性分析

doi: 10.11999/JEIT180824

解放军信息工程大学郑州 450001

基金项目: 国家自然科学基金(61702548, 61601515)，河南省基础与前沿技术课题(162300410192)

详细信息

作者简介:
赵建：男，1989年生，博士生，研究方向为公钥密码的设计与分析

高海英：女，1978年生，教授，博士生导师，研究方向为密码算法的设计与分析

胡斌：男，1971年生，教授，博士生导师，研究方向为密码算法的设计与分析

通讯作者:
赵建　back_zj@126.com

中图分类号: TP309
计量
- 文章访问数: 3098
- HTML全文浏览量: 1265
- PDF下载量: 98
- 被引次数: 0
出版历程
- 收稿日期: 2018-08-22
- 修回日期: 2019-01-23
- 网络出版日期: 2019-02-15
- 刊出日期: 2019-08-01

Analysis Method for Concrete Security of Attribute-based Encryption Based on Learning With Errors

The PLA Information Engineering University, Zhengzhou 450001, China

Funds: The National Natural Science Foundation of China (61702548, 61601515), The Fundamental and Frontier Technology Research of Henan Province (162300410192)

摘要

摘要: 为了能全面研究基于容错学习(LWE)的属性基加密(ABE)方案的安全性，考察其抵抗现有攻击手段的能力，在综合考虑格上算法和方案噪声扩张对参数的限制后，利用已有的解决LWE的算法及其可用程序模块，该文提出了针对基于LWE的ABE方案的具体安全性分析方法。该方法可以极快地给出满足方案限制要求的具体参数及方案达到的安全等级，此外，在给定安全等级的条件下，该方法可以给出相应的具体参数值。最后，利用该方法分析了4个典型的基于LWE的属性基加密方案的具体安全性。实验数据表明，满足一定安全等级的基于LWE的属性基方案的参数尺寸过大，还无法应用到实际中。
- 属性基加密方案 /
- 具体安全性 /
- 容错学习
Abstract: In order to comprehensively study the security of the Attribute-Based Encryption (ABE) scheme based on Learning With Errors (LWE) and test its ability to resist existing attacks, an analysis method for concrete security of ABE based on LWE is proposed. After consideration of the parameter restrictions caused by algorithms on lattices and noise expansion, this method applies the existing algorithms to solving LWE and the available program modules, and it can quickly provide the specific parameters that satisfy the scheme and estimate the corresponding security level. In addition, it can output the specific parameters that satisfy the pre-given security level. Finally, four existing typical schemes are analyzed by this method. Experiments show that the parameters are too large to be applied to practical applications.
- Attribute-Based Encryption (ABE) /
- Concrete security /
- Learning With Errors (LWE)

HTML全文

表 1 符号定义

符号	意义	符号	意义
$d$	整数值	${{\mathbb{Z}}_q}$	模$q$的剩余类环
${{a}}$	列向量${{a}}$	${{\mathbb{Z}}^{n \times m}}$	$n \times m$整数矩阵集合
${{A}}$	矩阵${{A}}$	$\left\lceil {q/2} \right\rceil $	大于$q/2$的最小整数
${{A}} ^{\rm{T}}$	矩阵${{A}}$的转置	$\left\lfloor {q/2} \right\rfloor $	小于q/2的最大整数
${{A}}\|{{B }}$	矩阵${{A}}$和矩阵${{B }}$合并	$\varTheta (n)$	渐进精确界记号
${\mathbb{Z}}$	整数域	$\omega (n)$	非渐进紧下界记号
${\mathbb{R}}$	实数域	$O(n)$	渐进上界记号

下载: 导出CSV

表 2 密码算法的安全级别

安全等级(${2^n}$)	40	64	80	128	192	256
安全级别	薄弱(weak)	传统(legacy)	基准(baseline)	标准(standard)	较高(high)	超高(ultra)

下载: 导出CSV

表 3 d, n=64时参数和最低安全等级${λ}$的关系

$c$	$q$	$\log q \approx $	$m$	${\rm{Dis}}( \cdot )$？	${λ}$
8	281474976710677	48	6144	否	–
11	73786976294838206459	66	8448	是	30.6
16	79228162514264337593543950319	96	12288	是	31.1
32	6277101735386680763835789423207666416102355444464034513029	192	24576	是	32.0
64	39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627990307047	384	48727	是	32.9

下载: 导出CSV

表 4 ${d} {= 1}$时参数和最低安全等级${λ}$的关系

$n$	$c$	$q$	$\log q \approx $	$m$	${\rm{Dis}}( \cdot )$？	$\alpha $	${λ} $
128	8	72057594037927931	56	14336	否	–	–
128	10	1180591620717411303449	70	17920	是	6.01e–18	31.8
512	7	9223372036854775783	63	64512	否	–	–
512	8	4722366482869645213711	72	73728	是	3.30e–18	35.1
1024	7	1180591620717411303449	70	143360	否	–	–
1024	8	1208925819614629174706189	80	163840	是	2.10e–20	60.1
1275	7	5477360094305419921879	72	184146	否	–	–
1275	8	6983634120239410400390599	83	210452	是	4.11e–21	81.3
4096	6	4722366482869645213711	72	589824	否	–	–
4096	7	19342813113834066795298819	84	688128	是	2.95e–21	636.7

下载: 导出CSV

表 5 达到基准安全等级${λ} ' \approx{80}$时方案的参数

$d$	$n$	$\log q \approx $	$m$	$\alpha $
1	1275	82.5	210452	4.11e–21
2	1375	104.3	286694	1.42e–27
4	2925	161.2	943015	2.04e–44
8	5500	285.8	3143580	1.27e–81
16	11000	537.0	1181490	6.32e–157

下载: 导出CSV

表 6 方案数据量大小(GB)

$d$	公钥	主密钥	密文	密钥
1	12.96	1719.55	0.006098	2138.19
2	43.39	8044.95	0.017530	9050.57
4	1716.67	536681.89	0.302340	553453.20
8	295332.43	168482949.37	26.900739	168812017.63
16	1064847265.92	1143637238342.29	48402.517727	1143645963601.98

下载: 导出CSV

表 7 方案中参数和最低安全等级${λ} $的关系

方案	AF	$n$	$\log q \approx $	$m$	$\alpha $	$\lambda $
文献[9]	d = 1	128	103	26368	4.28e–25	32.5
	k = 2	1024	120	245760	3.71e–29	40.6
	p = 10	4096	132	1081344	4.46e–32	335.3
文献[16]	$r = 2$	128	93	8836	4.46e–22	31.9
		1024	102	10609	2.94e–24	50.3
		4096	108	11881	1.03e–25	511.2
文献[17]	$l = 3$	128	87	67632	2.91e–28	31.7
		1024	96	591000	3.48e–31	37.8
		4096	101	2483646	4.18e–33	185.8

下载: 导出CSV

表 8 方案达到基准安全等级${λ} ' \approx {80}$时方案的参数

方案	$n$	$\log q \approx $	$m$	$\alpha $
文献[9]	1750	125	437500	2.16e–30
文献[16]	1380	104	11024	8.86e–25
文献[17]	2500	99	1486359	2.03e–32

下载: 导出CSV

表 9 方案数据量大小(GB)

方案	公钥	密文	密钥
文献[9]	44.5652	0.0255	5570.6550
文献[16]	1.1012	1.8354	1.4683
文献[17]	342.6093	0.1370	0.2056

下载: 导出CSV

参考文献(17)

SAHAI A and WATERS B. Fuzzy identity-based encryption[C]. The 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Aarhus, Denmark, 2005: 457–473. doi: 10.1007/11426639_27.

AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, Pennsylvania, USA, 1996: 99–108. doi: 10.1145/237814.237838.

REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. The 37th Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.

LYUBASHEVSKY V, PEIKERT C, and REGEV O. On ideal lattices and learning with errors over rings[J]. Journal of the ACM, 2010, 60(6): 43. doi: 10.1145/2535925

ALBRECHT M R, PLAYER R, and SCOTT S. On the concrete hardness of learning with Errors[J]. Journal of Mathematical Cryptology, 2015, 9(3): 169–203. doi: 10.1515/jmc-2015-0016

BECKER A, DUCAS L, GAMA N, et al. New directions in nearest neighbor searching with applications to lattice sieving[C]. The Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia, 2016: 10–24. doi: 10.1137/1.9781611974331.ch2.

SCHNEIDER M. Sieving for shortest vectors in ideal lattices[C]. The 6th International Conference on Cryptology in Africa, Cairo, Egypt, 2013: 375–391. doi: 10.1007/978-3-642-38553-7_22.

AGRAWAL S, BONEH D, and BOYEN X. Efficient lattice (H)IBE in the standard model[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 553–572. doi: 10.1007/978-3-642-13190-5_28.

BONEH D, NIKOLAENKO V, and SEGEV G. Attribute-based encryption for arithmetic circuits[EB/OL]. http://eprint.iacr.org/2013/669, 2013.

CHEN Yuanmi and NGUYEN P Q. BKZ 2.0: Better lattice security estimates[C]. The 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, 2011: 1–20. doi: 10.1007/978-3-642-25385-0_1.

BAI Shi and GALBRAITH S D. Lattice decoding attacks on binary LWE[C]. The 19th Australasian Conference on Information Security and Privacy, Wollongong, NSW, Australia, 2014: 322–337. doi: 10.1007/978-3-319-08344-5_21.

PAAR C and PELZL J. Understanding Cryptography: A Textbook for Students and Practitioners[M]. Berlin Heidelberg: Springer, 2010: 156.

LINDNER R and PEIKERT C. Better key sizes (and attacks) for LWE-based encryption[C]. The Cryptographers’ Track at the RSA Conference 2011 Topics in Cryptology, San Francisco, USA, 2011: 319–339. doi: 10.1007/978-3-642-19074-2_21.

ALBRECHT M R, CID C, FAUGèRE J, et al. On the complexity of the BKW algorithm on LWE[J]. Designs, Codes and Cryptography, 2015, 74(2): 325–354. doi: 10.1007/s10623-013-9864-x

ZHAO Jian, GAO Haiying, and ZHANG Junqi. Attribute-based encryption for circuits on lattices[J]. Tsinghua Science and Technology, 2014, 19(5): 463–469. doi: 10.3969/j.issn.1007-0214.2014.05.005

赵建, 高海英, 胡斌. 基于理想格的高效密文策略属性基加密方案[J]. 电子与信息学报, 2018, 40(7): 1652–1660. doi: 10.11999/JEIT170863

ZHAO Jian, GAO Haiying, and HU Bin. An efficient ciphertext-policy attribute-based encryption on ideal lattices[J]. Journal of Electronics &Information Technology, 2018, 40(7): 1652–1660. doi: 10.11999/JEIT170863

ZHANG Jiang, ZHANG Zhenfeng, and GE Aijun. Ciphertext policy attribute-based encryption from lattices[C]. The 7th ACM Symposium on Information, Computer and Communications Security, Seoul, Korea, 2012: 16–17. doi: 10.1145/2414456.2414464.

施引文献

资源附件(0)

访问统计