基于格的用户匿名三方口令认证密钥协商协议

王彩芬，陈丽



基于格的用户匿名三方口令认证密钥协商协议

王彩芬，陈丽

（西北师范大学计算机科学与工程学院，甘肃 兰州 730070）

随着量子理论的快速发展，离散对数问题和大整数分解问题在量子计算下存在多项式求解算法，其安全性受到严重威胁，因此，提出2个基于环上带误差学习问题的用户匿名三方口令认证密钥协商方案，包括基于格的隐式认证密钥协商方案和基于格的显式认证密钥协商方案，并证明了其安全性。其中，隐式认证密钥协商协议通信量少、认证速度快，显式认证密钥协商协议安全性更高，同时实现用户和服务器的双向认证、可抗不可测在线字典攻击。与其他口令认证密钥协商协议相比，所提协议有更高的效率和更短的密钥长度，能够抵抗量子攻击，因此，该协议既高效又安全，适用于大规模网络下的通信。

格密码；可证明安全；口令认证；密钥交换；环上带误差

1 引言

随着大数据时代的到来以及量子计算机的快速发展，人们对数据的安全有了更高的要求，格密码依靠其独特的困难问题和归约结果成为密码学研究的热点，基于离散对数问题和大整数分解问题在量子计算下存在多项式求解算法，其安全性受到严重威胁，因此，格理论被应用于抗量子攻击的密码体制中。

认证密钥交换（AKE, authenticated key exchange）允许通信双方相互认证并协商出共享密钥，两方口令认证密钥协商[1]（2PAKE, two-party password authenticated key exchange）协议要求用户和服务器共享相同的口令，实现单个用户和服务器的相互认证，不适用于用户和用户之间的通信，为解决其局限性，密码学研究者提出三方口令认证密钥交换[2,3]（3PAKE, three-party password authenticated key exchange）协议，使每个用户和服务器共享一个低熵的口令，实现用户间的相互认证和密钥协商，适用于大规模网络下的通信。认证密钥交换通常分为显式认证和隐式认证，显式认证是指协议结束后，用户确信与之通信的就是意定的参与方；隐式认证是指协议结束后，用户相信只有意定的参与方才能计算出相同的会话密钥。显式认证协议中除了隐式认证之外，还包含一个显式密钥确认过程，使参加协议的用户可以确保其特别指定的用户确实已经拥有与其相同的会话密钥。

2005年，文献[2]基于判定性Diffie-Hellman假设（DDH, decisional Diffie-Hellman assumption）提出3PAKE协议。2006年，文献[3]提出可证明安全性的3PAKE协议，随后，有不同效率和安全性的3PAKE[4,5]协议相继被提出，但是这些已有的3PAKE的安全性都依赖于离散对数问题和大整数分解问题等一系列传统的困难问题，不能抵抗量子攻击。2009年，文献[6]首次提出了基于格的2PAKE协议，其方案基于误差学习（LWE, learning with error）问题，但存在密钥长度过长和效率低等问题。2011年，文献[7]基于平滑投射散列函数（SPH, smooth projective hashing）提出了一个更高效的2PAKE协议。2012年，文献[8]基于LWE问题提出可证明安全的两方密钥交换方案。2013年，文献[9]使用密钥封装机制提出基于RLWE的密钥交换协议，但该协议被文献[10]指出难以抵抗外部攻击者实施的假冒攻击。由于2PAKE协议的局限性，文献[11]基于近似平滑投射散列函数（ASPH, approximate smooth projective hashing）提出格的3PAKE协议。2015年，文献[12]基于RLWE困难问题提出可证明安全的2PAKE协议。同年，文献[13]基于LWE困难问题提出认证密钥交换方案，但该协议存在模数大、效率低等局限；文献[14]提出一种新型的基于环上带误差学习问题的认证密钥交换方案，但该方案是两方认证密钥协商协议。2016年，文献[15]提出基于LWE的2PAKE协议。同年，文献[16]提出基于验证元的三方口令认证密钥交换协议，但通信量较多、效率较低。2017年，文献[17]提出了基于口令的两方密钥协商协议的形式化模型，并证明其安全性。本文在其基础上，设计了一个基于格的RLWE困难问题的3PAKE协议的安全模型，并证明了协议的安全性。

为解决上述协议的局限性，提出2个基于格的用户匿名三方口令认证密钥协商协议，包括基于格的三方隐式认证密钥协商协议和基于格的三方显式认证密钥协商协议，其中，隐式认证密钥协商协议通信量少，显式认证密钥协商协议除了满足隐式认证的所有条件之外，还需要满足密钥确认，即协议参与方可以确定协议的其他参与方获得了特定的会话密钥，同时实现用户和服务器的双向认证、可抗不可测在线字典攻击。所提方案避免了2PAKE的局限性，有更高的效率和更短的密钥长度，能够抵抗量子攻击，适用于服务器和用户间的三方通信，并证明了其安全性。因此，该协议既高效又安全，适用于大规模网络下的通信。

