基于格的口令認證密鑰交換協議綜述

郭淵博，尹安琪

（信息工程大學密碼工程學院，河南 鄭州 450001）

0 引言

近年來，隨著5G、云計算、大數據、人工智能等高新技術的飛速發展，人類的生產、生活也隨之走向深度的信息化、網絡化、數字化。以“互聯網+”為代表的新型發展生態已經成為中國社會發展的國家戰略。由于網絡的開放性與匿名性，互聯網在快速發展的同時衍生出一系列安全問題，網絡空間儼然成為國家安全的“第五疆域”[1]。身份認證系統是保護網絡資產過程中的重要關卡[2]，一旦其被攻破，信息和網絡系統內所有的安全措施就形同虛設。

基于口令的身份認證技術不存在高熵密鑰的管理問題（相比基于智能卡、U 盾等信任物體的身份認證技術），也不存在用戶不可撤銷的隱私泄露問題（相比基于指紋、虹膜等生物特征的身份認證技術），大大降低了認證成本并提高了安全系統的便利性、可部署性。然而，與已經得到深入、廣泛研究的高熵密鑰認證方式相比，口令認證的研究成果相對不足。口令認證作為一種低熵認證方式，雖然曾一度因各種安全問題被認為必將消亡，但迄今為止，口令認證仍是各類信息和安全系統中應用最廣泛的認證方式之一[3]。由于口令認證是唯一不需要進行硬件部署的認證方式，在絕大多數網站中，基于口令的單因子認證方式無可替代[1]。口令在工業界的作用也從未淡化，其不僅在傳統的電子政務、商務、醫療等領域繼續發揮優勢，還向交通、稅務、廣電、能源、水利、教育等多領域不斷擴展[4]。雖然在2022 年MIT Technology Review“十大突破性技術”[5]掀起了“終結口令”的第二次浪潮，但汪定等[3]指出，無口令身份認證方案目前存在兼容性差、可擴展性低、成本高和存在隱私泄露等風險，并特別指出無口令身份認證方案降低了用戶對身份的控制權，因而有52%的被調研者并不接受此類認證方式。因此，學術界與工業界逐漸達成共識，在可預見的未來，口令認證仍將是用戶最主要的認證方式之一[1,3,5]。

現階段，口令認證的相關研究聚焦于設計適用于不同應用場景的安全高效的口令認證密鑰交換（PAKE,password-authenticated key exchange）協議。PAKE 協議使只擁有低熵口令的協議參與方可以通過非安全信道協商用于安全通信的高熵密鑰[6]。研究者先后提出了一系列PAKE協議[7-13]，如著名的SPR[7]、PAK[8]、PPK[9]、KOY/GL[10-11]和JG/GK[12-13]協議。上述協議都是基于傳統困難問題的，但早在1994年Shor[14]就證明，存在量子算法可以解密所有基于大整數分解和離散對數等傳統困難問題的密碼體制，且量子計算機已經誕生[15]，其量產化和實用化只是時間問題。因此，基于傳統困難問題的PAKE 協議在即將到來的量子時代不再安全。

為應對量子攻擊，密碼學者已經開始研究各種抗量子的密碼體制。除了以AES、DES 為代表的對稱密碼體制外，現有公認的抗量子密碼體制主要分為以下5 類[16-17]：基于哈希的密碼體制[18]、基于編碼的密碼體制[19]、基于多變量的密碼體制[20]、基于格的密碼體制[21]和基于同源的密碼體制。其中，基于格的密碼體制有以下優勢：1) 密碼學者已經完成了格上部分困難問題從平均情況下困難性到最壞情況下困難性的歸約證明[22]，因此基于格的密碼體制不僅具有更強的安全性，在應用時還支持困難實例的隨機選取[22]，這也是此類密碼體制獨有的優勢；2) 格上的運算一般具有線性漸近復雜度，如小整數的矩陣、向量的模乘/加，而基于大整數分解和離散對數等傳統困難問題的密碼體制需要采用大整數模/冪運算，相比之下基于格的密碼體制具有高效性[23]；3) 格上有多個困難問題被證明是困難的，如最短向量問題、最近向量問題、帶差錯學習問題，這為基于格的密碼體制提供了豐富的密碼學原語選擇空間[16]；4) 鑒于格的簡單代數和幾何結構，基于格的密碼體制易于通過軟件和硬件實現[17]；5) 密碼服務功能較強，在全同態加密[24]、多線性映射[17]等領域具有廣泛的應用前景。因此，基于格的密碼體制被美國國家標準與技術研究院（NIST）認為是后量子時代最具潛力的密碼體制[25]。

然而與已經得到深入研究和廣泛應用的傳統密碼體制相比，關于基于格的密碼體制的研究相對不足。當前，相關研究主要集中在加密算法和哈希函數2 個領域，關于格上PAKE 協議的研究成果還比較有限。隨著網絡和信息技術的快速發展，各方對大規模通信系統中的身份認證方案需求日盛；但格上相關方案的執行效率較低，且個別方案僅實現了密鑰傳輸。另一方面，目前格上PAKE 協議的研究多關注如何提高單服務器PAKE 協議的執行效率，此類協議固有的缺陷是無法抵抗服務器泄露攻擊；個別可抵抗此類攻擊的相關方案未實現唯口令設置和密鑰交換，且執行效率低下。

早期協議的研究基于啟發式安全性分析，這使協議研究一度陷入了“提出→攻擊→改進→攻擊→改進”的循環[1]。因此，可證明安全逐漸成為必要的設計目標。PAKE 協議的研究也由此衍生出以下2 條技術路線：在隨機預言機模型（ROM,random oracle model）/理想加密模型下最優化PAKE 協議的性能[9,26-28]；在標準模型下，構造可證明安全的高效PAKE 協議[13,29-33]。相比之下，在標準模型下構造可證明安全的PAKE 協議更加困難。然而，在格PAKE 方案中使用隨機預言機比在一般方案中更具安全威脅，主要原因如下：隨機預言機的安全性本身存疑，因為在實際應用時隨機預言機需要被具體的哈希函數替代[34]；對于PAKE 協議而言，使用隨機預言機還可能導致協議遭受離線口令猜測攻擊；格密碼方案的主要應用場景為后量子時代，量子敵手可以在量子態下訪問隨機預言機[35-36]，這進一步加劇了使用隨機預言機對格PAKE 方案的安全威脅。因此，在格PAKE 方案中應盡量避免使用隨機預言機，這使基于格假設構造PAKE 方案更加困難。

