尹安琪，郭淵博，汪定，曲彤洲，陳琳

（1.信息工程大學(xué)密碼工程學(xué)院，河南 鄭州 450001；2.南開(kāi)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，天津 300350；3.南開(kāi)大學(xué)天津市網(wǎng)絡(luò)與數(shù)據(jù)安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津 300350）

0 引言

口令認(rèn)證密鑰交換協(xié)議的通信方只需要使用低熵口令就可以在非安全信道上協(xié)商用于安全通信的高熵密鑰[1]。與其他認(rèn)證方式相比，口令認(rèn)證可以避免使用公鑰基礎(chǔ)設(shè)施（PKI，public key infrastructure）和涉及個(gè)人隱私的生物特征，有效提高安全系統(tǒng)在部署上的低成本性和便利性[2]。

然而，當(dāng)前口令泄露問(wèn)題日益突出，如很多網(wǎng)站都發(fā)生過(guò)客戶口令泄露問(wèn)題，且口令泄露在短期內(nèi)往往難以被發(fā)現(xiàn)，如Yahoo 時(shí)隔4 年才發(fā)現(xiàn)其泄露了30 億客戶口令，這進(jìn)一步加劇了口令泄露的危害。另一方面，基于傳統(tǒng)困難問(wèn)題（如大整數(shù)分解、離散對(duì)數(shù)）的密碼體制無(wú)法抵抗量子算法的攻擊[3]，且量子計(jì)算技術(shù)飛速發(fā)展，特別是商用量子計(jì)算機(jī)已經(jīng)誕生[4]，因此基于傳統(tǒng)困難問(wèn)題的口令認(rèn)證密鑰交換（PAKE，password-authenticated key exchange）協(xié)議在量子時(shí)代將不再安全。

格密碼體制是典型的抗量子密碼體制，因其在計(jì)算上具有高效性、在困難實(shí)例選取上實(shí)現(xiàn)了隨機(jī)性[5]且在全同態(tài)加密等領(lǐng)域應(yīng)用前景廣泛[6]，被認(rèn)為是最有潛力的后量子密碼體制之一。但格上PAKE 協(xié)議的研究起步較晚且投入較少。如目前格上的PAKE 協(xié)議多為單服務(wù)器設(shè)置，此類方案在單個(gè)服務(wù)器上存儲(chǔ)了客戶的認(rèn)證信息（如口令或口令的哈希值）；一旦該服務(wù)器泄露，認(rèn)證信息將全部泄露，即此類協(xié)議存在口令泄露問(wèn)題。

兩/多服務(wù)器認(rèn)證是抵御服務(wù)器泄露攻擊的有效方式，但基于格困難問(wèn)題的此類研究相當(dāng)有限。在基于傳統(tǒng)困難問(wèn)題的PAKE 協(xié)議領(lǐng)域，相關(guān)方案可分為基于PKI 模型[7-8]、基于身份（ID，identity）[9-10]和唯口令[11]3 種。但只有唯口令方案符合PAKE 協(xié)議的設(shè)計(jì)初衷，即允許客戶在只擁有低熵口令的前提下實(shí)現(xiàn)認(rèn)證。其他2 種方案分別需要客戶管理系統(tǒng)公鑰和服務(wù)器身份等信息。相比之下，目前在格上只存在個(gè)別基于PKI 模型的多服務(wù)器口令認(rèn)證密鑰傳輸協(xié)議[6]，且不能應(yīng)用于兩服務(wù)器場(chǎng)景。雖然在格上實(shí)例化ID2S 架構(gòu)[10]是實(shí)現(xiàn)抗量子兩服務(wù)器PAKE 協(xié)議的可行技術(shù)路線，但只能得到基于ID 的密鑰傳輸方案，即上述2 種基于格的方案雖然宣稱是PAKE 協(xié)議，但實(shí)際上都只實(shí)現(xiàn)了密鑰傳輸。

此外，格上的PAKE 協(xié)議目前還不能很好地發(fā)揮格密碼體制的線性計(jì)算優(yōu)勢(shì)。主要原因之一是現(xiàn)有方案一般需要使用簽名/驗(yàn)簽[12-13]、零知識(shí)證明[14-15]等密碼原語(yǔ)來(lái)保證安全性。而格上的多服務(wù)器PAKE 方案[6]進(jìn)一步需要使用全同態(tài)加密、秘密共享等密碼原語(yǔ)。這些昂貴密碼原語(yǔ)的使用降低了協(xié)議的執(zhí)行效率，且增加了通信與存儲(chǔ)開(kāi)銷。

據(jù)本文分析，實(shí)現(xiàn)格上高效的兩服務(wù)器PAKE協(xié)議主要有三點(diǎn)挑戰(zhàn)。1)實(shí)現(xiàn)唯口令設(shè)置和密鑰交換。一方面要使客戶不需要存儲(chǔ)和管理系統(tǒng)公鑰、服務(wù)器身份等信息，從而提高安全系統(tǒng)的可部署性；另一方面要實(shí)現(xiàn)密鑰交換而不局限于密鑰傳輸。2)避免使用簽名/驗(yàn)簽、全同態(tài)加密、零知識(shí)證明和秘密共享等昂貴密碼原語(yǔ)，并降低協(xié)議通信輪次，以精簡(jiǎn)協(xié)議架構(gòu)進(jìn)而降低協(xié)議開(kāi)銷和簡(jiǎn)化協(xié)議的安全性分析。3)設(shè)計(jì)格上IND-CCA2 安全的兩方平滑投影哈希函數(shù)（SPHF，smooth projective hash function），同時(shí)約束基于的公鑰加密（PKE，public key encryption）方案中相關(guān)參數(shù)的大小，以消除帶誤差學(xué)習(xí)（LWE，learning with error）問(wèn)題不完全同態(tài)性對(duì)SPHF 正確性的影響。該類SPHF 是構(gòu)建唯口令兩服務(wù)器PAKE 協(xié)議的有效數(shù)學(xué)工具[11，16]，但據(jù)本文所知，目前還沒(méi)有基于格的兩方SPHF，且此前即使是格上的集中式SPHF 最多也只能保證不可區(qū)分性選擇密文攻擊（IND-CCA1，indistinguishability under chosen-ciphertext attack）的安全性。

因此，本文主要研究格上IND-CCA2 安全的兩方SPHF，以解決現(xiàn)有分布式SPHF 無(wú)法抵抗量子攻擊和現(xiàn)有格上SPHF 安全性不高的問(wèn)題，并進(jìn)一步提出格上可證明安全的唯口令兩服務(wù)器PAKE 協(xié)議，以抵抗服務(wù)器泄露、量子攻擊，同時(shí)解決現(xiàn)有格上相關(guān)方案可部署性差且執(zhí)行效率低的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，與其他相關(guān)方案相比，所提出的SPHF和PAKE 協(xié)議具有較高的執(zhí)行效率。

1 相關(guān)工作

在基于傳統(tǒng)困難問(wèn)題的PAKE 協(xié)議領(lǐng)域，文獻(xiàn)[17]首次給出了唯口令的方案，這使PAKE 協(xié)議的研究不再局限于PKI 模型。早期PAKE 協(xié)議的開(kāi)銷一般很大，甚至不具備實(shí)用性。文獻(xiàn)[18]在2001 年提出了第一個(gè)高效的PAKE 架構(gòu)稱為KOY 架構(gòu)。此后，為降低協(xié)議各方面的開(kāi)銷，協(xié)議的通信輪次不斷降低，協(xié)議架構(gòu)由最初的三輪（KOY[18]/GL[19]和JG[20]/GK[21]架構(gòu)）發(fā)展到兩輪[22]以及一輪[23]架構(gòu)。但上述方案都是單服務(wù)器方案，無(wú)法抵御服務(wù)器泄露攻擊。為此，兩/多服務(wù)器PAKE 協(xié)議應(yīng)運(yùn)而生。文獻(xiàn)[9-10]雖然宣稱提出了基于身份的通用兩服務(wù)器PAKE 協(xié)議架構(gòu)，即可以基于任何兩方PAKE 方案實(shí)現(xiàn)兩服務(wù)器PAKE 協(xié)議，但實(shí)際上只能實(shí)現(xiàn)密鑰傳輸。文獻(xiàn)[11]基于秘密共享技術(shù)，提出了一種唯口令的門(mén)限PAKE 協(xié)議。但一般情況下，多服務(wù)器PAKE 協(xié)議不能用于兩服務(wù)器場(chǎng)景，反之亦然。

