基于RLWE 支持身份隱私保護的雙向認證密鑰協(xié)商協(xié)議

楊亞濤，韓新光，黃潔潤，趙陽

（1.西安電子科技大學通信工程學院，陜西 西安 710071；2.北京電子科技學院電子與通信工程系，北京 100070）

1 引言

密鑰交換協(xié)議（key exchange protocol）[1]能夠使通信雙方或者多方在復雜信道上安全通信。1976年，Diffie 和 Hellman 設計了經(jīng)典的Diffie-Hellman 密鑰交換協(xié)議[2]，密鑰協(xié)商需要兩輪消息傳輸，此協(xié)議無法抵抗敵手發(fā)起的中間人攻擊和重放攻擊等，同時也不能提供相互認證的功能。

2001年，Li 等[3]提出適用于多服務環(huán)境的身份驗證協(xié)議，這個解決方案導致通信成本和計算成本太高，不能適用于實際情況。2012年，Liu等[4]提出了一個基于離散對數(shù)問題的多服務器認證協(xié)議。2004年，Tsaur 等[5]提出了一種基于RSA 算法和大整數(shù)問題的多服務器協(xié)議。同年，Juang[6]提出另一種使用對稱加密來驗證身份的多服務器身份驗證協(xié)議。然而，Chang 等[7]表明Juang 的協(xié)議易受離線字典攻擊，因此提出了一個克服Juang 的協(xié)議安全漏洞的方案。2009年，Regev 等[8]提出了帶錯誤的學習（LWE,learning with error）問題，說明了格上的最短向量問題等。2009年，Liao 等[9]提出了一種多服務器場景下的認證協(xié)議。2010年，Wu 等[10]提出了基于用戶認證的密鑰交換協(xié)議，該協(xié)議可以抵抗重放和密鑰復制等攻擊，并保證部分前向安全。Yoon等[11]引入了另一個基于客戶端/服務器的用戶認證密鑰交換協(xié)議來提高性能。2010年，Lyubashevsky 等[12]引入環(huán)上帶誤差學習（RLWE,ring learning with error）問題，困難性基于理想格上的最短向量問題（SVP,shortest vector problem）。2011年，He 等[13]提出了橢圓曲線上的用戶認證和密鑰交換協(xié)議，該協(xié)議提供了遠程相互認證與密鑰協(xié)商，并可抵御各種已知的攻擊。然而，Islam 等[14]證明了He 等[13]的協(xié)議易受已知密鑰會話臨時攻擊、冒充攻擊，無法保證用戶的匿名性。2010年，Hao 等[15]提出了一個基于客戶/服務器模型的PAKE（password authenticated key exchange）協(xié)議，該協(xié)議的安全性基于離散對數(shù)的困難性，這很容易受到量子計算機的攻擊。2015年，Zhang 等[16]提出了一種新的基于格理論的認證與密鑰交換方案。但是，他們需要參與者公鑰/私鑰對來完成身份認證。文獻[17]提出了一隱私保護的會話密鑰協(xié)商方法。文獻[18]提出了一種身份隱藏且非延展安全的認證密鑰協(xié)商方法。2016年，文獻[19]提出了基于 LWE 的2PAKE 協(xié)議。文獻[20]提出了關于驗證元的三方口令認證密鑰交換協(xié)議，但是存在效率低、占用資源多等缺點。2016年，Tseng 等[21]提出了用戶身份驗證和基于身份的密碼系統(tǒng)的密鑰協(xié)商協(xié)議，該協(xié)議能夠抵抗移動多服務器中的隨機數(shù)泄露攻擊。2018年，Wu 等[22]提出了一種新的基于混沌映射的多服務器環(huán)境用戶匿名認證密鑰協(xié)商方案，不能抵抗量子計算機的攻擊。同年，Sharma 等[23]提出了一種無配對的認證密鑰協(xié)商協(xié)議，計算成本低，特別是對于低功率設備，但是存在長期密鑰泄露和短暫密鑰泄露的風險。2017年，Jheng 等[24]提出了一種基于格理論的客戶端/服務器端模型的口令認證密鑰協(xié)商協(xié)議，該協(xié)議通過共享口令完成相互認證密鑰協(xié)商，但該協(xié)議用戶的身份信息不具有匿名性且不能抵抗中間人攻擊。

本文設計了一種基于RLWE 支持身份隱私保護的認證密鑰協(xié)商協(xié)議。該協(xié)議通過C 類承諾機制的設計，將通信雙方不愿暴露的真實身份信息隱藏為承諾值的形式，承諾值消息具有完整性，不可篡改。協(xié)議基于RLWE 困難問題，在保障身份匿名的前提下，通過2輪的消息交互不僅完成了雙向身份認證，而且保證傳輸消息的完整性，并協(xié)商出共享會話密鑰。通過分析，在協(xié)議執(zhí)行效率上，完成匿名的雙向認證與密鑰協(xié)商只需經(jīng)過2輪的消息傳輸，公鑰長度較短。在安全性上，所提協(xié)議能夠抵抗偽造攻擊、重放攻擊、密鑰復制攻擊和中間人攻擊。在eCK 模型下滿足可證明安全性，可以抵抗量子計算攻擊。

