基于格的口令認(rèn)證密鑰交換協(xié)議綜述

郭淵博，尹安琪

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

0 引言

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

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

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

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

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

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

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

面對(duì)即將產(chǎn)業(yè)化的量子計(jì)算機(jī)、不斷更新的口令攻擊手段，以及國(guó)家對(duì)網(wǎng)絡(luò)和信息系統(tǒng)的高安全需求，本文對(duì)目前格上PAKE 協(xié)議的研究現(xiàn)狀進(jìn)行分析與總結(jié)，以期為相關(guān)領(lǐng)域研究人員提供更清晰的現(xiàn)狀梳理和為未來(lái)研究方向提供借鑒。

1 預(yù)備知識(shí)

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

表1 參數(shù)含義

1.1 基本概念

定義1格[41]。設(shè)矩陣A ∈Rm×n，且A的列向量線性無(wú)關(guān)。格Λ可定義為

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

定義2理想格[42]。設(shè)k為正整數(shù)，n=2k，多項(xiàng)式f(x)=x n+1 ∈Z[x]，另設(shè)多項(xiàng)式環(huán)為R=Z[x] ＜f(x)＞，環(huán)R中的元素為＜g(x)＞=，且g(x)的系數(shù)是 Zn中的元素。令I(lǐng)是環(huán)R的理想，則I中所有元素的系數(shù)構(gòu)成 Zn的一個(gè)子格，稱(chēng)對(duì)應(yīng)于理想I(I?R=Z[x] ＜f(x)＞) 的一個(gè)子格（關(guān)于Zn的子格）為f-理想格。

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

對(duì)于格Λ∈Zm，令

進(jìn)一步，定義格Λ上的離散高斯分布為

特別地，若c=0，可將DΛ,β,c簡(jiǎn)記為DΛ,β。

下文中的錯(cuò)誤概率分布采用截?cái)嚯x散高斯分布[37]，即DΛ,β的定義域?yàn)閨|x||＜βn。根據(jù)Katz 等[37]研究，在統(tǒng)計(jì)上，截?cái)喔咚狗植寂c非截?cái)喔咚狗植枷嘟?，因此下文直接稱(chēng)截?cái)喔咚狗植紴楦咚狗植?。本文用表示Zq上的某分布，取樣方法為y←DΛ,β，輸出「qy」(modq)[37]。

1.2 公鑰加密體制

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

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

1) 系統(tǒng)建立：模擬器運(yùn)行密鑰生成算法生成公私鑰對(duì)(pk,sk) ←KeyGen(1κ)，并向PPT 敵手A公開(kāi)公鑰pk。

2) 詢(xún)問(wèn)階段：A向模擬器（也可以是挑戰(zhàn)預(yù)言機(jī)）進(jìn)行多項(xiàng)式有界次的加密詢(xún)問(wèn)。

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

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

若b'=b，則稱(chēng)敵手成功，并定義此時(shí)的敵手優(yōu)勢(shì)為

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

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

1) 系統(tǒng)建立：模擬器運(yùn)行密鑰生成算法生成公私鑰對(duì)(pk,sk) ←KeyGen(1κ)，并向PPT 敵手A公開(kāi)公鑰pk。

2) 詢(xún)問(wèn)階段1：A向模擬器進(jìn)行多項(xiàng)式有界次的加/解密詢(xún)問(wèn)。

3) 挑戰(zhàn)階段：A選擇2 個(gè)等長(zhǎng)的不同明文m1,m2，并向模擬器發(fā)送 (m1,m2)；模擬器選擇隨機(jī)比特，計(jì)算挑戰(zhàn)密文c*←Enc(m*,pk)，并向A發(fā)送c*。

4) 詢(xún)問(wèn)階段2：A收到挑戰(zhàn)密文c*后，向模擬器進(jìn)行多項(xiàng)式有界次的加/解密詢(xún)問(wèn)。

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

若b'=b，則稱(chēng)敵手成功，并定義此時(shí)的敵手優(yōu)勢(shì)為