與基于傳統(tǒng)困難問(wèn)題的PAKE 協(xié)議相比，格上PAKE 協(xié)議的研究起步較晚。文獻(xiàn)[24]在2009 年才在KOY 架構(gòu)下提出了第一個(gè)格上的PAKE 協(xié)議。文獻(xiàn)[15]基于非交互式零知識(shí)證明技術(shù)，在2017 年給出了格上第一個(gè)兩輪PAKE 協(xié)議。直到2018 年，文獻(xiàn)[14]才提出了第一個(gè)格上的一輪PAKE 協(xié)議，但該協(xié)議需要使用零知識(shí)證明、簽名/驗(yàn)簽以及平滑性放大等技術(shù)來(lái)保證IND-CCA2 安全性，這導(dǎo)致協(xié)議的計(jì)算、存儲(chǔ)和通信開(kāi)銷較大。文獻(xiàn)[12]改進(jìn)了文獻(xiàn)[14]中的一輪PAKE協(xié)議，雖提高了效率卻仍無(wú)法避免簽名/驗(yàn)簽算法的使用。與上述基于格的單服務(wù)器PAKE 協(xié)議相比，格上兩/多服務(wù)器PAKE 協(xié)議的研究更加不足。文獻(xiàn)[6]宣稱提出了格上第一個(gè)多服務(wù)器PAKE 協(xié)議，但該方案實(shí)際上只實(shí)現(xiàn)了密鑰傳輸，并沒(méi)有實(shí)現(xiàn)密鑰交換；該方案基于PKI 模型，且需要多次使用全同態(tài)加密、簽名/驗(yàn)簽、零知識(shí)證明、秘密共享等技術(shù)來(lái)保證安全性，開(kāi)銷較大。雖然可以在格上實(shí)例化通用的ID2S 協(xié)議架構(gòu)[9-10]，但只能得到基于ID 的密鑰傳輸方案，無(wú)法實(shí)現(xiàn)唯口令認(rèn)證和密鑰交換，且該架構(gòu)無(wú)法避免簽名/驗(yàn)簽算法的使用，而基于格的簽名/驗(yàn)簽算法一般具有較大的算法參數(shù)，這會(huì)進(jìn)一步增大協(xié)議開(kāi)銷。

SPHF 是構(gòu)建PAKE 協(xié)議的有效數(shù)學(xué)工具，但SPHF 的應(yīng)用不局限于該領(lǐng)域，其在零知識(shí)證明、不經(jīng)意傳輸以及證據(jù)加密等領(lǐng)域[14]都具有相當(dāng)廣泛的應(yīng)用。SPHF（實(shí)際上是精確SPHF）的概念最初由文獻(xiàn)[25]提出。由于在格上構(gòu)建精確SPHF 比較困難[26]，文獻(xiàn)[24]首次提出了一種基于格的近似SPHF，并利用糾錯(cuò)碼技術(shù)，僅基于該近似SPHF 實(shí)現(xiàn)了格上的第一個(gè)PAKE 協(xié)議。隨后，文獻(xiàn)[14-15]基于上述技術(shù)路線，提出了基于不同格上PKE 方案的近似SPHF。文獻(xiàn)[27]提出了一種格上IND-CCA1 安全的公鑰加密算法，一般稱為MP 公鑰加密算法，由于其執(zhí)行效率較高，因此成為格PAKE 領(lǐng)域應(yīng)用最廣泛的公鑰加密算法之一。文獻(xiàn)[28]則基于MP 公鑰加密算法[28]提出了一種格上的精確SPHF，但由于算法參數(shù)較大，計(jì)算開(kāi)銷成倍提高。

SPHF 可分為適應(yīng)性[24]與非適應(yīng)性[14]兩類。在非適應(yīng)性SPHF中，投影密鑰的計(jì)算不需要使用密文，因而此類SPHF 成為構(gòu)建低輪次（特別是一輪）PAKE 協(xié)議的有效數(shù)學(xué)工具[14]。目前，格上的非適應(yīng)性SPHF 只能保證IND-CCA1或不可區(qū)分性選擇明文攻擊（IND-CPA，indistinguishability under chosen-plaintext attack）的安全性[13]。雖然個(gè)別文獻(xiàn)[14]基于帶標(biāo)簽的IND-CCA2 安全的PKE 方案設(shè)計(jì)了非適應(yīng)性SPHF，但由于要求標(biāo)簽固定，該SPHF 只能保證IND-CPA 安全。

此外，根據(jù)計(jì)算參與方的數(shù)量多少SPHF 又可以分為集中式和分布式兩類。在基于傳統(tǒng)困難問(wèn)題的SPHF 領(lǐng)域，文獻(xiàn)[11]提出了一種基于DDH 假設(shè)的分布式SPHF，但無(wú)法抵御量子攻擊，也不適用于兩方計(jì)算場(chǎng)景。文獻(xiàn)[16]實(shí)際上隱式地給出了一種兩方SPHF，也無(wú)法抵抗量子攻擊。據(jù)本文所知，目前格上還不存在分布式（包括兩方）SPHF。

本文工作借鑒文獻(xiàn)[29-30]的研究思路展開(kāi)，主要貢獻(xiàn)總結(jié)如下。

1)基于LWE 問(wèn)題的加法同態(tài)屬性，提出了一種格上IND-CCA2 安全的非適應(yīng)性兩方SPHF，支持一輪兩方PAKE 協(xié)議的構(gòu)造。由于LWE 問(wèn)題的不完全同態(tài)性會(huì)影響SPHF 的正確性，本文還約束了所基于的PKE 方案中相關(guān)參數(shù)的大小。

2)基于所提出的兩方SPHF，在被動(dòng)和主動(dòng)敵手的攻擊下，分別提出了基于格的兩服務(wù)器PAKE協(xié)議，以抵抗量子和服務(wù)器泄露攻擊。所提出的2 個(gè)協(xié)議都是唯口令設(shè)置，且不需要使用簽名/驗(yàn)簽、全同態(tài)加密、秘密共享等密碼原語(yǔ)，被動(dòng)敵手攻擊下的協(xié)議還避免了零知識(shí)證明的使用，因而提高了安全系統(tǒng)的可部署性和效率。

3)在文獻(xiàn)[13，16]中安全模型的基礎(chǔ)上，給出了一種更加現(xiàn)實(shí)的兩服務(wù)器PAKE 安全模型，該模型可以更加準(zhǔn)確地評(píng)估PAKE 協(xié)議面臨的真實(shí)風(fēng)險(xiǎn)。在所提出的更加現(xiàn)實(shí)的PAKE 安全模型下，嚴(yán)格證明了本文2 個(gè)協(xié)議的安全性。證明基于標(biāo)準(zhǔn)模型，從而避免了隨機(jī)預(yù)言機(jī)的使用。對(duì)于PAKE 協(xié)議而言，使用隨機(jī)預(yù)言機(jī)不僅存在實(shí)際應(yīng)用中被一般哈希函數(shù)替代而導(dǎo)致的安全隱患，還可能造成PAKE協(xié)議遭受離線口令猜測(cè)攻擊。

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

在介紹本文所需的預(yù)備知識(shí)之前，首先給出本文必要的符號(hào)說(shuō)明，如表1 所示。

2.1 基于格困難問(wèn)題的公鑰加密算法

格。設(shè)矩陣A∈?m×n，且A的列向量線性無(wú)關(guān)，另設(shè)格用Λ表示，并定義格Λ為

