理想格上的多階段認證密鑰交換協議

摘要：現有的格基認證密鑰交換協議普遍基于Bellare-Rogaway等單階段模型，忽略了實際通信場景中會話密鑰建立的階段分離。針對這一問題，基于MSKE模型提出了一種格基多階段認證密鑰交換協議。該方案使用預共享的口令進行認證，并使用Peikert誤差消除機制結合服務器靜態密鑰實現多階段密鑰協商。分析表明，該方案整體只引入少量計算開銷，實現了雙向認證、二階會話密鑰完美前向保密、抗量子攻擊等特性，在MSKE模型下滿足KD-2FS-M安全等級，是一種簡單高效的后量子多階段密鑰交換協議。

關鍵詞：密鑰交換；格密碼；前向保密；誤差學習問題

中圖分類號：TP918.4文獻標志碼：A文章編號：1001-3695（2023）01-046-0278-05

doi： 10.19734/j.issn.1001-3695.2022.05.0262

Multi-stage authenticated key exchange protocol over ideal lattice

Chen Xiao，"" Wang Baocheng

（School of Information， North China University of Technology， Beijing 100144， China）

Abstract：

The existing lattice-based key exchange protocols generally base on the single-stage security models like Bellare-Rogaway， which ignoring the stage separation of session key’s construction in secure communication. In order to solve this problem， this paper proposed a lattice-based multi-stage authenticated key exchange protocol based on MSKE model. The scheme used pre-shared password for authentication， and the construction of multi-stage key exchange adopted the Peikert error-reconciliation mechanism and the server’s static key. The security analysis shows that the protocol only introduces a small computing overhead， allow the mutual authentication， two-stage perfect forward-secrecy， and resists quantum attack. This protocol meets the KD-2FS-M security level under MSKE model. It is a simple and efficient post-quantum multi-stage key exchange protocol.

Key words：key exchange; lattice-based cryptography; forward-secrecy; learning with errors

0引言

密鑰交換（key exchange，KE）協議這一概念最早由Diffie等人［1］提出，它允許通信參與者在公開的信道中協商產生會話密鑰進行保密通信。認證密鑰交換協議（authenticated key exchange，AKE）通過引入身份信息的方式實現通信雙方的認證，解決了傳統Diffie-Hellman密鑰交換協議無法抵御中間人攻擊的缺陷。目前，AKE被廣泛應用于各類安全通信協議之中。

在QUIC［2］、TLS［3］與Signal［4］等安全通信協議中，會話密鑰的建立通常要視為一個連續的過程，可以與密鑰的使用任意交錯，高強度的密鑰可能是分階段獲得和使用的。如QUIC為實現零往返時間（zero round trip times，0-RTT），使用服務器預共享密鑰協商生成中期密鑰來保護首輪通信，之后再交換新一輪協商所需的密鑰元素以生成更強的會話密鑰。 現有單階段AKE模型往往不適應此類理想策略的構建，這已經在HMQV［5］、Kudla-Paterson［6］、NAXOS［7］等文獻中有了較為深刻的探討。針對此類階段分離的協商策略，Fischlin等人［8］曾提出了一種多階段密鑰交換（multi-stage key exchange protocol，MSKE）模型，并給出了一種擴展形式的QUIC協議，協議將QUIC底層密鑰交換協議劃分為兩個階段，一階段協商提供0-RTT支持，二階段會話密鑰實現完美前向保密。2020年，Cohn-Gordon等人［9］又將MSKE模型推廣至更新的Signal協議，分析了Signal協議下的密鑰協商與密鑰派生過程，將Signal協議下的會話密鑰建立過程建模為一個三階段密鑰交換協議，并證明了Signal協議下多階段密鑰交換的強安全性與MSKE模型針對異步通信場景的獨特優勢。

1997年，Shor［10］提出了一種量子算法，可以在多項式時間內解決大數因子分解問題，隨著量子計算的發展，目前基于傳統困難問題密碼體制的安全性需要重新審視。2015年，美國國家標準局在全球范圍內開展了后量子密碼算法標準的征集工作［11］。在后量子密碼算法設計的諸多方案中，格密碼被認為是最有力的競爭者［12］。2005年，Regev等人［13］基于格理論提出了誤差學習問題（learning with errors，LWE），LWE問題具有良好的代數結構，在密碼學得到推廣。2010年，Lyubashevsky等人［14］又提出環上誤差學習問題（ring learning with errors，RLWE），較之LWE，基于該困難問題構造的方案在效率方面具有顯著的提升。自RLWE問題誕生以來，格基密鑰交換協議一直是后量子密碼學研究的熱門方向。