該游戲與定義8 中游戲的不同之處在于，其不能執(zhí)行“詢(xún)問(wèn)階段2”，即敵手A收到模擬器發(fā)送的挑戰(zhàn)密文c*后，不能再向模擬器進(jìn)行加/解密詢(xún)問(wèn)。

1.3 平滑投影哈希函數(shù)

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

設(shè)口令為pw，pw 的集合為D，并設(shè)公鑰加密方案的公鑰為pk；令Cpk表示與pk 對(duì)應(yīng)的 (label,C)對(duì)的集合，其中，label 表示有效標(biāo)簽，C表示與pk相對(duì)應(yīng)的密文。對(duì)于給定的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) 的集合，本文稱(chēng)三元組 (label,C,pw) 為一個(gè)單詞，用W表示。單詞 (label,C,pw) 的第一個(gè)元素為有效標(biāo)簽label，第三個(gè)元素為口令pw∈D，第二個(gè)元素為與pw 相對(duì)應(yīng)的合法密文。令L={Lpw| pw∈D}，易知L?X。

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

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

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

特別地，若錯(cuò)誤比例參數(shù)ε=0，則上述近似平滑投影哈希函數(shù)為平滑投影哈希函數(shù)。此外，上述投影密鑰的計(jì)算不依賴(lài)密文，所以上述SPHF 是非適應(yīng)性SPHF[48]。

近似SPHF 只能實(shí)現(xiàn)近似正確性，Benhamouda等[48]給出了通過(guò)糾錯(cuò)碼算法實(shí)現(xiàn)正確性放大從而得到SPHF 的通用技術(shù)，現(xiàn)介紹該技術(shù)。

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

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

鑒于存在標(biāo)準(zhǔn)技術(shù)能夠?qū)⒔破交队肮：瘮?shù)轉(zhuǎn)換為平滑投影哈希函數(shù)，為方便描述，下文中直接省略“近似”二字。

1.4 PAKE 協(xié)議安全性分析模型

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

Bellare 等[49]提出的安全性分析模型一般稱(chēng)為BR 模型，是第一個(gè)針對(duì)實(shí)例認(rèn)證和密鑰交換的標(biāo)準(zhǔn)安全性分析模型，該模型面向的是對(duì)稱(chēng)兩方協(xié)議。Bellare 等[50]基于BR 模型提出了一種針對(duì)三方協(xié)議的安全性分析模型。Blake-Wilson 等[51]進(jìn)一步提出了一種針對(duì)非對(duì)稱(chēng)協(xié)議的安全性分析模型。Mackenzie[52]和Bellare 等[26]提出了面向口令認(rèn)證的安全性分析模型，其中Bellare 等[26]提出的安全性分析模型是目前應(yīng)用最廣泛的PAKE 協(xié)議安全性分析模型之一，一般稱(chēng)為BPR 模型，下面介紹該模型。

假設(shè)PAKE 協(xié)議在公開(kāi)網(wǎng)絡(luò)上展開(kāi)，參與方包括合法用戶u∈ User、合法服務(wù)器s∈Sever 和非法敵手 A ∈ Adervasry={A,?,?,…}。假設(shè)敵手可以執(zhí)行仿冒、篡改、重放、竊聽(tīng)、中間人等攻擊[53]。另設(shè)口令空間為D，其大小為||D||。

在BPR 模型中，敵手與合法參與方（包括用戶和服務(wù)器）之間通過(guò)以下預(yù)言機(jī)進(jìn)行交互，實(shí)際上是敵手與各實(shí)例的交互。

下面，給出BPR 模型中伙伴關(guān)系、正確性、新鮮性、敵手優(yōu)勢(shì)和安全的PAKE 協(xié)議等定義。

