RLWE-type Authentication Key Exchange Protocol Based on Key Encapsulation Mechanism

doi:10.3969/j.issn.1671-1122.2021.06.010

Abstract

Abstract:

At present, constructing key exchange protocol based on lattice theory has become the research frontier in the field of key exchange. Designing efficient key exchange protocol with stronger security, smaller size of key and ciphertext and communication overhead is an important and difficult problem in the field of lattice key exchange.Based on the compact RLWE public key encryption scheme and the ciphertext compression and NTT conversion technology in NewHope-Simple, and combined with FO conversion mechanism, an active secure KEM scheme is proposed. Using the implicit authentication and identity authentication methods, an authenticated key exchange protocol which can prove secure under the standard eCK model is constructed. In terms of protocol security, the proposed protocol improves from passive security to active security compared with NewHope-Simple protocol. In terms of ciphertext size and communication overhead, compared with the existing key exchange protocols based on key encapsulation mechanism, the key encapsulation mechanism in this protocol effectively reduces the ciphertext size and communication overhead through analysis, which is a compact, efficient and active secure anti-quantum authentication key exchange protocol based on key encapsulation mechanism.

Key words: RLWE, FO conversion, encryption mechanism, authentication key exchange, standard eCK model

CLC Number:

TP309

WANG Chao, HAN Yiliang, DUAN Xiaowei, LI Yu. RLWE-type Authentication Key Exchange Protocol Based on Key Encapsulation Mechanism[J]. Netinfo Security, 2021, 21(6): 80-88.

Figures/Tables 4

References 21

[1]	SHOR P. Polynomial-time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer[J]. Siam Review, 1999,41(2):303-332. doi: 10.1137/S0036144598347011 URL
[2]	AJTAI M, DWORK C. A Public-key Cryptosystem with Worst-case/Average-case Equivalence[C]// ACM. 29rd Annual ACM Symposium on the Theory of Computing, May 4-6, 1997, El Paso, Texas, USA. New York: ACM, 1997: 284-293.
[3]	CHEN L, JORDAN S, LIU YK, et al. Report on Post-quantum Cryptography[R]. USA: National Institute of Standards and Technology, NISTIR 8105, 2016.
[4]	PEIKERT C. A Decade of Lattice Cryptography[J]. Foundations & Trends in Theoretical Computer Science, 2016,10(4):283-424.
[5]	HAN Yiliang, WANG Zhong. Anti-quantum Cryptography Scheme Based on Multivariate and LRPC Codes[J]. Netinfo Security, 2019,19(8):36-43.
	韩益亮, 王众. 基于多变量和LRPC码的抗量子密码方案研究[J]. 信息网络安全, 2019,19(8):36-43.