PAKE 協議還面臨離線口令猜測攻擊、在線口令猜測攻擊和各種新型口令猜測攻擊的威脅[1]。抵抗離線口令猜測一直是PAKE 協議設計的重點與難點[13,37]。當前，口令泄露問題日益突出，2021 年，僅RockYou2021 數據集就泄露了84 億條口令記錄。知名網站（Yahoo、163 等）、社交媒體（Facebook、Instagram 等）、營銷服務提供商（大眾、奧迪等）也都發生過口令泄露問題，且口令泄露在短期內往往難以被發現，這進一步加劇了口令泄露的危害。相比之下，在進行在線口令猜測時，攻擊者無法獲得用戶口令文件且可執行的猜測次數受限，因此無論是在學術界還是在工業界，在線口令猜測一直被認為是易于防范的[11,36]。但事實是用戶與服務器商正遭受日趨嚴重的在線口令猜測攻擊，如Github 和iCloud 等知名網站都遭受過此類攻擊。Wang 等[38]指出當前的研究大大低估了真實攻擊者在線口令猜測的成功率。此外，隨著網絡化、信息化、數字化的深入發展，還涌現出一系列新型口令猜測攻擊，如基于深度學習的[39]和基于云計算增強的[40]口令猜測攻擊等，這導致PAKE 協議面臨更加嚴重甚至未知的安全威脅。另一方面，《“十四五”規劃和2035 年遠景目標綱要》明確指出要“加強重要領域數據資源、重要網絡和信息系統安全保障”；并且，在2019 年10 月26 日、2021 年6 月10 日和2021 年8 月20 日，《中華人民共和國密碼法》《中華人民共和國數據安全法》和《中華人民共和國個人信息保護法》相繼問世，這對口令認證技術提出了更高的要求。

面對即將產業化的量子計算機、不斷更新的口令攻擊手段，以及國家對網絡和信息系統的高安全需求，本文對目前格上PAKE 協議的研究現狀進行分析與總結，以期為相關領域研究人員提供更清晰的現狀梳理和為未來研究方向提供借鑒。

1 預備知識

本節主要介紹后續綜述所需的基本概念、格上困難問題、公鑰加密體制、平滑投影哈希函數（SPHF,smooth projective hash function）和PAKE協議的安全性分析模型等。首先給出必要的符號說明，其中，矩陣和向量分別用加粗的大寫和小寫字母表示，如矩陣A和向量a；其他參數含義如表1 所示。

表1 參數含義

1.1 基本概念

定義1格[41]。設矩陣A ∈Rm×n，且A的列向量線性無關。格Λ可定義為

其中，A為格Λ的基矩陣，m為格Λ的維數，n為格Λ的秩。

定義2理想格[42]。設k為正整數，n=2k，多項式f(x)=x n+1 ∈Z[x]，另設多項式環為R=Z[x] ＜f(x)＞，環R中的元素為＜g(x)＞=，且g(x)的系數是 Zn中的元素。令I是環R的理想，則I中所有元素的系數構成 Zn的一個子格，稱對應于理想I(I?R=Z[x] ＜f(x)＞) 的一個子格（關于Zn的子格）為f-理想格。

定義3離散高斯分布[43]。設高斯函數的中心為c，平滑參數為β（β∈ (0,1)）。另設隨機向量x和高斯權重函數的表達式為

對于格Λ∈Zm，令

進一步，定義格Λ上的離散高斯分布為

特別地，若c=0，可將DΛ,β,c簡記為DΛ,β。

下文中的錯誤概率分布采用截斷離散高斯分布[37]，即DΛ,β的定義域為||x||＜βn。根據Katz 等[37]研究，在統計上，截斷高斯分布與非截斷高斯分布相近，因此下文直接稱截斷高斯分布為高斯分布。本文用表示Zq上的某分布，取樣方法為y←DΛ,β，輸出「qy」(modq)[37]。

1.2 公鑰加密體制

公鑰加密是指由對應的唯一一對密鑰（包括公鑰和私鑰）組成的加密算法。根據安全性的不同，公鑰加密方案可分為選擇明文攻擊下不可區分性（IND-CPA,indistinguishability under chosen-plaintext attack）安全和選擇密文攻擊下不可區分性（IND-CCA,indistinguishability under chosen-ciphertext attack）安全2 種；進一步，根據攻擊者或敵手能力的不同，IND-CCA 安全又可以分為IND-CCA1 安全（在現有文獻中，有時直接稱IND-CCA1 安全為IND-CCA 安全）和適應性選擇密文攻擊下不可區分（IND-CCA2,indistinguishability under adaptive chosen-ciphertext attack）安全。下面，正式給出3 種安全性的定義。

定義7IND-CPA 安全。設κ為安全參數，對于給定的公鑰加密方案PKE=(KeyGen,Enc,Dec)，令任意概率多項式時間（PPT,probabilistic polynomial time）敵手A執行以下游戲（也稱為實驗）。

1) 系統建立：模擬器運行密鑰生成算法生成公私鑰對(pk,sk) ←KeyGen(1κ)，并向PPT 敵手A公開公鑰pk。

2) 詢問階段：A向模擬器（也可以是挑戰預言機）進行多項式有界次的加密詢問。

3) 挑戰階段：A選擇2 個等長的不同明文m1,m2，并向模擬器發送 (m1,m2)；模擬器選擇隨機比特b←r{0,1}，計算挑戰密文c*←Enc(m*,pk)，并向A發送c*。

