基于RLWE的后量子認(rèn)證密鑰交換協(xié)議

李子臣 謝 婷 張卷美 徐榮華

1(北京印刷學(xué)院 北京 102600)2(西安電子科技大學(xué)通信工程學(xué)院 西安 710071)3(北京電子科技學(xué)院 北京 100018)(lizc2020@163.com)

密鑰交換(key exchange，KE)協(xié)議在安全通信領(lǐng)域具有重要的基礎(chǔ)性作用，其旨在使得通信雙方在不安全的信道上可以協(xié)商出共同的會話密鑰.Diffile-Hellman密鑰交換協(xié)議的提出在公鑰密碼學(xué)史上具有里程碑的意義，但此協(xié)議為被動安全的密鑰交換協(xié)議，無法抵御中間人攻擊.而認(rèn)證密鑰交換(authenticated key exchange,AKE)協(xié)議，不僅使通信雙方通過協(xié)商得到共享會話密鑰，且可為通信雙方提供有效認(rèn)證.AKE協(xié)議中，通信雙方各自持有一個長期公私鑰對與一個臨時公私鑰對，其中長期公鑰由可信賴的第三方頒發(fā)，雙方通過信息交互與計算最終得到共享會話密鑰.

隨著量子計算機(jī)技術(shù)不斷取得突破，特別是以Shor算法為典型代表的量子算法的提出，在理論上相關(guān)運(yùn)算操作可實現(xiàn)從指數(shù)級別向多項式級別的轉(zhuǎn)變，對于經(jīng)典計算機(jī)來說足夠困難的問題必將在可預(yù)期的將來被實用型量子計算機(jī)輕易破解.2015年8月美國國家安全局宣布當(dāng)前聯(lián)邦政府使用的“密碼算法B 套件”將升級為抗量子密碼系統(tǒng).2016 年4 月美國國家標(biāo)準(zhǔn)局在全球范圍內(nèi)展開了后量子密碼算法的征集工作.近年來歐洲國家的“后量子密碼”(PQCrypto)和“安全密碼”(SAFEcrypto)項目以及日本的CREST密碼數(shù)學(xué)項目都取得了優(yōu)秀成果.量子計算的前溯性威脅使部署后量子密碼技術(shù)需求更加迫切.

格密碼具有較好的擴(kuò)展性，可設(shè)計加密、數(shù)字簽名、密鑰交換協(xié)議、全同態(tài)密碼等，被認(rèn)為是后量子密碼算法中最有力的競爭者.在理論研究方面，1996年Ajtai[1]首先基于格上小整數(shù)解問題(short integer solution,SIS)構(gòu)造了抗碰撞雜湊函數(shù)；1998年Hoffstein等人[2]基于NTRU密碼體制的公鑰加密方案，與格上困難問題密切相關(guān).2005年Regev等人[3]基于格理論提出錯誤學(xué)習(xí)問題(learning with errors,LWE)，可歸約為一般格上最近向量的最壞情形；2010年Lyubashevsky等人[4]提出了基于環(huán)上錯誤的學(xué)習(xí)問題(ring learning with errors,RLWE)，可歸約為理想格上的困難問題SVP(shortest vector problem)的最壞情形；2015年Langlois等人[5]研究了基于模上錯誤學(xué)習(xí)性問題(module learning with errors,MLWE)，MLWE問題是理想格與一般格的推廣.中國密碼學(xué)研究者王小云等人[6]、張平原等人[7]、劉亞敏等人[8]對格密碼理論方面也進(jìn)行了較深入的研究.在應(yīng)用實現(xiàn)方面，美國微軟公司于2016年4月發(fā)布了格密碼庫；2016年7月美國谷歌公司在后量子項目試驗中，在其瀏覽器進(jìn)行了格理論設(shè)計的KE協(xié)議相關(guān)部署測試工作.基于格理論構(gòu)造密碼系統(tǒng)已成為當(dāng)前后量子密碼領(lǐng)域研究的熱點(diǎn).

本文基于格理論RLWE困難問題設(shè)計了一種新型AKE協(xié)議.首先基于密文壓縮技術(shù)提出了一個IND-CPA安全的公鑰加密算法，在此基礎(chǔ)上使用Fujisaki-Okamoto變換技術(shù)得到一種IND-CCA安全的密鑰封裝機(jī)制(key encapsulation mechanism，KEM)，最后通過參與者雙方分別擁有長期、臨時公私鑰對的隱式認(rèn)證方式構(gòu)造了一種AKE協(xié)議.協(xié)議在錯誤分布選取上，采用抽樣效率相較于高斯分布更高的二項分布.采用密文壓縮方式為基礎(chǔ)構(gòu)造有關(guān)方案，與使用計算較復(fù)雜的錯誤協(xié)調(diào)技術(shù)相比，更加簡潔高效.本文提出的AKE協(xié)議在eCK模型下可證明安全且可達(dá)到弱的完美前向安全[16]，是一種更加簡潔安全、高效的后量子AKE協(xié)議.

