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

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

Abstract

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

CLC Number:

TN918.1

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.

Figures/Tables 5

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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

名称	集中式/两方	安全级别	仿真时间/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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 37

Related Articles 8

Metrics

Recommended 0

[1]	Yuanbo GUO, Anqi YIN. Research on password-authenticated key exchange protocol over lattices [J]. Journal on Communications, 2022, 43(12): 172-187.
[2]	Caifen WANG,Li CHEN. Three-party password authenticated key agreement protocol with user anonymity based on lattice [J]. Journal on Communications, 2018, 39(2): 21-30.
[3]	Zhi-yan XU,Li-bing WU,Li LI,De-biao HE. Provably secure certificateless aggregate signature scheme in wireless roaming authentication [J]. Journal on Communications, 2017, 38(7): 123-130.
[4]	De-xin YANG,Bo YANG,Xi-ming LI. Efficient two-server password authenticated key exchange scheme [J]. Journal on Communications, 2010, 31(9A): 228-232.
[5]	Jian SHU,Chun-xiang XU. Analysis and improvement of a password-based authenticated key exchange protocol [J]. Journal on Communications, 2010, 31(3): 51-56.
[6]	Feng-jiao WANG,Yu-qing ZHANG. New security model for cross-realm C2C-PAKE protocol [J]. Journal on Communications, 2008, 29(4): 24-29.
[7]	Hui-xian LI,Liao-jun PANG. Provably secure secret sharing scheme based on bilinear maps [J]. Journal on Communications, 2008, 29(10): 45-50.
[8]	Jun LIU,Jian-xin LIAO,Feng ZHU,Chun WANG. Correcting the security definition of the Bellare-Rogaway 3PKD model [J]. Journal on Communications, 2007, 28(9): 1-6.