4) 猜測階段：A收到挑戰密文c*后，輸出關于b的猜測比特b'。

若b'=b，則稱敵手成功，并定義此時的敵手優勢為

若對于任意PPT 敵手A，存在可忽略函數negl(κ)，使此時的敵手優勢滿足(κ) ≤negl(κ)，則稱公鑰加密 方 案PKE=(KeyGen,Enc,Dec)是IND-CPA 安全的。

定義8IND-CCA2 安全。設κ為安全參數，對于給定的公鑰加密方案PKE=(KeyGen,Enc,Dec)，令任意PPT 敵手A執行以下游戲。

1) 系統建立：模擬器運行密鑰生成算法生成公私鑰對(pk,sk) ←KeyGen(1κ)，并向PPT 敵手A公開公鑰pk。

2) 詢問階段1：A向模擬器進行多項式有界次的加/解密詢問。

3) 挑戰階段：A選擇2 個等長的不同明文m1,m2，并向模擬器發送 (m1,m2)；模擬器選擇隨機比特，計算挑戰密文c*←Enc(m*,pk)，并向A發送c*。

4) 詢問階段2：A收到挑戰密文c*后，向模擬器進行多項式有界次的加/解密詢問。

5) 猜測階段：A輸出b的猜測比特b' 。

若b'=b，則稱敵手成功，并定義此時的敵手優勢為

該游戲與定義8 中游戲的不同之處在于，其不能執行“詢問階段2”，即敵手A收到模擬器發送的挑戰密文c*后，不能再向模擬器進行加/解密詢問。

1.3 平滑投影哈希函數

平滑投影哈希函數是一種隱式證明方法，其概念最初由Cramer 等[47]提出，Katz 等[33]根據格上的應用需求對此概念進行修改，本文采用Katz 等[33]的相關定義。平滑投影哈希函數是構造唯口令PAKE 協議的有效數學工具，除此之外，還可應用于零知識證明、不經意傳輸和證據加密等領域。

設口令為pw，pw 的集合為D，并設公鑰加密方案的公鑰為pk；令Cpk表示與pk 對應的 (label,C)對的集合，其中，label 表示有效標簽，C表示與pk相對應的密文。對于給定的pk，定義集合X和{Lpw}pw∈D如下[32]：1)X:={(label,C,pw) | (label,C)∈Cpk&&pw∈D}；2)Lpw:={(label,Enc(pk,pw ||label),pw∈D)}。

X表示三元組 (label,C,pw) 的集合，本文稱三元組 (label,C,pw) 為一個單詞，用W表示。單詞 (label,C,pw) 的第一個元素為有效標簽label，第三個元素為口令pw∈D，第二個元素為與pw 相對應的合法密文。令L={Lpw| pw∈D}，易知L?X。

下面，正式給出SPHF 的定義。

定義10 平滑投影哈希函數[37]。首先給出近似SPHF 的概念。設漢明距離函數為Ham，錯誤比例參數為ε；哈希密鑰為kh，哈希密鑰的長度為l，kh的集合為KH；投影密鑰為kp,kp 的集合為KP；Hash 表示哈希函數，其定義域為X、值域為Zq；由Hash 構成的哈希函數簇用? 表示；ProjKG 表示定義域為KH、值域為KP 的投影函數。近似SPHF可由取樣算法定義，輸入公鑰pk 和集合L、X，輸出 (K,G,?={Hash(W,kh):X→ {0,1}n},S,ProjKG(kh): KH → KP)，且滿足以下條件。

2) 近似正確性：對于 ?W=（label,C,pw）∈L，哈希值有2 種計算方式，其一為通過哈希密鑰計算h=Hash（W,kh）；其二為由投影密鑰kp 計算，即存在投影哈希函數ProjHash，滿足以投影密鑰kp、單詞W和W∈L的證據r為輸入，以投影哈希值ph為輸出，且哈希值h與投影哈希值ph 近似相等，即式(7)成立。

特別地，若錯誤比例參數ε=0，則上述近似平滑投影哈希函數為平滑投影哈希函數。此外，上述投影密鑰的計算不依賴密文，所以上述SPHF 是非適應性SPHF[48]。

近似SPHF 只能實現近似正確性，Benhamouda等[48]給出了通過糾錯碼算法實現正確性放大從而得到SPHF 的通用技術，現介紹該技術。

令{HashKG',ProjKG',Hash',ProjHash'}為近似SPHF，值域為{0,1}v；令ECC 為糾錯碼算法，可以糾正ε比例的錯誤，那么下述{HashKG,ProjKG,Hash,ProjHash}是SPHF。

kh ←HashKG(params)：輸入 kh1←hashKG'(params)，在ECC 的定義域中隨機選擇kh2，輸出哈希密鑰 kh :=(kh1,kh2)。

鑒于存在標準技術能夠將近似平滑投影哈希函數轉換為平滑投影哈希函數，為方便描述，下文中直接省略“近似”二字。

1.4 PAKE 協議安全性分析模型

早期協議，也包括PAKE 協議的安全性分析是啟發式的，這使協議的研究陷入了“設計→攻擊→改進→攻擊→改進”的循環，因此可證明安全逐漸成為安全協議設計的必要目標。協議的安全性分析模型一般定義了協議的通信環境（包括敵手模型）和安全性等，是研究可證明安全方案的重要基礎，下面介紹PAKE 協議的安全性分析模型。

Bellare 等[49]提出的安全性分析模型一般稱為BR 模型，是第一個針對實例認證和密鑰交換的標準安全性分析模型，該模型面向的是對稱兩方協議。Bellare 等[50]基于BR 模型提出了一種針對三方協議的安全性分析模型。Blake-Wilson 等[51]進一步提出了一種針對非對稱協議的安全性分析模型。Mackenzie[52]和Bellare 等[26]提出了面向口令認證的安全性分析模型，其中Bellare 等[26]提出的安全性分析模型是目前應用最廣泛的PAKE 協議安全性分析模型之一，一般稱為BPR 模型，下面介紹該模型。