其中，A為格Λ的基矩陣，m為格Λ的維數(shù)，t為上的隨機(jī)向量。

判定性LWE（dLWEn，m，q，χ）問(wèn)題。設(shè)m，n，q，u為正整數(shù)，其中m≥n，q≥2，m=poly(n)，q≤2poly(n)。另設(shè)正整數(shù)e為dLWEn，m，q，χ問(wèn)題誤差，且e的概率分布為χ。dLWEn，m，q，χ問(wèn)題定義為區(qū)分以下分布的問(wèn)題：1)At，χ=(a，u=＜t，a＞+e)，其中

誤差分布。設(shè)w為隨機(jī)向量，并設(shè)概率密度函數(shù)ρs，c(w)=exp(-π||w-c||2/s2)。對(duì)于格Λ∈Zm×n，設(shè)。Λ上的離散高斯分布為

其中，向量c和變量s分別為離散高斯分布的中心和平滑參數(shù)。進(jìn)一步地，若將DΛ，s，c(w)的定義域約束為，那么為截?cái)嚯x散高斯分布。由于截?cái)嚯x散高斯分布和離散高斯分布在統(tǒng)計(jì)上相近[24]，為便于描述，下文直接省略截?cái)喽帧１疚闹衐LWEn，m，q，χ問(wèn)題的誤差分布χ為截?cái)嚯x散高斯分布。格上IND-CCA2 安全的公鑰加密方案。在格上，一般利用IND-CPA 安全的PKE[31（]在隨機(jī)預(yù)言機(jī)模型下）或IND-CCA1 安全的PKE（利用哈希證明、零知識(shí)證明、陷門(mén)或BCHK 等技術(shù)[32]）構(gòu)建IND-CCA2安全的PKE。因此，目前基于格上PKE[28，33]構(gòu)建的PAKE 協(xié)議需要使用額外的密碼原語(yǔ)來(lái)保證IND-CCA2 安全性。上述BCHK 技術(shù)又分為基于簽名和基于Mac 這2 種。文獻(xiàn)[32]利用基于Mac 的BCHK 技術(shù)，提出了一種IND-CCA2 安全的PKE，本文將其記作ZYF。接下來(lái)介紹該方案。

設(shè)m，n，，k，κ為正整數(shù)，其中nlbd≥3κ，。設(shè) (encoded，decoded)表示編/解碼算法，F(xiàn)(2κ)表示階為2κ的有限域，H:{0，1}*→ F(2κ)/{0}表示定義域?yàn)閧0，1}*、值域?yàn)镕(2κ)/{0}的抗碰撞哈希函數(shù)，F(xiàn)RD:F(2κ)→表示定義域?yàn)镕(2κ)、值域?yàn)槿炔罹幋a算法，KG和ENC 分別表示密鑰生成算法和加密算法，那么ZYF方案的定義如下。

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

設(shè)pw 為口令，D為口令空間，label 為有效標(biāo)簽，hash 為哈希函數(shù)，C和Cpk分別為與公鑰pk 對(duì)應(yīng)的密文和(label，C)對(duì)的集合。對(duì)給定的公鑰pk，定義集合X和Lpw（pw∈D）分別為

一般稱三元組 (label，C，pw)為單詞，用W表示。根據(jù)X和Lpw的定義可知，L={Lpw}pw∈D?X。

現(xiàn)給出近似平滑投影哈希函數(shù)的概念[24]。令Ham 表示漢明距離函數(shù)，l表示哈希密鑰長(zhǎng)度，參數(shù)ε表示錯(cuò)誤的比例；KH 表示哈希密鑰，K表示KH 的集合；KP 表示投影密鑰，S表示KP 的集合；HASH 表示定義域?yàn)閄、值域?yàn)閆q的哈希函數(shù)；H表示關(guān)于HASH 的哈希函數(shù)簇；projKG 表示投影函數(shù)，其定義域?yàn)镵，值域?yàn)镾。近似平滑投影哈希函數(shù)定義為輸入公鑰pk和集合L、X，輸出 (K，G，H={HASH(W，KH):X → {0，1}n}，S，projKG(KH):K → S)，且滿足以下條件。

2)正確性。對(duì)于?W=(label，C，pw)∈L，哈希值h=HASH(W，KH)可由投影密鑰KP 確定。即存在一個(gè)函數(shù)projHASH，稱為投影哈希函數(shù)，以投影密鑰KP、W以及W∈L的證據(jù)r為輸入，投影哈希值ph 為輸出，且滿足以下條件

3)平滑性。對(duì)于?W=(label，C，pw)∈X/L，K和KP=projKG(KH)，以下2 個(gè)分布在統(tǒng)計(jì)上不可區(qū)分

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

令{hashKG′，projKG′，HASH′，projHASH′}表示近似SPHF，其值域?yàn)閧0，1}v；令ECC 表示糾錯(cuò)碼算法，其可以糾正ε比例的錯(cuò)誤。那么以下定義的{hashKG，projKG，HASH，projHASH}是SPHF。

由于上述技術(shù)可以直接將近似SPHF 轉(zhuǎn)換為SPHF，為方便描述下文直接稱近似平滑投影哈希函數(shù)為平滑投影哈希函數(shù)。

3 兩服務(wù)器PAKE 安全模型

本節(jié)基于文獻(xiàn)[13，16，34]中的模型，給出了一種更加現(xiàn)實(shí)的兩服務(wù)器PAKE 安全模型，該模型能更加準(zhǔn)確地評(píng)估PAKE 協(xié)議面臨的真實(shí)風(fēng)險(xiǎn)。

3.1 通信模型

協(xié)議的參與方包括客戶C∈Client，服務(wù)器A，B∈Sever和敵手/攻擊者A ∈Adv。客戶持有口令pwC，服務(wù)器A和B分別存儲(chǔ)口令份額pwA，C和pwB，C，且滿足pwA，C+pwB，C(modq)=pwC。一個(gè)服務(wù)器可以處理多個(gè)客戶的認(rèn)證請(qǐng)求，本文僅以一個(gè)客戶為例，研究?jī)煞?wù)器PAKE 協(xié)議。

在協(xié)議執(zhí)行過(guò)程中存在“客戶-服務(wù)器”之間和“服務(wù)器-服務(wù)器”之間的通信。本文假設(shè)敵手完全控制“客戶-服務(wù)器”之間的通信，因此敵手可以竊聽(tīng)、注入、篡改、延遲或攔截該通信網(wǎng)絡(luò)上的任何消息。服務(wù)器的存儲(chǔ)空間相對(duì)充足，可以存儲(chǔ)長(zhǎng)期密鑰等其他信息。因此，本文假設(shè)“服務(wù)器-服務(wù)器”之間的通信是安全的，即敵手無(wú)法竊聽(tīng)或控制未泄露服務(wù)器之間的通信。實(shí)際上可通過(guò)設(shè)置可信服務(wù)器來(lái)實(shí)現(xiàn)秘密信息的分發(fā)。此外，假設(shè)服務(wù)器與客戶之間的通信是異步的；并假設(shè)服務(wù)器之間的通信是半同步的，即若客戶向服務(wù)器端發(fā)送消息，各服務(wù)器可以在規(guī)定的時(shí)間間隔內(nèi)收到該消息。

文獻(xiàn)[34]提出的BPR 模型是應(yīng)用最廣泛的PAKE 安全模型之一。在BPR 模型中，每個(gè)參與方可以與其他參與方并行地執(zhí)行多個(gè)協(xié)議。該模型用實(shí)例Π建模協(xié)議的執(zhí)行，如表示客戶C的第i個(gè)實(shí)例，表示服務(wù)器A的第jA個(gè)實(shí)例，且一個(gè)實(shí)例只能使用一次。每個(gè)實(shí)例，如，擁有一個(gè)狀態(tài)變量。其中，表示實(shí)例的會(huì)話標(biāo)識(shí)，它為接收和發(fā)送的消息統(tǒng)一編號(hào)，服務(wù)器之間的傳輸消息不計(jì)入在內(nèi)；表示客戶C認(rèn)為的其通信伙伴的標(biāo)識(shí)，在兩服務(wù)器PAKE 協(xié)議中，對(duì)于客戶C而言，是一個(gè)集合，即={A，B|A，B∈Sever}；表示會(huì)話密鑰，同理；表示標(biāo)識(shí)是否終止的二值變量，若終止，則=1，這表示完成了消息的發(fā)送和接收；表示標(biāo)識(shí)是否被接收的二值變量，若實(shí)例最終被接收，那么=1，這表示成功終止。