2 基礎知識

2.1 格

簡單地說，格（lattice）是實數(shù)空間中線性無關向量的整系數(shù)組合的集合。可以形式化地描述為給定n個m維的線性無關的向量b1,b2,…,bn∈Rm×n，由它們作為基形成的格是由下列向量組成的集合，如式(1)所示。

其中，b1,b2,…,bn為格的一組基，記為B=[b1,b2,…,bn]∈Rm×n。

2.2 RLWE 問題

定義1搜索性 RLWE 問題。令a均勻隨機選取，e∈R是服從正態(tài)分布ψ的差錯向量，若己知b∈R，且b=as+e，則由a、b求解s的問題就是搜索性RLWE 問題。

定義2判定性 RLWE 問題。令s均勻隨機選取，e∈R是服從正態(tài)分布ψα的差錯向量，計算b=as+e，且b∈R。記As,ψ為(a,b)的分布，則如何區(qū)分As,ψ與R×R上的均勻分布問題就是判定性RLWE 問題。假設判定性RLWE 問題是困難的，則As,ψ偽隨機。

2.3 eCK 模型

定義3假設會話是新鮮的，則滿足以下條件。

1)敵手E未對通信方i,j進行Ephemeral_Secret Reveal()和Static_Key Reveal()查詢。

這里假設敵手E 能夠任意偽造、重放和刪除通信信息，是一個概率多項式時間的圖靈機，且可完成以下功能。

1)Establish_Party(i)。敵手E 可在CA 上注冊參與者i的公鑰。

2)Ephemeral_Secret Reveal(i)。敵手E 獲得i的臨時私鑰。

5)Static_Key Reveal(i)。敵手E 獲得i的長期私鑰。

2.4 C 類承諾機制

G是階為q的群，q是素數(shù)，N是群G的生成元[25]。承諾時期，承諾者承諾被隱藏信息a∈{0,1,2,…,q-1}，計算com()=Na，將com()函數(shù)值發(fā)送給接收者。打開承諾，承諾者發(fā)送a給接收者，接收者證實等式com()=Na。

3 協(xié)議設計

3.1 協(xié)議參數(shù)選取

假設n是2的整數(shù)次冪，pw 是Alice 和Bob 的共享口令，G是階為q的群，q是素數(shù)，N是群G的生成元。素數(shù)q滿足q＞8且qm od2n=1，Rq是模數(shù)為q的多項式環(huán)，且，X是在Rq上的高斯離散分布，g是雙方共享的公共參數(shù)，(pk,sk)是Bob 的公鑰/私鑰對，IDA和IDB是Alice和 Bob 的身份信息，協(xié)議中的 com 函數(shù)為com()=NH(ID)。協(xié)議中涉及的散列函數(shù)H使用SHA256算法，輸出256 bit 的消息摘要。

3.2 協(xié)議執(zhí)行流程

協(xié)議的執(zhí)行流程如圖1所示，具體如下。

1)Alice 隨機選擇y1∈(1,2,···,q)，計算u1=y1+H(IDA)，Alice 的身份信息IDA經(jīng)過com()函數(shù)處理得到承諾值MA。Alice 選取參數(shù)fA,α,Nonce ←χ，利用fA,α生成認證參數(shù)X=gα+2fA，隨后利用Bob 的公鑰pk 加密得到Alice 的身份認證信息AuthA，之后將H(IDA)|X|AuthA|u1發(fā)送給Bob。

2)Bob 接收到H(IDA)|X|AuthA|u1后進行以下操作。

① Bob 接收到數(shù)據(jù)u1|H(IDA)，首先驗證消息y1|u1|MA的完整性。Bob 計算。驗證是否成立，如果等式成立，證明消息傳送過程中，參數(shù)未被更改，消息具有完整性；反之，則消息驗證失敗，Bob 拒絕通信。

② Bob 收到AuthA后，利用自己的私鑰sk 解密得到散列值HA=H(X|MA|pw|Nonce)和隨機參數(shù)Nonce。Bob 利用參數(shù)X|MA|pw|Nonce，首先計算HB=H(X|MA|pw|Nonce)，若HB=HA，則Alice 的身份認證通過；反之失敗，Bob 拒絕通信。若身份認證成功，Bob 隨后選取參數(shù)fB,β,rB←χ得到認證參數(shù)Y=gβ+2fB，KB=Xβ+2rB。利用Sig 和 Extr 函數(shù)得到wB=Sig(KB)，ρB=Extr(KB,wB)。