假設PAKE 協議在公開網絡上展開，參與方包括合法用戶u∈ User、合法服務器s∈Sever 和非法敵手 A ∈ Adervasry={A,?,?,…}。假設敵手可以執行仿冒、篡改、重放、竊聽、中間人等攻擊[53]。另設口令空間為D，其大小為||D||。

在BPR 模型中，敵手與合法參與方（包括用戶和服務器）之間通過以下預言機進行交互，實際上是敵手與各實例的交互。

下面，給出BPR 模型中伙伴關系、正確性、新鮮性、敵手優勢和安全的PAKE 協議等定義。

定義13 新鮮性[26]。設用戶u與服務器s是伙伴關系，如果敵手未訪問過Reveal(u,i)預言機，且未訪問過Reveal(s,j) 預言機，則稱實例是新鮮的實例。

設用戶u與服務器s是伙伴關系，并設PPT 敵手執行Test(u,i) 預言機詢問后給出了猜測比特b'。若敵手未訪問過Reveal(u,i) 和Reveal(s,j) 預言機，且b'=b，稱敵手攻擊成功。

定義14 敵手優勢[26]。設A表示攻擊協議Π的PPT 敵手，且A可對一個實例執行多項式次Execute、Send、Reveal 預言機詢問，但能且只能對新鮮的實例執行一次Test 預言機詢問。用Success表示“敵手攻擊成功”事件，定義A攻擊協議Π的優勢AdvA,Π為

設κ是安全參數，negl(κ)是關于κ的可忽略函數。理想情況下，鑒于b的隨機性，敵手攻擊成功的概率為根據式(9)，此時敵手優勢為AdvA,Π=negl(κ)，那么敵手A在統計上不能區分真實的會話密鑰和與之等長的隨機字符串。因此，會話密鑰是安全的，這表示PAKE協議具備語義安全性。

人腦的記憶能力有限，用戶傾向于選擇短的、低熵的口令，且用戶經常在多個網站使用相同或相近的口令，因而用戶實際使用的口令空間較小。鑒于此，敵手總可以通過窮盡口令空間的方式來執行在線仿冒攻擊，這導致PAKE 協議無法避免在線口令猜測攻擊[54]。一般情況下，若此類攻擊是敵手的最佳攻擊方式，則稱PAKE 協議是安全的。

定義15 安全的PAKE 協議。設κ是安全參數，A是攻擊協議Π的PPT 敵手，且A執行在線口令猜測攻擊的次數上限為Q(κ)。假設口令服從均勻分布，并用D表示口令空間，||D|| 表示口令空間的大小，則稱協議Π是安全的口令認證密鑰交換協議，如果對于所有的PPT 敵手A，存在可忽略函數negl(κ)滿足

2 基于格的兩方PAKE 協議

現階段，在基于格的PAKE 協議領域中，有關兩方PAKE 協議的成果最為豐富。兩方PAKE 協議的典型應用場景如圖1 所示，參與方包括一個用戶和一個認證服務器，其中用戶持有口令pw，認證服務器通常存儲口令或口令的哈希值、與口令相關的令牌等。根據認證服務器是否直接存儲口令，格上的兩方PAKE 協議大致可以分為對稱和非對稱兩類。

2.1 對稱兩方PAKE 協議

對稱PAKE 協議在服務器端直接存儲了用戶口令，用于對用戶進行認證。在格上實現對稱PAKE協議的技術路線一般為基于格上的公鑰加密算法，通過設計基于格的SPHF 實現格上的兩方PAKE 協議。該技術路線的技術難點在于構建基于格的SPHF，這是因為LWE 問題只具備不完全加法同態性，直接基于格上困難問題設計的SPHF 難以滿足正確性要求。為此，Katz 等[37]提出了近似SPHF 的概念，并首次給出了在格上實現PAKE 協議的可行方法，該方法也成為構造格上PAKE 協議的典型方法，即利用基于格的近似SPHF 和糾錯碼技術來實現（精確）SPHF 的功能，進而實現基于格的PAKE協議。Katz 等[37]由此提出了第一個基于格的SPHF和PAKE 協議。該協議屬于KOY/GL 架構[10-11]，因而是基于標準安全模型的，且該協議需要3 輪通信，在用戶和服務器端都需要基于IND-CCA2安全的公鑰加密算法。

JG/GK 架構[12-13]是另一種基于標準安全模型的典型PAKE 架構，Ding 等[55]基于此架構提出了一種基于格的高效PAKE 協議。與Katz 等[37]的方案相比，該協議雖然也需要3 輪通信，但實現了互認證，且該協議在用戶端只需要使用IND-CPA 安全的公鑰加密算法，因而提高了用戶端的性能。Ding 等[55]曾斷言，除非基于格的精確SPHF 更加高效，否則沒有必要設計格上的精確SPHF。但在2013 年，Blazy等[56]提出了一種基于LWE問題的精確SPHF，并指出精確SPHF 至少可以使PAKE 協議的構造不局限于BPR 安全模型。

借鑒基于傳統困難問題的PAKE 協議的研究路線，減少通信輪（次）和弱化協議所基于的安全性假設依然是格上PAKE 協議的重要優化方向。Zhang等[57]首先提出了一種基于格的可拆分公鑰加密算法，并基于此提出了一種基于格的非適應性SPHF，這2 種構造除用于實現PAKE 協議外，還具有相對獨立的研究價值；然后，基于Abdalla 等[58]的通用兩輪PAKE 協議架構，Zhang 等[57]提出了一種格上的兩輪兩方PAKE 協議。