2012年，Ding［15］提出了第一個基于LWE問題的后量子密鑰交換方案，開創性地提出一種誤差消除機制來解決RLWE會話密鑰的匹配問題。2014年，Peikert［16］在文獻［15］基礎上，提出了一種新的誤差消除機制，減少了密文長度且降低了會話密鑰協商失敗的概率。2015年，Bos等人［17］采用Peikert式誤差協調機制，基于標準Diffie-Hellman協議構造了一個后量子密鑰交換協議，并給出了其與TLS協議的應用。同年，Zhang等人［18］基于LWE問題提出了一種后量子AKE協議，使用環數學特性實現通信參與者的身份認證。2020年，Zhao 等人［19］基于 LWE 問題，使用一種對稱密鑰共識算法，設計了結合智能卡與生物信息的雙因子認證密鑰交換協議，通過引入額外的認證元素提高方案安全性。2021年，李子臣等人［20］基于RLWE問題采用Peikert誤差消除提出一種C/S模式下的口令認證密鑰交換協議，使用NTRU算法和服務器預共享密鑰加密認證信息，在通信的安全度上具有額外優勢。上述方案均是在單階段密鑰交換模型之下進行構造，會話密鑰不滿足前向保密或是只滿足弱的前向保密，且需兩輪到三輪交互才可使用會話密鑰保護通信。

本文提出了一種理想格上的多階段認證密鑰交換協議，協議設計的思路來自文獻［8］中的擴展QUIC形式的多階段密鑰交換協議。主要貢獻有：a）基于RLWE問題，使用Peikert式誤差消除機制實現了一種后量子多階段密鑰交換協議，協議支持0-RTT，實現雙向認證、前向保密；b）在MSKE模型下證明本文協議是安全的多階段密鑰交換協議，評估了協議計算開銷與通信開銷，并與現有后量子認證密鑰交換協議進行了對比。協議引入少量計算開銷，實現了0-RTT支持、前向保密、雙向認證、抗量子攻擊等特性。

1知識背景

1.1環上誤差學習問題

單回顧Lyubashevsky等人［14］提出的環上誤差學習問題。

定義1RLWE分布。設Z是有理整數環，定義多項式R=Ζ［X］/〈f（X）〉，其中f（X）=Xn+1，正整數n為2的冪次方。定義整數q≥2，Rq=R/qRZq［X］/（Xn+1）。對于向量s∈Rq，定義在Rq×Rq的RLWE分布（a，a·s+e mod q）；其中χ是Rq上的離散高斯分布， a$Rq，噪聲向量v$Rq。

定義2判定性RLWE問題。給定某RLWE分布（a，b），a$Rq，b=a·s+e mod q。給定v$Rq，定義判定RLWE問題，以不可忽略的概率區分（a，b）與（a，v）。

1.2Peikert誤差消除機制

回顧Peikert于文獻［16］中提出的逐位誤差消除機制。

設模數q≥2為偶數，p=2可整除q，定義Zq={-q/2，…，0，…，（q/2）-1}。定義不相交區間I0={0，1，…，q/4-1}，I1={-q/4，…，-1}，及區間E=［-q/8，q/8）∩Zq。對于v∈Zq，定義模近似函數·p：Zq→Zp，vp：=（p/q）·v」，其中·」：Zq→Zp，為v」p=|（p/q）·v|。交叉近似函數〈·〉2：Zq→Z2，〈v〉2：=（4/q）·v」 mod 2。

定義誤差消除函數rec（ω，b）：Zq×Z2→Z2

rec（ω，b）：=0ω∈Ib+E mod q1其他

設模數q為奇數，隨機函數dbl（·）：Zq→Z2q，給定v∈Zq是均勻隨機的，與v獨立的隨機項∈Z，則dbl（v）=2v-。

1.3安全模型

本文協議使用了Fischlin等人［8］提出的MSKE安全模型。MSKE模型下參與者的身份集表示為U，并且每個參與者身份U∈υ都與一個經過認證的長期公鑰pkU和私鑰skU相關聯。每一個會話作為列表ListS條目維護，由標簽為label的元組T唯一標識。