定義13 新鮮性[26]。設(shè)用戶u與服務(wù)器s是伙伴關(guān)系，如果敵手未訪問(wèn)過(guò)Reveal(u,i)預(yù)言機(jī)，且未訪問(wèn)過(guò)Reveal(s,j) 預(yù)言機(jī)，則稱(chēng)實(shí)例是新鮮的實(shí)例。

設(shè)用戶u與服務(wù)器s是伙伴關(guān)系，并設(shè)PPT 敵手執(zhí)行Test(u,i) 預(yù)言機(jī)詢(xún)問(wèn)后給出了猜測(cè)比特b'。若敵手未訪問(wèn)過(guò)Reveal(u,i) 和Reveal(s,j) 預(yù)言機(jī)，且b'=b，稱(chēng)敵手攻擊成功。

定義14 敵手優(yōu)勢(shì)[26]。設(shè)A表示攻擊協(xié)議Π的PPT 敵手，且A可對(duì)一個(gè)實(shí)例執(zhí)行多項(xiàng)式次Execute、Send、Reveal 預(yù)言機(jī)詢(xún)問(wèn)，但能且只能對(duì)新鮮的實(shí)例執(zhí)行一次Test 預(yù)言機(jī)詢(xún)問(wèn)。用Success表示“敵手攻擊成功”事件，定義A攻擊協(xié)議Π的優(yōu)勢(shì)AdvA,Π為

設(shè)κ是安全參數(shù)，negl(κ)是關(guān)于κ的可忽略函數(shù)。理想情況下，鑒于b的隨機(jī)性，敵手攻擊成功的概率為根據(jù)式(9)，此時(shí)敵手優(yōu)勢(shì)為AdvA,Π=negl(κ)，那么敵手A在統(tǒng)計(jì)上不能區(qū)分真實(shí)的會(huì)話密鑰和與之等長(zhǎng)的隨機(jī)字符串。因此，會(huì)話密鑰是安全的，這表示PAKE協(xié)議具備語(yǔ)義安全性。

人腦的記憶能力有限，用戶傾向于選擇短的、低熵的口令，且用戶經(jīng)常在多個(gè)網(wǎng)站使用相同或相近的口令，因而用戶實(shí)際使用的口令空間較小。鑒于此，敵手總可以通過(guò)窮盡口令空間的方式來(lái)執(zhí)行在線仿冒攻擊，這導(dǎo)致PAKE 協(xié)議無(wú)法避免在線口令猜測(cè)攻擊[54]。一般情況下，若此類(lèi)攻擊是敵手的最佳攻擊方式，則稱(chēng)PAKE 協(xié)議是安全的。

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

2 基于格的兩方PAKE 協(xié)議

現(xiàn)階段，在基于格的PAKE 協(xié)議領(lǐng)域中，有關(guān)兩方PAKE 協(xié)議的成果最為豐富。兩方PAKE 協(xié)議的典型應(yīng)用場(chǎng)景如圖1 所示，參與方包括一個(gè)用戶和一個(gè)認(rèn)證服務(wù)器，其中用戶持有口令pw，認(rèn)證服務(wù)器通常存儲(chǔ)口令或口令的哈希值、與口令相關(guān)的令牌等。根據(jù)認(rèn)證服務(wù)器是否直接存儲(chǔ)口令，格上的兩方PAKE 協(xié)議大致可以分為對(duì)稱(chēng)和非對(duì)稱(chēng)兩類(lèi)。

2.1 對(duì)稱(chēng)兩方PAKE 協(xié)議