Zhang 等[57]提出的兩輪PAKE 架構需要使用模擬健全的非交互式零知識（SS-NIZK,simulation sound non-interactive zero-knowledge）證明，因此執行效率較低，且目前格上還不存在標準模型下的SS-NIZK 證明，所以Zhang 等[57]的方案需要使用隨機預言機。為此，同樣基于Abdalla 等[58]提出的通用兩輪PAKE 協議架構，Benhamouda 等[48]提出了格上第一個不需要使用SS-NIZK 證明的兩輪PAKE 協議。在此基礎上，Li 等[44]利用MP 公鑰加密方案[59]，也提出了一種格上不需要SS-NIZK 證明的兩輪PAKE 協議。該協議通過弱化協議所基于的安全性假設（在服務器端只需要基于IND-CPA 的安全模型）降低了協議各方面的開銷。尹安琪等[60]通過安全性證明指出，Li 等[44]將兩輪PAKE 協議中服務器端的安全性假設降低到IND-CPA 不能保證協議的安全性；進一步，尹安琪等[60]提出了一種格上可證明安全的兩輪PAKE 協議，該協議將用戶端的安全性假設降低到IND-CPA，因而降低了用戶端的計算、通信和存儲等開銷。2018 年，基于Katz 等[33]提出的通用一輪PAKE 架構，Benhamouda 等[48]利用其所提出的格上非適應性SPHF 和SS-NIZK 證明，給出了一種格上一輪PAKE 協議的實現方法，但沒有給出具體的協議構造和安全性證明。Li 等[61]基于Benhamouda 等[48]的研究，利用MP 公鑰加密方案[59]，提出了一種高效的基于格的SPHF，并基于此實現了一種格上的一輪PAKE 協議。

為進一步提高格上PAKE 協議的執行效率和降低協議各方面的開銷，格上PAKE 協議的另一個研究方向是基于理想格上困難問題（如RLWE 困難問題）來構造協議。2010 年，Lyubashevsky 等[62]提出了LWE 問題在環上的變體——RLWE 問題，并將RLWE 問題的困難性規約到理想格上困難問題中最難實例的求解。基于RLWE 問題的加密體制很好地克服了基于歐氏格的密碼體制（如LWE 問題）中密鑰過長的缺陷，并且可以通過快速傅里葉變換算法提高加/解密運算速度。2013 年，葉茂等[63]提出了一種基于理想格的SPHF，該SPHF 可用于構造基于理想格的PAKE 協議，從而提高協議性能。2019 年，利用Lyubashevsky 等[62]基于RLWE 問題的公鑰加密方案，Karbasi 等[64]提出了一種基于理想格的SPHF，并基于此在KOY/GL 架構[10,65]下構造了一種基于理想格的PAKE 協議。

表2 對比了不同對稱PAKE 協議的性能對比。通信輪（次）特指服務器與用戶之間的通信輪（次），其中，通信輪數是指通信雙方之間雙向通信的數量，次數是指通信雙方之間單向通信的數量；如果是異步通信，通信輪數等于通信次數，如果是同步通信，通信次數是通信輪數的2 倍。

根據表2，格上PAKE 協議的通信輪次由Katz等[37]、Ding 等[55]方案的3 輪架構，逐漸發展到Zhang等[57]的兩輪架構和Benhamouda 等[48]和Li 等[61]的一輪架構，從而得到了具有最優通信輪次的PAKE協議。更少的通信輪（次）通常代表更低的通信開銷和更低的通信風險，一直是格上PAKE 協議的重要優化方向。但低輪（次）的PAKE 協議一般無法實現顯式認證，只能實現隱式認證。

表2 不同對稱PAKE 協議的性能對比

目前，格上的部分低輪（次）PAKE 協議（包括Zhang 等[57]的兩輪方案和Benhamouda 等[48]、Li等[61]一輪PAKE 方案等）需要使用SS-NIZK 證明來保證安全性，這種昂貴的密碼學原語會影響協議性能的提升，且在格上還不存在基于標準模型的SS-NIZK 證明，因此上述方案都需要使用隨機預言機。隨機預言機不僅在實際應用時需要被具體的哈希函數替代，還可能導致PAKE 遭受離線口令猜測攻擊。此外，量子敵手可以在量子態下訪問隨機預言機，這進一步增大了在格密碼方案中使用隨機預言機的危害。因此，應該在格PAKE 方案中盡量避免隨機預言機的使用。Li 等[44]和尹安琪等[60]提出的格上兩輪PAKE方案同時避免了SS-NIZK證明和隨機預言機的使用，相比之下安全性更高。

Katz 等[37]的3 輪PAKE 方案、Zhang 等[57]的兩輪PAKE 方案，以及Benhamouda 等[48]和Li 等[61]的一輪PAKE 方案在用戶端和服務器端都需要基于IND-CCA2 的安全模型。而Ding 等[55]的3 輪PAKE協議、尹安琪等[60]的兩輪PAKE 協議將格上PAKE協議在用戶端所基于的安全模型降低到IND-CPA安全，Li 等[44]的兩輪PAKE 方案將服務器端所基于的安全模型降低到IND-CPA 安全。一般而言，基于更強安全模型的密碼方案具有更大的計算和存儲等開銷，因此，與一輪PAKE協議相比，兩輪PAKE協議雖然在通信輪（次）上存在劣勢，但在用戶端或服務器端可能具有更高的執行效率。

此外，與基于傳統困難問題的PAKE 方案（如Katz 等[33]的方案）相比，基于格的PAKE 方案不僅可以抵抗量子攻擊，且格上的基本運算是小整數的模乘/加等具有線性漸近復雜度的運算，比傳統PAKE 方案的大整數模冪運算更加高效。

2.2 非對稱兩方PAKE 協議

對稱PAKE 方案在服務器端存儲了用戶的口令，因此存儲的或真實的口令一旦泄露，攻擊者就可以輕易仿冒合法用戶，即此類方案無法抵抗服務器泄露攻擊。非對稱PAKE 協議是解決該問題的一種有效方法，因為此類協議只需要在服務器端存儲與口令相關的哈希值或驗證器或者令牌，用戶不需要向服務器端發送真實的口令。