2 预备知识

定义4 3PAKE协议的安全模型。

安全游戏。定义挑战者CH和概率多项式时间敌手A的安全参数，挑战者代表诚实用户运行协议。

3 基于格的密钥协商协议

针对之前协议存在的安全性问题，提出了基于格的三方口令认证密钥协商协议，减少了公钥长度，降低了计算复杂度和消息传输量，提高了协议的运行速度，实现了用户的匿名性。其中，隐式密钥协商协议通信量较少，显式认证密钥协商协议更安全。协议中使用的符号如表1所示。

表1 本文方案使用的符号说明

图1 基于格的三方隐式认证密钥协商方案

3.1 基于格的三方隐式认证密钥协商方案

基于格的三方隐式认证密钥协商方案（以下简称方案1）如图1所示。

3.1.1 初始化阶段

3.1.2 隐式认证与密钥协商阶段

3.2 基于格的三方显式认证密钥协商方案

由于基于格的三方隐式认证密钥协商方案通信量少、认证速度快，但不能保证用户得到了相应的会话密钥，因此，提出基于格的三方显式认证密钥协商方案（以下简称方案2），如图2所示。

3.2.1 初始化阶段

基于格的显式认证密钥协商协议的初始化阶段和基于格的隐式认证密钥协商协议的初始化阶段相同，见3.1.1节。

3.2.2 显式认证与密钥协商阶段

3.3 方案的正确性

2个方案的正确性证明相同，下面是诚实用户执行方案2时双方拥有相同的会话密钥的正确性证明。

4 安全性证明

2) 假设随机预言机对任何新询问都使用新的输出进行响应，重复询问之前的消息时，输出相同。

各协议介绍如下。

证明 显然成立，因为增加了敌手赢得游戏的机会。

表2 性能比较

综合引理4~引理10的结论可知，定理1结论成立。因此，方案可证明是安全的。

5 协议性能比较

从安全性和效率出发，给出本文2个方案与文献[6,11~13,16]方案的比较，如表2所示。

在安全性方面，与传统的3PAKE协议相比，本文方案1和方案2能够抵抗量子攻击，同时实现了用户的匿名性以及用户和服务器的双向认证，可抵抗不可测在线字典攻击。文献[6]是基于LWE困难问题的2PAKE协议，需要3轮通信，所以3PAKE协议至少需要6轮通信，且不满足用户和服务器的相互认证，不能抵抗不可测字典攻击，不满足用户匿名性；文献[11]是基于ASPH的3PAKE协议，需要3轮通信，不满足用户的匿名性；文献[12]是基于RLWE困难问题的2PAKE协议需要2轮通信，所以3PAKE协议至少需要4轮通信，且不满足用户匿名性；文献[13]提出隐式认证和显式认证2个2PAKE方案，分别需要2轮和3轮通信，所以3PAKE协议至少需要4轮和6轮通信，效率较低且不满足用户匿名性；文献[16]提出基于ASPH的3PAKE协议，需要4轮即8条消息传输量，通信量多、效率较低且不满足用户匿名性。本文方案1和方案2是3PAKE协议，分别需要2轮和3轮通信，远高于文献[6,12,13,16]的通信效率。文献[11]与本文方案2的消息传输量相同，但效率低于本文方案1。与现有方案相比，本文方案需要的采样数小，减少了公钥长度，降低了计算复杂度和消息传输量，提高了协议的运行速度，实现了用户的匿名性。因此，本文方案1和方案2具有更高的安全性和通信效率。

6 结束语

基于口令认证的密钥协商协议是用户仅选择一个简单的口令，通过服务器，在用户间建立一个共享的会话密钥。由于2PAKE协议不能实现大规模端到端的通信，且传统的困难问题不能抵抗量子攻击，因此，提出2个基于格的3PAKE协议，包括基于格的用户匿名三方隐式认证密钥协商方案和基于格的用户匿名三方显式认证密钥协商方案，并证明了协议的安全性。其中，隐式认证密钥协商协议通信量少、执行效率高，显式认证密钥协商协议安全性更高，同时实现用户和服务器的双向认证可抗不可测在线字典攻击。因此，所提协议既高效又安全。

[1] LAW L, MENEZES A, QU M, et al. An efficient protocol for authenticated key agreement[J]. Designs, Codes and Cryptography, 2003, 28(2): 119-134.

[2] ABADLLA M, FOUQUE P A, POINTCHEVAL D. Password-based authenticated key exchange in the three-party setting[C]//International Workshop on Public Key Cryptography. 2005: 65-84.

[3] RAIMANDO M D, GENNARO R. Provably secure threshold password-authenticated key exchange[J]. Journal of Computer and System Sciences, 2006, 72(6): 978-1001.

[4] ZHAO F, GONG P, LI S, et al. Cryptanalysis and improvement of a three-party key agreement protocol using enhanced Chebyshev polynomials[J]. Nonlinear Dynamics, 2013, 74(1-2): 419-427.

