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

王彩芬, ,

(西北師范大學 計算機科學與工程學院,蘭州 730070)

0 概述

隨著量子計算機的發(fā)展,傳統的困難問題在量子計算下存在多項式求解算法,其安全性受到越來越多的挑戰(zhàn),格密碼依靠其獨特的困難問題和歸約結果成為密碼學研究的熱點,基于標準格的密碼方案具有較長的密鑰和較高的密文擴張率,且格的表示方式需要較大的空間,而理想格的表示方式簡單,對內具有乘法封閉性、對外具有乘法吸收性,其可以克服標準格的相關缺點。因此,理想格在密碼方案中被廣泛使用,如公鑰加密[1-3]、數字簽名[4-6]、密鑰協商協議[7-9]等。

認證密鑰交換(Authenticated Key Exchange,AKE)允許通信方在不安全的信道中相互認證并協商出共享密鑰,兩方口令認證密鑰交換(Two-party Password Authenticated Key Exchange,2PAKE)[10]協議中每2個用戶共享一個低熵口令,導致該協商協議不適用于用戶間的通信。為解決2PAKE的局限性,密碼學者提出三方口令認證密鑰交換(Three-party Password Authenticated Key Exchange,3PAKE)協議[11-12],并將其應用于大規(guī)模網絡下的通信。文獻[10]基于誤差學習問題(Learing With Error,LWE),提出基于格的2PAKE協議,該方案存在密鑰較長和效率較低等問題,無法應用在大規(guī)模的通信系統中。文獻[7]針對一般格上密鑰長度過大的問題提出基于理想格的環(huán)上誤差學習(Ring Learning With Error,RLWE)問題,并證明其分布是偽隨機的。文獻[8]提出基于理想格的近似平滑投射Hash函數(ASPH)。文獻[13]基于格的口令認證密鑰交換協議,在相關加密算法的研究中提出基于理想格的2PAKE協議,該協議消息傳輸量較大,且不滿足用戶的匿名性。文獻[10]提出基于理想格的認證密鑰交換方案,其協議不使用任何加密原語,該方案的安全性基于RLWE困難問題,不適用于大規(guī)模網絡中的通信。文獻[11]基于ASPH提出基于格的3PAKE協議,該協議不滿足用戶的匿名性。文獻[12]提出一種新型基于RLWE問題的認證密鑰交換方案,該方案基于RLWE問題提出兩方密鑰協商協議。文獻[14]提出基于驗證元的3PAKE協議,該協議通信量較多,效率較低。

針對上述協議的局限性,本文提出基于理想格的用戶匿名3PAKE協議,在文獻[15]安全模型的基礎上構建3PAKE協議的安全模型,并在標準模型下證明該協議的安全性。

1 相關定義

定義1理想格

定義2離散高斯分布[16]

定義3RLWE問題

根據RLWE問題,有以下相關引理:

定義4Cha和Mod2函數[9]

根據Cha和Mod2函數定義,有以下引理:

定義53PAKE協議的安全模型

在文獻[15]安全模型的基礎上構建3PAKE協議的安全模型。協議中使用的符號及說明如表1所示。

表1 基于理想格的3PAKE協議符號說明

從以下方面描述安全模型的定義:

安全游戲:定義挑戰(zhàn)者XH和概率多項式時間敵手A的安全參數k,挑戰(zhàn)者代表誠實用戶運行協議P。

用戶和口令:假設一個固定的用戶集合Y分為2個非空集合:客戶X和服務器Σ,假設非空字典D的長度為L。在開始游戲前,非空字典D隨機均勻分配給每個客戶C∈X一個口令pwC,并給敵手A分配口令。?S∈Σ,有pwS=(f(pwC))C,f是被P指定的有效、可計算的單向函數。XH生成P的公共參數,并發(fā)送給A,模型假設敵手知道惡意客戶口令集合,游戲開始。

Corrupt(Y)詢問:如果U∈Y,返回(f(pwC))C;否則,返回pwU給A。

結束游戲:最后,A輸出b′作為b的猜測。如果b′=b,則攻擊者攻擊成功。

2 基于理想格的密鑰協商協議

針對文獻[9-13]中存在的一些安全性問題,本文提出了基于理想格的用戶匿名3PAKE協議。

2.1 協議內容

2.1.1 初始化階段

如圖1所示,當用戶B和C進行安全通信時,用戶分別輸入臨時身份TIDB、TIDC,兩者在服務器的協助下進行相互認證,并協商一個共享的會話密鑰。其中,協議基于RLWE困難問題,Rq=Zq/(xn+1),σ=Mod2(kS,ω)=Mod2(kB,ω)=Mod2(kC,ω)。

