Two-round three-party password-authenticated key exchange protocol over lattices without non-interactive zero-knowledge proof

doi:10.11772/j.issn.1001-9081.2023040417

Abstract

Abstract:

Focused on the issues of high communication rounds and low execution efficiency in existing lattice-based three-party Password-Authenticated Key Exchange （PAKE） protocols， a two-round three-party PAKE protocol over lattices without Non-Interactive Zero-Knowledge （NIZK） proof was proposed. First， the advantage of non-adaptive approximate smooth projective hash function was taken to achieve key exchange and reduce the number of communication rounds without NIZK proof. Second， session keys were constructed by using hash values and projection hash values without random oracles， thus avoiding potential password guessing attacks. Finally， formal security proof of the proposed protocol was given in the standard model. Simulation results show that compared with lattice-based three-party PAKE protocols， the proposed protocol has the execution time reduced by 89.2% - 98.6% on the client side and 19.0% - 91.6% on the server side. It is verified that the proposed protocol can resist quantum attacks with high execution efficiency and few communication rounds.

Key words: lattice, three-party key exchange, Password-Authenticated Key Exchange (PAKE), Non-Interactive Zero-Knowledge (NIZK), provably secure

摘要：

针对现有基于格的三方口令认证密钥交换（PAKE）协议通信轮次较多、执行效率较低等问题，提出一种格上无非交互式零知识证明的两轮三方PAKE协议。首先，利用非适应性近似平滑投影哈希函数实现密钥交换，在不使用非交互式零知识（NIZK）证明的前提下，降低协议的通信轮数；其次，利用哈希值和投影哈希值构造会话密钥，不需要使用随机预言机，避免了随机预言机导致的潜在口令猜测攻击。在标准模型下给出所提协议的形式化安全证明。仿真结果表明，与基于格的三方PAKE协议相比，所提协议的执行时间在客户端缩短了89.2%~98.6%，在服务器端缩短了19.0%~91.6%。验证了所提协议能够抵抗量子攻击，具有较高的执行效率，同时减少了协议通信轮数。

关键词: 格, 三方密钥交换, 口令认证密钥交换, 非交互式零知识, 可证明安全

CLC Number:

TP309

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.

尹新媛, 郑小建, 熊金波. 格上无非交互式零知识证明的两轮三方PAKE协议[J]. 《计算机应用》唯一官方网站, 2024, 44(3): 805-810.

Figures/Tables 4

Tab. 1 Symbols definition

符号	含义	符号	含义
$κ$	安全参数	$D$	口令空间
$n e g l ⋅$	可忽略函数	$D$	口令空间的大小
$p w$	口令	ECC/ECC^-1	纠错码算法
$H a m$	汉明距离函数	$P r$	概率函数
$← r$	随机取样	$p o l y (⋅)$	多项式函数

Tab. 1 Symbols definition

符号	含义	符号	含义
$κ$	安全参数	$D$	口令空间
$n e g l ⋅$	可忽略函数	$D$	口令空间的大小
$p w$	口令	ECC/ECC^-1	纠错码算法
$H a m$	汉明距离函数	$P r$	概率函数
$← r$	随机取样	$p o l y (⋅)$	多项式函数

Fig. 1 Two-round tree-party PAKE protocol over lattices without NIZK proof

Tab. 2 Comparison of execution time among different third-party PAKE protocols

协议	客户端	服务器端
文献［11］协议	1.918 681 118 1	2.888 690 508 4
文献［2］协议	13.987 025 054 6	27.974 053 010 2
本文协议	0.201 193 686 1	2.339 465 461 4

Tab. 3 Comparison of security and other performance among different three-party PAKE protocols

协议	抗量子攻击	安全模型	安全性假设		零知识证明	通信轮数	通信开销
协议	抗量子攻击	安全模型	客户端	服务器端	零知识证明	通信轮数	通信开销
文献［11］协议	√	标准模型	IND-CPA	IND-CCA	×	3	2［（mn+m+n） log q+3n］
文献［2］协议	√	随机预言机	IND-CCA	IND-CCA	√	2	2［（2m+2n₁） log q+2n］
本文协议	√	标准模型	IND-CPA	IND-CCA	×	2	2［（mn+m+2n） log q+2n］

