可证明安全的抗量子两服务器口令认证密钥交换协议

doi:10.11959/j.issn.1000-436x.2022052

通信学报 ›› 2022, Vol. 43 ›› Issue (3): 14-29.doi: 10.11959/j.issn.1000-436x.2022052

可证明安全的抗量子两服务器口令认证密钥交换协议

尹安琪¹, 郭渊博¹, 汪定²^,³, 曲彤洲¹, 陈琳¹

¹ 信息工程大学密码工程学院，河南郑州 450001
² 南开大学网络空间安全学院，天津 300350
³ 南开大学天津市网络与数据安全技术重点实验室，天津 300350

修回日期:2022-02-15 出版日期:2022-03-25 发布日期:2022-03-01
作者简介:尹安琪（1995- ），女，山东临沂人，信息工程大学博士生，主要研究方向为安全协议设计及格密码理论等
郭渊博（1975- ），男，陕西周至人，博士，信息工程大学教授、博士生导师，主要研究方向为网络防御、数据挖掘、机器学习和人工智能安全等
汪定（1985- ），男，湖北十堰人，博士，南开大学教授、博士生导师，主要研究方向为公钥密码学、系统安全、人工智能等
曲彤洲（1994- ），男，辽宁铁岭人，信息工程大学博士生，主要研究方向为网络安全和安全专用芯片设计等
陈琳（1975- ），女，河南开封人，博士，信息工程大学副教授、硕士生导师，主要研究方向为信息安全、安全专用芯片设计等
基金资助:
国家自然科学基金资助项目(61501515)

Provably secure quantum resistance two-server password-authenticated key exchange protocol

Anqi YIN¹, Yuanbo GUO¹, Ding WANG²^,³, Tongzhou QU¹, Lin CHEN¹

¹ Department of Cryptogram Engineering, Information Engineering University, Zhengzhou 450001, China
² College of Cyber Science, Nankai University, Tianjin 300350, China
³ Tianjin Key Laboratory of Network and Data Security Technology, Nankai University, Tianjin 300350, China

Revised:2022-02-15 Online:2022-03-25 Published:2022-03-01
Supported by:
The National Natural Science Foundation of China(61501515)

摘要/Abstract

摘要：

针对基于格的单服务器口令认证密钥交换（PAKE）协议不能抵抗服务器泄露攻击，而目前基于格的多服务器 PAKE 协议的执行效率较低且不适用于两服务器场景的问题，利用带误差学习（LWE），提出了格上第一个非适应性两方平滑投影哈希函数（SPHF），具备不可区分适应性选择密文攻击（IND-CCA2）的安全性，并约束了所基于的公钥加密（PKE）方案中相关参数的大小。基于此，分别针对被动和主动敌手的攻击，提出了相应的格上可证明安全的两服务器PAKE协议。所提出的2个协议可抵御量子攻击且实现了唯口令设置，也不需要使用签名/验签、全同态加密、秘密共享等昂贵密码原语来保证安全性，被动敌手攻击下的协议还避免了零知识证明的使用。此外，在标准模型下，对所提出的2个协议进行了严格的安全性证明。实验结果表明，所提出的两方SPHF和两服务器PAKE协议的执行效率较高。

关键词: 口令认证密钥交换协议, 两服务器, 平滑投影哈希函数, 可证明安全, 抗量子

Abstract:

Aiming at the problem that the lattice-based single-sever password-authenticated key exchange (PAKE) protocols are not resistant to server compromise attack, while the existing lattice-based multi-server PAKE protocols are inefficient and incompatible with two-server scenarios.The first lattice-based two-party smooth projective hash function (SPHF) was proposed by utilizing the learning with errors (LWE), which was indistinguishability under adaptive chosen-ciphertext attack(IND-CCA2) secure.The parameters of the based public key encryption (PKE) scheme were also identified.On this basis, pertinent two-server PAKE protocols from lattices were designed countering both passive and active attackers.The two quantum resistance protocols were able to achieve password-only settings and the expensive cryptographic primitives were not used, including signature/verification, fully homomorphic encryption and secret sharing.The utilization of zero knowledge proofs were avoided by the protocol under the passive attackers.In the standard model, rigorous security proofs were provided for the two proposed protocols.Experimental results show that the proposed SPHF and PAKE protocols exhibit higher execution efficiency.

Key words: password-authenticated key exchange protocol, two-server, smooth projective hash function, provably secure, quantum resistance

中图分类号:

TN918.1

