李子臣，謝 婷，蔡居良，張?bào)戕?/p>

(1.西安電子科技大學(xué) 通信工程學(xué)院，西安 710071； 2.北京印刷學(xué)院 教務(wù)處，北京 102600；3.北京電子科技學(xué)院 通信工程系，北京 100070)(*通信作者電子郵箱xieting0713@163.com)

0 引言

密鑰交換(Key Exchange， KE)協(xié)議[1-2]使雙方或多方在不安全的信道上協(xié)商出共同的會(huì)話密鑰，在安全通信領(lǐng)域具有重要的基礎(chǔ)作用。1976年，Diffile-Hellman提出了著名的Diffile-Hellman密鑰交換協(xié)議[3]，該協(xié)議拉開了公鑰密碼學(xué)的序幕，具有里程碑的意義。但Diffile-Hellman協(xié)議為被動(dòng)安全的密鑰交換協(xié)議，無法抵抗中間人攻擊。而認(rèn)證密鑰交換(Authenticated Key Exchange, AKE)協(xié)議旨在不僅使雙方協(xié)商得到共享會(huì)話密鑰，且為通信雙方提供有效認(rèn)證。AKE協(xié)議中，通信雙方各自擁有一個(gè)長(zhǎng)期公私鑰對(duì)和一個(gè)臨時(shí)公私鑰對(duì)，其中長(zhǎng)期公鑰由可信賴的第三方頒發(fā)，雙方通過信息交互與計(jì)算最終得到共享會(huì)話密鑰。

量子計(jì)算機(jī)相關(guān)技術(shù)的飛速發(fā)展，使傳統(tǒng)的公鑰密碼體制隨之面臨嚴(yán)重威脅。2015年，美國(guó)國(guó)家標(biāo)準(zhǔn)和技術(shù)研究院(National Institute of Standards and Technology, NIST)頒布的后量子密碼學(xué)報(bào)告中指出：由于量子計(jì)算技術(shù)的迅速發(fā)展，現(xiàn)有的公鑰密碼標(biāo)準(zhǔn)將不再安全。目前，NIST、美國(guó)國(guó)家安全局(National Security Agency, NSA)以及由歐盟贊助的后量子密碼PQCRYPTO項(xiàng)目均已在全球范圍內(nèi)展開后量子密碼算法標(biāo)準(zhǔn)有關(guān)征集工作。其中，后量子密鑰交換協(xié)議已經(jīng)被NIST列為一項(xiàng)重大科研項(xiàng)目，設(shè)計(jì)安全高效的后量子密鑰交換協(xié)議具有重要的理論意義和應(yīng)用價(jià)值。

基于格理論已構(gòu)造出了加密、數(shù)字簽名、密鑰交換等諸多方案，而且在全同態(tài)加密方案[4]的構(gòu)造上出現(xiàn)了許多優(yōu)秀成果?；诟窭碚摰拿艽a系統(tǒng)具有可并行運(yùn)算、較高漸進(jìn)效率、可抵抗量子攻擊的優(yōu)勢(shì)，其構(gòu)造后量子AKE協(xié)議已成為當(dāng)前研究的熱點(diǎn)。2005年,Regev等[5]基于格理論提出帶誤差的學(xué)習(xí)(Learning With Errors， LWE)問題，并指出可使用量子規(guī)約技術(shù)將LWE問題的平均情形困難性歸約為一般格上困難問題——最短無關(guān)向量問題(Shortest Independent Vector Problem, SIVP)的最壞情形；2010年，Lyubashevsky等[6]提出了基于環(huán)上帶誤差的學(xué)習(xí)(Ring Learning With Errors， RLWE)問題，其困難性可規(guī)約到理想格上的困難問題——最短向量問題(Shortest Vector Problem, SVP)的最糟糕情形；2015年，Langlois等[7]研究了基于模上誤差學(xué)習(xí)性(Module Learning With Errors， MLWE)問題，它是LWE與RLWE的推廣。