目前，在格上實現非對稱PAKE 方案的常用方法是基于格上困難問題實例化傳統的基于傳統困難問題（一般是數論困難問題）的非對稱PAKE 協議。基于傳統困難問題的典型非對稱PAKE 方案包括SPR[7]、PAK[8]、PPK[9]方案。2017 年，Ding 等[66]利用RLWE 困難問題，分別在格上實例化了PAK和PPK 協議[8-9]，從而得到了抗量子的非對稱兩輪和3 輪PAKE 協議，這2 個協議在服務器端存儲了口令的哈希值，Ding 等[66]還在ROM 下嚴格證明了這2 個協議的安全性。同年，Gao 等[67]利用RLWE困難問題在格上實例化了SPR 方案[7]，從而得到了一種抗量子的SPR 協議，并在通用可組合（UC,universally composable）模型下證明了方案的安全性；該協議只需要在服務器端存儲一個與口令相關的驗證器，并且該驗證器不會泄露口令的任何信息。因為不需要存儲口令或者口令的哈希值，該方案的安全性得到了進一步的提高。2021 年，舒琴等[68]利用Peikert 式誤差調和機制，在UC 模型下提出了一種更加高效的可證明安全的非對稱PAKE 協議。

Li 等[54]在2020 年指出現有的非對稱PAKE 方案，更確切地說是方案中使用的口令哈希方案（PHS,password hashing scheme），要么基于ROM（使用隨機預言機的局限性見本文的引言部分），要么基于傳統困難問題（此類方案無法抵抗量子攻擊）。為此，利用基于格的SPHF，Li 等[54]提出了第一個基于格的PHS，并在此基礎上提出了一種標準模型下可證明安全的格上非對稱PAKE 協議，該協議在服務器端存儲了口令的哈希值，可以有效抵抗服務器泄露攻擊和量子攻擊。

現階段，隨著人們對個人隱私關注度的提高，很多用戶期望在認證過程中隱藏個人身份信息，匿名認證方案可以有效解決該問題。2018 年，Feng等[69]基于RLWE 問題的困難性，首次提出了一種基于理想格的匿名PAKE 方案，使用戶可以在不泄露身份信息的前提下，通過公開信道實現身份認證和密鑰交換。Dabra 等[70]在2021 年指出Feng等[69]的方案簡單、高效，但不能抵抗信號泄露攻擊、電子欺騙攻擊、操縱攻擊和用戶匿名違規攻擊。基于Ding 等[71]零知識認證協議中直接公鑰驗證的思想，Dabra 等[70]提出了一種新的基于理想格的匿名PAKE 方案，并在ROR（real-or-random）模型下證明了方案的安全性。該方案可以抵抗信號泄露等攻擊，包括注冊、登錄、認證和口令更新等功能。進一步，Ding 等[72]在2022 年指出，若主密鑰重用，Dabra 等[70]的方案仍不能抵抗信號泄露攻擊；為此，他們利用Ding 等[73]隨機密鑰交換方案中的思想，對Dabra 等[70]的方案進行改進，從而提出了一種改進的理想格上的匿名PAKE方案，并對方案進行了嚴格的安全性證明，該協議保證了方案在主密鑰重用的情況下也能抵抗信號泄露攻擊。

上述方案雖然可以解決服務器端的口令泄露問題，但無法解決用戶端的口令泄露問題。多因子認證方式是解決該問題的有效方法，若將口令身份認證看作網絡和信息系統的第一道防線，那么為解決該問題可以引入第二道防線——智能卡。2021年，基于RLWE 問題的困難性，Wang 等[74]利用Alkim 等[75]提出的格上密鑰交換方案首次提出了抗量子的雙因子PAKE 方案，該方案在隨機預言機模型下是可證明安全的，且可以抵抗密鑰重用攻擊、信號泄露攻擊和密鑰不匹配攻擊。

表3 對比了非對稱PAKE 協議的性能。為對用戶進行認證，Ding 等[66]、Gao 等[67]和Li 等[54]的方案在服務器端存儲了口令的哈希值，而舒琴等[68]、Feng等[69]、Dabra 等[70]和Ding 等[71]的方案在服務器端存儲了與口令相關的驗證器。相比之下，存儲口令的驗證器要比存儲與口令直接相關的哈希值更加安全。Li等[54]雖然也在服務器端存儲了口令的哈希值，但他們提出了一種抗量子的口令哈希方案，因而提高了相應PAKE 方案的安全性。Ding 等[66]、Gao 等[67]、Feng等[69]方案的安全性是基于隨機預言機的，本文在引言部分總結了使用隨機預言機的潛在安全威脅。Dabra等[70]、Ding 等[71]方案的安全性是基于ROR 模型[76]的，Li等[54]的非對稱PAKE方案是基于標準模型的，這兩類方案都避免了隨機預言機的使用，因而具有更高的實際安全性。舒琴等[68]的方案在UC 模型下仍然是可證明安全的，在表3 所有的協議中具有更強的實際安全性。

表3 非對稱PAKE 協議的性能對比

Feng 等[69]、Dabra 等[70]和Ding 等[72]的匿名非對稱PAKE 方案使用戶可以在不公開個人身份信息的前提下進行身份認證和密鑰交換，因而保護了用戶的個人隱私。Feng 等[69]的方案不能抵抗信號泄露攻擊，Dabra 等[70]的方案在主密鑰重用的情況下也不能抵抗此類攻擊，而Ding 等[72]的方案在主密鑰重用的情況下依然可以抵抗此類攻擊。

3 基于格的三方PAKE 協議

現有格上PAKE 協議的研究多針對兩方應用場景，即多為兩方PAKE 協議，此類方案要求每2 個用戶之間都共享一個口令或口令的哈希值等，因而此類方案在應用于大規模通信系統時會產生繁重的口令管理問題。另一方面，由于人腦的記憶能力有限，用戶可記憶口令的數目和長度有限，一般只能記憶5～7 個短的、低熵的口令[77]；若用戶重復使用口令，將帶來嚴重的安全問題。三方PAKE 協議可以有效解決該問題，其典型應用場景如圖2 所示。協議參與方包括多個用戶和一個認證服務器，每個用戶只需要與可信服務器共享一個口令，就可以實現與任意其他用戶（同樣與可信服務器共享口令的用戶）進行身份認證與密鑰交換。