3.2 敵手模型

本文假設(shè)敵手最多入侵某客戶2 個(gè)認(rèn)證服務(wù)器中的一個(gè)，并稱被入侵的服務(wù)器為泄露服務(wù)器。本文將敵手分為被動(dòng)和主動(dòng)2 種類型。在被動(dòng)敵手攻擊下，泄露服務(wù)器仍按協(xié)議的定義執(zhí)行，但敵手可以獲得該服務(wù)器的內(nèi)部狀態(tài)信息。而主動(dòng)敵手可以進(jìn)一步控制泄露服務(wù)器向客戶和相關(guān)服務(wù)器發(fā)送的消息。注意，在本文的通信模型下，被動(dòng)敵手也可以控制服務(wù)器向客戶發(fā)送的消息，但2 種敵手都無(wú)法竊聽(tīng)或控制2 個(gè)未泄露服務(wù)器之間的通信。

BPR 模型[34]用預(yù)言機(jī)建模敵手能力，敵手可以通過(guò)訪問(wèn)不同的預(yù)言機(jī)來(lái)執(zhí)行不同的攻擊。在BPR模型中，敵手與客戶或服務(wù)器（實(shí)際上是客戶或服務(wù)器的實(shí)例）之間的交互是通過(guò)訪問(wèn)預(yù)言機(jī)實(shí)現(xiàn)的。根據(jù)BPR和文獻(xiàn)[16]中的安全模型，現(xiàn)將兩服務(wù)器PAKE 協(xié)議中的敵手能力建模為以下預(yù)言機(jī)。

Execute(C，i，A，B，jA，jB)。該預(yù)言機(jī)建模離線口令猜測(cè)攻擊，并根據(jù)協(xié)議的定義向敵手返回實(shí)例之間的傳輸信息。

以下Send 預(yù)言機(jī)建模在線口令猜測(cè)攻擊，敵手可以向客戶或服務(wù)器發(fā)送Send 預(yù)言機(jī)詢問(wèn)。

Send(C，i，(A，B)msg)。該預(yù)言機(jī)向?qū)嵗l(fā)送消息msg，并根據(jù)協(xié)議的定義向敵手返回傳輸消息。特別地，Send(C，i，(A，B))可以啟動(dòng)客戶C與服務(wù)器(A，B)之間的一次協(xié)議執(zhí)行。

Send(A，jA，B，C，msg)。該預(yù)言機(jī)向?qū)嵗l(fā)送消息msg，并根據(jù)協(xié)議的定義向敵手返回傳輸消息。特別地，若服務(wù)器A（或B）泄露，敵手可以額外獲得A（或B）的內(nèi)部狀態(tài)信息。

Reveal(C，A，i)。該預(yù)言機(jī)（其中A∈pidC）建模會(huì)話密鑰泄露攻擊，如會(huì)話密鑰的非法擦除等，并向敵手返回會(huì)話密鑰。

在介紹Test預(yù)言機(jī)前，首先給出新鮮性的概念。

Test(C，A，i)。該預(yù)言機(jī)（其中A∈pidC）不建模任何真實(shí)的敵手能力，只用于定義安全協(xié)議。該預(yù)言機(jī)選擇一個(gè)隨機(jī)比特b，若b=1，其向敵手返回真實(shí)會(huì)話密鑰；否則，其向敵手返回與等長(zhǎng)的隨機(jī)串。敵手只能執(zhí)行一次Test(C，A，i)詢問(wèn)，且只能執(zhí)行關(guān)于新鮮會(huì)話密鑰的Test 詢問(wèn)。

在本文中，敵手仿冒某泄露服務(wù)器向相關(guān)服務(wù)器發(fā)送消息的行為也屬于在線口令猜測(cè)攻擊。

在主動(dòng)敵手攻擊下（不妨設(shè)服務(wù)器A泄露），任何協(xié)議無(wú)法保證正確性條件2)一定成立，但本文在第5.2 節(jié)提出的協(xié)議滿足若=1，那么正確性條件3)一定成立。

敵手優(yōu)勢(shì)?？诹钫J(rèn)證密鑰交換協(xié)議應(yīng)該具備語(yǔ)義安全性，即敵手無(wú)法區(qū)分真實(shí)的會(huì)話密鑰及與之等長(zhǎng)的隨機(jī)串。設(shè)敵手進(jìn)行Test 詢問(wèn)后，給出的猜測(cè)比特為b′，若b′=b，稱敵手成功，并記該事件為Success。定義敵手優(yōu)勢(shì)Adv(A)為

理想情況下，敵手成功的概率Pr(Success)的上限為+negl(κ)（negl(κ)為可忽略函數(shù)）。此時(shí)敵手優(yōu)勢(shì)Adv(A)的上限為negl(κ)。但由于客戶實(shí)際使用的口令空間較小，敵手總能通過(guò)在線口令猜測(cè)成功，敵手優(yōu)勢(shì)的上限必定大于negl(κ)。因此，如果敵手所能執(zhí)行的最佳攻擊方式為在線口令猜測(cè)攻擊，則稱PAKE 協(xié)議是安全的。

設(shè)概率多項(xiàng)式時(shí)間（PPT，probabilistic polynomial time）的敵手執(zhí)行在線攻擊有次數(shù)上限，為Q(κ)。文獻(xiàn)[11]在定義安全PAKE 協(xié)議時(shí)，一般假設(shè)口令服從均勻分布，此時(shí)敵手優(yōu)勢(shì)的上限為negl(κ)。但文獻(xiàn)[35]的研究表明，口令服從均勻分布大大低估了敵手在線口令猜測(cè)的成功率，因而基于口令均勻分布假設(shè)的安全模型也大大低估了PAKE 協(xié)議面臨的真實(shí)風(fēng)險(xiǎn)。因此，本節(jié)假設(shè)口令分布服從CDF-Zipf 定律[35]，并重新定義了文獻(xiàn)[11]中的安全兩服務(wù)器PAKE 協(xié)議。

定義1安全兩服務(wù)器PAKE 協(xié)議。設(shè)PPT 敵手A執(zhí)行在線口令猜測(cè)攻擊的次數(shù)有上限，為Q(κ)；并設(shè)口令空間為D，且口令分布服從CDF-Zipf 定律。假設(shè)敵手最多入侵某客戶2 個(gè)認(rèn)證服務(wù)器中的一個(gè)，如果對(duì)于所有的PPT 敵手A，存在可忽略函數(shù)negl(κ)，滿足

稱協(xié)議Π 是安全的兩服務(wù)器PAKE 協(xié)議，其中，C′=0.062 239和s′=0.155 478是CDF-Zipf 分布的擬合參數(shù)[13]，κ是安全參數(shù)。

根據(jù)文獻(xiàn)[36]，基于CDF-Zipf 口令分布模型的敵手優(yōu)勢(shì)與真實(shí)敵手優(yōu)勢(shì)最多相差0.491%，且與基于口令均勻分布模型進(jìn)行口令猜測(cè)相比，基于CDF-Zipf 口令分布模型進(jìn)行口令猜測(cè)的成功率可提高2～3 倍。因此，所提出的兩服務(wù)器PAKE 安全模型更加現(xiàn)實(shí)，其精確度可比基于口令均勻分布假設(shè)的安全模型提高2～3 倍。

4 格上的IND-CCA2 安全的兩方SPHF

