后量子前向安全的可組合認證密鑰交換方案

陳 明

(宜春學院數學與計算機科學學院 江西宜春 336000)

認證密鑰交換(authenticated key exchange, AKE)協議用于在開放網絡環境下，網絡通信實體之間確認彼此身份、協商共享會話密鑰，為通信提供機密性、認證性和完整性保障.自Diffie和Hellman提出密鑰交換(簡稱為DHKE[1])概念以來，AKE協議得到廣泛的研究和應用，是保障網絡通信安全的基礎協議之一.

AKE協議的一個重要安全屬性是會話密鑰的前向安全性(forward secrecy, FS)，是指參與會話的用戶長期私鑰泄露不影響之前已經建立的會話密鑰的安全性.隨著量子計算技術的發展，FS被賦予了新的含義，即向后量子時代過渡的時期，AKE協議被要求能抵抗未來量子計算機的攻擊.后量子的網絡通信安全受到越來越多政府、研究機構和學者的關注.2016年美國國家標準與技術研究所(National Institute of Standards and Technology, NIST)開啟了下一代密鑰交換和數字簽名的后量子標準征集工作[2].我國、日本及歐洲也相繼開展相關研究項目.

近20年來，基于格(lattice)上困難問題構建密碼系統的研究[3-8]取得進展，為后量子密碼研究和應用奠定了基礎.在Asiacrypt2009會議上，Katz等人[9]提出了首個基于格問題的口令認證密鑰交換協議.隨后，文獻[10-24]分別提出多種基于格上困難問題的密鑰交換方案.總體來看，提出的方案分為2種類型:一類采用密鑰封裝機制(key encapsulation mech-anism, KEM)傳輸會話密鑰材料;另一類則基于格上LWE(ring-learning with errors, Ring-LWE)問題[4,7-8]構造了類似DHKE的密鑰交換機制(記為DHKE-like[10,18,20]).需要指出的是，由于缺乏后量子的公鑰基礎設施(public key infrastructure, PKI)支持，基于格的密鑰交換協議在當下還不能作為后量子密鑰交換的完整解決方案.一種過渡時期的解決辦法是將后量子的(無認證)密鑰交換與現有的公鑰密碼系統整合，利用現有公鑰密碼技術實現實體的相互認證，典型的方案有Bos等人[18]將基于Ring-LWE問題的DHKE-like機制與TLS[25]握手協議進行整合，實現會話密鑰的后量子前向安全性.但是，TLS協議需要多輪信息交換，不適合某些特殊的應用場景，如多方認證、傳感器網絡、自組織網絡和專用網絡等.

為了適應更加廣泛的網絡應用環境，考慮過渡時期對AKE方案的可擴展性需求，本文提出“簽密[26](signcryption, SC)+DHKE-like”的可組合AKE架構.

簽密的概念由Zheng[26]在1997年的美密會議上提出，能在一個密碼學的邏輯步驟中同時實現消息的機密性和認證性，在網絡通信領域有著廣闊的應用前景，得到了廣泛研究.

本文的主要工作是：本文提出以DHKE-like為基礎的一輪(2-pass)AKE方案，主要工作包括3個方面:

1) 提出“SC+DHKE-like”架構的通用可組合AKE方案(記為GC-AKE).具體來說，采用具有IND-CCA安全(indistinguishability against chosen ciphertext attacks)和SEUF-CMA[27]安全(strong existentially unforgeable under adaptive chosen mess-ages attacks)的SC機制對DHKE-like中的臨時公鑰參數進行加密和簽名，實現實體認證和會話密鑰協商.但是，一個關鍵問題是，理想格上DHKE-like機制的臨時公鑰大小為幾十Kb，其簽密的計算以及通信開銷較大.為了降低開銷，本文設計了臨時公鑰特征提取和恢復函數進行特征提取、公鑰隱藏和恢復，將認證過程中簽密消息的長度從幾十Kb降低為nb(本文取n=1 024).

2) 基于現有AKE的安全模型，定義了wAKE-PFS安全模型，重點模擬AKE協議的完美前向安全性(perfect FS, PFS).在wAKE-PFS模型下，本文GC-AKE協議的安全性被規約到敵手求解DDH-like問題(見本文3.1節定義8)，以及攻破SC機制的IND-CCA和SEUF-CMA安全性.

3) 考慮到(后量子)過渡時期的實際應用需求，提出一種基于身份的簽密(identity-based signcryp-tion, IBSC)機制，以Boneh等人[28]提出的短簽名方案BBS為基礎擴展而來，在選擇身份安全模型下實現了IND-CCA和SEUF-CMA安全性.將IBSC機制與理想格上的DHKE-like組合，可實現用戶的相互認證，以及抵抗量子計算機的完美前向安全性.

1 相關工作

后量子密鑰交換的前期研究工作主要集中于構造無認證的密鑰交換方案，或者KEM機制，作為一個獨立的密碼套件與其他加密原語(如數字簽名)進行組合(類似TLS[25]和SIGMA方案[29])，實現實體的認證和密鑰交換.比較典型的方案包括：Ding等人[10]提出了格上DHKE-like密鑰交換方案；Peikert[16]基于Ring-LWE問題提出了帶密鑰調節機制的KEM方案；Bos等人[18]采用Peikert的密鑰調節機制構造了BCNS-DHKE-like協議及其在一般格上的變形(Frodo[19])；Alkim等人[20]將BCNS-DHKE-like協議進行簡化，提出了NewHope方案，將Ring-LWE實例中誤差采樣的離散高斯分布替換為中心二項分布，以提高采樣效率；隨后，Alkim等人將NewHope方案變形，提出更加簡化的NewHope-Simple KEM[21]方案，并且采用了密文壓縮技術以降低通信開銷.