T=（label，U，V，role，kidU，kidV，stexec，sID，K，stkey，tested），其中U與V為通信雙方身份，role∈{init，resp}記錄會話所有者的角色，kid為通信參與者密鑰標識，K記錄階段i建立的會話密鑰，stexec與stkey∈{revealed，fresh}分別記錄會話狀態與階段i建立的會話密鑰的狀態，tested記錄會話密鑰測試狀態，testedi=true指示Ki已經完成測試。

在MSKE安全模型下，不允許臨時密鑰及內部值（如服務器預共享密鑰）泄露。敵手被模擬為一組隨機預言機，控制長期公鑰，可以通過以下查詢與會話進行交互：

NewTempKey（U）： 生成一個新的臨時密鑰對（tpk，sk），創建并返回一個唯一的標識符kid。

NewSession（U，V，role，kidU，kidV）： 為U創建新的會話，設置U的角色為role，密鑰標識符為kidU。V為預期通信伙伴，密鑰標識符為kidV。

send（label，m）： 發送消息m給標簽為label的會話。如果ListS不存在指定會話返回⊥，否則以U身份在消息m上運行協議，并向敵手提供響應和更新stexec。

reveal（label，i）： 表示label.Ki泄露。如果ListS不存在指定會話返回⊥，否則設置stkey，i為revealed表示敵手獲得Ki。在密鑰依賴情況下，如果ilt;j，則label.Kj與通信伙伴labelp.Kj均設置為revealed。

corrupt（U）： 敵手獲得skU。之后不允許對U所擁有的會話進行進一步的詢問。在stage-j前向保密的情況下，如果ilt;j或igt;stage，使stkey，i為revealed，指階段j前的會話密鑰及尚未建立的密鑰可能泄露。

test（label，i）： 測試會話label在i階段的會話密鑰。在安全游戲中test被給予一個統一隨機測試位btest。

對于多階段密鑰交換協議，文獻［8］根據密鑰依賴與密鑰獨立，會話密鑰前向保密階段，雙向認證與單向認證，將多階段密鑰交換安全劃分層次，如圖1所示。

2理想格上的多階段認證密鑰交換協議

2.1方案描述

設多項式環Rq=Ζq［X］/〈Xn+1〉，n為2的冪次方， χ為Rq對應的離散高斯分布。KDFex t，KDFexp：G×{0，1}*→{0，1}λ是偽隨機函數。H：{0，1}*→Rq為散列函數。

在密鑰交換協議開始之前，用戶C需要與服務器S建立首次連接。首次連接過程中，服務器會預先產生長期靜態的秘密e，skS$Rq，及對應的公鑰pkS。為用戶分配預共享公鑰pkS，和獨特的隨機參數nonceS。用戶隨機選取a$Rq，并通過安全信道將a與口令pwd提交給服務器。屆時用戶與服務器間確立預共享信息（a，pkS，pwd，nonceS）。

后續協議執行過程如圖2所示。圖中使用的info可設置如可公開的服務器配置信息及區分階段的標簽信息等。

a）客戶端C隨機選取向量ikC$χ，eC$χ，nonceC$χ，生成對應公鑰ipkC=a·ikC+eC。使用服務器預共享公鑰pkS與自身私鑰ikC，計算D1=pkS·ikC+e′C。對于D1有D1dbl（D1）∈R2q，C1←〈D1〉2q，2，W1←C12q，2∈{0，1}n。隨后計算擴展密鑰PRK1=KDFext（W1|nonceC|nonceS），與一階段會話密鑰K1=KDFexp（PRK1|info1）。

客戶端發送（C1，nonceC，nonceC，Auth1，ipkC）至服務器。服務器接收客戶端發來的消息后，計算W1=rec（2ipkU·skS，C1）與PRK1、K1。

b）服務器隨機選取向量eskS$χ，eS$χ，生成公鑰epkS=a·eskS+eS。使用上一階段收到的ipkU與eskS計算D2=ipkU·eskS+e′S，其中e′S$χ。計算D2←dbl（D2）∈R2q，C2←〈D2〉2q，2，W2←C12q，2∈{0，1}n。計算PRK2與2階段的根密鑰K2。隨后服務器使用K1對消息進行加密m=EK1（epkS，Auth2）。發送（C2，m）給用戶。

用戶收到服務器消息，解密DK1（epkS，Auth2），認證后計算W2=rec（2epkS·ikC，C2），PRK2=KDFext（K2|nonceC|nonceS）。與K2=KDFexp（PRK2|info2）。屆時，雙方可使用二階段會話密鑰K2進行后續的安全通信。

