王彩芬，陳麗

?

基于格的用戶匿名三方口令認(rèn)證密鑰協(xié)商協(xié)議

王彩芬，陳麗

（西北師范大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，甘肅 蘭州 730070）

隨著量子理論的快速發(fā)展，離散對(duì)數(shù)問題和大整數(shù)分解問題在量子計(jì)算下存在多項(xiàng)式求解算法，其安全性受到嚴(yán)重威脅，因此，提出2個(gè)基于環(huán)上帶誤差學(xué)習(xí)問題的用戶匿名三方口令認(rèn)證密鑰協(xié)商方案，包括基于格的隱式認(rèn)證密鑰協(xié)商方案和基于格的顯式認(rèn)證密鑰協(xié)商方案，并證明了其安全性。其中，隱式認(rèn)證密鑰協(xié)商協(xié)議通信量少、認(rèn)證速度快，顯式認(rèn)證密鑰協(xié)商協(xié)議安全性更高，同時(shí)實(shí)現(xiàn)用戶和服務(wù)器的雙向認(rèn)證、可抗不可測(cè)在線字典攻擊。與其他口令認(rèn)證密鑰協(xié)商協(xié)議相比，所提協(xié)議有更高的效率和更短的密鑰長(zhǎng)度，能夠抵抗量子攻擊，因此，該協(xié)議既高效又安全，適用于大規(guī)模網(wǎng)絡(luò)下的通信。

格密碼；可證明安全；口令認(rèn)證；密鑰交換；環(huán)上帶誤差

1 引言

隨著大數(shù)據(jù)時(shí)代的到來以及量子計(jì)算機(jī)的快速發(fā)展，人們對(duì)數(shù)據(jù)的安全有了更高的要求，格密碼依靠其獨(dú)特的困難問題和歸約結(jié)果成為密碼學(xué)研究的熱點(diǎn)，基于離散對(duì)數(shù)問題和大整數(shù)分解問題在量子計(jì)算下存在多項(xiàng)式求解算法，其安全性受到嚴(yán)重威脅，因此，格理論被應(yīng)用于抗量子攻擊的密碼體制中。

認(rèn)證密鑰交換（AKE, authenticated key exchange）允許通信雙方相互認(rèn)證并協(xié)商出共享密鑰，兩方口令認(rèn)證密鑰協(xié)商[1]（2PAKE, two-party password authenticated key exchange）協(xié)議要求用戶和服務(wù)器共享相同的口令，實(shí)現(xiàn)單個(gè)用戶和服務(wù)器的相互認(rèn)證，不適用于用戶和用戶之間的通信，為解決其局限性，密碼學(xué)研究者提出三方口令認(rèn)證密鑰交換[2,3]（3PAKE, three-party password authenticated key exchange）協(xié)議，使每個(gè)用戶和服務(wù)器共享一個(gè)低熵的口令，實(shí)現(xiàn)用戶間的相互認(rèn)證和密鑰協(xié)商，適用于大規(guī)模網(wǎng)絡(luò)下的通信。認(rèn)證密鑰交換通常分為顯式認(rèn)證和隱式認(rèn)證，顯式認(rèn)證是指協(xié)議結(jié)束后，用戶確信與之通信的就是意定的參與方；隱式認(rèn)證是指協(xié)議結(jié)束后，用戶相信只有意定的參與方才能計(jì)算出相同的會(huì)話密鑰。顯式認(rèn)證協(xié)議中除了隱式認(rèn)證之外，還包含一個(gè)顯式密鑰確認(rèn)過程，使參加協(xié)議的用戶可以確保其特別指定的用戶確實(shí)已經(jīng)擁有與其相同的會(huì)話密鑰。

2005年，文獻(xiàn)[2]基于判定性Diffie-Hellman假設(shè)（DDH, decisional Diffie-Hellman assumption）提出3PAKE協(xié)議。2006年，文獻(xiàn)[3]提出可證明安全性的3PAKE協(xié)議，隨后，有不同效率和安全性的3PAKE[4,5]協(xié)議相繼被提出，但是這些已有的3PAKE的安全性都依賴于離散對(duì)數(shù)問題和大整數(shù)分解問題等一系列傳統(tǒng)的困難問題，不能抵抗量子攻擊。2009年，文獻(xiàn)[6]首次提出了基于格的2PAKE協(xié)議，其方案基于誤差學(xué)習(xí)（LWE, learning with error）問題，但存在密鑰長(zhǎng)度過長(zhǎng)和效率低等問題。2011年，文獻(xiàn)[7]基于平滑投射散列函數(shù)（SPH, smooth projective hashing）提出了一個(gè)更高效的2PAKE協(xié)議。2012年，文獻(xiàn)[8]基于LWE問題提出可證明安全的兩方密鑰交換方案。2013年，文獻(xiàn)[9]使用密鑰封裝機(jī)制提出基于RLWE的密鑰交換協(xié)議，但該協(xié)議被文獻(xiàn)[10]指出難以抵抗外部攻擊者實(shí)施的假冒攻擊。由于2PAKE協(xié)議的局限性，文獻(xiàn)[11]基于近似平滑投射散列函數(shù)（ASPH, approximate smooth projective hashing）提出格的3PAKE協(xié)議。2015年，文獻(xiàn)[12]基于RLWE困難問題提出可證明安全的2PAKE協(xié)議。同年，文獻(xiàn)[13]基于LWE困難問題提出認(rèn)證密鑰交換方案，但該協(xié)議存在模數(shù)大、效率低等局限；文獻(xiàn)[14]提出一種新型的基于環(huán)上帶誤差學(xué)習(xí)問題的認(rèn)證密鑰交換方案，但該方案是兩方認(rèn)證密鑰協(xié)商協(xié)議。2016年，文獻(xiàn)[15]提出基于LWE的2PAKE協(xié)議。同年，文獻(xiàn)[16]提出基于驗(yàn)證元的三方口令認(rèn)證密鑰交換協(xié)議，但通信量較多、效率較低。2017年，文獻(xiàn)[17]提出了基于口令的兩方密鑰協(xié)商協(xié)議的形式化模型，并證明其安全性。本文在其基礎(chǔ)上，設(shè)計(jì)了一個(gè)基于格的RLWE困難問題的3PAKE協(xié)議的安全模型，并證明了協(xié)議的安全性。

