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

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

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

1 引言

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

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

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

2 基礎(chǔ)知識(shí)

2.1 格

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

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

2.2 RLWE 問題

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

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

2.3 eCK 模型

定義3假設(shè)會(huì)話是新鮮的，則滿足以下條件。

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

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

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

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

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

2.4 C 類承諾機(jī)制

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

3 協(xié)議設(shè)計(jì)

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

假設(shè)n是2的整數(shù)次冪，pw 是Alice 和Bob 的共享口令，G是階為q的群，q是素?cái)?shù)，N是群G的生成元。素?cái)?shù)q滿足q＞8且qm od2n=1，Rq是模數(shù)為q的多項(xiàng)式環(huán)，且，X是在Rq上的高斯離散分布，g是雙方共享的公共參數(shù)，(pk,sk)是Bob 的公鑰/私鑰對(duì)，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 隨機(jī)選擇y1∈(1,2,···,q)，計(jì)算u1=y1+H(IDA)，Alice 的身份信息IDA經(jīng)過com()函數(shù)處理得到承諾值MA。Alice 選取參數(shù)fA,α,Nonce ←χ，利用fA,α生成認(rèn)證參數(shù)X=gα+2fA，隨后利用Bob 的公鑰pk 加密得到Alice 的身份認(rèn)證信息AuthA，之后將H(IDA)|X|AuthA|u1發(fā)送給Bob。

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

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

② Bob 收到AuthA后，利用自己的私鑰sk 解密得到散列值HA=H(X|MA|pw|Nonce)和隨機(jī)參數(shù)Nonce。Bob 利用參數(shù)X|MA|pw|Nonce，首先計(jì)算HB=H(X|MA|pw|Nonce)，若HB=HA，則Alice 的身份認(rèn)證通過；反之失敗，Bob 拒絕通信。若身份認(rèn)證成功，Bob 隨后選取參數(shù)fB,β,rB←χ得到認(rèn)證參數(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，隨機(jī)選擇y2∈(1,2,···,q)，計(jì)算u2=y2+H(IDs)和 Bob 的身份認(rèn)證信息AuthB=HB′(Y|MB|pw|wB|Nonce +1)，隨后將H(IDB)|Y|AuthA|u2|wB發(fā)送給Alice。

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

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

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

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

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

假設(shè)q是大于2的素?cái)?shù)，，信號(hào)函數(shù)Sig(x)可定義為

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

證畢。

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

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

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

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

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

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

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

1)密鑰復(fù)制攻擊

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

2)偽造攻擊

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

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

3)抵抗重放攻擊

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

4)抵抗中間人攻擊

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

證畢。

4 性能分析

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

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

5 結(jié)束語

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