基于容錯(cuò)學(xué)習(xí)的屬性基加密方案的具體安全性分析

趙建; 高海英; 胡斌

doi:10.11999/JEIT180824

基于容錯(cuò)學(xué)習(xí)的屬性基加密方案的具體安全性分析

doi: 10.11999/JEIT180824

解放軍信息工程大學(xué) ??鄭州 ??450001

基金項(xiàng)目: 國(guó)家自然科學(xué)基金(61702548, 61601515)，河南省基礎(chǔ)與前沿技術(shù)課題(162300410192)

詳細(xì)信息

作者簡(jiǎn)介:
趙建：男，1989年生，博士生，研究方向?yàn)楣 €密碼的設(shè)計(jì)與分析

高海英：女，1978年生，教授，博士生導(dǎo)師，研究方向?yàn)槊艽a算法的設(shè)計(jì)與分析

胡斌：男，1971年生，教授，博士生導(dǎo)師，研究方向?yàn)槊艽a算法的設(shè)計(jì)與分析

通訊作者:
趙建　back_zj@126.com

中圖分類號(hào): TP309
計(jì)量
- 文章訪問數(shù): 3150
- HTML全文瀏覽量: 1311
- PDF下載量: 101
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-08-22
- 修回日期: 2019-01-23
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要: 為了能全面研究基于容錯(cuò)學(xué)習(xí)(LWE)的屬性基加密(ABE)方案的安全性，考察其抵抗現(xiàn)有攻擊手段的能力，在綜合考慮格上算法和方案噪聲擴(kuò)張對(duì)參數(shù)的限制后，利用已有的解決LWE的算法及其可用程序模塊，該文提出了針對(duì)基于LWE的ABE方案的具體安全性分析方法。該方法可以極快地給出滿足方案限制要求的具體參數(shù)及方案達(dá)到的安全等級(jí)，此外，在給定安全等級(jí)的條件下，該方法可以給出相應(yīng)的具體參數(shù)值。最后，利用該方法分析了4個(gè)典型的基于LWE的屬性基加密方案的具體安全性。實(shí)驗(yàn)數(shù)據(jù)表明，滿足一定安全等級(jí)的基于LWE的屬性基方案的參數(shù)尺寸過大，還無法應(yīng)用到實(shí)際中。
- 屬性基加密方案 /
- 具體安全性 /
- 容錯(cuò)學(xué)習(xí)
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 符號(hào)定義

符號(hào)	意義	符號(hào)	意義
$d$	整數(shù)值	${{\mathbb{Z}}_q}$	模$q$的剩余類環(huán)
${{a}}$	列向量${{a}}$	${{\mathbb{Z}}^{n \times m}}$	$n \times m$整數(shù)矩陣集合
${{A}}$	矩陣${{A}}$	$\left\lceil {q/2} \right\rceil $	大于$q/2$的最小整數(shù)
${{A}} ^{\rm{T}}$	矩陣${{A}}$的轉(zhuǎn)置	$\left\lfloor {q/2} \right\rfloor $	小于q/2的最大整數(shù)
${{A}}\|{{B }}$	矩陣${{A}}$和矩陣${{B }}$合并	$\varTheta (n)$	漸進(jìn)精確界記號(hào)
${\mathbb{Z}}$	整數(shù)域	$\omega (n)$	非漸進(jìn)緊下界記號(hào)
${\mathbb{R}}$	實(shí)數(shù)域	$O(n)$	漸進(jìn)上界記號(hào)

下載: 導(dǎo)出CSV

表 2 密碼算法的安全級(jí)別

安全等級(jí)(${2^n}$)	40	64	80	128	192	256
安全級(jí)別	薄弱(weak)	傳統(tǒng)(legacy)	基準(zhǔn)(baseline)	標(biāo)準(zhǔn)(standard)	較高(high)	超高(ultra)

下載: 導(dǎo)出CSV

表 3 d, n=64時(shí)參數(shù)和最低安全等級(jí)${λ}$的關(guān)系

$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

下載: 導(dǎo)出CSV

表 4 $q7j3ldu95 {= 1}$時(shí)參數(shù)和最低安全等級(jí)${λ}$的關(guān)系

$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

下載: 導(dǎo)出CSV

表 5 達(dá)到基準(zhǔn)安全等級(jí)${λ} ' \approx{80}$時(shí)方案的參數(shù)

$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

下載: 導(dǎo)出CSV

表 6 方案數(shù)據(jù)量大小(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

下載: 導(dǎo)出CSV

表 7 方案中參數(shù)和最低安全等級(jí)${λ} $的關(guān)系

方案	AF	$n$	$\log q \approx $	$m$	$\alpha $	$\lambda $
文獻(xiàn)[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
文獻(xiàn)[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
文獻(xiàn)[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

下載: 導(dǎo)出CSV

表 8 方案達(dá)到基準(zhǔn)安全等級(jí)${λ} ' \approx {80}$時(shí)方案的參數(shù)

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

下載: 導(dǎo)出CSV

表 9 方案數(shù)據(jù)量大小(GB)

方案	公鑰	密文	密鑰
文獻(xiàn)[9]	44.5652	0.0255	5570.6550
文獻(xiàn)[16]	1.1012	1.8354	1.4683
文獻(xiàn)[17]	342.6093	0.1370	0.2056

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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]. 電子與信息學(xué)報(bào), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)