在基于格的AKE方面，Fujioka等人[13-14]、Zhang等人[17]、Ding等人[11-12]分別提出一輪隱式認證和密鑰交換方案，融合對方實體的長期和臨時公鑰與自身的長期和臨時私鑰，以某種方式融入到會話密鑰的計算中，實體的相互認證有賴于會話雙方計算一致的會話密鑰.具體來說，Fujioka等人[13]提出一種通用的AKE構造方法，采用一種稱之為“twisted PRF”的技術(類似于NAXOS trick[30])，2個偽隨機函數(pseudo-random function, PRF)分別輸入實體的長期私鑰和臨時私鑰，相互交織，輸出高安全性的密鑰材料，實現抵抗長期私鑰泄露的偽裝攻擊和臨時私鑰泄露攻擊.然而，Fujioka方案實例[14]計算過程復雜，通信開銷較大，總體的性能較差.Zhang等人[17]基于Ring-LWE問題構造了類似HMQV[31]協議的隱式認證與密鑰交換方案.Zhang等人[17]的方案采用了Ding等人[10]提出的DHKE-like密鑰交換機制，在會話雙方之間協商得到2個近似相等的多項式，通過密鑰調節機制，從2個多項式中提取一致的會話密鑰材料.但是，在基于Ring-LWE問題的DHKE-like密鑰交換中重用公鑰被認為存在私鑰泄露風險[32-33].為了彌補這一缺陷，Ding等人[12]提出公鑰可重用AKE方案，利用一個隨機諭言機(一個密碼Hash函數)對臨時公鑰進行結構調整.Yang等人[23]提出一種強安全性的通用AKE方案，采用OT-IND-CCA[23]安全(one-time IND-CCA)的KEM設計了一種OTKEM機制傳遞密鑰材料，使用強不可偽造簽名算法實現實體認證，并提出一種基于Ring-LWE問題的OTKEM實例.然而，Yang等人[23]提出的OTKEM實例計算和通信代價太高，難以實際應用.李子臣等人[24]將NewHope-Simple KEM[21]方案變形為公鑰加密機制，以此為基礎構造了基于Ring-LWE問題的AKE方案.但是，李子臣等人提出的AKE方案不能抵抗密鑰重用攻擊，具體分析見本文5.2.1節.

此外，Wang等人[15]提出格上的基于身份AKE協議(ID-AKE)，采用ABB-IBE[34]加密傳輸會話密鑰材料.該方案構造簡單，安全性低，不具有前向安全性.趙秀鳳等人[22]提出一種基于BCNS-DHKE-like機制的ID-AKE方案(記為Zhao-AKE).但是，Zhao-AKE方案存在較為嚴重的安全缺陷，具體在本文5.2.2節分析.由于基于格的IBC系統普遍存在密鑰尺寸較大的問題，使得格上基于身份的KEM密文尺寸大，限制了其在AKE領域的應用.就目前的文獻來看，尚沒有高效、安全的基于格的ID-AKE協議發表.

本文提出一種可組合的AKE方案，重點關注在過渡時期的后量子前向安全性.本文方案采用“SC+DHKE-like”組合，可實現跨密碼體制的AKE協議，適應多種應用需求.例如針對過渡時期的網絡通信安全需求，本文4.2節提出的GC-AKE實例采用基于橢圓曲線密碼(elliptic curve cryptography, ECC)的IBSC與基于Ring-LWE問題的DHKE-like機制組合，實現了跨密碼體制的ID-AKE協議.盡管本文方案以BCNS-DHKE-like協議為基礎，但是可采用具有DDH-like性質的其他DHKE-like協議(如DHKE[1]和NewHope[20]協議)直接替換.此外，通過將SC機制擴展為多接收者的簽密方案，還可以將本文的GC-AKE方案擴展到多方認證的應用環境.對比相關的通用AKE方案，例如文獻[14,23]，本文方案在實現較強安全性的同時，具有結構簡單、可組合的優勢，同時在計算、存儲和通信開銷方面具有一定優勢.

2 背景知識

2.1 數學概念與定義

本節簡要描述本文所使用的數學概念和符號，以及困難數學問題.

2.1.1 雙線性映射理論

本節簡要闡述與本文相關的雙線性對理論及假設，詳細內容請參考文獻[28,35].

雙線性映射:給定素數階為p的循環群G1，G2和GT，g1和g2分別是G1和G2的生成元，且存在同構函數ψ:G2→G1，使得ψ(g2)=g1成立，定義雙線性映射e:G1×G2→GT滿足3個性質.

2) 非退化性.e(g1,g2)≠1.

3) 可計算性.給定任意的u∈G1,v∈G2，能有效計算e(u,v).

為了敘述簡潔，本文省略了“modp”運算.

2.1.2 環的定義及困難問題

R=Z[X](Xn+1)是一個分圓多項式環，其中，n為2的整數冪，環的元素是系數為整數的多項式.

令Rq=RqR，Rq的成員用它的所有系數組成的向量表示，每個系數是Zq中的成員，q為整數模量.

令‖·‖和‖·‖分別表示向量(或多項式)的歐拉范數和無窮范數，令a←UR表示從R中抽取均勻隨機的元素a，令χ表示R上的概率分布，e←χ表示從χ中隨機抽取元素e.

BCNS-DHKE-like方案以Rq上Ring-LWE問題為基礎，下面描述其判定性問題和假設，詳細內容請查閱文獻[8,18].

定義1.判定Ring-LWE問題.給定參數(n，q，R，Rq，χ)，對隨機選擇的s←χ，定義諭言機OD,s按2個步驟執行：1)隨機選取a←URq和e←χ；2)返回(a,as+e)∈Rq×Rq.

判定Ring-LWE問題是區分OD,s的輸出與Rq×Rq上的隨機均勻樣本.特定地，定義區分算法A，則A的優勢為

定義1中，s從錯誤分布χ中選取，而不是Rq的均勻分布，Lyubashevsky等人[8]證明了s的選取不影響判定Ring-LWE問題的困難性(文獻[8]的引理2.24).

2.2 AKE協議安全模型

本文安全模型以Cremers等人[36]的eCK-PFS模型為基礎，融合了王霏和陳明[37]對eCK-PFS模型的擴展.下面對相關概念進行簡要闡述，詳細內容見文獻[36-37]和本文3.3.2節.