1 預(yù)備知識

1.1 判定型RLWE，HNF-RLWE問題

判定型RLWE問題是指給定分布(a,v)，區(qū)分(a,v)為RLWE分布還是隨機(jī)均勻分布.

判定型HNF-RLWE問題是指給定分布(a,v)，區(qū)分(a,v)為RLWE分布還是隨機(jī)均勻分布.

1.2 中心二項分布

1.3 密文壓縮技術(shù)

┌l(fā)bq┐.

由定義可得壓縮函數(shù)和解壓函數(shù)之間的關(guān)系為x′=Decompress(Compressq(x,d),d)，其中x與x′滿足|x′-xmod±q|≤Bq=┌q/2d+1」.

2 基于RLWE問題AKE協(xié)議方案設(shè)計

基于RLWE困難問題設(shè)計了一種新型AKE協(xié)議.首先基于加密機(jī)制以及密文壓縮技術(shù)提出一種IND-CPA安全的公鑰加密方案，在此公鑰加密方案的基礎(chǔ)上并使用Fujisaki-Okamoto變換技術(shù)得到了一種IND-CCA安全的KEM方案，在KEM方案基礎(chǔ)上，通過通信雙方各持有一對長期、臨時私鑰的隱式認(rèn)證方式構(gòu)造了一個命名為NLPQ(new lattice post quantum)的AKE協(xié)議.

2.1 IND -CPA安全的公鑰加密方案

算法1～3分別為密鑰生成、加密以及解密算法，下面分別對3個算法進(jìn)行具體說明.

算法1.密鑰生成算法：NLPQ.KeyGen.

②a←Parse(SHAKE-128(seed))；

④y=Compress(a·s+e,d)；

⑤pk=(y,seed)，sk=s.

算法2.加密算法：NLPQ.Enc(pk，m),其中pk=(y,seed)，m∈M.

①x′=Decompressq(y,d)；

③a←Parse(SHAKE-128(seed))；

⑤y′=Compressq(a·s′+e′,d)；

⑥y″=Compressq(x·s′+e″+┌q/2┐·m,d)；

⑦ 返回值c=(y′,y″).

算法3.解密算法：NLPQ.Dec，其中sk=s，c=(y′,y″).

①u=Decompressq(y′,d)；

②v=Decompressq(y″,d)；

③ 返回值m′=Compressq(v-u·s,1).

2.2 IND-CCA密鑰封裝機(jī)制

已知雜湊函數(shù)G：{0,1}*→{0,1}512，H：{0,1}*→{0,1}256，應(yīng)用Fujisaki-Okamoto變換，可將IND-CPA安全的公鑰加密方案轉(zhuǎn)變?yōu)镮ND-CCA安全的KEM方案[19].本節(jié)設(shè)計的IND-CCA安全的KEM方案包括NLPQ.KeyGen，NLPQ.Encaps，NLPQ.Decaps三個算法組成，其中NLPQ.KeyGen為2.1節(jié)的算法1.算法4，5分別為NLPQ.Encaps和NLPQ.Decaps.

算法4.加密封裝算法NLPQ.Encaps，其中pk=(y,seed).

①m←{0,1}256；

② (k,t)=G(pk,m)，k和t的長度均為256 b；

③ (y′,y″)=IND-CPA.Enc((y,seed),m)；

④c′=(y′,y″,t)；

⑤K=H(k,H(c′))；

⑥ 返回值(c′,K).

算法5.算法NLPQ.Decaps，其中sk=s，c=(y′,y″,t)).

①m′=IND-CPA.Dec(s,(y′,y″))；

② (k′,t′)=G(pk,m′)；

③ (z′,z″)=Enc((y,seed),m′)；

④ 如果滿足(z′,z″,t′)=(y′,y″,t)條件時，返回值K=H(k′,H(c′))；

⑤ 否則返回值K=H(r,H(c′))，r是一個隨機(jī)秘密種子.

2.3 密鑰交換協(xié)議方案

使用算法1～5構(gòu)造的KE協(xié)議方案如圖1所示：

AB(pk,sk)←NLPQ.KeyGenv()pk→(c,K)←NLPQ.Encaps(pk)key=NLPQ.Decaps(sk,c)c←key=K

Fig.1 Key exchange protocol圖1 密鑰交換協(xié)議

2.4 認(rèn)證密鑰交換協(xié)議