圖1 基于理想格的3PAKE協議示意圖

當用戶加入系統時,需要向服務器S注冊。以用戶B為例,該注冊過程具體如下:

1)B→S:(B,HpwB)

用戶B隨機選取身份B和口令pwB,并任意選取隨機數a,B計算HpwB=h(pwB‖a),并將注冊請求(B,HpwB)發(fā)送給服務器S。

2)S→B:(TIDB,H(·))

當S收到用戶B的注冊請求消息(B,HpwB)后,計算TIDB=B⊕HpwB,并將TIDB、H(·)發(fā)送給用戶B。

2.1.2 相互認證與密鑰協商階段

用戶的相互認證與密鑰協商具體過程如下:

1)B→S:M1=〈TIDB,m1〉

用戶B輸入TIDB、pwB,隨機選取sB,eB←χβ計算α1=asB+2eB,γ1=H1(pwB),m1=α1+γ1,B將M1發(fā)送給S。

2)C→S:M2=〈TIDC,m2〉

用戶C輸入TIDC,pwC,隨機選取sC,eC←χβ計算α2=asC+2eC,γ2=H1(pwC),m2=α2+γ3,C將M2發(fā)送給S。

3)S→B,C:M3=〈m3〉

4)skB=H3(B,S,C,m,μ,σ,γ)

5)skC=H3(B,S,C,m,μ,σ,γ)

2.2 方案的正確性

q是一個大素數,若q>16β2n3/2,誠實用戶運行方案,用戶獲得的會話密鑰不匹配的概率可忽略。由引理3得,如果kC和kS非常接近,即|kC-kS|

3 安全性證明

認證協議能否得到廣泛應用,不僅要其設計合理,還要具備正確性和安全性,本文給出基于理想格的用戶匿名3PAKE協議的安全性證明。

定理1設n是安全參數,Dn是口令空間,若RLWE問題是困難的,則方案在標準模型下是安全的。因此,存在可忽略函數negl(n),對運行時間為t的敵手A,執(zhí)行Execute、Send、Test詢問的次數最多為qe、qs、qt,有AdvDn,Gx(A)≤qs/|Dn|+negl(n)成立。

游戲G0是H和真實協議的交互,H向模擬器S詢問,并收到回答。

|Adv(H,G1)-Adv(H,G0)|≤negl(n)

(1)

|Adv(H,G2)-Adv(H,G1)|≤negl(n)

(2)

|Adv(H,G3)-Adv(H,G2)|≤negl(n)

(3)

|Adv(H,G4)-Adv(H,G3)|≤negl(n)

(4)

|Adv(H,G5)-Adv(H,G4)|≤negl(n)

(5)

游戲G6和G5基本相同,下述情況除外:如果客戶E收到Send(E,i,m3‖skS)詢問,檢查〈m3‖skS〉是否由匹配生成,如果不是,對m3進行解密,求解γ1,如果pwE1=pwE,則H攻擊成功,但游戲G6不減少H成功的概率。

m3=H2(μ1,μ2,ω,γ1,γ2),因為哈希函數的單向性,所以攻擊者很難求解出真實的γ1=H1(pwE),即使求出正確的γ1,也很難得到真實的口令pwE。因此,式(6)成立。

|Adv(H,G6)|≤|Adv(H,G5)|

(6)

游戲G7和G6基本相同,下述情況除外:如果客戶E收到Send(E,i,m3‖skS)詢問,且〈m3‖skS〉由匹配生成,此時,客戶和S使用共同的γ1,因為γ1對H不可見,所以H成功攻擊協議的概率不變。因此,式(7)成立。

|Adv(H,G7)|=|Adv(H,G6)|

(7)

|Adv(H,G8)-Adv(H,G7)|≤negl(n)

(8)

|Adv(H,G9)|≤|Adv(H,G8)|

(9)

|Adv(H,G10)-Adv(H,G9)|≤negl(n)

(10)

|Adv(H,G11)-Adv(H,G10)|≤negl(n)

(11)

若攻擊者猜測口令失敗,則只可通過猜測隨機比特b攻擊協議,如果用隨機值代替會話密鑰,則H成功的概率為1/2。如游戲G6和G9,H每次通過猜測隨機比特b獲得正確口令的概率最多是1/|Dn|,因此,H最后成功攻破協議的優(yōu)勢最多為qs/|Dn|。綜上式(1)～式(11),有AdvDn,Gx(H)≤qs/|Dn|+negl(n)成立,敵手攻破協議的優(yōu)勢是可忽略的量,即定理1結論成立。