為解決上述協(xié)議的局限性，提出2個(gè)基于格的用戶匿名三方口令認(rèn)證密鑰協(xié)商協(xié)議，包括基于格的三方隱式認(rèn)證密鑰協(xié)商協(xié)議和基于格的三方顯式認(rèn)證密鑰協(xié)商協(xié)議，其中，隱式認(rèn)證密鑰協(xié)商協(xié)議通信量少，顯式認(rèn)證密鑰協(xié)商協(xié)議除了滿足隱式認(rèn)證的所有條件之外，還需要滿足密鑰確認(rèn)，即協(xié)議參與方可以確定協(xié)議的其他參與方獲得了特定的會(huì)話密鑰，同時(shí)實(shí)現(xiàn)用戶和服務(wù)器的雙向認(rèn)證、可抗不可測(cè)在線字典攻擊。所提方案避免了2PAKE的局限性，有更高的效率和更短的密鑰長(zhǎng)度，能夠抵抗量子攻擊，適用于服務(wù)器和用戶間的三方通信，并證明了其安全性。因此，該協(xié)議既高效又安全，適用于大規(guī)模網(wǎng)絡(luò)下的通信。

2 預(yù)備知識(shí)

定義4 3PAKE協(xié)議的安全模型。

安全游戲。定義挑戰(zhàn)者CH和概率多項(xiàng)式時(shí)間敵手A的安全參數(shù)，挑戰(zhàn)者代表誠(chéng)實(shí)用戶運(yùn)行協(xié)議。

3 基于格的密鑰協(xié)商協(xié)議

針對(duì)之前協(xié)議存在的安全性問題，提出了基于格的三方口令認(rèn)證密鑰協(xié)商協(xié)議，減少了公鑰長(zhǎng)度，降低了計(jì)算復(fù)雜度和消息傳輸量，提高了協(xié)議的運(yùn)行速度，實(shí)現(xiàn)了用戶的匿名性。其中，隱式密鑰協(xié)商協(xié)議通信量較少，顯式認(rèn)證密鑰協(xié)商協(xié)議更安全。協(xié)議中使用的符號(hào)如表1所示。

表1 本文方案使用的符號(hào)說明

圖1 基于格的三方隱式認(rèn)證密鑰協(xié)商方案

3.1 基于格的三方隱式認(rèn)證密鑰協(xié)商方案

基于格的三方隱式認(rèn)證密鑰協(xié)商方案（以下簡(jiǎn)稱方案1）如圖1所示。

3.1.1 初始化階段

3.1.2 隱式認(rèn)證與密鑰協(xié)商階段

3.2 基于格的三方顯式認(rèn)證密鑰協(xié)商方案

由于基于格的三方隱式認(rèn)證密鑰協(xié)商方案通信量少、認(rèn)證速度快，但不能保證用戶得到了相應(yīng)的會(huì)話密鑰，因此，提出基于格的三方顯式認(rèn)證密鑰協(xié)商方案（以下簡(jiǎn)稱方案2），如圖2所示。

3.2.1 初始化階段

基于格的顯式認(rèn)證密鑰協(xié)商協(xié)議的初始化階段和基于格的隱式認(rèn)證密鑰協(xié)商協(xié)議的初始化階段相同，見3.1.1節(jié)。

3.2.2 顯式認(rèn)證與密鑰協(xié)商階段

3.3 方案的正確性

2個(gè)方案的正確性證明相同，下面是誠(chéng)實(shí)用戶執(zhí)行方案2時(shí)雙方擁有相同的會(huì)話密鑰的正確性證明。

4 安全性證明

2) 假設(shè)隨機(jī)預(yù)言機(jī)對(duì)任何新詢問都使用新的輸出進(jìn)行響應(yīng)，重復(fù)詢問之前的消息時(shí)，輸出相同。