圖2 三方PAKE 協議的典型應用場景

雖然存在通用的技術可以基于兩方PAKE 協議實現三方PAKE 協議[76]，但會增加協議的通信輪（次），并且無法實現顯式認證。因此，2013 年，葉茂等[78]在JG/GK[12-13]架構的基礎上，首次提出了基于格的三方PAKE 協議，并在標準模型下證明了協議的安全性。在該協議中，每個用戶與認證服務器都可以在3 輪通信內實現顯式的互認證。2017 年，Xu 等[79]基于RLWE 問題，在隨機預言機模型下提出了一種格上的三方PAKE 協議，并嚴格證明了協議的安全性；與葉茂等[78]的方案相比，該方案的通信輪（次）更多，但由于環上的運算可以通過快速傅里葉變換加速，因此該協議具有較小的計算開銷。2018 年，于金霞等[80]利用Zhang 等[57]提出的兩方PAKE 協議，提出了一種基于格的兩輪三方PAKE 協議，但未克服Zhang 等[57]的方案僅能實現密鑰傳輸的問題，因而用戶所得到的會話密鑰僅由服務器端確定。2020 年，Yin 等[81]提出了一種新的可證明安全的格上兩輪三方PAKE協議，與于金霞等[80]的方案相比，該方案中的會話密鑰由認證雙方同時確定，提高了密鑰協商的公平性。

表4 對比了不同三方PAKE 協議的性能。與Abdalla 等[76]的傳統三方PAKE 協議相比，葉茂等[78]、于金霞等[80]、Xu 等[79]、Yin 等[81]的三方PAKE 協議基于格上困難問題，因而可以抵抗量子攻擊。此外，Abdalla 等[74]的方案使用了大整數模/冪運算，與格上的小整數向量/矩陣運算相比，開銷較大。Xu 等[79]的三方PAKE 協議不僅需要用戶與可信服務器進行通信，還需要用戶之間進行通信。相比之下，葉茂等[78]、于金霞等[80]和Yin 等[81]的三方PAKE 協議只需要用戶與服務器進行通信就能實現身份認證與密鑰交換。Xu 等[79]方案的優勢是基于RLWE 困難問題，因而計算開銷較小。

表4 不同三方PAKE 協議的性能對比

葉茂等[78]的格上三方PAKE 協議需要3 輪通信，而于金霞等[80]和Yin等[81]的方案需要兩輪通信，減小了協議的通信輪（次）。葉茂等[78]的三方PAKE協議的通信數據類型包括密文、投影密鑰和消息認證碼，該方案的密文復雜度、投影密鑰大于尹安琪等[80]的三方3PAKE 協議。Yin 等[81]、于金霞等[80]的三方PAKE 協議采用了可拆分公鑰加密體制，只需要驗證密文有效性就可以實現IND-CCA2 安全，避免了消息認證碼的傳輸。Xu 等[79]、于金霞等[80]、Yin 等[81]的格上三方PAKE 協議需要使用隨機預言機，但葉茂等[78]的方案是基于標準模型的，因而安全性更高。

4 基于格的分布式PAKE 協議

第2 節和第3 節中的PAKE 協議都屬于集中式認證方案，用戶認證信息（口令、口令的哈希值或與口令相關的令牌）都存儲在單個服務器上。若服務器端直接存儲了口令，則PAKE 協議將面臨服務器泄露攻擊的威脅；若在服務器端簡單存儲了口令的哈希值，則協議仍面臨離線字典攻擊的威脅。雖然在服務器端存儲口令相關的驗證器可以有效抵抗上述攻擊，但相關研究成果較少。而敵手執行此類攻擊的收益率很大，因為只需入侵存在安全漏洞的單個服務器，就有可能獲取數以千萬計的口令數據。例如在2021 年，僅RockYou2021 數據集就泄露了約84 億條口令記錄。分布式認證為解決服務器端的口令泄露問題提供了另一種解決方案。

圖3 給出了分布式PAKE 協議的典型應用場景。在一次協議執行中，參與方包括一個用戶和多個認證服務器，其中用戶持有口令，多個認證服務器分布式地存儲口令份額，對用戶的認證由多個認證服務器協同完成。敵手入侵部分服務器（一般是小于相應閾值數目的服務器）不會泄露口令的任何信息。目前，格上的相關研究成果較少。2021 年，Roy 等[82]通過基于格的秘密共享算法提出了格上首個分布式PAKE 協議，該協議可以抵抗量子攻擊和服務器攻擊，但需要基于PKI 模型，因而用戶在進行認證時除了需要記憶口令外，還需要存儲和管理系統公鑰。Roy 等[82]的方案是一種閾值方案，不適用于服務器數目小于閾值的應用場景，如兩服務器場景。2022 年，尹安琪等[83]通過設計基于格的兩方SPHF，提出了格上第一個兩服務器PAKE 協議，并在標準模型下證明了該協議的安全性。該協議實現了唯口令設置，因而可部署性更強。目前，格上分布式PAKE 協議的相關研究成果較少，對比之下，基于傳統困難問題的分布式PAKE 方案的研究成果相對豐富，大致可分為以下3 類：基于PKI 模型的方案[84-85]、基于身份的方案[86-87]和唯口令的方案[88]。在這3 類方案中，除用戶口令外，前兩類分別需要用戶管理系統公鑰和服務器身份等信息。

圖3 分布式PAKE 協議的典型應用場景

表5 給出了不同分布式PAKE 協議的性能對比。Katz 等[89]、Yi 等[86]、Yi 等[87]和Raimondo 等[88]的協議基于DDH 困難問題，無法抵抗量子攻擊；Roy等[82]和尹安琪等[83]的分布式PAKE 協議基于格上的困難問題，可以抵抗量子攻擊。