4 協議性能分析比較

從安全性和效率2個方面,對本文方案與文獻[9-11,13-14]方案進行比較,結果如表2所示。從表2可以看出,在安全性方面,與傳統的3PAKE協議相比,本文方案能夠抵抗量子攻擊,滿足用戶匿名性,用戶和服務器的相互認證可抗不可測在線字典攻擊,同時本文方案還具有較高的效率。文獻[9]基于RLWE困難問題的2PAKE協議需要2輪通信,因此,其3PAKE協議至少需要4輪通信,且不滿足用戶匿名性;文獻[10]基于LWE困難問題的2PAKE協議需要3輪通信,因此,其3PAKE協議至少需要6輪通信,且不滿足用戶和服務器的相互認證,不能抵抗字典攻擊,且不能滿足用戶匿名性;文獻[11]基于ASPH的3PAKE協議需要3輪通信,通信量較多且不滿足用戶的匿名性;文獻[13]基于ASPH的2PAKE協議需要3輪通信,因此,其3PAKE協議至少需要6輪通信,通信量大且不滿足用戶匿名性,不能在大規(guī)模通信系統中使用;文獻[14]基于ASPH的3PAKE協議,需要4輪即8條消息傳輸量,效率較低且不滿足用戶匿名性。由于基于理想格的密鑰協商協議較少,因此與其他方案相比,本文協議減少了公鑰長度,降低了計算復雜度和消息傳輸量,提高了運行速度。

表2 不同協議性能比較

5 結束語

基于標準格的密碼方案存在運行效率較低等缺點,而理想格的表示方式簡單,具有較少的密鑰量、較短的密鑰長度、較低的運行開銷以及較高的運行效率等特點。因此,本文提出基于理想格的用戶匿名3PAKE協議,實現用戶和服務器的雙向認證,并在標準模型下證明該協議的安全性。下一步將研究高效的基于理想格的多方密鑰協議。

[1] 楊曉元,吳立強,張敏情,等.基于理想格的適應性選擇密文安全公鑰加密方案[EB/OL].[2017-04-20].http://www.docin.com/p-1273161598.html.

[2] 古春生.近似理想格上的全同態(tài)加密方案[J].軟件學報,2015,26(10):2696-2719.

[3] 魏理豪,艾解清,劉生寒.理想格上高效的身份基加密方案[J].計算機工程,2016,42(7):134-138.

[4] 馮超逸,趙一鳴.基于理想格的可證明安全數字簽名方案[J].計算機工程,2017,43(5):103-107.

[5] 楊丹婷,許春根,徐 磊,等.理想格上基于身份的簽名方案[J].密碼學報,2015,2(4):306-316.

[6] 孫意如,梁向前,商玉芳.理想格上基于身份的環(huán)簽名方案[J].計算機應用,2016,36(7):1861-1865.

[7] LYUBASHEVSKY V,PEIKERT C,REGEV O.On ideal lattices and learning with errors over rings[C]//Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques.Berlin,Germany:Springer,2010:1-23.

[8] 葉 茂,胡學先,劉文芬.基于理想格的近似平滑投射Hash函數[J].信息工程大學學報,2013,14(1):13-21.

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

[10] KATZ J,VAIKUNTANATHAN V.Smooth projective hashing and password-based authenticated key exchange from lattices[C]//Proceedings of the 15th International Conference on the Theory and Application of Cryptology and Information Security:Advances in Cryptology.Berlin,Germany:Springer,2009:636-652.

[11] 葉 茂,胡學先,劉文芬.基于格的三方口令認證密鑰交換協議[J].電子與信息學報,2013,35(6):1376-1381.

[12] 楊孝鵬,馬文平,張成麗.一種新型基于環(huán)上帶誤差學習問題的認證密鑰交換方案[J].電子與信息學報,2015,37(8):1984-1988.

[13] 葉 茂.基于格的口令認證密鑰交換協議和相關加密算法研究[D].鄭州:解放軍信息工程大學,2013.

[14] 楊曉燕,侯孟波,魏曉超.基于驗證元的三方口令認證密鑰交換協議[J].計算機研究與發(fā)展,2016,53(10):2230-2238.

[15] MACKENZIE P.The PAK suite:protocols for password-authenticated key exchange[EB/OL].[2017-05-05].https://www.researchgate.net/publication/2544702_The_PAK_suite_Protocols_for_Password-Authenticated_Key_Exchange.

[16] 詹海峰.基于格的高斯抽樣和密鑰交換[D].西安:西安電子科技大學,2014.