兩方SPHF 是構(gòu)建唯口令兩服務(wù)器PAKE 協(xié)議的有效數(shù)學(xué)工具。但據(jù)本文所知在格上還不存在此類SPHF。在基于傳統(tǒng)困難問(wèn)題的SPHF 領(lǐng)域，可以通過(guò)集中式SPHF 構(gòu)建兩方SPHF，但這在格上比較困難，原因有三。一是目前格上的SPHF 多是近似SPHF，利用此類SPHF 設(shè)計(jì)的兩方SPHF 不能滿足正確性要求。二是雖然存在個(gè)別精確SPHF[27]，但一方面該SPHF 基于強(qiáng)LWE 問(wèn)題，因而算法參數(shù)較大，執(zhí)行效率成倍降低；另一方面，鑒于強(qiáng)LWE 問(wèn)題也只具備不完全加法同態(tài)屬性，直接利用該SPHF 構(gòu)建的兩方SPHF 仍不能滿足正確性要求。三是現(xiàn)有的格上集中式SPHF 只具備IND-CPA 或IND-CCA1 安全性，基于這兩類SPHF設(shè)計(jì)的兩方SPHF 不能保證IND-CCA2 安全性。此外，為優(yōu)化協(xié)議的通信輪次，本節(jié)研究非適應(yīng)性SPHF。

本節(jié)利用LWE 問(wèn)題的加法同態(tài)屬性，基于ZYF 方案（見(jiàn)第2.1 節(jié)）研究格上IND-CCA2 安全的非適應(yīng)性兩方SPHF。

設(shè)ZYF方案的公鑰為pkZ，公共本原矩陣為Gb，哈希密鑰長(zhǎng)度為κ。記本文提出的格上非適應(yīng)性兩方SPHF為WI-2SPHF，包括哈希密鑰生成函數(shù)hashKG、投影函數(shù)proj、哈希函數(shù)HASH和投影哈希函數(shù)projHASH 這4 個(gè)子函數(shù)。WI-2SPHF (hashKG，proj，HASH，projHASH)的定義如下。

其中，RD(x)表示對(duì)x進(jìn)行四舍五入操作。最后輸出哈希值h:=(h1，…，hκ)。

由第2.2 節(jié)中SPHF 的定義可知，SPHF 要具備：1)正確性，即哈希值可通過(guò)哈希密鑰或者投影密鑰2 種途徑計(jì)算，這保證協(xié)議雙方可以協(xié)商一致的會(huì)話密鑰；2)平滑性，當(dāng)單詞W∈X/L時(shí)，即使公開(kāi)投影密鑰，敵手也不能學(xué)習(xí)到哈希值的任何信息，這保證了SPHF 的安全性。下面證明本文提出的WI-2SPHF 是平滑投影哈希函數(shù)。

定理1WI-2SPHF 是平滑投影哈希函數(shù)。

證明 詳見(jiàn)附錄1。

5 格上可證明安全的兩服務(wù)器PAKE 協(xié)議

在格上，PAKE 協(xié)議目前多為單服務(wù)器設(shè)置，無(wú)法抵抗服務(wù)器泄露攻擊。個(gè)別可抵抗該類攻擊的方案也只能實(shí)現(xiàn)密鑰傳輸，且需要基于PKI 模型[6]，因而客戶需要存儲(chǔ)和管理系統(tǒng)公鑰。雖然可以在格上實(shí)例化文獻(xiàn)[9-10]中通用的ID2S 架構(gòu)，但只能得到基于身份的兩服務(wù)器密鑰傳輸方案，導(dǎo)致客戶需要額外存儲(chǔ)和管理服務(wù)器身份等信息。因此，本節(jié)研究格上唯口令的兩服務(wù)器PAKE 協(xié)議，以提高安全系統(tǒng)的可部署性。此外，為應(yīng)對(duì)不同的性能和安全性需求，本節(jié)分別研究被動(dòng)和主動(dòng)敵手攻擊下可證明安全的兩服務(wù)器PAKE 協(xié)議。

5.1 針對(duì)被動(dòng)敵手攻擊的兩服務(wù)器PAKE 協(xié)議

假設(shè)協(xié)議在客戶C與服務(wù)器A、B之間執(zhí)行，C持有口令pwC，A和B分別存儲(chǔ)口令份額pwA，C和pwB，C，滿足pwA，C+pwB，C(modq)=pwC。

基于所提出的WI-2SPHF，本節(jié)針對(duì)被動(dòng)敵手攻擊，提出了一種格上可證明安全的唯口令兩服務(wù)器PAKE協(xié)議，記作2S-PAKE，如圖1 所示。

協(xié)議所需的密碼原語(yǔ)、初始化階段及執(zhí)行過(guò)程如下。

密碼原語(yǔ)。1)格上IND-CCA2 安全的ZYF 方案；2)基于格的兩方SPHF、WI-2SPHF。

初始化階段。協(xié)議參與方（包括客戶C與服務(wù)器A、B）在初始化階段建立公共參考序列CRS=((A，B)，Gb)，其中pkZ=(A，B)和Gb分別是ZYF 方案的公鑰和公共本原矩陣。

服務(wù)器A與服務(wù)器B的操作對(duì)稱，下文僅以服務(wù)器A為例說(shuō)明服務(wù)器端的操作。

本文通過(guò)證明定理 2，證明所提出的2S-PAKE 協(xié)議在第3 節(jié)中更現(xiàn)實(shí)的安全模型下是被動(dòng)敵手攻擊下安全的兩服務(wù)器PAKE 協(xié)議。

定理2若ZYF 方案是IND-CCA2 安全的公鑰加密方案，且WI-2SPHF 是平滑投影哈希函數(shù)，那么圖1 所示的2S-PAKE 協(xié)議在被動(dòng)敵手攻擊下是安全的兩服務(wù)器PAKE 協(xié)議。

證明協(xié)議的正確性與安全性證明見(jiàn)附錄2。

5.2 針對(duì)主動(dòng)敵手攻擊的兩服務(wù)器PAKE 協(xié)議

假設(shè)協(xié)議仍在客戶C與服務(wù)器A、B之間執(zhí)行。與針對(duì)被動(dòng)敵手攻擊的協(xié)議相比，針對(duì)主動(dòng)敵手攻擊的協(xié)議要求服務(wù)器A和B在運(yùn)行ExeAB 協(xié)議時(shí)，向?qū)Ψ阶C明其本身正確使用了口令份額，本節(jié)使用證據(jù)不可區(qū)分協(xié)議實(shí)現(xiàn)此目標(biāo)。

本節(jié)利用文獻(xiàn)[37]中的證據(jù)不可區(qū)分協(xié)議Σ，改進(jìn)圖1中的ExeAB 協(xié)議，從而得到主動(dòng)敵手攻擊下安全的兩服務(wù)器PAKE 協(xié)議。由于服務(wù)器A與服務(wù)器B的操作具有對(duì)稱性，下文僅以服務(wù)器A為例說(shuō)明ExeAB 協(xié)議的變化。

服務(wù)器A運(yùn)行Σ協(xié)議，各參數(shù)設(shè)置如式(14)所示。服務(wù)器A同時(shí)作為驗(yàn)證者，根據(jù)協(xié)議Σ對(duì)服務(wù)器B進(jìn)行驗(yàn)證，若驗(yàn)證失敗，則結(jié)束協(xié)議的執(zhí)行。

定理3若ZYF 方案是IND-CCA2 安全的公鑰加密方案，且WI-2SPHF 是平滑投影哈希函數(shù)，那么經(jīng)過(guò)上述改變后，圖1 所示的2S-PAKE協(xié)議在主動(dòng)敵手攻擊下是安全的兩服務(wù)器PAKE協(xié)議。

證明詳見(jiàn)附錄2。

6 協(xié)議仿真與性能分析

本節(jié)將所提出的WI-2SPHF和2S-PAKE 與其他相關(guān)方案進(jìn)行對(duì)比。為實(shí)現(xiàn)公平對(duì)比，所有的仿真實(shí)驗(yàn)均使用Python 語(yǔ)言，統(tǒng)一在Intel(R)Core(TM)i5-4590 平臺(tái)上進(jìn)行，該目標(biāo)平臺(tái)的操作系統(tǒng)為Windows7，頻率為3.3 GHz，內(nèi)存為8 GB。