本文在Zhang等[13]提出的認(rèn)證密鑰交換協(xié)議的研究基礎(chǔ)上，基于RLWE問題并使用Peikert式誤差協(xié)調(diào)機(jī)制提出了一種HQMV式認(rèn)證密鑰交換協(xié)議。Zhang等設(shè)計(jì)的認(rèn)證密鑰交換協(xié)議方案使用丁式誤差協(xié)調(diào)機(jī)制，為了滿足共享密鑰比特的均勻性以及安全性需求，Zhang等協(xié)議中參數(shù)模數(shù)q為亞指數(shù)級(jí)，相對(duì)較大，相應(yīng)通信量與計(jì)算量較大。而本文設(shè)計(jì)的認(rèn)證密鑰交換協(xié)議基于Peikert式誤差協(xié)調(diào)機(jī)制，該協(xié)議的模數(shù)q僅為多項(xiàng)式級(jí)，相對(duì)較小，因此通信量和計(jì)算量顯著降低。本文方案在BR模型[15]下可證明安全，并達(dá)到了弱前向安全(weak Perfect Forward Secrecy， wPFS)[16]。該協(xié)議安全性最終可歸約為格理論RLWE困難問題，是一種更加簡(jiǎn)潔高效、可抵御量子攻擊的后量子認(rèn)證密鑰交換協(xié)議。

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

1.1 環(huán)上帶誤差學(xué)習(xí)問題

定義1[5]判定型RLWE問題。已知n，q為正整數(shù)，χ為Rq上的某種分布，令秘密s∈Rq,定義如下兩個(gè)分布：

已知參數(shù)為(n,q,χ)的判定型RLWE問題為區(qū)分兩種分布Oχ,s與U。

已知參數(shù)為(n,q,χ)的判定型RLWE問題的短密鑰變體形式同樣為區(qū)分兩種分布Oχ,s與U。

1.2 丁式誤差協(xié)調(diào)機(jī)制

已知奇素?cái)?shù)q>2,環(huán)Rq=Zq[x]/(xn+1),定義環(huán)元素v=(v0,v1,…,vn-1)∈Rq,定義b=Cha(v)=(Cha(v0),Cha(v1),…,Cha(vn-1)),Mod2(v,b)=(Mod2(v0,b0),Mod2(v1,b1),…,Mod2(vn-1,bn-1))。已知v是從Rq中均勻隨機(jī)選取的，由于q是一個(gè)奇素?cái)?shù)，那么Mod2(v,b)的輸出并非是均勻分布的{0,1}n。

1.3 Peikert誤差協(xié)調(diào)機(jī)制與其多比特變形

1.3.1 Peikert式誤差協(xié)調(diào)機(jī)制

1.3.2 Peikert式誤差協(xié)調(diào)機(jī)制的多比特變形

Peikert誤差協(xié)調(diào)機(jī)制雙方僅能通過協(xié)調(diào)函數(shù)rec提取1比特密鑰，而一般化誤差協(xié)調(diào)機(jī)制是Peikert錯(cuò)誤協(xié)調(diào)機(jī)制的多比特變形，可保證雙方可以通過協(xié)調(diào)函數(shù)rec提取2B比特密鑰。

引理7[10]如果v∈Zq是均勻隨機(jī)的，那么給定〈v〉2B時(shí)，?v?2n在Zq上也是均勻隨機(jī)的。

1.4 基于兩種機(jī)制構(gòu)造的KE

1.4.1 基于丁式誤差構(gòu)造KE

2012年，Ding等首次提出利用丁式誤差協(xié)調(diào)機(jī)制[8]，并首次利用丁式誤差協(xié)調(diào)機(jī)制設(shè)計(jì)了一個(gè)被動(dòng)安全的密鑰交換協(xié)議。以基于RLWE問題使用丁式誤差協(xié)調(diào)機(jī)制構(gòu)造的密鑰交換協(xié)議為例，協(xié)議如圖1所示。

AliceBobsA,eA＄←χpA=msA+2eApA→sB,eB,e′B＄←χkB=pA·sB+2e′BPB=msB+2eBσ=Cha(kB)e′A＄←χPB,σ←skB=Mod2(kB,σ)kA=PB·sA+2e′AskA=Mod2(kA,σ)

圖1 基于丁式誤差協(xié)調(diào)機(jī)制構(gòu)造的被動(dòng)安全KE

Fig. 1 Passively secure KE based on
Ding’s error reconciliation mechanism

1.4.2 基于Peikert式誤差協(xié)調(diào)機(jī)制構(gòu)造的KE

2015年，Bos等[11]提出一種Diffie-Hellman類密鑰交換協(xié)議，其安全性基于RLWE問題，有效利用了Peikert式誤差協(xié)調(diào)機(jī)制，協(xié)議滿足被動(dòng)安全。協(xié)議如圖2所示。

AliceBobs,e＄←χs′,e′,e″＄←χb←as+eb→b′←as′+e′v←bs′+e″v＄←dbl(v)c←〈v〉2q,2∈{0,1}nkA=rec(2b′s,c)∈{0,1}nb′,c←kB=?v?2q,2∈{0,1}n