對(duì)稱(chēng)PAKE 協(xié)議在服務(wù)器端直接存儲(chǔ)了用戶口令，用于對(duì)用戶進(jìn)行認(rèn)證。在格上實(shí)現(xiàn)對(duì)稱(chēng)PAKE協(xié)議的技術(shù)路線一般為基于格上的公鑰加密算法，通過(guò)設(shè)計(jì)基于格的SPHF 實(shí)現(xiàn)格上的兩方PAKE 協(xié)議。該技術(shù)路線的技術(shù)難點(diǎn)在于構(gòu)建基于格的SPHF，這是因?yàn)長(zhǎng)WE 問(wèn)題只具備不完全加法同態(tài)性，直接基于格上困難問(wèn)題設(shè)計(jì)的SPHF 難以滿足正確性要求。為此，Katz 等[37]提出了近似SPHF 的概念，并首次給出了在格上實(shí)現(xiàn)PAKE 協(xié)議的可行方法，該方法也成為構(gòu)造格上PAKE 協(xié)議的典型方法，即利用基于格的近似SPHF 和糾錯(cuò)碼技術(shù)來(lái)實(shí)現(xiàn)（精確）SPHF 的功能，進(jìn)而實(shí)現(xiàn)基于格的PAKE協(xié)議。Katz 等[37]由此提出了第一個(gè)基于格的SPHF和PAKE 協(xié)議。該協(xié)議屬于KOY/GL 架構(gòu)[10-11]，因而是基于標(biāo)準(zhǔn)安全模型的，且該協(xié)議需要3 輪通信，在用戶和服務(wù)器端都需要基于IND-CCA2安全的公鑰加密算法。

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

借鑒基于傳統(tǒng)困難問(wèn)題的PAKE 協(xié)議的研究路線，減少通信輪（次）和弱化協(xié)議所基于的安全性假設(shè)依然是格上PAKE 協(xié)議的重要優(yōu)化方向。Zhang等[57]首先提出了一種基于格的可拆分公鑰加密算法，并基于此提出了一種基于格的非適應(yīng)性SPHF，這2 種構(gòu)造除用于實(shí)現(xiàn)PAKE 協(xié)議外，還具有相對(duì)獨(dú)立的研究?jī)r(jià)值；然后，基于Abdalla 等[58]的通用兩輪PAKE 協(xié)議架構(gòu)，Zhang 等[57]提出了一種格上的兩輪兩方PAKE 協(xié)議。

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

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

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

根據(jù)表2，格上PAKE 協(xié)議的通信輪次由Katz等[37]、Ding 等[55]方案的3 輪架構(gòu)，逐漸發(fā)展到Zhang等[57]的兩輪架構(gòu)和Benhamouda 等[48]和Li 等[61]的一輪架構(gòu)，從而得到了具有最優(yōu)通信輪次的PAKE協(xié)議。更少的通信輪（次）通常代表更低的通信開(kāi)銷(xiāo)和更低的通信風(fēng)險(xiǎn)，一直是格上PAKE 協(xié)議的重要優(yōu)化方向。但低輪（次）的PAKE 協(xié)議一般無(wú)法實(shí)現(xiàn)顯式認(rèn)證，只能實(shí)現(xiàn)隱式認(rèn)證。

表2 不同對(duì)稱(chēng)PAKE 協(xié)議的性能對(duì)比

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

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

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

2.2 非對(duì)稱(chēng)兩方PAKE 協(xié)議

對(duì)稱(chēng)PAKE 方案在服務(wù)器端存儲(chǔ)了用戶的口令，因此存儲(chǔ)的或真實(shí)的口令一旦泄露，攻擊者就可以輕易仿冒合法用戶，即此類(lèi)方案無(wú)法抵抗服務(wù)器泄露攻擊。非對(duì)稱(chēng)PAKE 協(xié)議是解決該問(wèn)題的一種有效方法，因?yàn)榇祟?lèi)協(xié)議只需要在服務(wù)器端存儲(chǔ)與口令相關(guān)的哈希值或驗(yàn)證器或者令牌，用戶不需要向服務(wù)器端發(fā)送真實(shí)的口令。