為方便進(jìn)行各類開(kāi)銷的對(duì)比，本節(jié)假設(shè)κ=32 bit，m=800 bit，=416 bit，n=32 bit，n1=16 bit，n2=16 bit，q=4 096 bit。該參數(shù)規(guī)模符合第2.1 節(jié)中的參數(shù)設(shè)置要求。

6.1 格上平滑投影哈希函數(shù)的評(píng)估

本節(jié)首先對(duì)不同的SPHF 進(jìn)行仿真，以得到相應(yīng)的執(zhí)行時(shí)間；然后從安全級(jí)別和仿真時(shí)間等方面對(duì)比評(píng)估所提出的WI-2SPHF。表2 給出了格上不同SPHF 的對(duì)比情況。

根據(jù)表2 可知，只有WI-2SPHF 具備INDCCA2 安全性。當(dāng)哈希密鑰長(zhǎng)度大于128 bit 時(shí)，WI-2SPHF-1S 計(jì)算開(kāi)銷最小，且WI-2SPHF-2S 的計(jì)算總開(kāi)銷小于集中式的 KV.SPHF[24]和Reg.SPHF[12]；當(dāng)哈希密鑰長(zhǎng)度為 512 bit 時(shí)，WI-2SPHF-1S 的計(jì)算開(kāi)銷比目前最優(yōu)的MP.SPHF[13]提高了約27.6%。綜上，本文方案具有高效性，這得益于本文的高效投影函數(shù)和兩方SPHF 避免了額外密碼原語(yǔ)的使用。而且隨著會(huì)話密鑰長(zhǎng)度的增加，WI-2SPHF-1S 計(jì)算開(kāi)銷的增幅最小，即其密鑰長(zhǎng)度可擴(kuò)展性較好。

表2 格上不同SPHF 的對(duì)比

6.2 兩服務(wù)器PAKE 協(xié)議的評(píng)估

本節(jié)首先仿真不同的協(xié)議，以得到相應(yīng)的執(zhí)行時(shí)間、存儲(chǔ)空間占用量和通信數(shù)據(jù)量；然后從執(zhí)行效率、存儲(chǔ)與通信開(kāi)銷以及安全性等方面對(duì)比評(píng)估所提出的兩服務(wù)器PAKE 協(xié)議。

據(jù)本文所知，Roy 協(xié)議[6]是目前格上唯一可抵抗服務(wù)器泄露攻擊的相關(guān)方案。若假設(shè)Roy 協(xié)議是兩服務(wù)器設(shè)置（實(shí)際上其不能用于兩服務(wù)器場(chǎng)景），其需要調(diào)用5 次全同態(tài)加密、2 次零知識(shí)證明、8 次簽名/驗(yàn)簽、2 次加/解密算法和9 次矩陣運(yùn)算，這對(duì)于資源受限的客戶端而言，在很多應(yīng)用場(chǎng)景中甚至不具備實(shí)用性。相比之下，在客戶端，本文協(xié)議避免了全同態(tài)加密、零知識(shí)證明以及簽名/驗(yàn)簽算法的使用。在服務(wù)器端，本文協(xié)議在被動(dòng)敵手攻擊下進(jìn)一步避免了秘密共享算法的使用，但所需的加/解密次數(shù)增加；在主動(dòng)敵手攻擊下，本文協(xié)議也需要使用零知識(shí)證明，但與Roy 協(xié)議相比仍具有高效性。然而，本文協(xié)議中矩陣運(yùn)算的次數(shù)高于Roy 協(xié)議，這主要是因?yàn)楸疚膮f(xié)議是密鑰交換協(xié)議，而Roy 協(xié)議只是密鑰傳輸協(xié)議。

文獻(xiàn)[6]的主要貢獻(xiàn)是提出一種秘密共享方案，Roy 協(xié)議則是由該方案導(dǎo)出的，協(xié)議架構(gòu)復(fù)雜，需要反復(fù)使用大量額外的密碼原語(yǔ)來(lái)保證安全性，這導(dǎo)致Roy 協(xié)議的效率明顯低于本文協(xié)議，且Roy協(xié)議僅是一種密鑰傳輸方案，沒(méi)有實(shí)現(xiàn)密鑰交換。為進(jìn)一步評(píng)估2S-PAKE 協(xié)議的性能，表3 給出了典型PAKE 協(xié)議架構(gòu)下不同協(xié)議之間的性能對(duì)比情況，其中仿真時(shí)間是指協(xié)議執(zhí)行的總時(shí)間。

根據(jù)表3可知，雖然2S-PAKE是兩服務(wù)器方案，但執(zhí)行效率依然高于除Li-Wang’s PAKE1 外的所有單服務(wù)器協(xié)議。若簡(jiǎn)單地將Li-Wang’s PAKE1 協(xié)議擴(kuò)展為兩服務(wù)器協(xié)議，其在服務(wù)器與客戶端的仿真時(shí)間都為0.009 434 s，相比之下，2S-PAKE 在客戶端和服務(wù)器端的仿真時(shí)間分別降低了 25.2%和15.1%。這說(shuō)明了本文方案的高效性，這主要得益于本文高效的WI-2SPHF。

2S-PAKE 在客戶與服務(wù)器間只需一輪通信，通信輪次最優(yōu)，但其通信開(kāi)銷大于KV.PAKE 外的其他協(xié)議，這主要是兩服務(wù)器認(rèn)證所致。因Zhang-Yu’s PAKE和Li-Wang’s PAKE2 是兩輪協(xié)議，其在通信時(shí)延上的優(yōu)勢(shì)小于其他協(xié)議。Katz et al.’s PAKE 的公鑰長(zhǎng)度較大，所以2S-PAKE 的存儲(chǔ)開(kāi)銷明顯較?。怀酥?，本文協(xié)議的存儲(chǔ)開(kāi)銷在客戶端與服務(wù)器端分別是其他協(xié)議的1.12～2.05 倍和1.12～2.01 倍，這主要是兩服務(wù)器認(rèn)證和公鑰長(zhǎng)度較大所致。在實(shí)際應(yīng)用時(shí)，本文協(xié)議在各開(kāi)銷上的劣勢(shì)將會(huì)減小，因?yàn)槠渌麉f(xié)議的開(kāi)銷要在表3中數(shù)據(jù)的基礎(chǔ)上添加由簽名/驗(yàn)簽等算法引入的額外部分。在主動(dòng)敵手攻擊下，本文協(xié)議在服務(wù)器端也需要額外計(jì)入由零知識(shí)證明帶來(lái)的開(kāi)銷，因此性能有所下降。

表3 典型PAKE 協(xié)議架構(gòu)下不同協(xié)議之間的性能對(duì)比

表4 給出了不同協(xié)議的安全性及其他性能對(duì)比。其中輪數(shù)（次數(shù)）特指服務(wù)器與客戶之間的通信輪次。輪數(shù)是指通信雙方之間雙向通信的數(shù)量，次數(shù)是指單向通信的數(shù)量。若是異步通信，二者相等；若是同步通信，后者是前者的兩倍。

與Yi1[9]、Yi2[10]和Raimondo et al.’s PAKE[11]協(xié)議相比，本文協(xié)議和Roy 協(xié)議[6]基于格困難問(wèn)題，可以抵抗量子攻擊。而本文協(xié)議與Raimondo et al.’s PAKE 是唯口令的PAKE 協(xié)議，不需要基于PKI 模型（Roy 協(xié)議）與服務(wù)器身份（Yi1、Yi2 協(xié)議），因此這3 個(gè)協(xié)議所對(duì)應(yīng)的安全系統(tǒng)具有更強(qiáng)的可部署性。本文協(xié)議與Yi1、Yi2 協(xié)議是兩服務(wù)器認(rèn)證協(xié)議，不適用于多服務(wù)器場(chǎng)景，而Roy、Raimondo et al.’s PAKE 協(xié)議是閾值方案，不適用于兩服務(wù)器及服務(wù)器數(shù)目小于相應(yīng)閾值的應(yīng)用場(chǎng)景。