會話(session)是協議實例的一次運行，由一個七元組Ts=(sactor,speer,srole,ssent,srecv,sstat,scomp)唯一標識.Ts記錄會話s的運行參數，sactor和speer記錄實體身份；srole是會話擁有者的角色；ssent和srecv記錄發送和接收的消息；sstat記錄臨時參數；scomp記錄會話狀態，scomp=T表示會話已完成，scomp=表示會話未完成.

敵手(adversary)被模擬為一個概率多項式時間圖靈機，允許執行如下詢問.

1)Send(s,M)詢問.模擬敵手發送消息M到會話s.

2)Corrupt(ID)詢問.詢問用戶ID的長期私鑰.

3)Ephemeral-key(s)詢問.詢問會話s的臨時秘密.

4)Session-key(s)詢問.詢問會話s的會話密鑰.

5)Test(s*)詢問.模擬器隨機選擇ζ∈{0,1}，如果ζ=0,輸出s*的會話密鑰，否則輸出隨機的SK←{0,1}λ.其中，λ為安全參數.

下面定義原始會話、匹配會話和會話新鮮性.

定義4.eCK-PFSfresh[36].如果已完成的會話s滿足6個條件，那么s滿足eCK-PFSfresh.

1)sactor，speer是誠實的參與者；

2) 未執行過Session-key(s)詢問；

3) 如果存在s*?s，則未執行Session-key(s*)詢問；

4) 不允許同時執行Ephemeral-key(s)詢問和Corrupt(sactor)詢問；

5) 對于所有滿足s′→s的s′，不允許同時執行Corrupt(speer)詢問和Ephemeral-key(s′)詢問；

6) 如果不存在s′滿足s′→s，那么在s完成之前，不允許執行Corrupt(speer)詢問.

此外，本文定義一類較弱的安全模型，命名為wAKE-PFS，不模擬協議的抗臨時秘密泄露攻擊(maximal exposure attacks, MEX[13])，即不允許敵手詢問會話的臨時秘密(Ephemeral-key(s)詢問).

定義6.wAKE-PFSfresh.如果已完成的會話s滿足5個條件，那么s滿足wAKE-PFSfresh.

1)sactor，speer是誠實的參與者；

2) 未執行過Session-key(s)詢問；

3) 如果存在s*?s，則未執行Session-key(s*)詢問；

4) 如果不存在s*?s，但是存在s′→s，則在s完成之前，不允許執行Corrupt(speer)詢問.

5) 如果不存在s′滿足s′→s，則不允許執行Corrupt(speer)詢問.

除了MEX安全性，wAKE-PFS模型能模擬AKE協議的其它安全屬性，包括KCI和PFS.

2.3 簽密及其安全模型

簽密由系統建立、密鑰生成、簽密和解簽密4個算法組成.本文以IBSC為例，定義為：

系統建立.輸入安全參數λ，PKG(private-key generator)產生系統的公開參數和主密鑰.

密鑰生成.輸入用戶身份ID，密鑰生成中心產生用戶密鑰SK并通過安全信道返回給用戶.IBC系統中，用戶私鑰實質是PKG對用戶ID的簽名.

簽密.輸入發送者私鑰SKs、接收者身份IDr和待簽密消息m，輸出密文c←SCIBSC(m,SKs,IDr).

解簽密.輸入發送者公鑰IDs、接收者私鑰SKr和密文c，輸出明文m←UnSCIBSC(c,SKr,IDs)或者“⊥”(表示密文無效).

簽密應同時滿足IND-CCA和EUF-CMA安全性，分別歸納為IND-CCA和EUF-CMA的2類安全游戲.本文AKE方案要求IBSC具有強的不可偽造性，以選擇身份安全模型為例，定義為：

初始化.C創建系統公開參數和N個用戶身份{ID1,ID2,…,IDN}，隨機選擇l∈{1,2,…,N}.

詢問1.敵手A自適應地提交多項式時間有界的詢問，挑戰者C模擬IBSC的相應算法對A的詢問進行應答.

1) 密鑰詢問.A提交用戶身份IDi，如果IDi=IDl，則終止模擬，否則C輸出IDi的長期私鑰.

2) 簽密詢問.A輸入(m,IDs,IDr)，C輸出簽密密文c.

3) 解簽密詢問.A輸入(c,IDs,IDr)，如果驗證簽密密文有效，則輸出明文m，否則返回⊥.

3 基于DHKE-like的AKE方案

本節提出一種以DHKE-like為基礎的GC-AKE方案，下面首先簡要闡述Bos等人[18]的DHKE-like方案，然后提出本文GC-AKE方案模型.

3.1 DHKE-like密鑰交換方案

BCNS-DHKE-like[18]方案在密鑰交換雙方交換2個近似相等的多項式環成員，采用Peikert[16]定義的密鑰調節機制從2個多項式中提取相同的密鑰材料.

首先簡要介紹Peikert[16]定義的密鑰調節機制.

定義MR(modular rounding)函數?·?q,2和CR(cross-rounding)函數〈·〉q,2為：

?·?q,2：Zq→Z2,x?x?q,2=2xq+1mod 2，
〈·〉q,2：Zq→Z2,x〈x〉q,2=4xqmod 2.

MR函數和CR函數的輸入可擴展為多項式，對多項式的每一個系數分別執行?·?q,2和〈·〉q,2運算.例如令f=fn-1Xn-1+…+f1X+f0∈Rq，則〈f〉q,2=(〈fn-1〉q,2,…,〈f1〉q,2,〈f0〉q,2)∈R2.

當q為奇數時，為了避免MRCR函數輸出偏倚，需要將模數擴大為2q，定義dbl函數為

dbl: Zq→Z2q,x

定義集合.

令E=[-q4,q4)，對與v∈Zq逼近的w∈Zq，令v′=dbl(v)∈Z調節函數定義為

基于Peikert[16]定義的密鑰調節機制，Bos等人[18]實現的BCNS-DHKE-like方案如圖1所示：

Fig. 1 Unauthenticated Diffie-Hellman-like key exchange圖1 無認證的Diffie-Hellman-like密鑰交換方案

定義8.DDH-like problem[18].給定參數(n，q，R，Rq，χ)和1個DHKE-like實例(a,b,b′,c,κ)，區分κ是DHKE-like的有效解還是{0,1}n上的隨機樣本.特定地，對于多項式時間敵手A，定義A贏得DDH-like挑戰的優勢為