Roy 等[82]的方案基于PKI 模型，用戶在進行身份認證時除了需要記憶口令外，還需要存儲服務器公鑰；Yi 等[86]、Yi 等[87]的方案是基于身份的，用戶需要額外管理服務器身份信息；Katz 等[89]、Raimondo 等[88]和尹安琪等[83]的方案實現了唯口令設置，因而其所對應的安全系統具有更強的可部署性。Katz 等[89]、Yi 等[86]、Yi 等[87]和尹安琪等[83]的分布式PAKE 方案是兩服務器認證方案，適合兩服務器應用場景；Roy 等[82]、Raimondo 等[88]的分布式PAKE 協議是閾值方案，適合服務器數目大于相應閾值的應用場景。

在用戶和服務器之間，Katz 等[89]、Yi 等[87]、Roy等[82]和Raimondo 等[88]的方案需要3 輪通信，Yi 等[86]的方案需要兩輪通信，尹安琪等[83]的協議則需要一輪通信，通信輪（次）不斷得到優化。多服務器PAKE方案[82,88]與兩服務器PAKE 方案[83,86-87,89]相比一般需要更多的通信次數。在表5 的協議中，除尹安琪等[83]的協議外，其他協議[82,86-89]都需要使用簽名/驗簽算法。Raimondo 等[88]、Katz 等[89]和尹安琪等[83]（被動敵手攻擊下的協議）避免了零知識證明的使用，有助于協議性能的提升；此外，Roy 等[82]的方案在每次協議執行時都需要多次使用秘密共享算法，這會進一步增加協議各方案的開銷。

在Roy 等[82]的協議中，會話密鑰由一方確定，相比之下，表5 中其他方案[83,86-88]的會話密鑰由認證雙方同時確定，這使密鑰協商更加公平。Yi 等[86]、Yi 等[87]的協議是否需要使用隨機預言機取決于其所基于的密碼學原語，而Katz 等[89]、Raimondo 等[88]、Roy 等[82]和尹安琪等[83]的協議基于標準模型，所以直接避免了隨機預言機的使用。

表5 不同分布式PAKE 協議的性能對比

5 未來研究方向

根據以上分析可知，現階段格上PAKE 協議的研究已經取得了一定的成果。但由于起步較晚且投入相對不足，現有格上PAKE 協議的相關技術還存在諸多局限性，也面臨許多挑戰，在未來的研究工作中，可以更多地關注以下幾個方面。

1) 量子隨機預言機模型（QROM,quantum random oracle model）中可證明安全的PAKE 方案。基于ROM 的方案與基于標準模型的方案相比，一般在執行效率上具有顯著優勢。目前，基于ROM的格PAKE 方案在證明安全性時一般只考慮具有經典訪問權限的敵手，但相關方案被實例化后，隨機預言機也被具體的哈希函數替代，此時量子敵手可以對隨機預言機進行量子訪問——QROM。因此，在經典ROM 下，可證明安全的方案可能無法抵抗量子敵手的攻擊。而在QROM 下證明方案的安全性比在經典模型下更加困難：一是量子敵手可以在輸入的指數疊加上查詢隨機預言機，因而在QROM下高效地模擬隨機預言機是困難的；二是經典的ROM 證明技術對QROM 來說并不適用。因此，為保證格PAKE 方案的高效性和安全性，需要研究在QROM 中可證明安全的相關方案。

2) 基于格的分布式口令更新方案。在基于口令的相關方案中，口令更新是一個基本的且重要的問題。但據本文所知，目前還不存在基于格的分布式口令更新方案。Raimondo 等[88]提出了基于傳統困難問題的門限口令更新方案，但無法抵抗量子攻擊。雖然存在基于格的成熟技術可以解決單服務器設置下的口令更新問題[69]，但利用此類方案無法直接構造分布式口令更新方案：一是在兩服務器或多服務器設置下，存在2 個或多個服務器身份（在單服務器設置下，只有一個服務器身份）；二是此時服務器并不存儲用戶口令的哈希值。因此，設計實現基于格的分布式口令更新方案，從而使基于口令的分布式身份認證系統的功能更加完善，是一個有挑戰且有重要現實意義的研究方向。

3) 基于格的口令哈希方案。口令哈希方案是構造非對稱PAKE 方案的重要數學組件。口令哈希方案可以對口令進行哈希處理，并將其與用戶名等其他重要信息一起存儲在服務器上，以便在用戶端登錄時服務器可以驗證用戶端注冊的口令[54]。當前的口令哈希函數要么基于經典ROM，因而不具備QROM 下的可證明安全性；要么基于傳統困難問題，無法抵抗量子攻擊。據本文所知，目前格上只存在一種標準模型下的口令哈希方案[54]，該方案在計算效率上還存在優化空間。若要使格上PAKE 方案更加安全實用，一是可以在QROM 下構造高效的（或在標準模型下構造更加有效的）格上口令哈希方案，二是要使方案能夠滿足口令隱藏性、保熵性、預哈希保熵性，且能抵抗原像攻擊、二次原像攻擊等。鑒于工業領域中非對稱PAKE 協議應用的廣泛性，基于格的口令哈希方案是一個具有重要現實意義的研究方向。

6 結束語

基于格的PAKE 協議可以抵抗量子攻擊，不存在高熵密鑰的管理問題，也不涉及用戶不可撤銷的隱私泄露問題，因而所對應的安全系統具有較強的可部署性。口令認證是應用最廣泛的身份認證技術之一，而基于格的PAKE 協議在后量子時代也將具有重要的意義。本文對現有的基于格的PAKE 協議進行了研究綜述，主要介紹了基于格的兩方PAKE協議（包括對稱和非對稱PAKE 協議）、三方PAKE協議和分布式PAKE 協議，并分別對比了不同類型PAKE 方案的安全性、通信輪（次）、認證方式等，最后展望了基于格的PAKE 協議的未來研究方向。