尹安琪, 郭渊博, 汪定, 曲彤洲, 陈琳. 可证明安全的抗量子两服务器口令认证密钥交换协议[J]. 通信学报, 2022, 43(3): 14-29.

Anqi YIN, Yuanbo GUO, Ding WANG, Tongzhou QU, Lin CHEN. Provably secure quantum resistance two-server password-authenticated key exchange protocol[J]. Journal on Communications, 2022, 43(3): 14-29.

图/表 5

表1

符号定义"

符号	含义
$κ$	安全参数
q	LWE问题的模数（为素数或某素数的幂）
$\leftarrow / \overset{r}{\leftarrow}$	取样/随机取样
$⌈ \cdot ⌉ / ⌊ \cdot ⌋$	向上/下取整
$\|\| x \|\| / \|\| A \|\|$	向量x的模/集合A的大小
\|\|	向量或矩阵的纵向级联
\|	向量或矩阵的横向级联
pw	口令
$D$	口令空间
⊥	非法标识
Ham(·,·)	汉明距离函数
$0$	零向量/零矩阵

表1

图1

表2

表3

表4

参考文献 37

[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.
[2]	汪定 . 口令安全关键问题研究[D]. 北京:北京大学, 2017.
	WANG D . Research on key issues in password security[D]. Beijing:Peking University, 2017.
[3]	SHOR P W , . Algorithms for quantum computation:discrete logarithms and factoring[C]// Proceedings of the 35th Annual Symposium on Foundations of Computer Science. Piscataway:IEEE Press, 1994: 124-134.
[4]	叶茂 . 基于格的口令认证密钥交换协议和相关加密算法研究[D]. 郑州:信息工程大学, 2013.
	YE M . Research on password-based authenticated key exchange protocols and associated encryption algorithms from lattices[D]. Zhengzhou:Information Engineering University, 2013.
[5]	ASIF R . Post-quantum cryptosystems for Internet-of-things:a survey on lattice-based algorithms[J]. IoT, 2021,2(1): 71-91.
[6]	ROY P S , DUTTA S , SUSILO W ,et al. Password protected secret sharing from Lattices[C]// Applied Cryptography and Network Security. Berlin:Springer, 2021: 442-459.
[7]	HALEVI S , KRAWCZYK H . Public-key cryptography and password protocols[J]. ACM Transactions on Information and System Security, 1999,2(3): 230-268.
[8]	GONG L , LOMAS M A , NEEDHAM R M ,et al. Protecting poorly chosen secrets from guessing attacks[J]. IEEE Journal on Selected Areas in Communications, 1993,11(5): 648-656.
[9]	YI X , HAO F , BERTINO E . ID-based two-server password-authenticated key exchange[C]// Computer Security ESORICS 2014. Berlin:Springer, 2014: 257-276.
[10]	YI X , RAO F Y , TARI Z ,et al. ID2S password-authenticated key exchange protocols[J]. IEEE Transactions on Computers, 2016,65(12): 3687-3701.
[11]	RAIMONDO D M , GENNARO R . Provably secure threshold password-authenticated key exchange[J]. Journal of Computer and System Sciences, 2006,72(6): 978-1001.
[12]	LI Z P , WANG D . Two-round PAKE protocol over lattices without NIZK[C]// Information Security and Cryptology. Berlin:Springer, 2019: 138-159.
[13]	LI Z P , WANG D . Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2022,15(1): 308-321.
[14]	BENHAMOUDA F , BLAZY O , DUCAS L ,et al. Hash proof systems over lattices revisited[C]// Public-Key Cryptography PKC 2018. Berlin:Springer, 2018: 644-674.
[15]	ZHANG J , YU Y . Two-round PAKE from approximate SPH and instantiations from lattices[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2017: 37-67.
[16]	KATZ J , MACKENZIE P , TABAN G ,et al. Two-server password-only authenticated key exchange[J]. Journal of Computer and System Sciences, 2012,78(2): 651-669.
[17]	BELLOVIN S M , MERRITT M . Encrypted key exchange:password-based protocols secure against dictionary attacks[C]// Proceedings 1992 IEEE Computer Society Symposium on Research in Security and Privacy. Piscataway:IEEE Press, 1992: 72-84.
[18]	KATZ J , OSTROVSKY R , YUNG M . Efficient password-authenticated key exchange using human-memorable passwords[C]// Lecture Notes in Computer Science. Berlin:Springer, 2001: 475-494.
[19]	GENNARO R , LINDELL Y . A framework for password-based authenticated key exchange[J]. ACM Transactions on Information and System Security (TISSEC), 2006,9(2): 181-234.
[20]	JIANG S Q , GONG G . Password based key exchange with mutual authentication[C]// International Workshop on Selected Areas in Cryptography. Berlin:Springer, 2004: 267-279.
[21]	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 Press, 2010: 516-525.
[22]	ABDALLA M , BENHAMOUDA F , POINTCHEVAL D . Public-key encryption indistinguishable under plaintext-checkable attacks[J]. IET Information Security, 2016,10(6): 288-303.
[23]	KATZ J , VAIKUNTANATHAN V . Round-optimal password-based authenticated key exchange[C]// Theory of Cryptography. Berlin:Springer, 2011: 293-310.
[24]	KATZ J , VAIKUNTANATHAN V . Smooth projective hashing and password-based authenticated key exchange from lattices[C]// Advances in Cryptology - ASIACRYPT 2009. Berlin:Springer, 2009: 636-652.
[25]	CRAMER R , SHOUP V . Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption[C]// Advances in Cryptology - EUROCRYPT 2002. Berlin:Springer, 2002: 45-64.
[26]	PEIKERT C , VAIKUNTANATHAN V , WATERS B . A framework for efficient and composable oblivious transfer[C]// Advances in Cryptology - CRYPTO 2008 Berlin:Springer, 2008: 554-571.
[27]	MICCIANCIO D , PEIKERT C . Trapdoors for lattices:simpler,tighter,faster,smaller[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2012: 700-718.
[28]	BLAZY O , CHEVALIER C , DUCAS L ,et al. Exact smooth projective hash function based on LWE[R]. 2013.
[29]	尹安琪, 曲彤洲, 郭渊博 ,等. 格上基于密文标准语言的可证明安全两轮口令认证密钥交换协议[J]. 电子学报, 2021:doi.org/10.12263/DZXB.20210517.
	YIN A Q , QU T Z , GUO Y B ,et al. Provably secure two-round PAKE based on ciphertext standard language over lattices[J]. Acta Electronica Sinica， 2021:doi.org/10.12263/DZXB.20210517.
[30]	BENHAMOUDA F , BLAZY O , CHEVALIER C ,et al. New techniques for SPHFs and efficient one-round PAKE protocols[C]// Advances in Cryptology-CRYPTO 2013. Berlin:Springer, 2013: 449-475.
[31]	CANETTI R , GOLDREICH O , HALEVI S . The random oracle methodology,revisited[J]. Journal of the ACM, 2004,51(4): 557-594.
[32]	ZHANG J , YU Y , FAN S Q ,et al. Improved lattice-based CCA2-secure PKE in the standard model[J]. Science China Information Sciences, 2020,63(8): 1-22.
[33]	REGEV O . On lattices,learning with errors,random linear codes,and cryptography[J]. Journal of the ACM, 2009,56(6): 1-40.
[34]	BELLARE M , POINTCHEVAL D , ROGAWAY P . Authenticated key exchange secure against dictionary attacks[C]// International conference on the theory and applications of cryptographic techniques. Berlin:Springer, 2000: 139-155.
[35]	WANG D , CHENG H B , WANG P ,et al. Zipf’s law in passwords[J]. IEEE Transactions on Information Forensics and Security, 2017,12(11): 2776-2791.
[36]	WANG D , WANG P . On the implications of Zipf’s law in passwords[C]// Computer Security - ESORICS 2016. Berlin:Spinger, 2016: 111-131.
[37]	BAUM C , BOOTLE J , CERULLI A ,et al. Sub-linear lattice-based zero-knowledge arguments for arithmetic circuits[C]// Advances in Cryptology - CRYPTO 2018. Berlin:Springer, 2018: 669-699.

名称	集中式/两方	安全级别	仿真时间/s
名称	集中式/两方	安全级别	1 bit	128 bit	256 bit	512 bit
KV.SPHF	集中式	IND-CCA1	0.001 243	0.159 105	0.318 210	0.636 420
MP.SPHF	集中式	IND-CCA1	0.000 034	0.004 343	0.008 686	0.017 373
Reg.SPHF	集中式	IND-CPA	0.004 779	0.611 750	1.223 500	2.447 000
SPKE.SPHF	集中式	IND-CPA	0.000 044	0.005 700	0.011 401	0.022 803
WI-2SPHF-1S	两方	IND-CCA2	0.000 303	0.003 352	0.006 430	0.012 584
WI-2SPHF-2S	两方	IND-CCA2	0.000 606	0.006 705	0.012 860	0.025 170
注：WI-2SPHF-1S表示WI-2SPHF在一个服务器上的执行情况；WI-2SPHF-2S表示WI-2SPHF在2个服务器上的执行情况

协议	协议类型	仿真时间/s		轮数（次数）	通信开销/bit	存储开销/bit
协议	协议类型	客户端	服务器端	轮数（次数）	通信开销/bit	客户端	服务器端
Zhang-Yu’s PAKE	单服务器	0.019 393	0.019 365	2(2)	80 652	810 696	810 696
Li-Wang’s PAKE1	单服务器	0.004 717	0.004 717	1(2)	28 416	461 220	461 220
Li-Wang’s PAKE2	单服务器	0.612 124	0.009 369	2(2)	28 416	452 016	461 616
Benhamouda et al.’s PAKE	单服务器	0.018 751	0.018 656	1(2)	85 248	825 636	825 636
Katz et al.’s PAKE	单服务器	0.102 555	0.102 583	3(3)	931 852	32 573 884	32 573 884
2S-PAKE	两服务器	0.007 706	0.008 010	1(4)	131 472	926 976	926 784
注：除本文的2S-PAKE协议外，其他协议的开销还需要在表中数据的基础上添加由签名/验签等算法引入的额外部分

协议	量子攻击	唯口令	服务泄露	签名/验签	零知识证明	服务器数目	轮数（次数）	安全模型	协议类型
Yi1	×	×	√	√	√	2	2(4)	—	密钥传输
Yi2	×	×	√	√	√	2	3(6)	—	密钥传输
Roy	√	×	√	√	√	N	3(6N)	标准模型	密钥传输
Raimondo et al.’s PAKE	×	√	√	√	×	N	3(6N)	标准模型	密钥交换
2S-PAKE（被动）	√	√	√	×	×	2	1(4)	标准模型	密钥交换
2S-PAKE（主动）	√	√	√	×	√	2	1(4)	标准模型	密钥交换

可证明安全的抗量子两服务器口令认证密钥交换协议

Provably secure quantum resistance two-server password-authenticated key exchange protocol

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献 37

相关文章 15

Metrics

推荐阅读 0

[1]	黄华伟. 基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析[J]. 通信学报, 2023, 44(3): 220-226.
[2]	廉欢欢, 侯慧莹, 赵运磊. 后量子基于验证元的三方口令认证密钥交换协议[J]. 通信学报, 2022, 43(4): 95-106.
[3]	郭渊博, 尹安琪. 基于格的口令认证密钥交换协议综述[J]. 通信学报, 2022, 43(12): 172-187.
[4]	王后珍, 蔡鑫伟, 郭岩, 张焕国. 基于矩阵填充问题的五轮零知识身份认证方案[J]. 通信学报, 2021, 42(11): 79-86.
[5]	刘镇,韩益亮,杨晓元,柳曙光. 基于RLWE的可证明安全无陷门签密方案[J]. 通信学报, 2020, 41(6): 14-25.
[6]	彭长根, 张小玉, 丁红发, 杨善慧. 基于Cocks身份密码体制的高效签密方案[J]. 通信学报, 2020, 41(12): 128-138.
[7]	田有亮,李秋贤,张铎,王琳杰. 可证明安全的理性委托计算协议[J]. 通信学报, 2019, 40(7): 135-143.
[8]	王彩芬,陈丽. 基于格的用户匿名三方口令认证密钥协商协议[J]. 通信学报, 2018, 39(2): 21-30.
[9]	李昊星,李凤华,宋承根,阎亚龙. 支持身份认证的数据持有性证明方案[J]. 通信学报, 2016, 37(10): 117-127.
[10]	张宇，杜瑞颖，陈晶，侯健，周庆，王文武. 对一个基于身份签密方案的分析与改[J]. 通信学报, 2015, 36(11): 174-179.
[11]	魏江宏,刘文芬,胡学先. 前向安全的密文策略基于属性加密方案[J]. 通信学报, 2014, 35(7): 38-45.
[12]	马海英,曾国荪,王占君,王伟. 高效可证明安全的基于属性的在线/离线加密机制[J]. 通信学报, 2014, 35(7): 104-112.
[13]	魏江宏，刘文芬，胡学先. 前向安全的密文策略基于属性加密方案[J]. 通信学报, 2014, 35(7): 5-45.
[14]	马海英，曾国荪，王占君，王伟. 高效可证明安全的基于属性的在线/离线加密机制[J]. 通信学报, 2014, 35(7): 13-112.
[15]	杨玉龙,彭长根,周洲,张晓培. 基于Edwards曲线的移动RFID安全认证协议[J]. 通信学报, 2014, 35(11): 132-138.