定理1.給定參數(n，q，R，Rq，χ)，如果判定Ring-LWE問題是難解的，那么DDH-like問題也是困難的.特定地，對于多項式時間敵手A，贏得DDH-like挑戰的優勢為

其中，B1和B2為判定Ring-LWE問題的敵手.

定義8和定理1來源于文獻[18]的定義3和定理1，文獻[18]對定理1進行了安全性規約，本文不再贅述.

3.2 基于DHKE-like的認證密鑰交換方案

本文提出的GC-AKE方案包含系統建立、用戶密鑰生成和密鑰交換3個階段.

1) 系統建立.輸入安全參數λ，認證權威運行Setup算法，產生系統參數para={n,q,Rq,χ,a,H}.其中，a←URq，H：{0,1}*→{0,1}λ為密鑰導出函數.

2) 用戶密鑰生成.給定用戶的標識為ID，令用戶的公私鑰為(pkID,skID).這里不具體指定用戶密鑰生成的方式，可基于PKI系統或者IBC系統等.

3) 密鑰交換.如果Alice與Bob期望建立安全會話，按如下步驟進行認證與密鑰交換，如圖2所示.令Alice,Bob的身份和密鑰分別為(IDA,pkA,skA),(IDB,pkB,skB).

Fig. 2 Generic authenticated key exchange protocol圖2 通用的AKE協議

③ Alice計算θB←UnSC(cB,skA,pkB)，κA←rec(2bBtA,θB)，SKAB=H(IDA,IDB,μA,θB,κA).

在理想信道下，如果簽密方案滿足正確性，且BCNS-DHKE-like密鑰交換有效，那么誠實的Alice和Bob能以極大的概率(不小于1-2-217)輸出一致的會話密鑰，SKAB=SKBA.也就是說，如果密文c是簽密算法的有效輸出c←SC(μ,ski,pkj)，則接收者必然輸出有效的μ←UnSC(c,skj,pki)，進而認證雙方能建立有效的DHKE-like實例(a,bA,bB,μA,θB,κA,κB)，使得κA=κB.可見，本文GC-AKE方案滿足正確性.

本文GC-AKE方案以無認證DHKE-like方案為基礎，組合簽密方案，實現實體的認證和密鑰協商.DHKE-like方案每次選擇新鮮的臨時公(私)鑰，與用戶長期私鑰無關，實現了會話密鑰的新鮮性和前向安全性；簽密方案對發送者和接收者的身份進行了綁定，只有擁有相應私鑰的用戶才能完成密鑰交換，協商一致的會話密鑰，融合了顯式認證(簽名)和隱式認證(加密).本文方案具有可組合的特點，根據不同安全需求，可采用任何滿足安全性要求的簽密方案和DHKE-like方案進行組合，實現認證密鑰交換.例如本文4.2節提出的GC-AKE實例采用基于ECC的IBSC與基于Ring-LWE問題的DHKE-like機制組合，既能滿足現實的應用需求，還能實現抵抗量子計算攻擊的前向安全性.

3.3 GC-AKE方案的安全性分析

本節首先分析F(*)函數的安全性，然后采用wAKE-PFS模型對GC-AKE方案進行安全性規約.

3.3.1F(*)函數的安全性分析

從3方面分析F(bA)函數的安全性.

2) 分析敵手完整恢復bA的概率.同上，由于bA的每個系數的符號位等于“0”的概率近似為12，則敵手完整恢復bA的概率為max(2-1 024,εSC).其中，εSC為敵手攻破SC方案IND-CCA安全的概率.

3.3.2 GC-AKE方案安全性規約

本文采用wAKE-PFS模型對GC-AKE方案進行安全性規約.與eCK-PFS模型不同，wAKE-PFS模型不允許敵手詢問會話的內部狀態(臨時秘密參數).

根據wAKE-PFSfresh定義，本文主要考慮6種攻擊場景S1～S6，如表1所示.令s表示Test會話，s分為發起者會話(I)和響應者會話(R)這2類，每一類會話分別存在3種情形：1)存在s*?s(則至少存在一個原始會話s*→s)；2)不存在s*?s，但存在s′→s；3)s*?s和s′→s都不存在.表1中，MS表示匹配會話，OS表示原始會話；Yes表示存在s*?s或s′→s，No則表示不存在；allowed表示允許敵手執行Corrupt詢問，allowed*表示在s完成之前不允許敵手執行Corrupt詢問，disallowed表示不允許敵手執行Corrupt詢問.

表1中，所有場景均允許敵手詢問會話擁有者的私鑰(Corrupt(sactor)詢問)，表明所有場景均可模擬密鑰泄露偽裝攻擊(KCI)；S1和S4場景允許敵手在任意時刻詢問挑戰會話雙方的私鑰，由于s存在匹配會話，限制了敵手在挑戰會話中主動注入臨時秘密的能力，而場景S2和S5允許敵手在s完成之后詢問對端實體的私鑰(Corrupt(speer))，能模擬協議的完美前向安全性(PFS).

“BR+wPFS”模型不區分匹配會話與原始會話，不能模擬S2，S5；S2，S5分別包含在S3，S6中；這是wPFS與PFS安全性的主要區別.

定理2.給定參數(n，q，R，Rq，χ)，如果DDH-like假設成立，并且SC方案滿足IND-CCA和SEUF-CMA安全性，那么本文提出的GC-AKE協議滿足wAKE-PFS安全.

證明. 首先考慮定義7的第1個條件，2個誠實的用戶完全如實地按照協議執行，如果他們完成了一次匹配的會話，根據匹配會話條件，如果SC方案有效，接收方能正確恢復bA和θB，進而，密鑰交換雙方能輸出相同的會話密鑰SKAB=SKBA，且Pr(SKAB=SKBA)≥1-2-217.

其次，對于定義7的第2個條件，根據安全游戲，本文將GC-AKE協議的安全性規約為求解DDH-like問題和攻破SC方案的IND-CCA和SEUF-CMA安全性.