根據(jù)表4 可知，只有本文的2S-PAKE 協(xié)議在被動(dòng)敵手攻擊下不需要使用零知識(shí)證明與簽名/驗(yàn)簽等來(lái)保證安全性，提高了執(zhí)行效率并降低了通信與存儲(chǔ)開(kāi)銷。而在主動(dòng)敵手攻擊下，本文協(xié)議只需要在服務(wù)器端使用零知識(shí)證明。此外，Raimondo et al.’s PAKE和Roy 協(xié)議在每次執(zhí)行時(shí)都需要多次使用秘密共享算法，這進(jìn)一步增加了協(xié)議的開(kāi)銷。

表4 不同協(xié)議的安全性及其他性能對(duì)比

與密鑰傳輸協(xié)議Yi1、Yi2和Roy 協(xié)議相比，本文協(xié)議和Raimondo et al.’s PAKE 協(xié)議可實(shí)現(xiàn)密鑰交換，會(huì)話密鑰由所有參與方協(xié)商而成，而不是由一方選定。此外，Yi1 與Yi2 協(xié)議是否需要使用隨機(jī)預(yù)言機(jī)取決于所基于的密碼原語(yǔ)，而Raimondo et al.’s PAKE、Roy和本文協(xié)議基于標(biāo)準(zhǔn)模型，直接避免了隨機(jī)預(yù)言機(jī)的使用。隨機(jī)預(yù)言機(jī)的安全性本身存疑，因?yàn)樵趯?shí)際應(yīng)用中需要使用具體的哈希函數(shù)替代隨機(jī)預(yù)言機(jī)；而對(duì)于PAKE 協(xié)議而言，使用隨機(jī)預(yù)言機(jī)可能導(dǎo)致更加嚴(yán)重的安全威脅，因?yàn)檫@可能導(dǎo)致PAKE 協(xié)議遭受離線口令猜測(cè)攻擊。

綜上，本文提出的SPHF和PAKE 協(xié)議基于格困難問(wèn)題，只需要采用矩陣、向量等線性運(yùn)算，與傳統(tǒng)困難問(wèn)題（如大整數(shù)分解和離散對(duì)數(shù)問(wèn)題）采用的模冪運(yùn)算相比，在實(shí)現(xiàn)上具有高效性，且與傳統(tǒng)困難問(wèn)題相比，格困難問(wèn)題具有最壞情況與平均情況下的安全性歸約，因此本文協(xié)議在應(yīng)用時(shí)可以隨機(jī)選取困難實(shí)例，這大大提高了協(xié)議使用的便利性。此外，由于本文協(xié)議是唯口令設(shè)置，所對(duì)應(yīng)的安全系統(tǒng)不需要硬件部署，也不涉及用戶不可撤銷的隱私泄露問(wèn)題，可部署性強(qiáng)。

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

本文基于LWE 問(wèn)題的加法同態(tài)屬性，提出了一種格上IND-CCA2 安全的非適應(yīng)性兩方SPHF，可支持一輪兩方PAKE 協(xié)議的構(gòu)造。本文還約束了該SPHF 所基于的PKE中相關(guān)參數(shù)的大小，以消除LWE問(wèn)題的不完全加法同態(tài)屬性對(duì)SPHF正確性的影響，且該SPHF 具有相對(duì)獨(dú)立的研究?jī)r(jià)值，可應(yīng)用于證據(jù)加密、零知識(shí)證明和不經(jīng)意傳輸?shù)阮I(lǐng)域。

在此基礎(chǔ)上，為抵抗量子和服務(wù)器泄露攻擊，本文分別針對(duì)被動(dòng)和主動(dòng)敵手的攻擊，提出了格上可證明安全的唯口令兩服務(wù)器PAKE 協(xié)議，前者執(zhí)行效率較高，后者安全性更高。本文提出的2 個(gè)協(xié)議在客戶與服務(wù)器之間都只需要一輪通信，不需要使用簽名/驗(yàn)簽、全同態(tài)加密和秘密共享等昂貴的密碼原語(yǔ)，被動(dòng)敵手攻擊下的協(xié)議還避免了零知識(shí)證明的使用，因此大大降低了計(jì)算、通信和存儲(chǔ)開(kāi)銷。據(jù)本文所知，本文提出的SPHF和PAKE 協(xié)議分別是第一個(gè)基于格的兩方SPHF和兩服務(wù)器PAKE 協(xié)議。本文還在標(biāo)準(zhǔn)模型下，基于一種更加現(xiàn)實(shí)的兩服務(wù)器PAKE 安全模型對(duì)本文的2 個(gè)協(xié)議進(jìn)行了嚴(yán)格的安全性證明。實(shí)驗(yàn)結(jié)果表明，本文提出的兩方SPHF和兩服務(wù)器PAKE 協(xié)議執(zhí)行效率較高。此外，在基于口令的安全方案中，口令更新是一個(gè)重要問(wèn)題。但據(jù)本文所知，目前還不存在基于格的分布式口令更新方案，這也是下一步的研究方向。

附錄1 WI-2SPHF 的正確性與平滑性證明

證明1)正確性證明

根據(jù)SPHF 的定義，要證明WI-2SPHF 的正確性，需要證明對(duì)于?W=(label，(c1，c2，c3，c4)，pw)∈L，式(15)成立。

根據(jù)WI-2SPHF 的參數(shù)設(shè)置，要保證式(15)成立只要保證和滿足SPHF 的正確性要求即可。

由式(16)可知，本文提出的WI-2SPHF 具備正確性。

2)平滑性證明平滑性要求即使投影密鑰泄露，哈希值與隨機(jī)數(shù)不可區(qū)分。首先證明對(duì)于?W=(label，(c1，c2，c3，c4)，pw)∈X/L，式(17)中的2 個(gè)分布在統(tǒng)計(jì)上不可區(qū)分。

不妨設(shè)A泄露，本文構(gòu)建模擬器Sim 為敵手模擬兩方SPHF 的執(zhí)行，且要求敵手無(wú)法區(qū)分真實(shí)的和模擬的兩方SPHF。Sim 應(yīng)該在已知(hA，phA，KPA)和WI-2SPHF 的輸出(hS，phS，KPS)，但不知哈希密鑰KHA和秘密s～A的前提下，成功模擬WI-2SPHF 的執(zhí)行。

根據(jù)第4 節(jié)中WI-2SPHF 的定義，對(duì)于i∈[1，κ]，模擬器Sim 可以計(jì)算

根據(jù)式(18)可知，B在不知道A的哈希密鑰KHA與秘密的前提下，可以正確計(jì)算投影密鑰KPB、哈希值hB與投影哈希值phB。因此，本文提出的WI-2SPHF 是平滑的。

綜上，定理1 成立。

證畢。

附錄2 格上兩服務(wù)器PAKE 協(xié)議的正確性與安全性證明

證明1)正確性證明

與被動(dòng)敵手攻擊下的協(xié)議相比，主動(dòng)敵手攻擊下的協(xié)議只改變了ExeAB，二者關(guān)于會(huì)話密鑰的計(jì)算方式是等價(jià)的。因此，本文只給出被動(dòng)敵手攻擊下協(xié)議的正確性證明。

由式(20)可知圖1 所示的2S-PAKE 是正確的。

2)安全性證明

①被動(dòng)敵手攻擊下協(xié)議的安全性證明

給定敵手A攻擊協(xié)議，Sim 為A模擬協(xié)議的執(zhí)行。下文假設(shè)A泄露，并對(duì)協(xié)議進(jìn)行安全性證明。

Sim 首先執(zhí)行初始化階段，包括選擇公共參數(shù)，為客戶C選擇口令pwC，并為A和B分發(fā)口令份額pwA，C和pwB，C（滿足(pwA，C+pwB，C)modq=pwC）等。

