可證明安全的抗量子兩服務器口令認證密鑰交換協(xié)議

2022-03-31 07:10:42尹安琪郭淵博汪定曲彤洲陳琳

通信學報 2022年3期

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

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

0 引言

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

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

本文工作借鑒文獻[29-30]的研究思路展開，主要貢獻總結如下。

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

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

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

2 預備知識

在介紹本文所需的預備知識之前，首先給出本文必要的符號說明，如表1 所示。

2.1 基于格困難問題的公鑰加密算法

格。設矩陣A∈?m×n，且A的列向量線性無關，另設格用Λ表示，并定義格Λ為

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 兩服務器PAKE 安全模型

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

3.1 通信模型

協(xié)議的參與方包括客戶C∈Client，服務器A，B∈Sever和敵手/攻擊者A ∈Adv?？蛻舫钟锌诹頿wC，服務器A和B分別存儲口令份額pwA，C和pwB，C，且滿足pwA，C+pwB，C(modq)=pwC。一個服務器可以處理多個客戶的認證請求，本文僅以一個客戶為例，研究兩服務器PAKE 協(xié)議。

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

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

3.2 敵手模型

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

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

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

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

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

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

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

在介紹Test預言機前，首先給出新鮮性的概念。

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

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

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

敵手優(yōu)勢。口令認證密鑰交換協(xié)議應該具備語義安全性，即敵手無法區(qū)分真實的會話密鑰及與之等長的隨機串。設敵手進行Test 詢問后，給出的猜測比特為b′，若b′=b，稱敵手成功，并記該事件為Success。定義敵手優(yōu)勢Adv(A)為

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

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

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

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

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

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

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

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

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

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

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

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

證明詳見附錄1。

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

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

5.1 針對被動敵手攻擊的兩服務器PAKE 協(xié)議

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

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

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

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

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

服務器A與服務器B的操作對稱，下文僅以服務器A為例說明服務器端的操作。

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

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

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

5.2 針對主動敵手攻擊的兩服務器PAKE 協(xié)議

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

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

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

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

證明詳見附錄2。

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

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

為方便進行各類開銷的對比，本節(jié)假設κ=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ù)設置要求。

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

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

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

表2 格上不同SPHF 的對比

6.2 兩服務器PAKE 協(xié)議的評估

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

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

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

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

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

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

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

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

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

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

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

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

7 結束語

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

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

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

證明1)正確性證明

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

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

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

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

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

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

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

綜上，定理1 成立。

證畢。

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

證明1)正確性證明

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

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

2)安全性證明

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

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

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

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

實驗P1。實驗P1與P0的區(qū)別如下。

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

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

注意Sim 可以執(zhí)行上述b)操作，因為此時是被動敵手攻擊，b)操作所需的參數(shù)對于Sim 而言是已知的。

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

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

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

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

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

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

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

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

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

實驗P6。服務器B改變其生成ZYF 密文的方式，用非法口令（口令服從CDF-Zipf 分布）的份額生成ZYF 的密文。

基于ZYF 方案的IND-CPA 安全性，利用標準的混合證明法，以及本文關于語義安全的定義易知

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

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

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

實驗P9。改變服務器B關于ZYF 密文的生成方式，將其替換為非法口令（服從CDF-Zipf 分布）份額的加密值。

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

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

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