圖2 基于Peikert式誤差協(xié)調(diào)機(jī)制構(gòu)造的KE

Fig. 2 KE based on Peikert’s error reconciliation mechanism

1.4.3 兩種誤差協(xié)調(diào)機(jī)制構(gòu)造KE的分析

丁式誤差協(xié)調(diào)機(jī)制與Peikert式協(xié)調(diào)機(jī)制本質(zhì)上為對(duì)偶關(guān)系，丁式誤差協(xié)調(diào)機(jī)制提取Zq元素的低位比特，Peikert誤差協(xié)調(diào)機(jī)制則提取的是Zq元素的高位比特。對(duì)于通信雙方擁有的近似相等的值，兩種誤差協(xié)調(diào)機(jī)制均是通過誤差處理得到相同密鑰，兩種誤差協(xié)調(diào)機(jī)制對(duì)于近似值的容錯(cuò)范圍均為|e|

兩種誤差協(xié)調(diào)機(jī)制也存在區(qū)別，其中丁式誤差協(xié)調(diào)機(jī)制使用的模數(shù)q為奇數(shù)，因此利用其構(gòu)造的密鑰交換協(xié)議雙方共同分擔(dān)的比特存在一定的偏差，得到的共同密鑰在{0,1}上的分布必然是不均勻的，在密鑰分布不均勻的情況下敵手能以不可忽略的概率猜測(cè)出對(duì)應(yīng)比特值，因此無法有效抵御敵手的攻擊。由于模函數(shù)的輸出分布與均勻分布并沒有明顯的不可區(qū)分性，由此可知，當(dāng)敵手通過會(huì)話狀態(tài)問詢時(shí)會(huì)得到一些共享密鑰相關(guān)的信息，密鑰交換協(xié)議將不再安全。在此時(shí)，為了達(dá)到安全性需求，最后經(jīng)過模函數(shù)得到的比特值雖然是高熵的，但必須使用隨機(jī)提取器才能保證雙方可得到幾乎為均勻分布的共享密鑰。在實(shí)際應(yīng)用中，根據(jù)NIST提供的標(biāo)準(zhǔn)可使用哈希函數(shù)如SHA-2得到一個(gè)均勻分布的密鑰，如果執(zhí)行哈希函數(shù)之后最終得到的比特串的長(zhǎng)度為K，則使用哈希函數(shù)之前的比特串的長(zhǎng)度至少為2K。根據(jù)文獻(xiàn)[13]參數(shù)設(shè)置，n=λ,q=λ4,此時(shí)模數(shù)q值很大，相應(yīng)計(jì)算量與通信量很大。

2 新型的基于RLWE問題的AKE

2.1 利用丁式誤差協(xié)調(diào)機(jī)制構(gòu)造的AKE

發(fā)起方i響應(yīng)方j(luò)si, ei←χsj, ej←χpi=asi+2eipj=asj+2ejri, fi, gi←χβrj, fj, gj←χβxi=ari+2fixi→yj=arj+2fjki=(pjd+yj)(sic+ri)+ 2dgiyj,wj←kj=(pic+xi)(sjd+rj)+2cgjwj=Cha(kj)∈{0,1}nσi=Mod2(ki,wj)∈{0,1}nσj=Mod2(kj,wj)∈{0,1}nski=H2(i, j,xi,yj,wj,σi)skj=H2(i, j,xi,yj,wj,σj)會(huì)話公共參數(shù):c=H1(i, j,xi)∈R, d=H1(j,i,yj,xi)∈R

圖3 Zhang等設(shè)計(jì)的認(rèn)證密鑰交換協(xié)議

Fig. 3 Authentication key exchange protocol designed by Zhang et al

Zhang等的協(xié)議為HMQV形式[16]的基于丁式誤差協(xié)調(diào)機(jī)制設(shè)計(jì)的實(shí)用的AKE，通信雙方i和j的長(zhǎng)期公私鑰均由可信任的第三方頒發(fā)。協(xié)議的安全性歸為基于格理論的RLWE問題，因此可抵御量子攻擊。但為了達(dá)到安全性需要，模數(shù)q達(dá)到了亞指數(shù)級(jí)，q較大，造成協(xié)議的通信量與計(jì)算量較大。

