基于环上误差学习问题的新型后量子认证密钥交换协议

doi:10.11772/j.issn.1001-9081.2018020387

计算机应用 ›› 2018, Vol. 38 ›› Issue (8): 2243-2248.DOI: 10.11772/j.issn.1001-9081.2018020387

基于环上误差学习问题的新型后量子认证密钥交换协议

李子臣^1,2, 谢婷^1,3, 蔡居良³, 张筱薇³

1. 西安电子科技大学通信工程学院, 西安 710071;
2. 北京印刷学院教务处, 北京 102600;
3. 北京电子科技学院通信工程系, 北京 100070

收稿日期:2018-02-23 修回日期:2018-04-11 出版日期:2018-08-10 发布日期:2018-08-11
通讯作者: 谢婷
作者简介:李子臣(1965-),男,河南焦作人,教授,博士,主要研究方向:公钥密码、信息安全;谢婷(1991-),女,河南鹤壁人,硕士研究生,主要研究方向:密码学、信息安全;蔡居良(1993-),男,河南郑州人,硕士研究生,主要研究方向:信息安全、密码学;张筱薇(1995-),女,河北衡水人,硕士研究生,主要研究方向:信息安全、密码学。
基金资助:
国家自然科学基金资助项目（61370188）。

New post quantum authenticated key exchange protocol based on ring learning with errors problem

LI Zichen^1,2, XIE Ting^1,3, CAI Juliang³, ZHANG Xiaowei³

1. School of Telecommunications Engineering, Xidian University, Xi'an Shaanxi 710071, China;
2. Office of Educational Administration, Beijing Institute of Graphic Communication, Beijing 102600, China;
3. Department of Communication Engineering, Beijing Electronic Science & Technology Institute, Beijing 100070, China

Received:2018-02-23 Revised:2018-04-11 Online:2018-08-10 Published:2018-08-11
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61370188).

摘要/Abstract

摘要： 针对量子计算机技术的迅速发展使得传统公钥密码体制的安全性面临严重威胁的现实性问题，提出一种新型的基于环上误差学习（RLWE）问题的后量子认证密钥交换协议。协议通过使用Peikert式误差协调机制，双方通过计算可直接得到均匀分布的共享比特值，从而使得通信双方得到相同的会话密钥。使用理想格上的解码基对协议正确性进行了分析，并设置合理参数从而保证协议双方以显著概率得到相同密钥值。该协议在BR （Bellare-Rogaway）模型下可证明安全并达到弱的完美前向安全性。协议安全性归约为格上RLWE困难问题，可抵御量子攻击。与现有基于RLWE问题设计的认证密钥交换协议相比，该协议中参数值模数的大小由亚指数级降低至多项式级，相应计算量和通信量显著减小，是一种更加简洁高效的后量子认证密钥交换协议。

关键词: 认证密钥交换协议, 环上误差学习问题, BR模型, 格, 后量子

Abstract: In view of the fact that the rapid development of quantum computer technology poses serious threat to the security of the traditional public-key cryptosystem, a new authenticated key exchange protocol scheme based on Ring Learning With Errors (RLWE) problem was proposed. By using Peikert error reconciliation mechanism, both parties of communication can directly obtain the shared bit value of the uniform distribution and get the same session key. The encoding bases of lattice was used to analyze the error tolerance, and reasonable parameters were selected to ensure that both parties can get the same session key with significant probability. The security of the protocol was proved in the BR (Bellare-Rogaway) model with weak perfect forward secrecy. The security of the protocol was attributed to the difficult RLWE problem of lattice, so that the protocol can resist quantum attacks. Compared with the existing authenticated key exchange protocols based on RLWE, the size of the parameter value modulus decreases from sub-exponential to polynomial magnitude, thus the corresponding amount of computation and communication are also significantly reduced. The results show that the proposed scheme is a more concise and efficient post quantum authenticated key exchange protocol.

Key words: authenticated key exchange protocol, Ring Learning With Errors (RLWE), BR (Bellare-Rogaway) model, lattice, post quantum

中图分类号:

TP301.4

李子臣, 谢婷, 蔡居良, 张筱薇. 基于环上误差学习问题的新型后量子认证密钥交换协议[J]. 计算机应用, 2018, 38(8): 2243-2248.

LI Zichen, XIE Ting, CAI Juliang, ZHANG Xiaowei. New post quantum authenticated key exchange protocol based on ring learning with errors problem[J]. Journal of Computer Applications, 2018, 38(8): 2243-2248.

参考文献