出于額外安全性考慮，在完成上述兩個階段后，雙方刪除各自生成的臨時私鑰，客戶端和服務端可以直接使用K2，或是計算新的密鑰SK=H（K2|K1|info）。

2.2方案正確性

密鑰擴展階段，用戶C與服務器S可分別計算得到D1= pkS·ikC+e′C=a·skS·ikC+e·ikC+e′C，2ipkC·skS=2·（a·ikC +eC）·skS=2·a·ikC·skS+2·eC·skS因D1=dbl（D1）=2D1－，則D1=2（a·skS·ikC+e·ikC+e′C）－。2ipkC·skS-D1=（2·a· ikC·skS+2·eC·skS）－2（a·skS·ikC+e·ikC+e′C）+，計算得2ipkC·skS－D1=2·eC·skS－2·e·ikC－2e′C+。令e*=2·eC· skS-2·e·ikC-2e′C，則2ipkC·skS－D1=2e*－。根據文獻［16］可知，當有極大概率使得‖2e*－‖lt;q/4，則服務器與用戶計算W1相等，進而可以獲得相同的PRK。同理前向保密密鑰擴展階段，有極大概率使得‖2epkS·ikC－D2‖lt;q/4，則服務器與用戶計算W2相等。因此可以獲得相同的會話密鑰。

2.3關于0-RTT支持

0-RTT指首輪交互即可使用會話密鑰來保護通信，本文協議提供了對0-RTT的支持。根據文獻［8］，客戶端在計算得到根密鑰元素W1后，通過密鑰派生函數產生需要的一階段密鑰K1，可基于依賴K1的對稱加密與服務器進行保密通信，以獲得通信效率的提高。但此時K1的安全性是缺乏保障的，它依賴于一個長期的、預共享的服務器靜態密鑰，該靜態密鑰泄露的風險影響K1的前向保密性。因此，在協議二階段服務器生成一次性的密鑰對（epk，ek），通過新一輪的協商獲得具有完美前向保密性的K2，這種0-RTT的支持，對異步消息傳遞是有價值的。

3安全性分析

根據文獻［8］，基于前文的敵手模型，從匹配安全性（ma-tching security）與多階段安全性（multi-stage security）出發證明本文方案是安全的多階段認證密鑰交換協議。

定義3匹配安全性。令KE為密鑰交換協議，當以下條件之一滿足時，稱敵手贏得了游戲GMatchKE，A，并設GMatchKE，A=1：

a）存在兩個不同label，labelp，對階段igt;0，有label.sidi=labelp.sidi≠⊥，label.stage≥i，labelp.stage≥i，且label.stexec≠rejected，labelp.stexec≠rejected，但是label.Ki≠ labelp.Ki。

b）存在兩個不同label，labelp，對于階段igt;0，有label.sidi=labelp.sidi≠⊥，label.role=init且labelp.role=resp，但label.U≠labelp.V或label.V≠labelp.U。

c）存在兩個label，labelp，對于對于階段igt;0，jgt;0，i≠j有label.sidi=labelp.sidj≠⊥。

d）存在三個不同label，labelp，labelo，對于階段igt;0，有label=labelp=labelo≠⊥。

如果對于所有PPT敵手A，下列優勢函數可以忽略不計，則認為KE是匹配安全的：

AdvMatchKE，A：=Pr［GMatchKE，A=1］

定義4多階段安全性。設KE是滿足匹配安全性的密鑰交換協議，挑戰者為每個參與者U∈υ生成長期公私鑰對并選擇隨機參數btest${0，1}，敵手獲得長期公鑰，使用預言機對會話進行查詢，并在某個節點輸出一個猜測b，當以下性質之一滿足時，稱敵手贏得了游戲GMulti-Stage，DKE，A，并設GMulti-Stage，DKE，A=1：a）b=btest；b）存在兩個label，labelp，與階段igt;0，有label.sidi=labelp.sidi，label.stkey，i=revealed且label.testedi=true，敵手已經測試并揭示了會話密鑰。

如果對于任意PPT敵手A，下列優勢函數可以忽略不計，則認為KE滿足多階段安全。

AdvMulti-Stage，DKE，A：=Pr［GMulti-Stage，DKE，A=1］－12

在后續的證明中使用AdvDRLWERq，A表示敵手A解決判定RLWE問題的優勢。設置sid1=info1，sid2=（info1，{Auth2，epk}K}。

定理1本文方案滿足雙向認證匹配安全，對于任意敵手A有AdvMatchMSKE，A≤n2s/q·2－|nonce|。其中ns是最大的會話數，|nonce|是方案中隨機參數的bit長度。