本文在對(duì)Zhang等設(shè)計(jì)的協(xié)議研究基礎(chǔ)上，提出了一種基于RLWE問題并使用Peikert式誤差協(xié)調(diào)機(jī)制的更加高效實(shí)用的認(rèn)證密鑰交換協(xié)議。由于該協(xié)議使用Peikert式誤差協(xié)調(diào)機(jī)制，在經(jīng)過協(xié)調(diào)函數(shù)處理時(shí)雙方就可得到均勻分布的{0,1}比特串，即可直接產(chǎn)生一個(gè)均勻無偏差的密鑰。Zhang等設(shè)計(jì)的協(xié)議為了滿足安全性的需求，需要選擇亞指數(shù)級(jí)的模數(shù)q，而本文設(shè)計(jì)的協(xié)議只需要多項(xiàng)式級(jí)較小的模數(shù)q便可達(dá)到安全性的需求，因此該協(xié)議在參數(shù)設(shè)置中的模數(shù)q相對(duì)較小，與張等設(shè)計(jì)的協(xié)議相比，通信量與計(jì)算量大大降低，協(xié)議更加簡(jiǎn)潔高效。

2.2 利用Peikert式誤差協(xié)調(diào)機(jī)制構(gòu)造的新型AKE

AliceBobsA, eA←χsB, eB←χrA, fA←χrB, fB←χxA=arA+fAxA→yB=arB+fBkB=g(pAc+xA)(sBd+rB)kA=g(PBd+yB)(sAc+rA)yB,wB←wB=〈kB〉2∈{0,1}nvA=rec(2kB,wB)∈{0,1}nvB=?kB?2∈{0,1}nSKB=H2(IDA,IDB, xA,yB,wB,vB)SKA=H2(IDA,IDB, xA,yB,wB,vA)會(huì)話公共參數(shù):c=H1(IDA,IDB,xA)∈R,d=H1(IDA,IDB,xA,yB)∈R

圖4 基于Peikert式誤差協(xié)調(diào)機(jī)制設(shè)計(jì)的新型AKE

Fig. 4 New AKE based on Peikert’s error reconciliation mechanism

下面是協(xié)議的具體執(zhí)行過程：

1)Alice首先從離散高斯分布χ中進(jìn)行隨機(jī)抽樣，得到長(zhǎng)期私鑰sA和誤差eA,sA和eA為n維向量，之后Alice通過計(jì)算pA=asA+eA得到長(zhǎng)期公鑰pA,并進(jìn)行公布;再從離散高斯分布χ中進(jìn)行隨機(jī)抽樣，得到臨時(shí)私鑰rA和誤差fA,rA和fA為n維向量，Alice通過計(jì)算xA=arA+fA得到臨時(shí)公鑰xA,并將xA發(fā)送給Bob；

3)Alice計(jì)算kA=g(PB·d+yB)(sA·c+rA),并計(jì)算vA=rec(2kB,wB),最后通過SKA=H2(IDA,IDB,xA,yB,wB,vA),得到會(huì)話共享密鑰SKA。

3 正確性分析

kA-kB=

g[(fB·rA-fA·rB)+(d·eB·rA-c·eA·rB)]=

g[(c·fB·sA-d·fA·sB)+c·d(eB·sA-eA·sB)]

4 參數(shù)設(shè)置

q≥

5 安全性分析

如果RLWE問題是困難的，則本文設(shè)計(jì)的AKE協(xié)議在標(biāo)準(zhǔn)模型BR模型[15]下是可證明安全的。具體而言，攻擊者M(jìn)贏得游戲的優(yōu)勢(shì)滿足：

AdvMGame0≤2n(n-1)t·

(AdvD1RLWE+AdvD2RLWE+AdvD3RLWE+AdvD4RLWE)

(1)

證明 通過下列游戲的形式證明協(xié)議的安全性，假設(shè)進(jìn)行此AKE的參與者的個(gè)數(shù)為n，每個(gè)用戶之間至多可進(jìn)行t次會(huì)話，攻擊者M(jìn)贏得游戲表示為事件Ei,AdvMGamei表示攻擊者M(jìn)贏得Gamei的優(yōu)勢(shì)，Di表示區(qū)分均勻分布與RLWE分布的區(qū)分器。

Game0:與提出的AKE協(xié)議描述相同，攻擊者M(jìn)贏得游戲Game0的優(yōu)勢(shì)為:

AdvMGame0=|2Pr(E0)-1|

(2)

Game1:隨機(jī)選擇s←(1,t),攻擊者M(jìn)進(jìn)行Test查詢，如果沒有測(cè)試到第s個(gè)會(huì)話，則退出游戲，那么此時(shí)輸出一個(gè)隨機(jī)值，其他情況則與Game0相同。令suc1表示成功猜測(cè)出這個(gè)事件，那么可以得到此時(shí)攻擊者M(jìn)贏得游戲Game1的優(yōu)勢(shì)為：

