基于格的用戶匿名三方口令認證密鑰協商協議

王彩芬，陳麗

?

基于格的用戶匿名三方口令認證密鑰協商協議

王彩芬，陳麗

（西北師范大學計算機科學與工程學院，甘肅 蘭州 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-）女，甘肅武威人，西北師范大學碩士生，主要研究方向為網絡與信息安全、密鑰協商協議。