格上无非交互式零知识证明的两轮三方PAKE协议

doi:10.11772/j.issn.1001-9081.2023040417

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (3): 805-810.DOI: 10.11772/j.issn.1001-9081.2023040417

格上无非交互式零知识证明的两轮三方PAKE协议

尹新媛, 郑小建(), 熊金波

福建师范大学计算机与网络空间安全学院，福州 350117

收稿日期:2023-04-12 修回日期:2023-07-05 接受日期:2023-07-10 发布日期:2023-12-04 出版日期:2024-03-10
通讯作者: 郑小建
作者简介:尹新媛（2002—），女，山东临沂人，主要研究方向：口令认证密钥交换协议
熊金波（1981—），男，湖南益阳人，教授，博士，CCF高级会员，主要研究方向：大数据安全、隐私保护。
基金资助:
国家自然科学基金资助项目(62272102)

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

Xinyuan YIN, Xiaojian ZHENG(), Jinbo XIONG

College of Computer and Cyber Security，Fujian Normal University，Fuzhou Fujian 350117，China

Received:2023-04-12 Revised:2023-07-05 Accepted:2023-07-10 Online:2023-12-04 Published:2024-03-10
Contact: Xiaojian ZHENG
About author:YIN Xinyuan， born in 2002. Her research interests include password-authenticated key exchange protocol.
XIONG Jinbo， born in 1981， Ph. D.， professor. His research interests include big data security，privacy protection.
Supported by:
National Natural Science Foundation of China(62272102)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP309

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

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.

图/表 4

表1 符号定义

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 (⋅)$	多项式函数

表1 符号定义

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 (⋅)$	多项式函数

图1 格上无NIZK证明的两轮三方PAKE协议

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

表2 不同三方PAKE协议的执行时间对比 ( s)

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

表3 不同三方PAKE协议的安全性及其他性能对比

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］

参考文献 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]	崔剑阳, 蔡英, 张宇, 范艳芳. 车载自组织网络中格基签密的可认证隐私保护方案[J]. 《计算机应用》唯一官方网站, 2024, 44(1): 233-241.
[2]	李金波, 张平, 张冀, 刘牧华. NTRU格上基于身份的环签名方案[J]. 《计算机应用》唯一官方网站, 2023, 43(9): 2798-2805.
[3]	杨盼, 张敏情, 葛虞, 狄富强, 张英男. 基于风格迁移过程的彩色图像信息隐藏算法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1730-1735.
[4]	陈林颖, 刘建华, 孙水华, 郑智雄, 林鸿辉, 林杰. 面向方面的自适应跨度特征的细粒度意见元组提取[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1454-1460.
[5]	隋佳宏, 毛莺池, 于慧敏, 王子成, 平萍. 基于图注意力网络的全局图像描述生成方法[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1409-1415.
[6]	张韵, 王淑营, 郑庆, 张海柱. 保持细节几何特征的三维网格模型轻量化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1226-1232.
[7]	吕学强, 张煜楠, 韩晶, 崔运鹏, 李欢. 融合边特征与注意力的表格结构识别模型[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 752-758.
[8]	马英杰, 肖靖, 赵耿, 曾萍, 杨亚涛. 可控网格多涡卷混沌系统族及其硬件电路实现[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 956-961.
[9]	刘丽, 陈长波. 带状稀疏矩阵乘法及高效GPU实现[J]. 《计算机应用》唯一官方网站, 2023, 43(12): 3856-3867.
[10]	徐贵双, 殷新春. 车载自组网无证书条件隐私保护认证方案[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3358-3367.
[11]	刘乾, 张洋铭, 万定生. 网格化分布式新安江模型并行计算算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3327-3333.
[12]	赵学健, 李豪, 唐浩天. 基于用户兴趣概念格约简的推荐评分预测算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3340-3345.
[13]	杨栩, 郭红伟, 李婉雪. 优化编码树单元级比特分配算法[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3195-3201.
[14]	农强, 张棒棒, 欧阳玉豪. 基于格的分层无证书代理签名方案[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 154-159.
[15]	赵洪, 喻书涵, 韩妍妍, 李兆斌. 无证书签名方案的分析与改进[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 147-153.

格上无非交互式零知识证明的两轮三方PAKE协议

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 26

相关文章 15

编辑推荐

Metrics