表1所概括的6種場景分別對應一個安全游戲.考慮到模擬過程冗長且差別不大，本文選取場景S1，S3和S5進行詳細敘述.場景S1模擬AKE協議的弱前向安全性(wPFS)，S5模擬AKE的完美前向安全性(PFS)，S3重點模擬AKE協議的KCI安全性.

游戲過程模擬為敵手A與挑戰者C之間的一系列游戲.C激活一個模擬器產生系統公開參數，創建N個獨立的用戶P={ID1,ID2,…,IDN}，發送給敵手A，接受敵手的詢問并做出相應的應答.令π表示本文GC-AKE協議，Sj表示游戲GameSi.j(i∈{1,2,3,4,5,6},j∈{0,1,2,3,…})中敵手猜測成功的事件，那么GameSi.j中敵手贏得游戲的優勢定義為：εj=|2Pr(Sj)-1|.令N，qI，qR分別表示游戲中創建的用戶數、發起者會話數和響應者會話數的上界.注意，模擬過程中，C將所有簽名驗證不成功的詢問作為無效詢問.

下面首先敘述S1的模擬過程，由一系列游戲GameS1.j組成.

GameS1.0：GameS1.0模擬真實的攻擊場景，A自適應地提交詢問，C按照協議π和安全模型的定義對A的詢問做出應答，那么A贏得游戲的優勢為：ε0=|2Pr(S0)-1|.

GameS1.1：在GameS1.0的基礎上，GameS1.1考慮一些小概率的碰撞事件，比如在不同的會話中發生臨時參數碰撞或者Hash碰撞等，當出現此類事件則模擬失敗.令E1表示上述小概率事件，根據差分引理(文獻[36]引理1)：

|Pr(S0)-Pr(S1)|≤Pr(E1)，
ε0=|2Pr(S0)-1|=2|Pr(S0)-Pr(S1)+
Pr(S1)-12|≤2(|Pr(S0)-Pr(S1)|+
|Pr(S1)-12|)≤ε1+2Pr(E1).

那么，GameS1.1中A成功的優勢為：ε1≥ε0-negl(λ).其中，negl(λ)為一個可忽略的函數，表示E1發生的概率.

GameS1.3：在GameS1.2的基礎上，GameS1.3模擬對DDH-like問題的挑戰.給定一個DDH-like問題實例(a,b*,b″,θ″,κ*)，模擬過程描述為：

1)C按照真實協議的系統建立算法生成系統公開參數para={n,q,Rq,χ,a,H}發送給A.

2)C按照協議的密鑰生成算法生成用戶密鑰(pkID,skID)，將(ID,pkID,skID)插入初始為空的列表LID.

3)A提交Send(s，IDj)詢問激活發起者會話s.令sactor=IDi，如果s=s*，C計算(b′*,μ*)←F(b*)，c*←SC(μ*,skIDi,pkIDj)，將(b′*,c*)返回給A(事件E3)；否則，C按照協議步驟計算響應消息(bi,ci)返回給A.最后更新Ts.

5)A提交Send(s，M)詢問.如果s是一個已激活的發起者會話，且scomp≠T，且如果s=s*，則置scomp=T；否則C按照協議計算得到sstat=(bi,bj,μi,ci,θj,κi,SKij)，更新Ts并置scomp=T；否則忽略.

6)A提交Corrupt(ID)詢問.如果ID∈P，則查詢LID返回用戶ID的私鑰，否則返回⊥.

7)A提交Reveal(s)詢問，如果s=s*∨s?s*，算法終止(破壞wAKE-PFSfresh)；否則，如果s不存在或scomp≠T則返回⊥；否則C查詢sstat，返回相應的SKij.

9) 最后，A輸出其猜測ζ′∈(0,1)，則C直接輸出ζ′作為對DDH-like挑戰的應答(事件E5).

GameS1.3與GameS1.2在事件E3～E5不同.事件E3描述用給定的DDH-like挑戰實例(a,b*,b″,θ″)替換挑戰會話s*及其匹配會話s″的輸出.假定(a,b*,b″,θ″)獨立于A的視角，則敵手不能區分GameS1.3和GameS1.2.事件E4和事件E5都是C的內部事件，對A透明.假設在DDH-like挑戰中，ζ=0表示κ*是DDH-like實例(a,b*,b″,θ″)的有效的解，則ζ=1表示κ*是{0,1}n上的隨機值.Test(s)詢問中，SK*根據κ*計算得到，如果ζ=0，則SK*是挑戰會話s*的正確會話密鑰；如果ζ=1，則SK*與隨機的SK*←U{0,1}λ不可區分，則GameS1.3和GameS1.2的Test(s)詢問輸出同分布.因此，敵手不能根據E4和E5區分GameS1.3和GameS1.2.則GameS1.3中敵手成功的優勢：ε3≥ε2-negl(λ).

根據系列游戲結果，A贏得GameS1的優勢為：ε≤ε1+negl(λ)≤qIqRε2+negl(λ)≤2qIqRεddhl+negl(λ).

場景S1的模擬到此結束，下面敘述場景S3的模擬過程.

GameS3.0：與GameS1.0相同，GameS3.0模擬真實的攻擊場景，A贏得游戲的優勢為：ε0=|2Pr(S0)-1|.

GameS3.1：與GameS1.1相同，在GameS3.0的基礎上，GameS3.1考慮一些小概率的碰撞事件，則A成功的優勢為：ε1≥ε0-negl(λ).

GameS3.3：在GameS3.2的基礎上，GameS3.3考慮對SC算法的SEUF-CMA攻擊.C創建模擬環境，構造諭言機OSC模擬SC算法的簽密和解簽密運算，運行子算法B，游戲模擬如下.

B維護初始為空的列表LSC=(IDi,IDj,ν,c).

步驟1)、2)與GameS1.3相同.

5)A提交Send(s，M)詢問.如果s是一個已激活的發起者會話，且scomp≠T，令sactor=IDi，M=(bj,cj).如果cj?LSC是與IDj相關的可驗證有效的簽密密文，IDj=ID*是密文cj的簽名者身份，那么B輸出cj作為對SEUF-CMA挑戰的應答，然后終止模擬(事件E3)；否則，B詢問諭言機OSC，解密cj得θj，按照協議計算得到sstat=(bi,bj,μi,ci,θj,κi,SKij)，更新Ts并置scomp=T；否則忽略.