證明根據定義4分析方案的匹配安全性。

回顧匹配安全性下的四個屬性，屬性a）要求對于任一階段，具有相同會話標識符sid的會話產生相同的會話密鑰。假設雙方label.Ki≠labelp.Ki，則KDFexp具有不同的輸入，進而會有label.sidi≠labelp.sidi，因此，不可能存在具有相同會話標識符但產生不同會話密鑰的階段。

匹配安全的屬性b）要求不存在擁有相同的會話標識符，但客戶機認為它與不同的服務器通信（label.U≠labelp.V）的情況。協議中的服務器的靜態公鑰包含于在info1，作為兩個會話標識符的一部分，則可以滿足這一屬性。

屬性c）要求不同階段的會話標識符應當是不同的。sid2包含了更多的元素（Auth2，epk），滿足了這一屬性。

屬性d）描述了三個會話產生了相同會話標識符的情況。這個概率受到sid參數發送碰撞概率的限制。為了在誠實各方的會話標識符之間發生沖突，第三個會話將需要選擇與其他兩個會話中的一次相同的組元素epk、nonce等。而本文協議中nonce$χ，epk$χ，在合理安全參數下發生碰撞的概率是可以忽略的。

綜上，本文協議滿足MSKE定義下的匹配安全性。

定理2在隨機預言機下，協議是滿足雙向認證、密鑰依賴、2階段前向保密（KD-2FS-M）的多階段密鑰交換協議，對于任意敵手A有

AdvMulti-Stage，DMSKE，A≤2nS·［（nsnu+nsnt）·AdvDRLWERq，B1+

2（qh+2qhns）·2-min{|PRK1|，|PRK2|}+2ns·AdvHMSKE，B2］

其中：ns為最大會話數；nu為最大參與者數；nt為生成的最大臨時密鑰數；qh為敵手的隨機預言機查詢次數。

證明本文協議滿足匹配安全性，測試會話雙方擁有誠實的通信合作伙伴，考慮敵手A只進行單次的test查詢的情況，根據文獻［21］，本文協議階段設置下敵手的優勢將受一個系數1/2ns的限制。

對于一階段密鑰K1的保密性，可以限制敵手成功區分會話密鑰和隨機密鑰的概率邊界至（a）敵手查詢隨機預言機KDFext獲得D1密鑰參數概率，加上（b）敵手沒有查詢隨機預言機KDFext獲得D1密鑰參數仍成功區分的條件概率。這里，給出下列安全游戲以限制敵手成功區分會話密鑰K1的概率。

Game0。與初始GMulti-Stage，DKE，A一致，敵手在一階段測試匹配安全的會話，這里定義

AdvGame0MSKE，A=Adv1-Multi-Stage，ksMSKE，A

Game1。在Game1中考慮敵手對隨機預言機KDFext查詢D1密鑰元素的情況，這個概率可以綁定至敵手解決DRLWE問題的優勢。構建規約B1解決DRLWE問題，給定Rq與a$Rq，取隨機向量X$Rq，Y$χ，替代客戶端的密鑰和服務器的靜態公鑰，計算注入test查詢，如果敵手根據兩個值對應的D′區分了KDFext中的D1，就認為敵手解決DRLWE問題。此外，該概率受邊界1/（ns·nu）的限制。

AdvGame0MSKE，A≤AdvGame1MSKE，A+ns·nu·AdvRq，BDRLWE1

Game2。考慮敵手沒有查詢隨機預言機KDFext獲得D1密鑰元素仍成功區分的概率，使用隨機采樣函數取代偽隨機函數KDFext，這時PRK對敵手來說會是一個未知的隨機值，可認為PRK${0，1}λ。由于敵手不能揭示合作會話中的會話密鑰，并且其他會話標識符的密鑰是獨立分布的，所以KDFexp的隨機性將限制測試會話密鑰和隨機密鑰區分的概率。可以將敵手的優勢綁定至查詢隨機預言機的次數，且與PRK取值空間大小相關。

AdvGame1MSKE，A≤AdvGame2MSKE，A+qh·2－|PRK|

Game3。在這個游戲中，考慮敵手向服務器發送了有效消息，如果任何兩個誠實的會話在哈希函數H的任何計算中對不同的輸入計算出相同的哈希值，則令挑戰者中止游戲。構建規約B2對抗哈希函數的抗碰撞能力。