[1] DODIS Y, MIRONOV I, STEPHENS-DAVIDOWITZ N. Message transmission with reverse firewalls-secure communication on corrupted machines[C]//Proceeding of Advances in Cryptology - CRYPTO 2016, LNCS 9814. Berlin:Springer, 2016:341-372.
[2] GONZÁLEZ-VASCO M I G, del POZO A L P, P SUÁREZ CORONA A. Group key exchange protocols withstanding ephemeral-key reveals[J]. IET Information Security, 2018, 12(1):79-86.
[3] DIFFILE W, HELLMAN M. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6):644-654.
[4] 王曌,丁勇,王会勇.基于环上容错学习和GSW的层次型全同态加密方案[J].计算机应用,2016,36(4):962-965. (WANG Z, DING Y, WANG H Y. Leveled fully homomorphic encryption scheme based on Ring-LWE-GSW[J]. Journal of Computer Applications, 2016, 36(4):962-965.)
[5] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2005, 56(6):84-93.
[6] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[C]//Proceeding of Advances in Cryptology - EUROCRYPT 2010, LNCS 6110. Berlin:Springer, 2010:1-23.
[7] LANGLOIS A, STEHLÉ D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3):565-599.
[8] DING J, XIE X, LIN X. A simple provably secure key exchange scheme based on the learning with errors problem [EB/OL]. [2017-06-09] http://pdfs.semanticscholar.org/b1e7/faec59a9bdd70e75f9d15496cf27916ce060.pdf.
[9] PEIKERT C. Lattice cryptography for the internet [C]// PQCrypto 2014: International Workshop on Post-Quantum Cryptography, LNCS 8772. Cham: Springer, 2014: 197-219.
[10] BOS J, COSTELLO C, DUCAS L, et al. Frodo: take off the ring! practical, quantum-secure key exchange from LWE [C]// Proceedings of the 201623rd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2016: 1006-1018.
[11] BOS J, COSTELLO C, NAEHRIG M, et al. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem [C]// SP 2015: Proceedings of the 2015 IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 2015: 553-570.
[12] ALKIM E, DUCAS L, PÖPPELMANN T, et al. Post quantum-key exchange — a new hope [C]// Proceedings of the 25th USENIX Security Symposium. Berkeley, CA: USENIX Association, 2016: 327-343.
[13] ZHANG J, ZHANG Z, DING J, et al. Authenticated key exchange from ideal lattices [C]// Proceedings of the Advances in Cryptology — EUROCRYPT 2015, LNCS 9057. Berlin: Springer, 2015: 719-751.
[14] DING J, ALSAYIGH S, LANCRENON J, et al. Provably secure password authenticated key exchange based on RLWE for the post-quantum world [C]// CT-RSA 2017: Proceedings of the Cryptographers' Track at the RSA Conference, LNCS 10159. Cham: Springer, 2017: 183-204.
[15] BELLARE M, ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols [C]// Proceeding of the 1993 ACM Conference on Computer & Communication Security. New York: ACM, 1993: 62-73.
[16] KRAWCZY H. HMQV: a high-performance secure Diffe-Hellman protocol [C]// Proceeding of Advances in Cryptology — CRYPTO 2005, LNCS 3621. Berlin: Springer, 2005: 546-566.
[17] APPLEBAUM B, CASH D, PEIKERT C, et al. Fast cryptographic primitives and circular-secure encryption based on hard learning problems [C]// Proceeding of Advances in Cryptology — CRYPTO 2009, LNCS 5677. Berlin: Springer, 2009: 595-618.
[18] ABDALLA M, BENHAMOUDA F, MACKENZIE P. Security of the J-PAKE password-authenticated key exchange protocol [C]// SP 2015: Proceedings of the 2015 IEEE Symposium on Security and Privacy. Washington, DC: IEEE Computer Society, 2015: 571-587.

基于环上误差学习问题的新型后量子认证密钥交换协议

New post quantum authenticated key exchange protocol based on ring learning with errors problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘子辰, 李小娟, 韦伟. 基于循环神经网络的专利价格自动评估[J]. 计算机应用, 2021, 41(9): 2532-2538.
[2]	曾祥银, 郑伯川, 刘丹. 基于深度卷积神经网络和聚类的左右轨道线检测[J]. 计算机应用, 2021, 41(8): 2324-2329.
[3]	龙超奇, 蒋瑜, 谢雨. 基于峰值网格改进的小波聚类算法[J]. 计算机应用, 2021, 41(4): 1122-1127.
[4]	陈朗, 王让定, 严迪群, 林昱臻. 融合残差网络和极限梯度提升的音频隐写检测模型[J]. 计算机应用, 2021, 41(2): 449-455.
[5]	王守华, 吴黎荣, 纪元法, 孙希延. 基于格理论的模糊度快速解算方法[J]. 计算机应用, 2020, 40(8): 2299-2304.
[6]	黄中展, 徐世明. 基于循环神经网络的正交网格的自动化生成算法[J]. 计算机应用, 2020, 40(7): 2009-2015.
[7]	王栖榕, 黄樟灿. 基于颜色特征的画家艺术风格提取方法[J]. 计算机应用, 2020, 40(6): 1818-1823.
[8]	邢志伟, 乔迪, 刘洪恩, 高志伟, 罗晓, 罗谦. 基于松弛算法的停机位分配优化方法[J]. 计算机应用, 2020, 40(6): 1850-1855.
[9]	丁辉, 李丽宏, 原钢. 融合GMS与VCS+GC-RANSAC的图像配准算法[J]. 计算机应用, 2020, 40(4): 1138-1143.
[10]	余英东, 杨怡, 林澜. 结合纹理特征分析的图像风格转换网络[J]. 计算机应用, 2020, 40(3): 638-644.
[11]	褚苏荣, 牛之贤, 宋春花, 牛保宁. 面向移动端的渐进网格简化算法[J]. 计算机应用, 2020, 40(3): 806-811.
[12]	金勇, 罗明, 董明扬. 基于NOMA系统的用户分组和功率分配策略[J]. 计算机应用, 2020, 40(3): 788-792.
[13]	张毅卓, 葛森, 王良军, 谢江, 曹洁, 张武. 基于格子Boltzmann方法和大涡模拟的颈动脉分叉狭窄流动并行计算[J]. 计算机应用, 2020, 40(2): 404-409.
[14]	刘斌, 何进荣, 李远成, 韩宏. 基于分布式神经网络的苹果价格预测方法[J]. 计算机应用, 2020, 40(2): 369-374.
[15]	刘智翔, 刘慧超, 黄冬梅, 周丽萍, 苏诚. 多种任务调度混合的IB-LBM并行优化方法[J]. 计算机应用, 2020, 40(2): 386-391.