6)A提交Corrupt(ID)詢問.如果ID=ID*，則算法終止(破壞wAKE-PFSfresh)；否則，如果ID∈P，B向C提交密鑰詢問返回用戶ID私鑰，否則返回⊥.

7)A提交Reveal(s)詢問，如果s=s*∨s?s*，算法終止(破壞wAKE-PFSfresh)；否則，如果s不存在或scomp≠T則返回⊥；否則B查詢sstat，返回對應的會話密鑰SKij.

9) 最后，A輸出其猜測ζ′∈(0,1).

如果事件E3發生，算法終止，A輸出隨機的ζ′∈(0,1)，則Pr(S3|E3)=12.如果事件E3不發生，則因此有：可得A成功的優勢為：

GameS3.4：在GameS3.3的基礎上，GameS3.4考慮對SC算法的IND-CCA攻擊.C創建模擬環境，運行子算法F，游戲模擬如下.

F維護初始為空的列表LSC=(IDi,IDj,ν,c).

步驟1)、2)與GameS1.3相同.

6)A提交Corrupt(ID)詢問.如果ID=ID*，則算法終止；否則，如果ID∈P，F向C提交密鑰詢問，將得到的用戶私鑰返回給A，否則返回⊥.

7)A提交Reveal(s)詢問，如果s=s*∨s?s*，算法終止；否則，如果s不存在或scomp≠T則返回⊥；否則查詢sstat，如果存在SKij，則返回SKij；否則返回隨機的SKij←U{0,1}λ(事件E7).

9) 最后，A輸出其猜測ζ′∈(0,1)，則C輸出ζ′作為對IND-CCA挑戰的應答.

根據系列游戲結果，A贏得游戲GameS3的優勢為：ε≤2NqIεF(1-εB)+negl(λ).

場景S3的模擬到此結束，下面敘述場景S5的模擬過程.

GameS5.0：與GameS1.0相同，GameS5.0模擬真實的攻擊場景，A贏得游戲的優勢為：ε0=|2Pr(S0)-1|.

GameS5.1：與GameS1.1類似地，在GameS5.0的基礎上，GameS5.1考慮小概率碰撞事件，A成功的優勢為：ε1≥ε0-negl(λ).

GameS5.3：與GameS3.3類似，在GameS5.2的基礎上，GameS5.3考慮對SC算法的SEUF-CMA攻擊.C創建模擬環境，運行子算法B，游戲模擬如下.

B維護初始為空的列表LSC=(IDi,IDj,ν,c).

步驟1)、2)、3)與GameS3.3相同.

步驟4)和5)與GameS3.3基本相同.不同之處在于事件E3的觸發條件：如果cj?LSC是與IDj相關的可驗證有效的簽密密文，IDj=ID*是密文cj的簽名者身份，且敵手尚未執行Corrupt(ID*)詢問，那么B輸出cj作為對SEUF-CMA挑戰的應答.

步驟7)、8)、9)與GameS3.3相同.

根據系列游戲結果，A贏得游戲GameS5的優勢為：ε≤2NqRεddhl(1-εB)+negl(λ).

證畢.

4 一種GC-AKE架構的ID-AKE方案

本節提出一種基于GC-AKE架構的ID-AKE方案，采用基于身份的簽密(IBSC)方案.根據GC-AKE架構的要求，IBSC方案應同時滿足IND-CCA和SEUF-CMA安全性.

4.1 強安全的基于身份簽密

本文的IBSC方案來源于Boneh和Boyen[28]提出的BBS簽名，王霏等人[37]將BBS簽名擴展為基于身份的簽名，本文進一步將其擴展為IBSC方案.下面簡要描述BBS方案及其擴展.

4.1.1 BBS簽名

BBS簽名基于雙線性映射理論，相關背景知識和符號定義見本文2.1節.

定理3[28].如果群G1,G2,GT上的(q,t′,ε′)-SDH假設成立，則BBS簽名實現了(t,qs,ε)-SEUF-CMA安全.其中，qs

文獻[28]對其進行了證明，這里不再贅述.

4.1.2 IBSC方案

IBSC方案描述如下.

簽密(SCIBSC).輸入待簽密消息m∈{0,1}n，發送者身份IDs及密鑰SKs=(xs,ys,zs)，接收者身份及公鑰參數(IDr,R3r)，步驟計算為：

解簽密(UnSCIBSC)：輸入密文c=(W,τ,ω,σ,t)，發送者身份及公鑰(IDs,R1s,R2s)，接收者身份IDr及密鑰SKr=(xr,yr,zr)，步驟計算為：

需要說明的是，本文IBSC方案沿用文獻[28]的符號定義，采用標準離散群的數學描述，具有更好的通用性.在具體實現中，為了降低開銷，BBS簽名可采用定義在y2=x3+2x±1上的橢圓曲線和超奇異橢圓曲線構建ECC系統.在本文第5節的分析中，也采用了基于ECC的方案.

4.1.3 IBSC方案安全性分析

初始化.輸入安全參數λ，挑戰者C生成系統公開參數param={G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.其中，H1,H2,H3,H4,H5模擬為隨機諭言機.C維護初始為空的L1=(ID,R,h1)，L2=(η,m,h2)，L3=(U,h3)，L4=(η,h4)，L5=(W,τ,ω,m,h5)和LID=(ID,R1ID,R2ID,R3ID,r1ID,r2ID,r3ID,xID,yID,wID)分別記錄H1,H2,H3,H4,H5詢問和用戶密鑰.

詢問1.A自適應地執行多項式時間有界的詢問，C模擬IBSC方案的相應算法做出應答.注意：詢問中隨機選擇的參數出現碰撞則重新選擇.

4)H3詢問.輸入Ui，C查詢L3，如果存在(Ui,h3i)，則輸出h3i；否則，隨機選擇并輸出h3i∈{0,1}n，將(Ui,h3i)插入L3.