已知通信參與者A和B分別持有長期公私鑰(pkA,skA)，(pkB,skB)，臨時公私鑰(pk1,sk1)，(pk2,sk2).利用通信雙方各自持有一對長期、臨時公私鑰對，構(gòu)造了一個基于RLWE問題的AKE協(xié)議，雙方最終得到了共享會話密鑰.圖2是基于HNF-RLWE問題構(gòu)造的AKE協(xié)議的具體過程.

AB(pkA,skA)←NLPQ.KeyGen()(pkB,skB)←NLPQ.KeyGen()(pk1,sk1)←NLPQ.KeyGen()(pk2,sk2)←NLPQ.KeyGen()(cB,KB)←NLPQ.Encaps(pkB)cB,c2→(cA,KA)←NLPQ.Encaps(pkA)(c2,K2)←NLPQ.Encaps(pk2)(c1,K1)←NLPQ.Encaps(pk1)K'B←NLPQ.Decaps(sk2,cB)K'A←NLPQ.Decaps(skA,c)cA,c1←K'2←NLPQ.Decaps(sk2,c2)K'1←NLPQ.Decaps(sk1,c1)key=H(K'A,KB,K'1,K2)key=H(KA,K'B,K1,K'2)

Fig.2 Authentication key exchange protocol 圖2 認(rèn)證密鑰交換協(xié)議

3 參數(shù)設(shè)置與正確性分析

為了滿足正確性與安全性需求，參數(shù)設(shè)置如下：模數(shù)q=12 289<214，維度n=1 024，此時NLPQ.IND-CPA公鑰加解密方案解密錯誤的概率δ是可以忽略的，可得解密正確性的概率為1-δ，其中δ<2-128.

Compressq(x·s′+e″+┌q/2」·m,d)代入上式可得

|e·s′+f·s′+e″+f″-e′·s-f′·s|<┌q/4」，此時

記為|v-u·s|=w+┌q/2」·m，向量v-u·s中

的每個元素為wi，可得|wi|<┌q/4」，已知在算法3中有m′=Compressq(v-u·s,1)，計算得到向量為v-u·s-┌q/2」·m′，其中的每個元素為vi，因此可以得到結(jié)果┌q/4」>|vi|，之后，向量w+┌q/2」·m-┌q/2」·m′中的每個元素設(shè)為mi，進(jìn)而

得到┌q/4」>|mi|，根據(jù)分析已知|wi|<┌q/4」，可

得┌q/2」·(m-m′)|<2×┌q/4」,由已知q是奇數(shù)，因此可得m=m′，由此可得NLPQ.IND-CPA公鑰加解密方案的正確性.由于雜湊函數(shù)G和H是隨機(jī)預(yù)言模型，F(xiàn)O變換技術(shù)使得IND-CPA安全的公鑰加解密方案轉(zhuǎn)變?yōu)镮ND-CCA安全的KEM方案，因此可得NLPQ.IND-CCA方案的正確性概率為1-δ，其中δ<2-128.因此依據(jù)算法1～5構(gòu)造的KE協(xié)議和AKE協(xié)議方案，通信參與雙方可得到正確的會話密鑰.

4 安全性分析及測試

4.1 協(xié)議安全性分析

本文構(gòu)造的協(xié)議方案基于隨機(jī)預(yù)言機(jī)在標(biāo)準(zhǔn)eCK模型下是可證明安全的，并且由文獻(xiàn)[16]相關(guān)結(jié)論可得可以達(dá)到弱的完美前向安全.此AKE協(xié)議的安全性最終可歸約為格上的HNF-RLWE問題的困難性.

情形1.猜測攻擊.攻擊者M(jìn)通過猜測得到通信雙方的會話密鑰.

情形2.密鑰復(fù)制攻擊.敵手M與參與者建立了與測試會話相同的會話，此時敵手M通過SessionKeyReveal()查詢可得到此次會話的會話密鑰key，攻擊者M(jìn)得到了測試會話的會話密鑰key.

情形3.偽造攻擊.攻擊者預(yù)先計算出會話密鑰材料，進(jìn)而通過H查詢得到會話密鑰key.

首先分析情形1，由于H為隨機(jī)預(yù)言機(jī)，因此通過t次猜測猜到會話密鑰的概率只有O(1/2t)，因此通過猜測攻擊無法得到真實的會話密鑰.

下面分析情形2，協(xié)議方案雜湊函數(shù)G和H為隨機(jī)預(yù)言機(jī)，生成碰撞的概率可以忽略；協(xié)議的參與者進(jìn)行每次新的會話時臨時私鑰隨機(jī)產(chǎn)生.因此，會話參與者2次不同的會話中持有相同的臨時私鑰的概率可忽略.情形2密鑰復(fù)制攻擊無法達(dá)到攻擊目的.

