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

王彩芬, ,

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

0 概述

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

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

針對(duì)上述協(xié)議的局限性,本文提出基于理想格的用戶匿名3PAKE協(xié)議,在文獻(xiàn)[15]安全模型的基礎(chǔ)上構(gòu)建3PAKE協(xié)議的安全模型,并在標(biāo)準(zhǔn)模型下證明該協(xié)議的安全性。

1 相關(guān)定義

定義1理想格

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

定義3RLWE問題

根據(jù)RLWE問題,有以下相關(guān)引理:

定義4Cha和Mod2函數(shù)[9]

根據(jù)Cha和Mod2函數(shù)定義,有以下引理:

定義53PAKE協(xié)議的安全模型

在文獻(xiàn)[15]安全模型的基礎(chǔ)上構(gòu)建3PAKE協(xié)議的安全模型。協(xié)議中使用的符號(hào)及說明如表1所示。

表1 基于理想格的3PAKE協(xié)議符號(hào)說明

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

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

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

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

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

2 基于理想格的密鑰協(xié)商協(xié)議

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

2.1 協(xié)議內(nèi)容

2.1.1 初始化階段

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

圖1 基于理想格的3PAKE協(xié)議示意圖

當(dāng)用戶加入系統(tǒng)時(shí),需要向服務(wù)器S注冊(cè)。以用戶B為例,該注冊(cè)過程具體如下:

1)B→S:(B,HpwB)

用戶B隨機(jī)選取身份B和口令pwB,并任意選取隨機(jī)數(shù)a,B計(jì)算HpwB=h(pwB‖a),并將注冊(cè)請(qǐng)求(B,HpwB)發(fā)送給服務(wù)器S。

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

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

2.1.2 相互認(rèn)證與密鑰協(xié)商階段

用戶的相互認(rèn)證與密鑰協(xié)商具體過程如下:

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

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

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

用戶C輸入TIDC,pwC,隨機(jī)選取sC,eC←χβ計(jì)算α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是一個(gè)大素?cái)?shù),若q>16β2n3/2,誠(chéng)實(shí)用戶運(yùn)行方案,用戶獲得的會(huì)話密鑰不匹配的概率可忽略。由引理3得,如果kC和kS非常接近,即|kC-kS|

3 安全性證明

認(rèn)證協(xié)議能否得到廣泛應(yīng)用,不僅要其設(shè)計(jì)合理,還要具備正確性和安全性,本文給出基于理想格的用戶匿名3PAKE協(xié)議的安全性證明。

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

游戲G0是H和真實(shí)協(xié)議的交互,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〉是否由匹配生成,如果不是,對(duì)m3進(jìn)行解密,求解γ1,如果pwE1=pwE,則H攻擊成功,但游戲G6不減少H成功的概率。

m3=H2(μ1,μ2,ω,γ1,γ2),因?yàn)楣：瘮?shù)的單向性,所以攻擊者很難求解出真實(shí)的γ1=H1(pwE),即使求出正確的γ1,也很難得到真實(shí)的口令pwE。因此,式(6)成立。

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

(6)

游戲G7和G6基本相同,下述情況除外:如果客戶E收到Send(E,i,m3‖skS)詢問,且〈m3‖skS〉由匹配生成,此時(shí),客戶和S使用共同的γ1,因?yàn)棣?對(duì)H不可見,所以H成功攻擊協(xié)議的概率不變。因此,式(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)

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

4 協(xié)議性能分析比較

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

表2 不同協(xié)議性能比較

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

基于標(biāo)準(zhǔn)格的密碼方案存在運(yùn)行效率較低等缺點(diǎn),而理想格的表示方式簡(jiǎn)單,具有較少的密鑰量、較短的密鑰長(zhǎng)度、較低的運(yùn)行開銷以及較高的運(yùn)行效率等特點(diǎn)。因此,本文提出基于理想格的用戶匿名3PAKE協(xié)議,實(shí)現(xiàn)用戶和服務(wù)器的雙向認(rèn)證,并在標(biāo)準(zhǔn)模型下證明該協(xié)議的安全性。下一步將研究高效的基于理想格的多方密鑰協(xié)議。

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

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

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

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

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

[6] 孫意如,梁向前,商玉芳.理想格上基于身份的環(huán)簽名方案[J].計(jì)算機(jī)應(yīng)用,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] 葉 茂,胡學(xué)先,劉文芬.基于理想格的近似平滑投射Hash函數(shù)[J].信息工程大學(xué)學(xué)報(bào),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] 葉 茂,胡學(xué)先,劉文芬.基于格的三方口令認(rèn)證密鑰交換協(xié)議[J].電子與信息學(xué)報(bào),2013,35(6):1376-1381.

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

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

[14] 楊曉燕,侯孟波,魏曉超.基于驗(yàn)證元的三方口令認(rèn)證密鑰交換協(xié)議[J].計(jì)算機(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].西安:西安電子科技大學(xué),2014.