5)H4詢問.輸入ηi，C查詢L4，如果存在(ηi,h4i)，則輸出h4i；否則隨機選擇輸出h4i∈{0,1}n，將(ηi,h4i)插入L4.

7) 密鑰詢問.輸入IDi，如果IDi=ID*，則C終止模擬；否則如果LID中存在(IDi,*,*,*,*,*,*,xi,yi,zi)則返回(xi,yi,zi)給A，否則返回⊥.

詢問2.A可以繼續提交詢問，詢問過程與第1階段相同，但是不能提交c*=(W*,τ*,ω*,*,*)的解簽密詢問.

證畢.

證明. 我們將IBSC方案的不可偽造性規約到BBS方案的SEUF-CMA安全性.規約過程分為初始化、詢問和偽造3個階段，包含2類模擬器C0和C1，以及敵手A.規約形式采用嵌套的游戲模擬方式，外層模擬以C0為模擬器，A為敵手，內層模擬(BBS挑戰游戲，參考文獻[28])以C1為模擬器，C0為敵手，C0可以向C1提交BBS簽名詢問，最后向C1提交偽造的BBS簽名.模擬之前，C0選擇i∈{1,2,…,N}，令IDi=ID*表示創建的第i個用戶身份.

初始化.輸入安全參數λ，挑戰者C1產生BBS挑戰游戲的公開參數(G1,G2,GT,g1,g2,e,u*,v*,α)發送給模擬器C0，C0產生IBSC游戲公開參數param={G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.與定理4的證明過程相同，H1,H2,H3,H4,H5模擬為隨機諭言機，C0維護初始為空的L1，L2，L3，L4，L5和LID分別記錄H1,H2,H3,H4,H5詢問和用戶密鑰.此外，C0維護初始為空的LSC=(Wi,τi,ωi,hi,σi,ti)記錄簽密詢問的結果.

詢問.A自適應地提交多項式時間的下列詢問.

步驟2)～7)與定理4證明過程相同.

8) 簽密詢問.輸入(IDs,IDr,mi)，如果IDs=ID*，C0按照SCIBSC算法第1)步計算得到(Wi,τi,ωi)，提交H5詢問得到h5i，然后向C1提交h5i的BBS簽名詢問得到簽名(σi,ti)，將ci=(Wi,τi,ωi,σi,ti)返回給A；否則，C0按照SCIBSC算法計算輸出ci=(Wi,τi,ωi,σi,ti).其中，H1,H2,H3,H4,H5運算替換為對應的諭言機詢問.最后，C0將(Wi,τi,ωi,h5i,σi,ti)插入LSC.

9) 解簽密詢問.與定理4相同.

顯然，如果c*=(W*,τ*,ω*,σ*,t*)是IBSC的有效的偽造密文，那么(h*5,σ*,t*)必然是BBS的有效的偽造簽名.即，如果A挑戰成功，則C0必然挑戰成功.

證畢.

4.2 基于IBSC的ID-AKE方案

本文ID-AKE方案基于3.2節提出的GC-AKE方案和4.1節提出的IBSC算法，描述如下.

系統建立.輸入安全參數λ，PKG產生系統參數para={n,q,Rq,χ,a,H,G1,G2,GT,g1,g2,e,α,P0,H1,H2,H3,H4,H5}.系統參數包含了基于格的和基于雙線性映射的2套參數.

密鑰交換.如果Alice與Bob期望建立安全會話，其密鑰交換過程與圖2基本相同.為了進一步增強安全性(主要考慮抵抗臨時秘密泄露攻擊(ESR))，將會話密鑰的計算方式替換為

但是這種增強的方式在基于格的密碼系統中并不直接適用.因為在基于格的環境下，不具有與離散群相同的CDH假設，則基于格的ESR安全性需要進一步討論.

5 對比分析

5.1 相關AKE方案對比分析

本文選擇FSXY方案[14]、BCNS方案[18]、YCL方案[23]和DBS方案[12]作為對照方案進行對比分析，如表2所示.其中，FSXY方案和YCL方案為通用AKE在格密碼系統下的實例；BCNS方案將DHKE-like密鑰交換與TLS握手協議整合，實現經典密碼系統下的實體認證以及后量子的會話密鑰前向安全；DBS方案則采用類似HMQV協議的密鑰交換方案，側重實現隱式認證.本文方案則遵循BCNS方案的思路，將DHKE-like密鑰交換與現有經典公鑰密碼系統相結合，重點關注會話密鑰的后量子前向安全性.此外，本文方案也融合了通用AKE的思想，以適應后量子密碼技術的發展，以及提供AKE方案的可擴展性.例如，BCNS-DHKE-like密鑰交換方案可直接使用其他具有類似DDH屬性的DHKE-like密鑰交換方案替代，比如NewHope[20]協議.

此外，李子臣等人[24]和趙秀鳳等人[22]也分別提出了基于Ring-LWE問題的AKE方案.但是，本文分析發現，這2種方案都存在較為嚴重的安全缺陷，具體的分析見本文5.2節.

Table 2 Comparison of Several AKE protocols

可以看出，FSXY方案和YCL方案在計算、存儲和通信方面的開銷都明顯較大.特別是通信開銷(表2第6列)，表2中僅列出了直接的密鑰交換開銷和公鑰傳輸的開銷，由于基于格的證書系統尚未建立，公鑰證書的開銷則未列入，其他如密鑰調節參數由于相對較小(1 024 b)也未列入.具體來看，FSXY方案共發送9個Rq上的成員(其中2個Rq上的成員為用戶長期公鑰)，YCL方案則多達2μ+m+5個Rq上的成員.以n=1 024，logq=32為例，1個Rq上的成員約為4 KB，則FSXY方案的通信開銷大于36 KB. BCNS方案、DBS方案和本文方案的總體開銷差別不大.BCNS方案的計算性能雖然較優，但是TLS握手協議需要多輪信息交互，其總體性能并不占優.此外，FSXY方案、YCL方案和DBS方案未指明用戶公鑰的授信機制，假定采用PKI體制，與公鑰證書相關的開銷并未在表2中列出.本文方案實例基于IBC系統，對用戶公鑰的授權驗證包含在IBSC算法中，在通信部分增加約160 B傳輸開銷(假定用戶身份標識為20 B).