AdvGame2MSKE，A≤AdvGame3MSKE，A+nsAdvHMSKE，B2

因為pwd及noncec對敵手是未知的，Game3中敵手隨機選擇輸入，若DRLWE是困難問題，則Pr［AdvHMSKE，B2］與Pr［AdvDRLWEMSKE，B1］應是極小概率事件，Game3與Game2，Game2與Game1，Game1與Game0之間的優勢差可以忽略。

此外，敵手不能通過期望另一個具有不同sid的會話向KDFexp產生相同的（PRK，info）輸入，這可能會允許敵手Reveal會話密鑰，并將測試會話密鑰與隨機密鑰區分。在協議中會話標識符信息info完全進入密鑰派生，因此不同會話的會話密鑰是獨立分布的。至此，對于一階段會話密鑰，存在可忽略函數negl（λ），使Adv1-Multi-Stage，ksMSKE，A≤negl（λ）。

二階段密鑰K2的前向保密性的分析與一階段類似，考慮到密鑰依賴的特性，在密鑰K2建立之前，敵手不能通過Reveal（label，1）查詢測試會話獲得密鑰K1，此外測試會話參與者的腐化只發生在K2建立之后。

類似的，對于二階段密鑰K2的前向保密性，可以限制敵手成功區分會話密鑰和隨機密鑰的概率邊界至（a）敵手對隨機預言機KDFext查詢D2的概率加上（b）敵手沒有對隨機預言機KDFext查詢D2。在第二階段，前者的概率依然受敵手解決DRLWE問題的優勢限制，與一階段不同的是，敵手執行GapDH挑戰將X、Y注入到客戶端的短暫密鑰和服務器的臨時密鑰時，必須猜測服務器使用的正確的臨時密鑰，服務器的Corrupt查詢只泄露長期秘密，而不泄露臨時密鑰，因此（a）情況的概率受1/（ns·nt）影響而不是1/（ns·nu）。（b）的概率依然受PRK對于敵手的隨機性的限制。同樣地，因為K1的新鮮性和hash碰撞性，敵手打破信道認證性向誠實客戶端發送有效通信消息的優勢可以忽略。

因此，與一階段類似的這里有Adv2-Multi-Stage，kfsMSKE，A≤negl（λ）。而AdvMulti-Stage，DMSKE，A≤2nS·［Adv1-Multi-Stage，ksMSKE，A+Adv2-Multi-Stage，kfsMSKE，A］≤negl（λ），可證定理2。根據多階段安全性定義有

AdvMulti-Stage，DKE，A=Pr［GMulti-Stage，DKE，A=1］－12≤negl（λ）

基于上述分析，本文協議滿足MSKE模型下的多階段安全性，是安全的KD-2FS-M多階段密鑰交換協議。

4方案分析

使用C語言與OpenSSL庫對本文方案部分模塊進行了實現，以測試方案的性能。測試計算機使用的系統版本是Windows 10專業版， CPU型號為AMD Ryzen 7 5800X，運行內存為8 GB，gcc版本為10.2.0。對離散高斯采樣（TimeGS）、多項式乘運算（TimePM）、多項式加運算（TimePA）、交叉近似算法（TimeCRD）、近似算法（TimeRD）、誤差協調算法（TimeRec）、hash運算（TimeHash）的時間開銷進行了測試，參數的選取采用了BCNS15［17］下的設置，即n=1024，q=232－1，σ=8/2π，測試中使用的hash函數為SHA-512。分別進行了10萬次測試，記錄了每一個模塊花費的平均CPU時間（單位μs）。表1中顯示了實驗的結果。

主要的計算開銷在高斯采樣與多項式乘法運算。對方案生成根密鑰W的計算開銷進行分析。本文協議的分為兩個階段，一階段客戶端執行四次高斯采樣，兩次多項式加法與多項式乘法運算，用于生成W1的近似算法一次，hash算法一次，服務器只執行誤差協調算法與hash算法。一階段，整體計算時間約為430.7 μs。 類似，二階段計算開銷約為363.22 μs。方案整體計算開銷約為793.92 μs。

文獻［17］給出了一種基于RLWE的認證密鑰交換協議，及其在TLS安全通信中的用例，協議共執行五次高斯采樣，三次多項式加法與多項式乘法運算，用于密鑰生成的計算開銷約為571.97 μs，但是文獻［17］的認證需執行一個數字簽名與驗簽的運算，經測試私鑰長度為3 072 bit的RSA簽名算法在同樣環境的計算開銷約為1 207 μs。相比之下，本文協議開銷更小。