圖1 協(xié)議流程

③Bob 將身份信息IDB經(jīng)com()函數(shù)處理得到承諾值MB，隨機選擇y2∈(1,2,···,q)，計算u2=y2+H(IDs)和 Bob 的身份認證信息AuthB=HB′(Y|MB|pw|wB|Nonce +1)，隨后將H(IDB)|Y|AuthA|u2|wB發(fā)送給Alice。

最終 Bob 獲得共享會話密鑰skB=H(MA|MB|X|Y|wB|Nonce|ρB)。

3)Alice 接收到H(IDB)|Y|AuthA|u2|wB后進行以下操作。

①Alice 接收到Bob 傳來的數(shù)據(jù)u2|H(IDB)，首先驗證消息y2|u2|MB的完整性。Alice 計算并驗證是否成立。若等式成立，證明消息傳遞途中參數(shù)y2|u2|MB沒有被更改，消息具有完整性。反之，消息驗證失敗，Alice 拒絕通信。

②Alice 利用參數(shù)Y|MB|wB，將Nonce +1計算。若等式成立，Bob 的身份認證成功。反之失敗，Alice 拒絕通信。若身份認證成功，Alice 隨機選取參數(shù)rA←χ，計算KA=Yα+2rA，利用Extr 函數(shù)得到參數(shù)ρA=Extr(KA,wB)，則Bob 的共享會話密鑰skA=H(MA|MB|X|Y|wB|Nonce|ρA)。共享會話密鑰skA=skB，完成密鑰協(xié)商。

3.3 協(xié)議的正確性證明

假設q是大于2的素數(shù)，，信號函數(shù)Sig(x)可定義為

證明假設q是大于8的奇數(shù)，則Extr 函數(shù)[26]定義為

證畢。

3.4 協(xié)議的安全性證明

定義4敵手E 獲勝的優(yōu)勢可定義為

協(xié)議安全性條件介紹如下。

1)敵手E 可在匹配會話中獲得相等的會話密鑰。

2)在隨機多項式時間內(nèi)，敵手E 取得游戲勝利的概率忽略不計。

定理1在多項式時間內(nèi)，若敵手E 在游戲中以不可忽略的概率獲勝，則存在模擬器Q，能夠以AdvΠ(Q)優(yōu)勢在以上時間內(nèi)解決最短向量困難問題。

證明協(xié)議的安全性證明可歸約到求解基于格上最短向量困難的問題上。假設敵手E 攻擊協(xié)議成功，則證明敵手可以解決格上的最短向量困難問題。由于協(xié)議中會話密鑰與隨機數(shù)的不可區(qū)分性，敵手E 在協(xié)議運行多次的情形下，選擇單次目標會話，從密鑰空間中的隨機數(shù)或真實的會話密鑰之間隨機獲得一個，協(xié)議的安全性基于敵手E 僅以可忽略的概率分辨真實的會話密鑰和密鑰空間中的隨機值。

1)密鑰復制攻擊

敵手E 與通信雙方創(chuàng)建一個與測試會話擁有一致會話密鑰的會話，協(xié)議中會話密鑰的產(chǎn)生所依賴的參數(shù)fA,fB,α,Nonce,rB,rA隨機選取，則證明在不同隨機參數(shù)的輸入情形下產(chǎn)生相同的會話密鑰的概率可忽略。敵手E 在eCK 模型下不允許對同一通信參與者進行Static_Key Reveal()和Ephemeral_Secret Reveal()的同步查詢，因此真實會話與攻擊會話中同時擁有相同的認證密鑰和相同隨機數(shù)的事件發(fā)生的概率可忽略，協(xié)議可抵抗密鑰復制攻擊。

2)偽造攻擊

敵手E 計算得到ρA,ρB，借助隨機預言機獲得會話密鑰skA=H(MA|MB|X|Y|wB|Nonce|ρA)。假設敵手E 通過模擬器Q 的隨機選取獲得的n次會話中包括m次匹配會話，則模擬器Q 在通信雙方Alice 和 Bob 之間獲得匹配會話的概率為。如果敵手E 以概率p獲得匹配會話，且敵手E 成功地獲得了會話密鑰skA，說明敵手E 可計算ρA,ρB，由于ρA=SVP (kA,wA)，ρB=SVP (kB,wB),說明模擬器Q 能夠攻克格上的最短向量問題。敵手E 在eCK 模型下不能對同一參與者完成Static_Key Reveal()和Ephemeral_ Secret Reveal()的同步查詢，而且隨機預言機隨機選取相同輸入的情況可忽略，敵手E 和模擬器Q 的關系為

假設敵手E 能夠在多項式時間內(nèi)，利用n次會話中的m次匹配會話，并且在游戲中以優(yōu)勢AdvΠ(Q)獲勝，證明模擬器Q 可在多項式時間內(nèi)以優(yōu)勢AdvΠ(Q)攻克SVP，并滿足AdvΠ(Q)≥，則協(xié)議可抵抗偽造攻擊得證。