在安全性方面(表2第7列)，BCNS方案僅實現了客戶端對服務器的認證，采用ACCE[39]安全模型(類似于BR+wPFS)；DBS方案實現了相互認證，采用了BR+wPFS模型；FSXY方案采用了CK+模型；YCL方案則采用了eCK-PFS模型；本文提出的通用AKE采用wAKE-PFS模型(見第2節)，而第4節提出的AKE實例則實現了eCK-PFS安全性.嚴格來講，FSXY方案和YCL方案的MEX安全性具有較大局限性.由于FSXY方案和YCL方案等通用AKE方案臨時秘密參數較多，不能像HMQV協議那樣將MEX安全性規約到一個確定的DHKE實例，部分參數泄露仍然不能保證MEX安全性.例如，FSXY方案中的(KA,KB,KT)和YCL方案中的rpgid1泄露同樣不能防止會話密鑰泄露，在實際應用中，不能區別對待臨時的秘密參數.在本文4.2節的AKE實例中，即使所有臨時的參數泄露(包括DHKE-like密鑰κ)，針對非量子攻擊者，也能確保會話密鑰的安全性.

5.2 2種AKE方案的安全性分析

5.2.1 NLPQ-AKE方案分析

李子臣等人[24]提出一種基于Ring-LWE問題的AKE方案(記為NLPQ-AKE).NLPQ-AKE中采用的IND-CPA安全的PKE(記為NLPQ-CPA-PKE)是NewHope-Simple KEM的變形.但是，文獻[21]不建議NewHope-Simple KEM方案的公鑰重復使用.Bauer等人[40]分析表明，對于NewHope-Simple CPA-KEM實例，重用公鑰會導致私鑰泄露，對于NewHope-Simple CCA-KEM實例，在可能重用公鑰的情況下，應謹慎設計CPA-KEM→CCA-KEM轉換中的關鍵步驟.不幸的是，NLPQ-AKE方案中的NLPQ-CCA-KEM機制完全暴露了NLPQ-CPA-PKE機制的密文，不能抵抗密鑰重用攻擊.NLPQ-AKE方案分為2組獨立(分別采用用戶長期公鑰和臨時公鑰)的密鑰交換，其中采用長期公鑰的NLPQ-CCA-KEM實例必然存在公鑰重用，將導致用戶長期私鑰的泄露.根據文獻[40]的測試結果，采用Alkim等人[21]推薦的系統參數，只需數千個重用公鑰的密文即以較大概率恢復對應的完整私鑰.

5.2.2 Zhao-AKE方案分析

趙秀鳳等人[22]提出一種基于BCNS-DHKE-like機制的ID-AKE方案(記為Zhao-AKE).但是，Zhao-AKE方案存在較為嚴重的安全隱患.具體來說，趙秀鳳等人提出一種新的基于身份密鑰生成算法(詳見文獻[22]的3.2節)，將用戶密鑰(Si=IiS+Mei)的安全性建立在Ring-LWE問題的困難性上.其中，Ii=H(IDi)和M為多項式環Rq上具有小范數的元素，S是系統主密鑰，ei是誤差值，S和ei服從Rq上的離散高斯分布.根據Ring-LWE假設，給定均勻隨機的a←URq，求解(a,as+e)∈Rq×Rq中的秘密s是困難的(其中s和e服從Rq上的離散高斯分布).由于Ii和M在Rq上并非隨機均勻分布，Zhao-AKE方案的用戶密鑰產生算法不滿足Ring-LWE假設條件，敵手可能利用Ii和M非均勻隨機分布的特性，實施對系統主密鑰S的猜測攻擊.就目前掌握的文獻資料來看，沒有相關的理論能夠證明非隨機均勻分布的(a,as+e)滿足Ring-LWE假設條件，而文獻[22]并未就這一關鍵問題展開討論.同理，用戶密鑰Si也不滿足判定Ring-LWE假設.文獻[22]的安全性證明中(引理10)，在Game3中用隨機的Ii←URq和M1←URq替換真實的Ii和M(Game2)，并聲稱敵手無法區分Game2和Game3(應用判定Ring-LWE假設).顯然，敵手可以通過計算Ii和M1的范數來區分，因為Game2中的Ii和M具有小的范數，而Rq上的隨機成員具有小范數的概率很低，Ii和M1的分布不滿足判定Ring-LWE假設條件，不適合應用這一假設，文獻[22]的安全性證明不成立.基于以上分析，Zhao-AKE方案[22]不是一種安全可靠的ID-AKE方案.

6 結束語

本文以格上(無認證)DHKE-like協議為基礎，采用簽密機制對DHKE-like協議中的臨時公鑰進行簽密，提出一種“SC+DHKE-like”的可組合AKE構造方案——GC-AKE.GC-AKE結構簡單，具有可組合的優點，可根據不同應用場景需求，采用不同密碼學原語加以組合.針對向后量子時代過渡的時期，面向AKE協議的后量子前向安全需求，本文提出采用基于ECC的IBSC結合基于理想格的DHKE-like協議實例.在wAKE-PFS模型下，本文的GC-AKE方案實現了可證明安全性，特別是實現了會話密鑰的PFS安全性.PFS安全性要求使用具有強不可偽造的簽名方案.因此，本文以BBS簽名為基礎，設計了強不可偽造的IBSC方案，并對其安全性進行了規約證明，實現了IND-CCA和SEUF-CMA安全性.但是，采用基于Ring-LWE問題的DHKE-like協議作為密碼套件存在一個關鍵問題，即：如果加密完整的臨時公鑰，則加密后的密文較大，使得AKE的計算和通信開銷較大.為了解決這一問題，本文提出臨時公鑰特征提取與隱藏函數，僅加密n位(本文取n=1 024)的特征值，顯著降低了需加密傳輸的數據量，使得本文的AKE協議實例的計算和通信開銷相對較優.進一步的優化可采用性能更優的DHKE-like協議替換BCNS-DHKE-like協議，如NewHope協議.