文獻［20］給出的基于RLWE的口令認證密鑰交換協議，方案執行六次高斯采樣，三次多項式加法與多項式乘法運算，整體計算開銷約為643.26 μs，文獻［20］整體計算開銷相比本文協議更低，但協議需要兩輪通信才可構建用于安全通信的會話密鑰，與本文協議一階段會話密鑰計算相比，文獻［20］花費更高。

之后本文從通信量、計算復雜度與部分安全特性方面與相關工作進行了比較。表2展示了幾個類似的密鑰交換協議與本文協議的對比。在通信開銷上，計算本協議兩輪交互整體的通信開銷。

文獻［8］給出了擴展QUIC形式的多階段密鑰交換協議，該方案基于ECC困難問題，與基于RLWE問題的方案相比，NIST256標準下的ECDH在通信開銷上會有優勢，但不能抵抗量子攻擊。此外，該協議只實現了響應方單向認證。本文協議在K1生成階段引入發送方認證進一步提高方案安全性，且本文協議的密鑰協商基于RLWE困難假設可以抵抗量子攻擊。

文獻［17］在TLS下的實現，完成了接收方對發送方的單向認證。與本文協議相比，文獻［17］使用的環運算次數更少，但是協議基于RSA簽名認證產生了較大的計算開銷，本文協議使用基于口令的方式實現認證，整體計算開銷更小，且文獻［17］需要兩輪通信才能進行會話密鑰保密的通信。

文獻［20］使用服務器預共享靜態密鑰，對協商過程的交換信息進行NTRU加密，同時結合用戶口令降低服務器靜態密鑰泄露帶來的安全影響。與本文協議相比，文獻［20］在整體的計算開銷上具有優勢，但協議不支持0-RTT需要至少兩輪通信才能建立第一個會話密鑰，且該協議出于安全性考慮使用時間間隔限制會話參與者的交互，沒有覆蓋現實場景中的異步需求。

此外，一個相關但不同方向上的研究為文獻［22］提出的后量子0-RTT密鑰交換協議，該協議的思想來自Günther等人［23］給出的FSOPKE協議，從密鑰封裝的角度使用可穿刺加密實現了首次前向安全的0-RTT密鑰交換協議。與本文方案相比，該方案提供了抵抗重放攻擊的0-RTT，只需一輪通信建立前向保密，但方案首輪穿透操作帶來了指數級的計算開銷，且FSOPKE本身需求建立同步時鐘，限制了在異步通信場景下的應用。

綜合上述分析，與現有的一些后量子密鑰交換方案相比，本文的多階段認證密鑰交換協議，引入少量計算開銷，實現了雙向認證、完美前向保密性與0-RTT支持，協議在MSKE模型下構建，方案結構簡單，具有一定的實用性。

5結束語

多階段密鑰交換協議在實現一些理想的構建策略時更加靈活，本文提出了一種后量子安全的多階段密鑰交換協議。方案的設計思路來自Fischlin等人給出的擴展QUIC形式的多階段密鑰交換協議，使用理想格上RLWE問題作為困難假設，結合Peikert誤差消除機制實現密鑰協商。協議實現了會話參與者的雙向認證，支持0-RTT，并通過增強的二階段會話密鑰實現前向保密。方案在MSKE模型下可證明安全，滿足KD-2FS-M安全等級。鑒于密鑰依賴與誤差消除的一些限制，本文沒有對協議支持的0-RTT的安全性進行討論，敵手獲得所有的共享信息，K1的安全性是無法保障的，需要進一步研究0-RTT安全性問題。

參考文獻：

［1］Diffie W，Hellman M E. New directions in cryptography ［J］. IEEE Trans on Information Theory，1976，22（6）： 644-654.

［2］Langley A，Chang W. QUIC crypto ［EB/OL］.（2016） ［2022-06-16］. https：//docs. google. com/document/d/1g5nIXAIkN_Y-7XJW5K45IblHd_L2f5LTaDUDwvZ5L6g/edit.

［3］Rescorla E. RFC 8446，The transport layer security（TLS） protocol version 1. 3 ［S/OL］.（2016） ［2022-06-16］. https：//tools. ietf. org/html/draft-ietf-tls-tls13-18.

［4］Perrin T，Marlinspike M. The double ratchet algorithm ［EB/OL］.（2016） ［2022-06-16］. https：//whispersystems. org/docs/specifications/doublerat chet/.

