基于LWE的抗量子认证密钥交换协议

doi:10.3969/j.issn.1671-1122.2020.10.012

信息网络安全 ›› 2020, Vol. 20 ›› Issue (10): 92-99.doi: 10.3969/j.issn.1671-1122.2020.10.012

基于LWE的抗量子认证密钥交换协议

李鱼, 韩益亮(), 李喆, 朱率率

武警工程大学密码工程学院,西安 710086

收稿日期:2020-04-15 出版日期:2020-10-10 发布日期:2020-11-25
通讯作者: 韩益亮 E-mail:hanyil@163.com
作者简介:李鱼（1995—）,男,重庆,硕士研究生,主要研究方向为抗量子密码|韩益亮（1977—）,男,甘肃,教授,博士,主要研究方向为信息安全、抗量子密码|李喆（1994—）,男,安徽,硕士研究生,主要研究方向为抗量子密码|朱率率（1985—）,男,山东,博士研究生,主要研究方向为抗量子密码
基金资助:
国家自然科学基金(61572521)

A Post Quantum Authenticated Key Exchange Protocol Based on LWE

LI Yu, HAN Yiliang(), LI Zhe, ZHU Shuaishuai

School of Cryptographic Engineering, Engineering University of PAP, Xi’an 710086, China

Received:2020-04-15 Online:2020-10-10 Published:2020-11-25
Contact: HAN Yiliang E-mail:hanyil@163.com

摘要/Abstract

摘要：

目前格上的密钥交换协议大都基于环上容错学习问题,需要充分利用环结构的效率和存储优势,但在实际应用中其安全性有待进一步研究,且实现认证需要额外的签名等复杂结构。文章基于LWE问题构造一种抗量子认证密钥交换协议,采用预计算提高协议的线上效率,验证协议双方均可正确计算得到一致会话密钥,设计系列安全性游戏并对协议的安全性加以证明。在两轮消息的交互中引入长期公私钥,在会话密钥计算中引入Hash函数实现协议的认证,在不使用额外的签名操作情况下可抵抗中间人攻击。由于目前没有可区分LWE分布和均匀随机分布的量子算法,文章所提出的协议可抵抗量子计算攻击。

关键词: 格密码, 认证密钥交换, 容错学习问题, 抗量子密码

Abstract:

Recently, the majority of key exchange protocols are based on ring-learning with errors. While the additional ring structure facilitates efficiency and storage, its actual security also needs to be further research. These protocols require a complex structure such as additional signatures to achieve authentication. In this paper, a post-quantum authenticated key exchange protocol based on LWE was proposed. The pre-computation is adopted to improve the efficiency of the protocol. It is verified that both parties of the protocol can correctly calculate the consistent session key. A series of security games are designed to prove the protocol proposed in this paper. The authentication is achieved by introducing the static public and secret keys in the extraction of shared bits and introducing a hash function in the calculation of the session key. The protocol can resist man-in-the-middle attacks and need no additional operations such as encryption or signature. There is currently no quantum algorithm that can distinguish between LWE distribution and uniform random distribution, so the proposed protocol can resist quantum computing attacks.

Key words: lattice-based cryptography, authenticated key exchange, learning with errors, post quantum cryptography

中图分类号:

TP309

李鱼, 韩益亮, 李喆, 朱率率. 基于LWE的抗量子认证密钥交换协议[J]. 信息网络安全, 2020, 20(10): 92-99.

LI Yu, HAN Yiliang, LI Zhe, ZHU Shuaishuai. A Post Quantum Authenticated Key Exchange Protocol Based on LWE[J]. Netinfo Security, 2020, 20(10): 92-99.

图/表 7

图1

表1

表2

表3

图2

图3

图4

参考文献 15