目前，在格上實(shí)現(xiàn)非對(duì)稱(chēng)PAKE 方案的常用方法是基于格上困難問(wèn)題實(shí)例化傳統(tǒng)的基于傳統(tǒng)困難問(wèn)題（一般是數(shù)論困難問(wèn)題）的非對(duì)稱(chēng)PAKE 協(xié)議?；趥鹘y(tǒng)困難問(wèn)題的典型非對(duì)稱(chēng)PAKE 方案包括SPR[7]、PAK[8]、PPK[9]方案。2017 年，Ding 等[66]利用RLWE 困難問(wèn)題，分別在格上實(shí)例化了PAK和PPK 協(xié)議[8-9]，從而得到了抗量子的非對(duì)稱(chēng)兩輪和3 輪PAKE 協(xié)議，這2 個(gè)協(xié)議在服務(wù)器端存儲(chǔ)了口令的哈希值，Ding 等[66]還在ROM 下嚴(yán)格證明了這2 個(gè)協(xié)議的安全性。同年，Gao 等[67]利用RLWE困難問(wèn)題在格上實(shí)例化了SPR 方案[7]，從而得到了一種抗量子的SPR 協(xié)議，并在通用可組合（UC,universally composable）模型下證明了方案的安全性；該協(xié)議只需要在服務(wù)器端存儲(chǔ)一個(gè)與口令相關(guān)的驗(yàn)證器，并且該驗(yàn)證器不會(huì)泄露口令的任何信息。因?yàn)椴恍枰鎯?chǔ)口令或者口令的哈希值，該方案的安全性得到了進(jìn)一步的提高。2021 年，舒琴等[68]利用Peikert 式誤差調(diào)和機(jī)制，在UC 模型下提出了一種更加高效的可證明安全的非對(duì)稱(chēng)PAKE 協(xié)議。

Li 等[54]在2020 年指出現(xiàn)有的非對(duì)稱(chēng)PAKE 方案，更確切地說(shuō)是方案中使用的口令哈希方案（PHS,password hashing scheme），要么基于ROM（使用隨機(jī)預(yù)言機(jī)的局限性見(jiàn)本文的引言部分），要么基于傳統(tǒng)困難問(wèn)題（此類(lèi)方案無(wú)法抵抗量子攻擊）。為此，利用基于格的SPHF，Li 等[54]提出了第一個(gè)基于格的PHS，并在此基礎(chǔ)上提出了一種標(biāo)準(zhǔn)模型下可證明安全的格上非對(duì)稱(chēng)PAKE 協(xié)議，該協(xié)議在服務(wù)器端存儲(chǔ)了口令的哈希值，可以有效抵抗服務(wù)器泄露攻擊和量子攻擊。

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

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

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

表3 非對(duì)稱(chēng)PAKE 協(xié)議的性能對(duì)比

Feng 等[69]、Dabra 等[70]和Ding 等[72]的匿名非對(duì)稱(chēng)PAKE 方案使用戶可以在不公開(kāi)個(gè)人身份信息的前提下進(jìn)行身份認(rèn)證和密鑰交換，因而保護(hù)了用戶的個(gè)人隱私。Feng 等[69]的方案不能抵抗信號(hào)泄露攻擊，Dabra 等[70]的方案在主密鑰重用的情況下也不能抵抗此類(lèi)攻擊，而Ding 等[72]的方案在主密鑰重用的情況下依然可以抵抗此類(lèi)攻擊。

3 基于格的三方PAKE 協(xié)議

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

圖2 三方PAKE 協(xié)議的典型應(yīng)用場(chǎng)景

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

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

表4 不同三方PAKE 協(xié)議的性能對(duì)比

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

4 基于格的分布式PAKE 協(xié)議