各協(xié)議介紹如下。

證明 顯然成立，因?yàn)樵黾恿藬呈众A得游戲的機(jī)會(huì)。

表2 性能比較

綜合引理4~引理10的結(jié)論可知，定理1結(jié)論成立。因此，方案可證明是安全的。

5 協(xié)議性能比較

從安全性和效率出發(fā)，給出本文2個(gè)方案與文獻(xiàn)[6,11~13,16]方案的比較，如表2所示。

在安全性方面，與傳統(tǒng)的3PAKE協(xié)議相比，本文方案1和方案2能夠抵抗量子攻擊，同時(shí)實(shí)現(xiàn)了用戶的匿名性以及用戶和服務(wù)器的雙向認(rèn)證，可抵抗不可測(cè)在線字典攻擊。文獻(xiàn)[6]是基于LWE困難問題的2PAKE協(xié)議，需要3輪通信，所以3PAKE協(xié)議至少需要6輪通信，且不滿足用戶和服務(wù)器的相互認(rèn)證，不能抵抗不可測(cè)字典攻擊，不滿足用戶匿名性；文獻(xiàn)[11]是基于ASPH的3PAKE協(xié)議，需要3輪通信，不滿足用戶的匿名性；文獻(xiàn)[12]是基于RLWE困難問題的2PAKE協(xié)議需要2輪通信，所以3PAKE協(xié)議至少需要4輪通信，且不滿足用戶匿名性；文獻(xiàn)[13]提出隱式認(rèn)證和顯式認(rèn)證2個(gè)2PAKE方案，分別需要2輪和3輪通信，所以3PAKE協(xié)議至少需要4輪和6輪通信，效率較低且不滿足用戶匿名性；文獻(xiàn)[16]提出基于ASPH的3PAKE協(xié)議，需要4輪即8條消息傳輸量，通信量多、效率較低且不滿足用戶匿名性。本文方案1和方案2是3PAKE協(xié)議，分別需要2輪和3輪通信，遠(yuǎn)高于文獻(xiàn)[6,12,13,16]的通信效率。文獻(xiàn)[11]與本文方案2的消息傳輸量相同，但效率低于本文方案1。與現(xiàn)有方案相比，本文方案需要的采樣數(shù)小，減少了公鑰長(zhǎng)度，降低了計(jì)算復(fù)雜度和消息傳輸量，提高了協(xié)議的運(yùn)行速度，實(shí)現(xiàn)了用戶的匿名性。因此，本文方案1和方案2具有更高的安全性和通信效率。

6 結(jié)束語(yǔ)

基于口令認(rèn)證的密鑰協(xié)商協(xié)議是用戶僅選擇一個(gè)簡(jiǎn)單的口令，通過服務(wù)器，在用戶間建立一個(gè)共享的會(huì)話密鑰。由于2PAKE協(xié)議不能實(shí)現(xiàn)大規(guī)模端到端的通信，且傳統(tǒng)的困難問題不能抵抗量子攻擊，因此，提出2個(gè)基于格的3PAKE協(xié)議，包括基于格的用戶匿名三方隱式認(rèn)證密鑰協(xié)商方案和基于格的用戶匿名三方顯式認(rèn)證密鑰協(xié)商方案，并證明了協(xié)議的安全性。其中，隱式認(rèn)證密鑰協(xié)商協(xié)議通信量少、執(zhí)行效率高，顯式認(rèn)證密鑰協(xié)商協(xié)議安全性更高，同時(shí)實(shí)現(xiàn)用戶和服務(wù)器的雙向認(rèn)證可抗不可測(cè)在線字典攻擊。因此，所提協(xié)議既高效又安全。

[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] 胡學(xué)先, 魏江宏, 葉茂. 對(duì)一個(gè)強(qiáng)安全的認(rèn)證密鑰交換協(xié)議的分析[J]. 電子與信息學(xué)報(bào), 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] 葉茂, 胡學(xué)先, 劉文芬. 基于格的三方口令認(rèn)證密鑰交換協(xié)議[J]. 電子與信息學(xué)報(bào), 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] 楊孝鵬, 馬文平, 張成麗. 一種新型基于環(huán)上帶誤差學(xué)習(xí)問題的認(rèn)證密鑰交換方案[J]. 電子與信息學(xué)報(bào), 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] 楊曉燕, 侯孟波, 魏曉超. 基于驗(yàn)證元的三方口令認(rèn)證密鑰交換協(xié)議[J]. 計(jì)算機(jī)研究與發(fā)展, 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

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61662069, No.61562077, No.61662071）；西北師范大學(xué)青年教師科研能力提升計(jì)劃基金資助項(xiàng)目（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-），女，河北安國(guó)人，博士，西北師范大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)槊艽a學(xué)、網(wǎng)絡(luò)安全、信息安全。

陳麗（1991-）女，甘肅武威人，西北師范大學(xué)碩士生，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、密鑰協(xié)商協(xié)議。