本文通過(guò)一系列實(shí)驗(yàn)來(lái)評(píng)估A的優(yōu)勢(shì)，其中P0表示敵手與真實(shí)協(xié)議交互的實(shí)驗(yàn)。具體地，本文通過(guò)證明相鄰2 個(gè)實(shí)驗(yàn)中的A的優(yōu)勢(shì)差是可忽略的和確定A在最后一個(gè)實(shí)驗(yàn)中的優(yōu)勢(shì)上限，來(lái)確定A在P0中的優(yōu)勢(shì)上限，從而證明協(xié)議的安全性。

實(shí)驗(yàn)P1。實(shí)驗(yàn)P1與P0的區(qū)別如下。

a)若發(fā)生以下情況，敵手不會(huì)成功，且實(shí)驗(yàn)中止：msgC發(fā)生了重復(fù)；由Sim 產(chǎn)生的msgA或msgB發(fā)生了重復(fù)。

b)將未泄露服務(wù)器B計(jì)算skA′的方式替換為skA′=projHASH(K PA，WC，A)⊕HASH(WA′，KHC，A)。

注意Sim 可以執(zhí)行上述b)操作，因?yàn)榇藭r(shí)是被動(dòng)敵手攻擊，b)操作所需的參數(shù)對(duì)于Sim 而言是已知的。

上述a)中情況發(fā)生的概率是可忽略的，因而其帶來(lái)的敵手優(yōu)勢(shì)變化也是可忽略的。相對(duì)于實(shí)驗(yàn)P0，實(shí)驗(yàn)P1中skB′計(jì)算方式的改變只是概念上的，這種改變不會(huì)帶來(lái)敵手優(yōu)勢(shì)的變化，所以

實(shí)驗(yàn)P2。改變skB′的計(jì)算方式，令其為一個(gè)隨機(jī)數(shù)。利用標(biāo)準(zhǔn)的混合證明法，易知，只要ENC 加密方案是安全的，那么該變化引起的敵手優(yōu)勢(shì)變化是可忽略的，即

為方便證明，下文將msg 分為敵手產(chǎn)生的和預(yù)言機(jī)產(chǎn)生的兩類。進(jìn)一步，若敵手產(chǎn)生的msg 對(duì)應(yīng)合法的口令，那么稱該msg 為合法的，否則稱其為非法的。假設(shè)模擬器Sim 生成的公私鑰對(duì)為(pkZ，skZ)（相關(guān)定義見(jiàn)ZYF 方案），注意私鑰skZ只在安全性證明中用于驗(yàn)證敵手生成的msg是否合法，而真實(shí)協(xié)議的執(zhí)行并不需要私鑰skZ。

根據(jù)以上證明可知

實(shí)驗(yàn)P4。若msgC由敵手產(chǎn)生且非法，將skB，C替換為隨機(jī)數(shù)，同時(shí)將MB替換為隨機(jī)數(shù)關(guān)于pkA的加密值。

根據(jù)平滑投影哈希函數(shù)的平滑性，并由msgC非法（WC，A∈X/L）可知，hA←HASH(WC，A，KHA)與隨機(jī)數(shù)不可區(qū)分，所以skB，C=skB⊕skA′=hB⊕phB⊕skA′與隨機(jī)數(shù)不可區(qū)分。同理MB的輸入也與隨機(jī)數(shù)不可區(qū)分。所以

實(shí)驗(yàn)P5。若msgC由敵手產(chǎn)生且合法，那么直接宣布敵手成功；在其他情況下，敵手成功的定義不變。

該改變只會(huì)增加敵手的優(yōu)勢(shì)，所以

此時(shí)，若msgC由之前的預(yù)言機(jī)生成，那么若msgC由敵手產(chǎn)生且非法，那么skC，B與MB是隨機(jī)的；若msgC由敵手產(chǎn)生且合法，那么敵手成功，且實(shí)驗(yàn)結(jié)束；若msgC重用，那么實(shí)驗(yàn)中止。

實(shí)驗(yàn)P6。服務(wù)器B改變其生成ZYF 密文的方式，用非法口令（口令服從CDF-Zipf 分布）的份額生成ZYF 的密文。

基于ZYF 方案的IND-CPA 安全性，利用標(biāo)準(zhǔn)的混合證明法，以及本文關(guān)于語(yǔ)義安全的定義易知

實(shí)驗(yàn)P7。若msgA與msgB由敵手產(chǎn)生且非法，改變msgA與msgB的回復(fù)方式，將skC，B和skC，A設(shè)置為隨機(jī)數(shù)。

由于msgA非法，即WA∈X/L且WA′∈X/L，根據(jù)SPHF 的平滑性可知，HASH(WA，KHC，A)和HASH(WA′，KHC，A)都與隨機(jī)數(shù)不可區(qū)分。根據(jù)圖 1 進(jìn)一步可知，在客戶端哈希值hC，A←HASH(WA，KHC，A)⊕HASH(WB′，KHC，B)與哈希值hC，B←HASH(WB，KHC，B)⊕HASH(WA′，KHC，A)都與隨機(jī)數(shù)不可區(qū)分，那么skC，A=hC，A⊕phC，A和skC，B=hC，B⊕phC，B也都與隨機(jī)數(shù)不可區(qū)分。所以

實(shí)驗(yàn)P8。若msgA與msgB由敵手產(chǎn)生且合法，那么直接宣布敵手成功，并中止實(shí)驗(yàn)；在其他情況下，敵手成功的定義保持不變。該改變只能增加敵手的優(yōu)勢(shì)，所以

實(shí)驗(yàn)P9。改變服務(wù)器B關(guān)于ZYF 密文的生成方式，將其替換為非法口令（服從CDF-Zipf 分布）份額的加密值。

根據(jù)ZYF 方案的IND-CCA2 安全性，并利用標(biāo)準(zhǔn)的混合證明方法，易知

在實(shí)驗(yàn)P9中，除了敵手A知曉其生成了合法的msgC（msgA/msgB）的情況外，協(xié)議的執(zhí)行與合法口令（口令份額）無(wú)關(guān)，這說(shuō)明即使敵手A獲得了泄露服務(wù)器A的口令份額pwA，C（pwA，C是Zq上的隨機(jī)數(shù)），pwC也是安全的。此外，模擬器Sim 除了檢驗(yàn)msgC（msgA/msgB）的合法性外，也不會(huì)使用合法的口令（口令份額）。

令GuessPW 表示以下事件：敵手發(fā)送了有效的msgC（msgA/msgB）。本文假設(shè)口令分布服從CDF-Zipf 定律，那么

這說(shuō)明，雖然對(duì)于一個(gè)msgC而言，敵手A可以進(jìn)行兩次在線口令猜測(cè)，但是敵手A要想成功，需要將有效的msgC同時(shí)發(fā)送給服務(wù)器A和服務(wù)器B，因此敵手A實(shí)際上執(zhí)行了兩次在線口令猜測(cè)。

若敵手A未能猜測(cè)出合法的口令，那么敵手A只能通過(guò)Test 預(yù)言機(jī)詢問(wèn)獲得成功，所以有

進(jìn)一步，根據(jù)b的隨機(jī)性可知，敵手A在實(shí)驗(yàn)P9中的優(yōu)勢(shì)滿足

那么，根據(jù)實(shí)驗(yàn)P1～實(shí)驗(yàn)P9的證明過(guò)程可知

綜上，定理2 成立。

②主動(dòng)敵手攻擊下協(xié)議的安全性證明

給定敵手A攻擊協(xié)議，假設(shè)模擬器Sim 為敵手A模擬協(xié)議的執(zhí)行。同樣假設(shè)服務(wù)器A泄露，并對(duì)主動(dòng)攻擊下的協(xié)議進(jìn)行安全性證明（假設(shè)服務(wù)器B泄露的相關(guān)證明與此相同）。下文只給出與被動(dòng)敵手攻擊下安全性證明的不同之處。

綜上，定理3 成立。

證畢。