[5] XIE Q, ZHAO J, YU X. Chaotic maps-based three-party password-authenticated key agreement scheme[J]. Nonlinear Dynamics, 2013, 74(4): 1021-1027.

[6] KATZ J, VAIKUNTANATHAN V. Smooth projective hashing and password-based authenticated key exchange from lattices[C]// International Conference on the Theory and Application of Cryptology and Information Security. 2009: 636-652.

[7] DING Y, FAN L. Efficient password-based authenticated key exchange fromlattices[C]//2011 Seventh International Conference on Computational Intelligence and Security (CIS). 2011: 934-938.

[8] DING J, XIE X, LIN X. A simple provably secure key exchange scheme based on the learning with errors problem[J]. IACR Cryptology Eprint Archive, 2014: 688.

[9] FUJIOKA A, SUZUKI K, XAGAWA K, et al. Practical and post-quantum authenticated key exchange from one-way secure key encapsulation mechanism[C]//The 8th ACM SIGSAC Symposium on Information, Computer and Communications Security. 2013: 83-94.

[10] 胡学先, 魏江宏, 叶茂. 对一个强安全的认证密钥交换协议的分析[J]. 电子与信息学报, 2013, 35(9): 2278-2282.

HU X X, WEIJ H, YE M.Cryptanalysis of a strongly secure authenticated key exchange protocol[J]. Journal of Electronics & Information Technology, 2013, 35(9): 2278-2282.

[11] 叶茂, 胡学先, 刘文芬. 基于格的三方口令认证密钥交换协议[J]. 电子与信息学报, 2013, 35(6): 1376-1381.

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.

[12] ZHANG J, ZHANG Z, DING J, et al. Authenticated key exchange from ideal lattices[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2015: 719-751.

[13] DING J, ALASYIGH S, LANCRENON J, et al. Provably secure password authenticsated key exchange based on RLWE for the post-quantumworld[C]//Cryptographers’ Track at the RSA Conference. 2017: 183-204.

[14] 杨孝鹏, 马文平, 张成丽. 一种新型基于环上带误差学习问题的认证密钥交换方案[J]. 电子与信息学报, 2015, 37(8): 1984-1988.

YANG X P, MA W P, ZHANG C L. New authenticated key exchange scheme based on ring learning with errors problem[J]. Journal of Electronics & Information Technology,2015, 37(8): 1984-1988.

[15] STEBILA D, MOSCA M. Post-quantum key exchange for the Internet and the open quantum safe project[R]. Cryptology Eprint Archive, Report 2016/1017, 2016.

[16] 杨晓燕, 侯孟波, 魏晓超. 基于验证元的三方口令认证密钥交换协议[J]. 计算机研究与发展, 2016, 53(10): 2230-2238.

YANG X Y, HOU M B, WEI X C. Verifier-based three-party password authenticated key exchange protocol[J]. Journal of Computer Research and Development, 2016, 53(10): 2230-2238.

[17] XU D, HE D, CHOO K R, et al. Provably secure three-party password authenticated key exchange protocol based on ring learning with error[J]. IACR Cryptology Eprint Archive, 2017: 360.

Three-party password authenticated key agreementprotocol with user anonymity based on lattice

WANG Caifen, CHEN Li

College of Computer Science and Engineering, Northwest Normal University, Lanzhou 730070, China

With the rapid development of quantum theory and the existence of polynomial algorithm in quantum computation based on discrete logarithm problem and large integer decomposition problem, the security of the algorithm was seriously threatened. Therefore, two authentication key agreement protocols were proposed rely on ring-learning-with-error (RLWE)assumption including lattice-based implicitauthentication key agreement scheme and lattice-based explicit authentication key agreement schemeand proved its security. The implicit authentication key agreement protocol is lessto communicate and faster to authentication, the explicit authentication key agreement protocol is more to secure. At the same time, bidirectional authentication of users and servers can resist unpredictable online dictionary attacks. The new protocol has higher efficiency and shorter key length than other password authentication key agreement protocols. It can resist quantum attacks. Therefore, the protocol is efficient, secure, and suitable for large-scale network communication.

lattice-based cryptology, provably secure, password authentication, key exchange, ring-learning-with-error

TP309.7

A

10.11959/j.issn.1000-436x.2018021

2017-09-18；

2018-01-17

国家自然科学基金资助项目（No.61662069, No.61562077, No.61662071）；西北师范大学青年教师科研能力提升计划基金资助项目（No.NWNU-LKQN-14-7）

The National Natural Science Foundation of China (No.61662069, No.61562077, No.61662071), The Foundation for Excellent Young Teachers by Northwest Normal University (No.NWNU-LKQN-14-7)

王彩芬（1963-），女，河北安国人，博士，西北师范大学教授、博士生导师，主要研究方向为密码学、网络安全、信息安全。

陈丽（1991-）女，甘肃武威人，西北师范大学硕士生，主要研究方向为网络与信息安全、密钥协商协议。