References 26

1	SHIN J S， JO M， HWANG J Y， et al. A verifier-based password-authenticated key exchange using tamper-proof hardware ［J］. The Computer Journal， 2021， 64 （8）： 1293-1302. 10.1093/comjnl/bxaa178
2	于金霞，廉欢欢，汤永利，等. 格上基于口令的三方认证密钥交换协议［J］. 通信学报， 2018， 39 （11）： 87-97. 10.11959/j.issn.1000-436x.2018237
	YU J X， LIAN H H， TANG Y L， et al. Password-based three-party authenticated key exchange protocol from lattices ［J］. Journal on Communications， 2018， 39（11）： 87-97. 10.11959/j.issn.1000-436x.2018237
3	郭渊博，尹安琪. 基于格的口令认证密钥交换协议综述［J］. 通信学报， 2022， 43（12）： 172-187.
	GUO Y B， YIN A Q. Research on password-authenticated key exchange over lattices ［J］. Journal on Communications， 2022， 43（12）： 172-187.
4	KEITH M， SHAO B， STEINBART P J. The usability of passphrases for authentication： an empirical field study ［J］. International Journal of Human-Computer Studies， 2007， 65（1）： 17-28. 10.1016/j.ijhcs.2006.08.005
5	CHANG C-C， CHANG Y-F. A novel three-party encrypted key exchange protocol ［J］. Computer Standards & Interfaces， 2004， 26 （5）： 471-476. 10.1016/j.csi.2003.12.001
6	STEINER M， TSUDIK G， WAIDNER M. Refinement and extension of encrypted key exchange ［J］. ACM SIGOPS Operating Systems Review， 1995， 29（3）： 22-30. 10.1145/206826.206834
7	CHANG T-Y， M-S HWANG， YANG W-P. A communication-efficient three-party password authenticated key exchange protocol［J］. Information Sciences， 2011， 181（1）： 217-226. 10.1016/j.ins.2010.08.032
8	ABDALLA M， P-A FOUQUE， POINTCHEVAL D. Password-based authenticated key exchange in the three-party setting ［C］// Proceedings of the 8th International Conference on Theory and Practice in Public Key Cryptography. Berlin： Springer， 2005： 65-84. 10.1007/978-3-540-30580-4_6
9	JIANG S， GONG G. Password based key exchange with mutual authentication ［C］// Proceedings of the 11th International Workshop on Selected Areas in Cryptography. Berlin： Springer， 2004： 267-279. 10.1007/978-3-540-30564-4_19
10	GROCE A， KATZ J. A new framework for efficient password-based authenticated key exchange ［C］// Proceedings of the 17th ACM Conference on Computer and Communications Security. New York： ACM， 2010： 516-525. 10.1145/1866307.1866365
11	叶茂，胡学先，刘文芬. 基于格的三方口令认证密钥交换协议［J］. 电子与信息学报， 2013， 35（6）： 1376-1381. 10.3724/sp.j.1146.2012.01135
	YE M， HU X X， LIU W F. Password authenticated key exchange protocol in the three party setting based on lattices ［J］. Journal of Electronics & Information Technology， 2013， 35（6）： 1376-1381. 10.3724/sp.j.1146.2012.01135