[1]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM, 2009,56(6):84-93.
[2]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors Over Rings [C]//Springer. 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 30 - June 3, 2010, Monaco and Nice, France. Berlin: Springer, 2010: 1-23.
[3]	LANGOLOIS A, STEHLÉ D. Worst-Case to Average-Case Reductions for Module Lattices[J]. Designs, Codes and Cryptography, 2015,75(3):565-599.
[4]	DING Jintai, LIN Xiaodong. A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem[J]. IACR Cryptology ePrint Archive, 2012,2012(1):688-703.
[5]	PEIKERT C. Lattice Cryptography for the Internet [C]//Springer. Post-Quantum Cryptography: 6th International Workshop, October 1-3, 2014, Waterloo, ON, Canada. Berlin: Springer, 2014: 197-219.
[6]	BOS J, COSTELLO C, NAEHRIG M, et al. Post-quantum Key Exchange for the TLS Protocol from the Ring Learning with Errors Problem [C]//IEEE. 2015 IEEE Symposium on Security and Privacy, May 17-21, 2015, San Jose, CA, USA. Piscataway: IEEE, 2015: 553-570.
[7]	ALKIM E, DUCAS L, PÖPPELMANN T, et al. Post Quantum Key Exchange—A New Hope [C]// USENIX. 25th USENIX Security Symposium, August 10-12, 2016, Austin, TX. Berkeley: USENIX, 2016: 327-343.
[8]	BOS J, COSTELLO C, DUCAS L, et al. Frodo: Take off the Ring! Practical, Quantum-secure Key Exchange from LWE [C]//ACM. 23rd ACM Conference on Computer and Communications Security, October 24-28, 2016, Vienna, Austria. New York: ACM, 2016: 1006-1018.
[9]	JIN Zhenzhong, ZHAO Yunlei. Optimal Key Consensus in Presence of Noise[J]. IACR Cryptology ePrint Archive, 2017,2017(1):1058-1122.
[10]	DING Jintai, ALSAYIGH S, LANCRENON J, et al. Provably Secure Password Authenticated Key Exchange Based on RLWE for The Postquantum World [C]//Springer. The Cryptographers' Track at the RSA Conference, February 14-17, 2017, San Francisco, CA, USA, Berlin: Springer, 2017: 183-204.
[11]	MACKENZIE P. The PAK Suite: Protocols for Password-authenticated Key Exchange: United States, 1363. 2[P]. 2001-11-1.
[12]	BOYKO V, MACKENZIE P, PATEL S. Provably Secure Password-authenticated Key Exchange Using Diffie-Hellman [C]//Springer. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, May 14-18, 2000, Bruges, Belgium. Berlin: Springer, 2000: 156-171.
[13]	BINDEL N, BUCHMANN J, RIE S. Comparing Apples with Apples: Performance Analysis of Lattice-Based Authenticated Key Exchange Protocols[J]. International Journal of Information Security, 2018,17(6):701-718.
[14]	BELLARE M, ROGAWAY, P. Entity Authentication and Key Distribution[C]//Springer. 13th Annual International Cryptology Conference, August 22-26, 1993, California, USA. Berlin: Springer, 1993: 232-249.
[15]	GAO Xinwei. Comparison Analysis of Ding's RLWE-Based Key Exchange Protocol and Newhope Variants[J]. Advances in Mathematics of Communications, 2019,13(2):221-223.

n	q	B	$\bar{m}=\bar{n}$	抗量子安全性/ bit
592	2¹²	2	8	119
752	2¹⁵	4	8	130
864	2¹⁵	4	8	161

协议	抗量子安全性 /bit	认证性	通信量i→j /KB	通信量j→i /KB	总通信量 /KB
文献[8]方案	119	—	7.120	7.112	14.232
	130	—	11.296	11.288	22.584
	161	—	12.976	12.968	25.944
本文方案	119	√	7.120	7.120	14.240
	130	√	11.296	11.296	22.592
	161	√	12.976	12.976	25.952

协议	抗量子安全性 /ms	线下过程 /ms	线上过程
协议	抗量子安全性 /ms	线下过程 /ms	发起/ms	响应/ms	完成/ms
文献[8]方案	119	—	3.447±0.087	3.553±0.041	0.097±0.002
	130	—	5.585±0.110	5.572±0.039	0.145±0.001
	161	—	7.149±0.133	7.130±0.029	0.167±0.001
本文方案	119	7.002±0.029	—	0.172±0.005	0.167±0.004
	130	11.605±0.340	—	0.224±0.030	0.217±0.330
	161	14.972±0.039	—	0.244±0.009	0.244±0.012

基于LWE的抗量子认证密钥交换协议

A Post Quantum Authenticated Key Exchange Protocol Based on LWE

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 15

相关文章 4

编辑推荐

Metrics

本文评价

[1]	江明明, 赵利军, 王艳, 王保仓. 面向云数据共享的量子安全的无证书双向代理重加密[J]. 信息网络安全, 2018, 18(8): 17-24.
[2]	陈莉, 顾纯祥, 尚明君. 抗量子攻击的高效盲签名方案[J]. 信息网络安全, 2017, 17(10): 36-41.
[3]	张焕国;王后珍. 抗量子计算密码体制研究(续前)[J]. , 2011, 11(6): 0-0.
[4]	张焕国;王后珍. 抗量子计算密码体制研究(待续)[J]. , 2011, 11(5): 0-0.