第2 節(jié)和第3 節(jié)中的PAKE 協(xié)議都屬于集中式認(rèn)證方案，用戶認(rèn)證信息（口令、口令的哈希值或與口令相關(guān)的令牌）都存儲(chǔ)在單個(gè)服務(wù)器上。若服務(wù)器端直接存儲(chǔ)了口令，則PAKE 協(xié)議將面臨服務(wù)器泄露攻擊的威脅；若在服務(wù)器端簡(jiǎn)單存儲(chǔ)了口令的哈希值，則協(xié)議仍面臨離線字典攻擊的威脅。雖然在服務(wù)器端存儲(chǔ)口令相關(guān)的驗(yàn)證器可以有效抵抗上述攻擊，但相關(guān)研究成果較少。而敵手執(zhí)行此類(lèi)攻擊的收益率很大，因?yàn)橹恍枞肭执嬖诎踩┒吹膯蝹€(gè)服務(wù)器，就有可能獲取數(shù)以千萬(wàn)計(jì)的口令數(shù)據(jù)。例如在2021 年，僅RockYou2021 數(shù)據(jù)集就泄露了約84 億條口令記錄。分布式認(rèn)證為解決服務(wù)器端的口令泄露問(wèn)題提供了另一種解決方案。

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

圖3 分布式PAKE 協(xié)議的典型應(yīng)用場(chǎng)景

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

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

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

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

表5 不同分布式PAKE 協(xié)議的性能對(duì)比

5 未來(lái)研究方向

根據(jù)以上分析可知，現(xiàn)階段格上PAKE 協(xié)議的研究已經(jīng)取得了一定的成果。但由于起步較晚且投入相對(duì)不足，現(xiàn)有格上PAKE 協(xié)議的相關(guān)技術(shù)還存在諸多局限性，也面臨許多挑戰(zhàn)，在未來(lái)的研究工作中，可以更多地關(guān)注以下幾個(gè)方面。

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

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

3) 基于格的口令哈希方案?？诹罟７桨甘菢?gòu)造非對(duì)稱(chēng)PAKE 方案的重要數(shù)學(xué)組件?？诹罟７桨缚梢詫?duì)口令進(jìn)行哈希處理，并將其與用戶名等其他重要信息一起存儲(chǔ)在服務(wù)器上，以便在用戶端登錄時(shí)服務(wù)器可以驗(yàn)證用戶端注冊(cè)的口令[54]。當(dāng)前的口令哈希函數(shù)要么基于經(jīng)典ROM，因而不具備QROM 下的可證明安全性；要么基于傳統(tǒng)困難問(wèn)題，無(wú)法抵抗量子攻擊。據(jù)本文所知，目前格上只存在一種標(biāo)準(zhǔn)模型下的口令哈希方案[54]，該方案在計(jì)算效率上還存在優(yōu)化空間。若要使格上PAKE 方案更加安全實(shí)用，一是可以在QROM 下構(gòu)造高效的（或在標(biāo)準(zhǔn)模型下構(gòu)造更加有效的）格上口令哈希方案，二是要使方案能夠滿足口令隱藏性、保熵性、預(yù)哈希保熵性，且能抵抗原像攻擊、二次原像攻擊等。鑒于工業(yè)領(lǐng)域中非對(duì)稱(chēng)PAKE 協(xié)議應(yīng)用的廣泛性，基于格的口令哈希方案是一個(gè)具有重要現(xiàn)實(shí)意義的研究方向。

6 結(jié)束語(yǔ)

基于格的PAKE 協(xié)議可以抵抗量子攻擊，不存在高熵密鑰的管理問(wèn)題，也不涉及用戶不可撤銷(xiāo)的隱私泄露問(wèn)題，因而所對(duì)應(yīng)的安全系統(tǒng)具有較強(qiáng)的可部署性?？诹钫J(rèn)證是應(yīng)用最廣泛的身份認(rèn)證技術(shù)之一，而基于格的PAKE 協(xié)議在后量子時(shí)代也將具有重要的意義。本文對(duì)現(xiàn)有的基于格的PAKE 協(xié)議進(jìn)行了研究綜述，主要介紹了基于格的兩方PAKE協(xié)議（包括對(duì)稱(chēng)和非對(duì)稱(chēng)PAKE 協(xié)議）、三方PAKE協(xié)議和分布式PAKE 協(xié)議，并分別對(duì)比了不同類(lèi)型PAKE 方案的安全性、通信輪（次）、認(rèn)證方式等，最后展望了基于格的PAKE 協(xié)議的未來(lái)研究方向。