12	XU D， HE D， CHOO K-K R， et al. Provably secure three-party password authenticated key exchange protocol based on ring learning with error ［J］. Cryptology ePrint Archive， 2017： 173311.
13	LIU C， ZHENG Z， JIA K， et al. Provably secure three-party password-based authenticated key exchange from RLWE ［C］// Proceedings of the 2019 International Conference on Information Security Practice and Experience. Cham： Springer， 2019： 56-72. 10.1007/978-3-030-34339-2_4
14	YIN A， GUO Y， SONG Y， et al. Two-round password-based authenticated key exchange from lattices ［J］. Wireless Communications and Mobile Computing， 2020， 2020： 8893628. 10.1155/2020/8893628
15	CHIESA A， MANOHAR P， SPOONER N. Succinct arguments in the quantum random oracle model ［C］// Proceedings of the 2019 Theory of Cryptography Conference. Cham： Springer， 2019： 1-29. 10.1007/978-3-030-36033-7_1
16	PEIKERT C. A decade of lattice cryptography ［J］. Foundations and Trends in Theoretical Computer Science， 2016， 10（4）： 283-424. 10.1561/0400000074
17	GENTRY C， PEIKERT C， VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions ［C］// Proceedings of the 40th Annual ACM Symposium on Theory of Computing. New York： ACM， 2008： 197-206. 10.1145/1374376.1374407
18	CRAMER R， SHOUP V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption ［C］// Proceedings of the 2002 International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2002： 45-64. 10.1007/3-540-46035-7_4
19	KATZ J， VAIKUNTANATHAN V. Smooth projective hashing and password-based authenticated key exchange from lattices ［C］// Proceedings of the 2009 International Conference on the Theory and Application of Cryptology and Information Security. Cham： Springer， 2009： 636-652. 10.1007/978-3-642-10366-7_37
20	BENHAMOUDA F， BLAZY O， DUCAS L， et al. Hash proof systems over lattices revisited ［C］// Proceedings of the 2018 IACR International Workshop on Public Key Cryptography. Cham： Springer， 2018： 644-674. 10.1007/978-3-319-76581-5_22
21	BELLARE M， POINTCHEVAL D， ROGAWAY P. Authenticated key exchange secure against dictionary attacks ［C］// Proceedings of the 2000 International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2000： 139-155. 10.1007/3-540-45539-6_11
22	GUO Y， ZHANG Z， GUO Y. Anonymous authenticated key agreement and group proof protocol for wearable computing ［J］. IEEE Transactions on Mobile Computing， 2022， 21（8）： 2718-2731. 10.1109/tmc.2020.3048703
23	ABDALLA M， BENHAMOUDA F， POINTCHEVAL D. Public-key encryption indistinguishable under plaintext-checkable attacks［C］// Proceedings of the 2015 IACR International Workshop on Public Key Cryptography. Berlin： Springer， 2015： 332-352. 10.1007/978-3-662-46447-2_15
24	REGEV O. On lattices， learning with errors， random linear codes， and cryptography ［J］. Journal of the ACM， 2009， 56（6）： 34. 10.1145/1568318.1568324
25	ZHANG J， YU Y. Two-round PAKE from approximate SPH and instantiations from lattices ［C］// Proceedings of the 2017 International Conference on the Theory and Application of Cryptology and Information Security. Cham： Springer， 2017： 37-67. 10.1007/978-3-319-70700-6_2
26	高艺恬，陈立全，屠天扬，等. 基于BRLWE的物联网后量子加密技术研究［J］.网络与信息安全学报，2022，8（5）：140-149. 10.11959/j.issn.2096-109x.2022024
	GAO Y T， CHEN L Q， TU T Y， et al. Post-quantum encryption technology based on BRLWE for internet of things ［J］. Chinese Journal of Network and Information Security， 2022， 8（5）： 140-149. 10.11959/j.issn.2096-109x.2022024

[1]	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.
[2]	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.
[3]	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.
[4]	NONG Qiang, ZHANG Bangbang, OUYANG Yuhao. Lattice-based hierarchical certificateless proxy signature scheme [J]. Journal of Computer Applications, 2023, 43(1): 154-159.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[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]	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.
[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]	LI Mingxia, LIU Baoxiang, ZHANG Chunying. Parameter optimization model of interval concept lattice based on compression theory [J]. Journal of Computer Applications, 2016, 36(11): 2945-2949.