3)抵抗重放攻擊

重放攻擊即攻擊者通過二次發(fā)送復制信息欺騙通信參與者的行為。協(xié)議中，Alice 每次隨機選取參數(shù)fA,α,Nonce,rA，計算X,KA,ρA；Bob 每次隨機選取參數(shù)fB,β,rB，計算Y,wB,ρB。使當前單次會話生成的認證函數(shù)值AuthA,AuthB不同，導致最終產(chǎn)生的會話密鑰skA,skB不可匹配，表明協(xié)議可抵抗消息的重放攻擊。

4)抵抗中間人攻擊

中間人攻擊可通過獲取通信雙方的通信信息，進行篡改和竊聽的攻擊行為。Bob 接收到數(shù)據(jù)u1|H(IDA)，首先驗證消息y1|u1|MA的完整性。計算驗證Nu1=dAMA是否成立，若成立，則證明通信過程中消息y1|u1|MA完整沒有被更改。同理，Alice接收到Bob 傳來的數(shù)據(jù)u2|H(IDB)，首先驗證消息y2|u2|MB的完整性。Alice 計算y2=u2-H(IDB)，，并驗證是否成立，若成立，則證明通信過程中消息完整，y2|u2|MB沒有被更改。在這2次驗證消息完整性的過程中，由于僅傳輸雙方雙份身份信息的摘要值H(IDA)|H(IDB)和經(jīng)過處理的參數(shù)u1|u2，并不能獲得參數(shù)y1|y2和MA|MB，則中間人無法對中的任意一項進行篡改并最終使等式成立，故此協(xié)議可抵抗中間人攻擊。

證畢。

4 性能分析

為了證明本文方案的優(yōu)勢，將其與其他經(jīng)典方案進行性能對比分析，如表1所示。文獻[27]是LWE問題上的2PAKE 協(xié)議，不滿足客戶和服務端的雙向認證，易受不可測字典攻擊，消息傳輸3輪。文獻[16]是RLWE 困難問題上的2PAKE 協(xié)議，消息傳輸2輪，用戶無法匿名。以上2種方案公鑰長度均為(2n+1)lgq。文獻[28]設計了隱式和顯式認證2類2PAKE 協(xié)議，公鑰長度為2nlgq，消息傳輸輪數(shù)分別為2輪和3輪，用戶無法匿名。文獻[29]困難假設基于ASPH 困難問題，用戶無法匿名，公鑰長度為(2n+1)lgq，且需要4輪通信，消息傳輸輪數(shù)最多。文獻[30]提出了一種基于格的三方認證密鑰協(xié)商協(xié)議，困難假設基于RLWE 問題，用戶具有匿名性，可抵抗不可測字典攻擊，消息傳輸輪數(shù)為3輪，公鑰長度為2nlgq。文獻[24]提出了一種基于格理論的客戶端/服務器端模型下口令認證密鑰協(xié)商協(xié)議，用戶不具有匿名性，消息傳輸需要2輪，公鑰長度為nlgq，可抵抗不可測字典攻擊，消息不具備完整性驗證。本文方案公鑰長度為nlgq，在實現(xiàn)用戶匿名性的前提下與以上方案相比公鑰長度最短，消息傳輸輪數(shù)少，僅需要2輪通信，且能抵抗中間人攻擊、不可測字典攻擊、密鑰復制攻擊、重放攻擊、偽造和量子攻擊。通過與Ding 等[28]的協(xié)議對比，本文方案公鑰長度縮短50%，且消息傳輸輪數(shù)僅需要2輪，具有更好的安全性和通信性能。

表1 協(xié)議性能對比分析

5 結束語

認證密鑰交換協(xié)議可以在不安全的信道上協(xié)商出共同的會話密鑰。為了解決執(zhí)行認證密鑰交換協(xié)議時通信雙方身份匿名問題，本文提出了一種基于C 類承諾機制的抗量子攻擊的雙向認證密鑰協(xié)商協(xié)議。該協(xié)議通過C 類承諾機制的設計，將通信雙方不愿暴露的真實身份信息隱藏為承諾值的形式。協(xié)議基于RLWE 困難問題，在保障身份匿名的前提下，通過2輪的消息交互不僅完成了雙向身份認證，而且保證傳輸消息的完整性，并協(xié)商出共享會話密鑰。通過分析，在協(xié)議執(zhí)行效率上，完成匿名的雙向認證與密鑰協(xié)商只需經(jīng)過2輪的消息傳輸，公鑰長度較短。本文協(xié)議滿足可證明安全，可抵抗量子攻擊。下一步研究計劃將把本文協(xié)議進行軟件快速實現(xiàn)。