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

doi:10.11772/j.issn.1001-9081.2018020387

Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (8): 2243-2248.DOI: 10.11772/j.issn.1001-9081.2018020387

Previous Articles Next Articles

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-11 Published:2018-08-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61370188).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP301.4

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	Xinyuan YIN, Xiaojian ZHENG, Jinbo XIONG. Two-round three-party password-authenticated key exchange protocol over lattices without non-interactive zero-knowledge proof [J]. Journal of Computer Applications, 2024, 44(3): 805-810.
[2]	Jianyang CUI, Ying CAI, Yu ZHANG, Yanfang FAN. Authenticatable privacy-preserving scheme based on signcryption from lattice for vehicular ad hoc network [J]. Journal of Computer Applications, 2024, 44(1): 233-241.
[3]	Jinbo LI, Ping ZHANG, Ji ZHANG, Muhua LIU. Identity-based ring signature scheme on number theory research unit lattice [J]. Journal of Computer Applications, 2023, 43(9): 2798-2805.
[4]	Xuejian ZHAO, Hao LI, Haotian TANG. Recommendation rating prediction algorithm based on user interest concept lattice reduction [J]. Journal of Computer Applications, 2023, 43(11): 3340-3345.
[5]	NONG Qiang, ZHANG Bangbang, OUYANG Yuhao. Lattice-based hierarchical certificateless proxy signature scheme [J]. Journal of Computer Applications, 2023, 43(1): 154-159.
[6]	Zhonghui LIU, Ziyou WANG, Fan MIN. Genetic algorithm for approximate concept generation and its recommendation application [J]. Journal of Computer Applications, 2022, 42(2): 412-418.
[7]	WU Guoliang, XU Jining. Chinese emergency event extraction method based on named entity recognition task feedback enhancement [J]. Journal of Computer Applications, 2021, 41(7): 1891-1896.
[8]	WANG Shouhua, WU Lirong, JI Yuanfa, SUN Xiyan. Fast ambiguity resolution method based on lattice theory [J]. Journal of Computer Applications, 2020, 40(8): 2299-2304.
[9]	Yizhuo ZHANG, Sen GE, Liangjun WANG, Jiang XIE, Jie CAO, Wu ZHANG. Parallel computing of bifurcation stenosis flows of carotid artery based on lattice Boltzmann method and large eddy simulation model [J]. Journal of Computer Applications, 2020, 40(2): 404-409.
[10]	Zhixiang LIU, Huichao LIU, Dongmei HUANG, Liping ZHOU, Cheng SU. IB-LBM parallel optimization method mixed with multiple task scheduling modes [J]. Journal of Computer Applications, 2020, 40(2): 386-391.
[11]	JIN Kaizhong, PENG Huili, ZHANG Xiaojian. Trajectory pattern mining with differential privacy [J]. Journal of Computer Applications, 2017, 37(10): 2938-2945.
[12]	WU Jie, LIANG Yan, MA Yuan. Incremental formation of concept lattice based on intent waned value [J]. Journal of Computer Applications, 2017, 37(1): 222-227.
[13]	LIU Mingye, HAN Yiliang, YANG Xiaoyuan. Signcryption scheme based on low-density generator-matrix code [J]. Journal of Computer Applications, 2016, 36(9): 2459-2464.
[14]	SUN Yiru, LIANG Xiangqian, SHANG Yufang. Identity based ring signature scheme in ideal lattice [J]. Journal of Computer Applications, 2016, 36(7): 1861-1865.
[15]	XIANG Wen, YANG Xiaoyuan, WANG Xu'an, WU Liqiang. Forward secure identity-based signcryption from lattice [J]. Journal of Computer Applications, 2016, 36(11): 3077-3081.