[6]	REGEV O. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[C]// ACM. 37rd Annual ACM Symposium on the Theory of Computing, May 22-24, 2005, Baltimore, MD, USA. New York: ACM, 2005: 84-93.
[7]	ALKIM E, BARRETO P S L M, BINDEL N, et al. The Lattice-based Digital Signature SchemeqTESLA[C]// Springer. 18rd International Conference on Applied Cryptography and Network Security, October 19-22, 2020, Rome, Italy. Cham: Springer, 2020: 441-460.
[8]	GAO Xinwei, DING Jintai, SARASWATHY R V, et al. Comparison Analysis and Efficient Implementation of Reconciliation-based RLWE Key Exchange Protocol[J]. International Journal of High Performance Computing and Networking, 2019,13(2):141-152. doi: 10.1504/IJHPCN.2019.097505 URL
[9]	CHEN Hao, DAI Wei, KIM M, et al. Efficient Multi-key Homomorphic Encryption with Packed Ciphertexts with Application to Oblivious Neural Network Inference[C]// ACM. 26rd ACM SIGSAC Conference on Computer and Communications Security, November 11-15, 2019, London, UK. New York: ACM, 2019: 395-412.
[10]	LYUBASHEVSKY V, PEIKERT C, REGEV O. On Ideal Lattices and Learning with Errors over Rings[C]// Springer. 29rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, May 30-June 3, 2010, Riviera, French. Berlin: Springer, 2010: 1-23.
[11]	BOS J W, DUCAS L, KILTZ E, et al. CRYSTALS-kyber: A CCA-secure Module-lattice-based KEM[C]//IEEE. 3rd IEEE European Symposium on Security and Privacy, April 24-26, 2018, London, UK. Piscataway, NJ: IEEE Press, 2018: 353-367.
[12]	LANGLOIS A, DAMIEN STEHLÉ. Worst-case to Average-case Reductions for Module Lattices[J]. Designs, Codes and Cryptography, 2015,75(3):565-599. doi: 10.1007/s10623-014-9938-4 URL
[13]	DING Jintai, XIE Xiang, 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.
[14]	PEIKERT C. Lattice Cryptography for the Internet [C]//Springer. 6rd International Workshop, Post-quantum Cryptography, October 1-3, 2014, Waterloo, ON, Canada. Berlin: Springer, 2014: 197-219.
[15]	BOS J W, 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.
[16]	ALKIM E, DUCAS L, POPPELMANN T, et al. Post-quantum Key Exchange: A New Hope [C]//USENIX. 25rd USENIX Security Symposium, August 10-12, 2016, Austin, TX. Berkeley: USENIX, 2016: 327-343.
[17]	ALKIM E, DUCAS L, POPPELMANN T, et al. NewHope without Reconciliation[J]. IACR Cryptology ePrint Archive, 2016,2016(1):1157-1166.
[18]	LI Zichen, XIE Ting, ZHANG Juanmei, et al. Post Quantum Authenticated Key Exchange Protocol Based on Ring Learning with Errors Problem[J]. Journal of Computer Research and Development, 2019,56(12):2694-2701.
	李子臣, 谢婷, 张卷美, 等. 基于RLWE的后量子认证密钥交换协议[J]. 计算机研究与发展, 2019,56(12):2694-2701.
[19]	YANG Yatao, HAN Xinguang, HUANG Jierun, et al. Bidirectional Authentication Key Agreement Protocol Supporting Identity’s Privacy Preservation Based on RLWE[J]. Journal on Communications, 2019,40(11):180-186.
	杨亚涛, 韩新光, 黄洁润, 等. 基于RLWE支持身份隐私保护的双向认证密钥协商协议[J]. 通信学报, 2019,40(11):180-186.
[20]	HÖVELMANNS K, KILTZ E, SCHÄGE S, et al. Generic Authenticated Key Exchange in the Quantum Random Oracle Model[C]// Springer. 23rd IACR International Conference on Public-key Cryptography, May 4-7, 2020, Edinburah, UK. Berlin: Springer, 2020: 389-422.
[21]	DENNIS H, KATHRIN H, EIKE K. A Modular Analysis of the Fujisaki-okamoto Transformation[C]// Springer. 15rd Theory of Cryptography Conference, November 12-15, 2017, Baltimore, USA. Berlin: Springer, 2017: 341-371.

协议	$n$	$q$	困难问题	安全性	安全模型
CRYSTALS-Kyber	256	7681	MLWE	主动安全	CK
文献[18]协议	1024	12289	RLWE	主动安全	eCK
NewHope-Simple	1024	12289	RLWE	被动安全	RO
本文协议	1024	12289	RLWE	主动安全	eCK

方案	封装密钥/B	解装密钥/B	密文量/B	通信量/B
NewHope-Simple	1824	1792	2176	4000
文献[18]方案	1451	3200	1579	3030
本文方案	1824	3776	896	2720

方案	维度$n$	${{d}_{u}}$	${{d}_{v}}$	密文量/B
CRYSTALS-Kyber	256	11	3	1184
本文方案	256	11	3	480