［5］Krawczyk H. HMQV： a high-performance secure Diffie-Hellman protocol ［C］// Proc of the 25th Annual International Cryptology Confe-rence. Berlin： Springer，2005： 546-566.

［6］Kudla C，Paterson K G. Modular security proofs for key agreement protocols ［C］// Proc of the 11th International Conference on Theory and Application of Cryptology and Information Security. Berlin： Springer，2005： 549-565.

［7］Lamacchia B，Lauter K，Mityagin A. Stronger security of authenticated key exchange ［C］// Proc of the 1st International Conference on Pro-vable Security. Berlin： Springer，2007： 1-16.

［8］Fischlin M，Gyunther F. Multi-stage key exchange and the case of Google’s QUIC protocol ［C］// Proc of the 21st ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press，2014： 1193-1204.

［9］Cohn-Gordon K，Cremers C，Dowling B，et al. A formal security analysis of the signal messaging protocol ［J］. Journal of Cryptology，2020，33（4）： 1914-1983.

［10］Shor P. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer ［J］. Siam Review，1999，41（2）： 303-332.

［11］Chen L，Jordan S，Liu Y，et al. Report on post-quantum cryptography，NISTIR 8105 ［R］. USA： National Institute of Standards and Technology，2016.

［12］Wang Xiaoyun，Liu Mingjie. Survey of lattice-based cryptography ［J］. Journal of Cryptologic Research，2014，1（1）： 13-27.

［13］Regev O. On lattices，learning with errors，random linear codes，and cryptography ［C］// Proc of the 37th Annual ACM Symposium on Theory of Computing. New York： ACM Press，2005： 84-93.

［14］Lyubashevsky V，Peikert C，Regev O. On ideal lattices and learning with errors over rings ［C］// Proc of the 29th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer，2010： 1-23.

［15］Ding Jintai. A simple provably secure key exchange scheme based on the learning with errors problem ［EB/OL］.（2012-12-10）. https：//eprint.iacr.org/2012/688.

［16］Peikert C. Lattice cryptography for the Internet ［C］// Proc of the 6th International Workshop on Post-Quantum Cryptography. Berlin： Springer，2014： 197-219.

［17］Bos J W，Costello C，Naehrig M，et al. Post-quantum key exchange for the TLS protocol from the ring learning with errors problem ［C］// Proc of the 36th IEEE Symposium on Security and Privacy. Piscata-way，NJ： IEEE Press，2015： 553-570.

［18］Zhang Jiang，Zhang Zhenfeng，Ding Jintai，et al. Authenticated key exchange from ideal lattices ［C］// Proc of the 34th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer，2015： 719-751.

［19］Zhao Zongqu，Ma Shaoti，Wang Yongjun，et al. Two-factor（biometric and password） authentication key exchange on lattice based on key consensus ［J］. Journal of China Universities of Posts and Telecommunications，2020，27（6）： 42-53.

［20］李子臣，謝婷，張卷美. 基于RLWE問題的后量子口令認證密鑰交換協議 ［J］. 電子學報，2021，49（2）： 260-267.（Li Zichen，Xie Ting，Zhang Juanmei. Post quantum password-based authentication key exchange protocols based on ring learning with errors problem ［J］. Acta Electronica Sinica，2021，49（2）： 260-267.）

［21］Dowling B，Fischlin M，Gyunther F，et al. A cryptographic analysis of the TLS 1. 3 handshake protocol candidates ［C］// Proc of the 22nd ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press，2015： 1197-1210.

［22］趙宗渠，馬少提，湯永利，等. 格上具有完全前向安全0輪往返時間密鑰交換協議 ［J］. 計算機應用研究，2021，38（3）： 893-898.（Zhao Zhongqu，Ma Shaoti，Tang Yongli，et al. Zero round trip time key exchange protocol with full forward secrecy on lattice ［J］. Application Research of Computers，2021，38（3）： 893-898.）

［23］Günther F，Hale B，Jager T，et al. 0-RTT key exchange with full forward secrecy ［C］// Proc of the 36th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin： Springer，2017： 519-548.

收稿日期：2022-03-04；修回日期：2022-06-27基金項目：北京市教育委員會科學研究計劃資助項目（110052971921/021）

作者簡介：陳霄（1998-），男，山東濟寧人，碩士研究生，主要研究方向為信息安全、密碼學（kros1s@qq.com）；王寶成（1979-），男，山東煙臺人，教授，碩導，博士，主要研究方向為信息安全、區塊鏈技術.