得AdvMGame1=|2Pr(E1)-1|=

(3)

Game2:從(1,n)個(gè)參與者中隨機(jī)選擇兩個(gè)參與者u,v，如果參與者v沒有被Test查詢，則退出游戲，此時(shí)輸出一個(gè)隨機(jī)值，其他情況與Game1相同，令suc2表示為成功猜測(cè)出這個(gè)事件，那么攻擊者M(jìn)贏得游戲Game2的優(yōu)勢(shì)為：

AdvMGame2=|2Pr(E2)-1|=

(4)

|Pr(E2)-Pr(E3)|≤AdvD1RLWE

(5)

|Pr(E3)-Pr(E4)|≤AdvD2RLWE

(6)

|Pr(E4)-Pr(E5)|≤AdvD3RLWE

(7)

(8)

由于在Game6中，AKE協(xié)議公開傳輸?shù)男畔⒕鶠殡S機(jī)均勻選擇，可知此時(shí)協(xié)議生成的會(huì)話密鑰是完全隨機(jī)的，因此攻擊者M(jìn)贏得游戲Game6的概率為：

(9)

由(2)～(9)式得(1)，此AKE協(xié)議在BR 模型下可證明安全，且安全性最終歸約為RLWE問題的困難性。

由于kA=g(PBd+yB)(sAc+rA),kB=g(pAc+xA)(sBd+rB),雙方會(huì)話密鑰的生成并不完全由參與者雙方的長(zhǎng)期公私鑰協(xié)商得到，同時(shí)也包含了雙方會(huì)話的臨時(shí)私鑰。當(dāng)長(zhǎng)期私鑰泄露前的會(huì)話密鑰沒有被敵手破壞時(shí)，即使會(huì)話雙方的長(zhǎng)期私鑰sA和sB被敵手獲得，但由于敵手未知臨時(shí)私鑰rA或rB的有關(guān)信息，無法計(jì)算出kA或kB,則敵手將無法獲得雙方會(huì)話密鑰，因此可得本文提出的AKE協(xié)議具有弱的完美前向安全性[16]。

6 效率對(duì)比

通過目前公開的學(xué)術(shù)文獻(xiàn)，對(duì)現(xiàn)有的基于RLWE問題、并使用不同的誤差協(xié)調(diào)機(jī)制構(gòu)造的KE、AKE方案與本文設(shè)計(jì)的方案進(jìn)行綜合分析。選取最典型的Ding方案[8]、Peikert方案[9]和NewHope[12]，這三個(gè)密鑰交換協(xié)議為被動(dòng)安全的密鑰交換協(xié)議，為非認(rèn)證密鑰交換協(xié)議。Zhang方案[13]、Ding口令方案[14]以及本方案均為認(rèn)證密鑰交換協(xié)議。通過密鑰交換協(xié)議方案的模數(shù)q、誤差分布、困難假設(shè)、誤差協(xié)調(diào)方式、通信及計(jì)算復(fù)雜度、安全性能等方面進(jìn)行對(duì)比以突顯本文方案的綜合性能。表1為本方案與現(xiàn)有的基于RLWE問題的密鑰交換方案性能對(duì)比情況。

表1 基于RLWE問題設(shè)計(jì)的密鑰交換協(xié)議的性能比較

7 結(jié)語

本文基于RLWE問題并使用Peikert式誤差協(xié)調(diào)機(jī)制提出了一種新型后量子認(rèn)證密鑰交換協(xié)議。使用格理論中理想格上的解碼基為工具進(jìn)行了正確性分析，并為保證通信雙方以顯著概率得到相同的會(huì)話密鑰設(shè)置了合理的參數(shù)。與現(xiàn)有的基于RLWE問題設(shè)計(jì)的認(rèn)證密鑰交換協(xié)議相比，本文協(xié)議采用Peikert式誤差協(xié)調(diào)機(jī)制使雙方得到共享會(huì)話密鑰，模數(shù)q由亞指數(shù)級(jí)降低至指數(shù)級(jí)，模數(shù)q顯著減小從而使協(xié)議的計(jì)算量與通信量得以有效降低。該協(xié)議在BR模型中可證明安全并具有弱的完美前向安全性,且協(xié)議的安全性可歸約為格理論中的RLWE困難問題，因此可抵御量子計(jì)算機(jī)的攻擊。下一步考慮基于LWE、RLWE以及MLWE問題設(shè)計(jì)更加簡(jiǎn)潔、安全高效的后量子認(rèn)證密鑰交換協(xié)議。