分析情形3中偽造攻擊：若攻擊者M(jìn)可構(gòu)造一個模擬器S，且模擬器S可利用M以不可忽略的優(yōu)勢解決RLWE問題.

證畢.

本文構(gòu)造的協(xié)議可抵御猜測攻擊、密鑰復(fù)制攻擊以及偽造攻擊，基于隨機(jī)預(yù)言機(jī)在標(biāo)準(zhǔn)eCK模型下是可證明安全的，且可以達(dá)到弱的完美前向安全.協(xié)議方案的安全性可歸約為格理論上的RLWE問題的困難性.

4.2 協(xié)議安全性測試

在本協(xié)議方案中，設(shè)置參數(shù)維度n=1 024，模數(shù)q=1 073 479 681，選用n=16的中心二項分布錯誤分布.在2015年Albrecht等人[20]提出的LWE測試器，為當(dāng)前最權(quán)威的針對LWE，RLWE問題的密碼系統(tǒng)的安全度測試工具.通過計算暴力搜索、BKW、格基歸約、MITM攻擊等攻擊復(fù)雜度來衡量密碼系統(tǒng)的安全度.基于LWE，RLWE問題的密碼系統(tǒng)的此種LWE測試器，被認(rèn)為是目前最準(zhǔn)確、高效、便捷的安全度測試工具.給定任意有效參數(shù)，LWE測試器便可輸出各種攻擊下的計算復(fù)雜度和空間復(fù)雜度，目前很多基于LWE和RLWE問題設(shè)計的公鑰密碼方案使用此工具進(jìn)行方案的安全度測試.

在LWE性能測試平臺上對本文設(shè)計的基于RLWE問題的協(xié)議進(jìn)行安全性測試，可得協(xié)議的安全度為313 b.結(jié)果如圖3所示：

Fig.3 Security test of the protocol圖3 協(xié)議的安全性測試

5 效率分析對比

依據(jù)目前公開的最新學(xué)術(shù)成果，基于格上困難問題設(shè)計的KE協(xié)議與本文設(shè)計的方案進(jìn)行綜合分析.選取最典型的無認(rèn)證KE協(xié)議方案BCNS15[11]，NewHope[12]，F(xiàn)rodo[13]方案.另外選取基于RLWE問題構(gòu)造的HMQV式AKE協(xié)議[14]、基于NTRU體制構(gòu)造的AKE方案[15].分別從模數(shù)q、維度n、困難問題假設(shè)、公私鑰以及密文長度(單位b)、通信復(fù)雜度以及協(xié)議安全度(單位b)進(jìn)行對比.表1為本方案與現(xiàn)有的基于格上困難問題設(shè)計有關(guān)方案性能指標(biāo)對比情況.本文方案在安全度上有較大優(yōu)勢，與安全度較高的NewHope方案相比，公私鑰以及密文尺寸相對較小.協(xié)議在較強(qiáng)安全性模型即標(biāo)準(zhǔn)eCK模型下可證明安全，并且可達(dá)到弱的完美前向安全.

Table 1 Performance Comparison of Key Exchange Protocols Based on Difficult Problem of Lattice表1 基于格困難問題設(shè)計的密鑰交換協(xié)議的性能比較

6 總 結(jié)

本文基于格理論RLWE困難問題，采用計算高效的密文壓縮方式設(shè)計出一種隱式認(rèn)證方式的AKE協(xié)議.協(xié)議在標(biāo)準(zhǔn)eCK模型下可證明安全，并且達(dá)到弱的前向安全.與當(dāng)前的無認(rèn)證的KE協(xié)議以及AKE協(xié)議相比，在公私鑰及密文長度、通信復(fù)雜度與安全度上有很強(qiáng)的競爭力.

量子計算機(jī)研制技術(shù)的迅速發(fā)展，使得現(xiàn)代公鑰密碼體制的安全性面臨著巨大挑戰(zhàn).目前政府、工業(yè)界以及相關(guān)標(biāo)準(zhǔn)化組織對于實用化的后量子密碼系統(tǒng)的需求迫切.2018年4月11—13日，美國國家標(biāo)準(zhǔn)與技術(shù)研究院召開了首屆后量子時代公鑰密碼標(biāo)準(zhǔn)化的國際會議，對2017年12月截止的在全球范圍內(nèi)征集的82個密碼算法進(jìn)行首輪評估測試，2019年初宣布共計26個密碼算法方案進(jìn)入了第2輪評估.

未來考慮基于RLWE問題及NTRU密碼體制設(shè)計出計算簡潔高效、安全度更高的KE協(xié)議.