基于RLWE的后量子認證密鑰交換協議

李子臣 謝 婷 張卷美 徐榮華

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

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

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

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

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

1 預備知識

1.1 判定型RLWE，HNF-RLWE問題

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

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

1.2 中心二項分布

1.3 密文壓縮技術

┌lbq┐.

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

2 基于RLWE問題AKE協議方案設計

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

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

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

算法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密鑰封裝機制

已知雜湊函數G：{0,1}*→{0,1}512，H：{0,1}*→{0,1}256，應用Fujisaki-Okamoto變換，可將IND-CPA安全的公鑰加密方案轉變為IND-CCA安全的KEM方案[19].本節設計的IND-CCA安全的KEM方案包括NLPQ.KeyGen，NLPQ.Encaps，NLPQ.Decaps三個算法組成，其中NLPQ.KeyGen為2.1節的算法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是一個隨機秘密種子.

2.3 密鑰交換協議方案

使用算法1～5構造的KE協議方案如圖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 密鑰交換協議

2.4 認證密鑰交換協議

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

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 認證密鑰交換協議

3 參數設置與正確性分析

為了滿足正確性與安全性需求，參數設置如下：模數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，因此可以得到結果┌q/4」>|vi|，之后，向量w+┌q/2」·m-┌q/2」·m′中的每個元素設為mi，進而

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

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

4 安全性分析及測試

4.1 協議安全性分析

本文構造的協議方案基于隨機預言機在標準eCK模型下是可證明安全的，并且由文獻[16]相關結論可得可以達到弱的完美前向安全.此AKE協議的安全性最終可歸約為格上的HNF-RLWE問題的困難性.

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

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

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

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

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

分析情形3中偽造攻擊：若攻擊者M可構造一個模擬器S，且模擬器S可利用M以不可忽略的優勢解決RLWE問題.

證畢.

本文構造的協議可抵御猜測攻擊、密鑰復制攻擊以及偽造攻擊，基于隨機預言機在標準eCK模型下是可證明安全的，且可以達到弱的完美前向安全.協議方案的安全性可歸約為格理論上的RLWE問題的困難性.

4.2 協議安全性測試

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

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

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

5 效率分析對比

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

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

6 總 結

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

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

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