格上基于密文標(biāo)準(zhǔn)語(yǔ)言的可證明安全兩輪口令認(rèn)證密鑰交換協(xié)議

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

（1.信息工程大學(xué)電子技術(shù)學(xué)院,河南鄭州 450001；2.南開(kāi)大學(xué)網(wǎng)絡(luò)空間安全學(xué)院,天津 300350）

1 引言

口令認(rèn)證密鑰交換協(xié)議可使只擁有低熵口令的協(xié)議參與方，在不安全的公開(kāi)網(wǎng)絡(luò)上，協(xié)商密碼學(xué)安全的會(huì)話密鑰［1］.現(xiàn)有PAKE 的研究多是基于傳統(tǒng)困難問(wèn)題的［2～5］；Shor算法［6］證明，存在量子算法可以解密所有基于大整數(shù)分解或離散對(duì)數(shù)的公鑰密碼體制；因此上述PAKE無(wú)法抵抗量子攻擊.而基于格的密碼體制可有效抵抗量子攻擊；與其他抗量子密碼體制（多變量公鑰密碼體制、基于Hash函數(shù)的數(shù)字簽名方案、基于編碼的密碼體制）相比，其在計(jì)算效率［7］、困難實(shí)例隨機(jī)選取［8］等方面具有顯著優(yōu)勢(shì)，但關(guān)于其的研究卻相對(duì)有限.

平滑投射哈希函數(shù)是構(gòu)造PAKE的重要數(shù)學(xué)工具.現(xiàn)有SPHF 一般是基于非標(biāo)準(zhǔn)密文語(yǔ)言的，不能在超多項(xiàng)式模數(shù)下應(yīng)用［9］.文獻(xiàn)［10］提出了一種支持一輪PAKE 協(xié)議構(gòu)造的適應(yīng)性SPHF；但并不能解決上述問(wèn)題.文獻(xiàn)［11］提出了一種基于密文標(biāo)準(zhǔn)語(yǔ)言的SPHF，但其所基于的公鑰加密（Public Key Encryption，PKE）方案計(jì)算效率較低，且該文未對(duì)相關(guān)協(xié)議進(jìn)行安全性證明.

KOY/GL［3，12］和JG/GK［4，5］架構(gòu)是目前應(yīng)用最廣泛的PAKE 協(xié)議架構(gòu)，但都需要三輪通信.文獻(xiàn)［1］率先提出了格上的兩輪PAKE；文獻(xiàn)［13］則利用可拆分函數(shù)，提出了一種可實(shí)現(xiàn)互認(rèn)證的兩輪PAKE；但二者均是基于隨機(jī)預(yù)言機(jī)的，且前者還需要基于可靠性模擬的非交互式零知識(shí)（Simulation-Sound Non-Interactive Zero-Knowledge，SS-NIZK）證明，計(jì)算效率較低.文獻(xiàn)［14］提出了第一個(gè)格上不需要SS-NIZK 的兩輪PAKE，但也是基于非標(biāo)準(zhǔn)密文語(yǔ)言的.

KOY/GL 架構(gòu)下的協(xié)議需要適應(yīng)性選擇密文攻擊下不可區(qū)分（INDistinguishability under Adaptive Chosen-Ciphertext Attack，IND-CCA2）的安全性假設(shè)，這導(dǎo)致協(xié)議計(jì)算效率較低，存儲(chǔ)開(kāi)銷較大.文獻(xiàn)［15］優(yōu)化了PAKE 的密文長(zhǎng)度，但仍需要IND-CCA2 的安全性假設(shè).JG/GK 架構(gòu)下的協(xié)議在客戶端僅需要選擇明文攻擊下不可區(qū)分（INDistinguishability under Chosen-Plaintext Attack，IND-CPA）的安全性假設(shè)，但此類協(xié)議仍需要三輪通信.目前格上的二輪［1，16］、一輪［2，10］PAKE在服務(wù)器和客戶端一般都需要IND-CCA2安全的加密方案.雖然文獻(xiàn)［14］提出的兩輪協(xié)議降低了服務(wù)器端的安全性假設(shè)，但本文指出了其協(xié)議設(shè)計(jì)中的一個(gè)錯(cuò)誤.

因此，研究格上基于密文標(biāo)準(zhǔn)語(yǔ)言的平滑投射哈希函數(shù)，是解決格上SPHF 不能在超多項(xiàng)式模數(shù)下應(yīng)用的有效方法；而降低格上PAKE 協(xié)議的通信輪次和安全性假設(shè)則對(duì)降低PAKE 協(xié)議的通信開(kāi)銷、計(jì)算開(kāi)銷以及提高協(xié)議的實(shí)際安全性具有重要意義.為此，本文提出了兩種格上基于密文標(biāo)準(zhǔn)語(yǔ)言的平滑投射哈希函數(shù)；并基于此提出了一種格上可證明安全的兩輪口令認(rèn)證密鑰交換協(xié)議，協(xié)議降低了客戶端所需的安全性假設(shè)；實(shí)驗(yàn)結(jié)果表明本文具有更優(yōu)的計(jì)算開(kāi)銷、通信開(kāi)銷和安全性假設(shè).

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

2.1 符號(hào)說(shuō)明

本文的符號(hào)定義見(jiàn)表1.

表1 符號(hào)定義

2.2 格及格上的加密方案

格［1］設(shè)m≥n，基矩陣B∈Rm×n（B的列向量線性無(wú)關(guān)），m維的格Λ格定義為

高斯離散分布［9］設(shè)s＞0，y∈Rm，定義Rm上的高斯權(quán)重函數(shù)為

設(shè)參數(shù)為s，中心為y，格Λ上的離散高斯分布為

帶差錯(cuò)學(xué)習(xí)（Learning With Errors，LWE）問(wèn)題［1］令q≥2，另設(shè)χ是Z 上的離散高斯分布.LWE 問(wèn)題的定義為，給定多項(xiàng)式數(shù)目的取樣，區(qū)分以下兩個(gè)分布：（1）(a，＜a，s＞+x)，是固定的隨機(jī)均勻選擇的秘密；（2）(a，b)，LWE 問(wèn)題的困難性說(shuō)明見(jiàn)文獻(xiàn)［6］.

格上的公鑰加密方案文獻(xiàn)［17］中的GPV 方案是格上經(jīng)典的基于LWE 問(wèn)題的IND-CPA 安全的PKE 之一，設(shè)明文為p0∈{0，1}，其定義如下.

為簡(jiǎn)化說(shuō)明，下文以IND-CPA 安全的方案為例構(gòu)造格上的SPHF，基于IND-CCA2 安全的方案構(gòu)造SPHF的方法與其相同.

2.3 平滑投射哈希函數(shù)

近似平滑投射哈希函數(shù)（Approximate Smooth Projective Hash Function，ASPHF）可通過(guò)抽樣算法定義，抽樣算法輸出（K，l，H=｛Hash（params，hk，W）｝l，S，HashKG：hk ←rK，ProjKG：K→S）；其中K、S為哈希、投射密鑰空間，HashKG 為K上的哈希密鑰生成函數(shù)；ProjKG 為K到S上的投射密鑰 生成函數(shù)［2］.ASPHF滿足：

（1）存在高效算法可以計(jì)算HashKG、ProjKG 和Hash(params，hk，W)；

（2）近似正確性：對(duì)于?hk ∈K，?W∈L，ph ←ProjKG(params，hk，W)以及可忽略函數(shù)negl(·)，若存在投射哈希函數(shù)ProjHash 使式（5）成立，稱該ASPHF為ε-ASPHF.

現(xiàn)介紹證明本文SPHF性質(zhì)所需的定理.

定理1［11］對(duì)于A∈其中m可以表示成n的多項(xiàng)式函數(shù).對(duì)于概率舍入函數(shù)R：Zq→{0，1}，滿足對(duì)于?x∈Zq，

其中C=(2πe)1/2·e-π＜1.此外，現(xiàn)有文獻(xiàn)通常直接稱ASPHF為SPHF［10，13，14］，下文也如此.

3 PAKE協(xié)議的安全模型

通信模型［19］假設(shè)通信在不安全的公開(kāi)網(wǎng)絡(luò)上進(jìn)行，參與方包括客戶u1，u2，…∈U，攻擊者（或敵手）ad1，ad2，…∈B和可信服務(wù)器s1，s2，…∈E.

攻擊者模型攻擊者ad1可在協(xié)議執(zhí)行過(guò)程中進(jìn)行消息的竊聽(tīng)、攔截、注入、篡改等.根據(jù)BPR 模型［19］，本文用Execute（u1，i，s1，j）預(yù)言機(jī)、Send（u1，i，msg）預(yù)言機(jī)、Revea（lu1，i）預(yù)言機(jī)以及Tes（tu1，i）預(yù)言機(jī)建模實(shí)例，并用預(yù)言機(jī)詢問(wèn)建模攻擊者的攻擊能力.各預(yù)言機(jī)的具體定義也與BRP模型［19］保持一致.

攻擊者優(yōu)勢(shì)［11］協(xié)議的安全性是通過(guò)一系列Game 定義的：攻擊者可以執(zhí)行一系列上述預(yù)言機(jī)詢問(wèn)（但只允許執(zhí)行一次Test 詢問(wèn)）；所有Game 執(zhí)行完畢后，攻擊者輸出猜測(cè)比特b'；若b′=b，稱攻擊者攻擊成功.本文用Success 表示攻擊成功事件，ad1在攻擊協(xié)議Π時(shí)的攻擊優(yōu)勢(shì)AdvΠ，ad1為

定義1（安全協(xié)議）設(shè)安全參數(shù)為n，口令空間為D，服從CDF-Zipf 分布［20］，另設(shè)概率多項(xiàng)式時(shí)間（Probabilistic Polynomial Time，PPT）攻擊者最多可執(zhí)行Q（n）次在線攻擊，稱PAKE 協(xié)議Π 是安全的，如果式（11）成立.

其中C'=0.062239，s'=0.155478.

本文假設(shè)口令服從CDF-Zipf分布.根據(jù)文獻(xiàn)［21］，CDF-Zipf 分布下敵手優(yōu)勢(shì)的準(zhǔn)確性，至少是均勻分布下敵手優(yōu)勢(shì)準(zhǔn)確性的3～4 倍.因此，本文安全協(xié)議模型至少比均勻隨機(jī)模型精確3～4倍.

4 基于密文標(biāo)準(zhǔn)語(yǔ)言的SPHF

4.1 基于KV密文標(biāo)準(zhǔn)語(yǔ)言的SPHF

為解決現(xiàn)有SPHF 不能在超多項(xiàng)式模數(shù)下應(yīng)用的問(wèn)題，本文提出了一種基于KV 密文標(biāo)準(zhǔn)語(yǔ)言（standard languages）的SPHF，記作KV-S-SPHF.下面首先定義本文中基于KV密文的標(biāo)準(zhǔn)語(yǔ)言

為構(gòu)造基于KV 密文標(biāo)準(zhǔn)語(yǔ)言的SPHF（記作KVS-SPHF），舍入函數(shù)應(yīng)該滿足：除1 次諧波外的（jj為奇數(shù)）次諧波的權(quán)重盡量為0.本文選擇的舍入函數(shù)及其波形分別如式（13）和圖1所示.

圖1 舍入函數(shù)波形圖

本文構(gòu)建的基于KV 密文標(biāo)準(zhǔn)語(yǔ)言的SPHF（記作KV-S-SPHF）如下：

（4）P← KV.ProjHash(ph=(u1，…，uk)，WKV=(label，c，p)；w=eKV)：輸 入 ph=(u1，…，uk)，WKV=(label，c，p)和eKV；投射函數(shù)如式（15）所示；輸出P=

下面證明KV-S-SPHF滿足正確性與平滑性.

證明（1）正確性證明

對(duì)于?WKV∈L，滿足

其中，Δ是不可忽略的小數(shù).因?yàn)樵跇?gòu)建KV-S-SPHF 中使用了舍入函數(shù)，只要保證式（17）成立即可.

進(jìn)一步，根據(jù)式（13）和式（17），可得式（18）.

因?yàn)閠·s·m=o(q)，所以有=o(q)（c是高斯取樣的誤差）在統(tǒng)計(jì)上成立.余弦函數(shù)是Lipschitz 連續(xù)函數(shù)，因此可通過(guò)積分來(lái)近似求和：

根據(jù)式（16）和式（19）可知，KV-S-SPHF 滿足近似正確性，根據(jù)文獻(xiàn)［11］中的正確性放大技術(shù)，我們可以得到一個(gè)具有統(tǒng)計(jì)正確性的KV-S-SPHF.

（2）平滑性證明

本文引入新舍入函數(shù)后，只要保證對(duì)于?WKV∈X-L，式（20）中的p2滿足|p2-1/2| ≤negl(n)，那么就可以保證KV-S-SPHF的平滑性.

令pR(x)=Pr(R(x(modq))=1)，那么pR(x)是一個(gè)以q為周期的周期信號(hào).現(xiàn)對(duì)pR(zi)進(jìn)行插值處理，得到式（21）.

根據(jù)式（13），有式（23）.

根據(jù)定理1及式（19）～（23），對(duì)于?WKV∈X-L，C=(2πe)1/2·e-π＜1，有

綜上，KV-S-SPHF是平滑投射哈希函數(shù).證畢.

4.2 基于GPV密文標(biāo)準(zhǔn)語(yǔ)言的SPHF

本小節(jié)研究基于GPV 密文標(biāo)準(zhǔn)語(yǔ)言的SPHF，記作GVP-S-SPHF.GPV 方案的公共矩陣為A，公鑰為pkGPV=BGPV=As+x∈，具體方案如下：

（4）P←GPV.ProjHash(ph=(u1，…，uk)，WGPV=(c，p)；w=eGPV)：輸入投射密鑰ph=(u1，…，uk)，WGPV=(c，p)和w=eGPV；其中p=(p1，…，pk)，c=(c1，…，ck)∈投射函數(shù)的計(jì)算方式如式（26）所示；輸出

GPV-S-SPHF 的正確性與平滑性證明過(guò)程與KV-SSPHF類似，不再贅述.

5 格上可證明安全的兩輪PAKE

5.1 兩輪協(xié)議及正確性分析

基于本文提出的兩種平滑投射哈希函數(shù)，本節(jié)提出了一種格上基于標(biāo)準(zhǔn)安全模型的不需要SS-NIZK 的二輪PAKE，如算法1所示.

密碼原語(yǔ)（1）KV 方案及KV-S-SPHF；（2）GPV方案及GPV-S-SPHF.

初始化階段建立KV 和GPV 方案的公鑰，即公共參考序列（Common Reference String，CRS）.

協(xié)議執(zhí)行過(guò)程假設(shè)協(xié)議在客戶u1和服務(wù)器s1之間執(zhí)行，u1和s1共享口令

正確性分析根據(jù)式（27）以及SPHF 的平滑性（見(jiàn)式（6）），本文協(xié)議滿足正確性.

5.2 安全性證明

本文通過(guò)證明定理2，來(lái)證明本文PAKE 協(xié)議是一個(gè)安全的PAKE協(xié)議.

定理2如果（1）KV 方案是IND-CCA2 安全的PKE，且KV-S-SPHF 是SPHF；（2）GPV 方案是IND-CPA安全的PKE，且GPV-S-SPHF 是SPHF；那么算法1 中的PAKE是一個(gè)安全的PAKE.

證明根據(jù)SPHF的正確性，式（28）成立.

證畢.

根據(jù)GPV方案的IND-CPA安全性，式（29）成立.證畢.

Game3 修改Execute 預(yù)言機(jī)，若雙方持有相同的口令，用服從Zipf 分布的非法口令來(lái)生成cs1.下證

該證明同Game2類似，不再贅述.

Game4 修改Execute 預(yù)言機(jī)，若雙方持有相同的口令，將雙方的會(huì)話密鑰替換為相互獨(dú)立的隨機(jī)數(shù).下證

證畢.

證明根據(jù)KV-S-SPHF 和GPV-S-SPHF 的平滑性，易知式（33）成立.

證畢.

該證明與Game2類似，不再贅述.

在Game6 中，對(duì)于Execute 預(yù)言機(jī)詢問(wèn)而言，所有的會(huì)話密鑰以及傳輸消息都是隨機(jī)的，與真實(shí)口令無(wú)關(guān).

下文開(kāi)始修改Send 預(yù)言機(jī)，并將Send 預(yù)言機(jī)分為以下三種：（1）Send（0ui，Start）：攻擊者ad1初始化ui與sj之間的協(xié)議；模擬器向ad1返回msg1.（2）Send1（sj，msg1）：ad1向sj發(fā)送msg1，返回給攻擊者msg2，并設(shè)置sj的會(huì)話密鑰（3）Send2（ui，msg2）：ad1向ui發(fā)送msg2；該預(yù)言機(jī)不向ad1返回任何消息，只是設(shè)置ui的會(huì)話密鑰

本文用skKV表示KV 方案的私鑰，用skGPV表示GPV方案的私鑰，注意協(xié)議執(zhí)行本身并不需要私鑰.

Game7 如果Execute 產(chǎn)生的某個(gè)msg1 與Send0預(yù)言機(jī)產(chǎn)生的某msg1發(fā)生了碰撞，那么直接宣布ad1攻擊成功.該變化只會(huì)增加ad1的優(yōu)勢(shì)，因此

證明考慮msg1 不是由預(yù)言機(jī)產(chǎn)生的情況：情況（1）只會(huì)增加ad1的優(yōu)勢(shì)；根據(jù)SPHF 的平滑性，情況（2）變化前后，ad1所觀察到分布是統(tǒng)計(jì)上不可區(qū)分的，所以式（35）成立.

證畢.

Game9 修改Send2，令mgs1 是由預(yù)言機(jī)產(chǎn)生的，若msg2 也是由預(yù)言機(jī)產(chǎn)生的，那么可能會(huì)出現(xiàn)以下兩種情況：（1）若u1和s1持有相同的口令，令否則，為u1隨機(jī)選擇一個(gè)會(huì)話密鑰

證明如果msg1 和msg2 是由預(yù)言機(jī)產(chǎn)生的：上述情況（1）與Game8 保持一致；對(duì)于上述情況（2），根據(jù)SPHF 的平滑性，該變化只會(huì)帶來(lái)可忽略的攻擊者優(yōu)勢(shì)的變化；若msg2不是預(yù)言機(jī)產(chǎn)生的：上述情況（3）只會(huì)增加ad1優(yōu)勢(shì)；根據(jù)KV-S-SPHF 的平滑性，上述情況（4）只會(huì)帶來(lái)可忽略的優(yōu)勢(shì)變化.綜上，式（36）成立.

證畢.

證明方式同Game2，不再贅述.

該證明方法與Game2類似，但ad2要檢測(cè)ad1是否構(gòu)造了合法的msg1 和msg2.因?yàn)閍d2只能通其自己的“挑戰(zhàn)”預(yù)言機(jī)判斷msg2 的合法性，所以該證明依賴于KV方案的IND-CCA2安全性.

證明記攻擊者ad1猜測(cè)出正確口令為事件Guess，攻擊者ad1未能猜測(cè)出正確口令為事件NGuess，則

在Game11 中，所有的口令都已經(jīng)被替換為服從Zipf分布的隨機(jī)數(shù)，所以

Pr[SuccessGame11|Guess]≤C′·Q(n)s′+negl(n)（40）

若攻擊者沒(méi)有猜測(cè)出正確口令，那么其只能通過(guò)比特猜測(cè)取勝，又在Game11 中，會(huì)話密鑰已經(jīng)替換為隨機(jī)數(shù)，所以

根據(jù)式（10）、式（39）、式（40）和式（41）可知，

又根據(jù)式（28）～（38），及式（42）可知

綜上，定理2成立.

證畢.

6 協(xié)議仿真與性能評(píng)估

6.1 協(xié)議仿真與效率評(píng)估

本文在Intel（R）Core（TM）i5-4590 平臺(tái)上對(duì)本文提出的協(xié)議以及其他相關(guān)協(xié)議進(jìn)行仿真.目標(biāo)平臺(tái)為單CPU（四核），操作系統(tǒng)為Windows7，內(nèi)存為8 GB，主頻為3.3 GHz.本文用python 語(yǔ)言實(shí)現(xiàn)各種密碼原語(yǔ)，其執(zhí)行時(shí)間如表2 所示，其中Enc 代表加密算法.

表2 密碼原語(yǔ)執(zhí)行時(shí)間

表3 給出了不同協(xié)議的計(jì)算開(kāi)銷.根據(jù)表3，本文協(xié)議在客戶端具有最優(yōu)的執(zhí)行效率，這主要是因?yàn)楸疚膮f(xié)議的客戶端加密算法以及GPV.SPHF 都具有較高的計(jì)算效率，且不需要零知識(shí)證明.在服務(wù)器端，本文協(xié)議的密碼原語(yǔ)與K-PAKE-1 方案相同，但本文協(xié)議在不增加計(jì)算開(kāi)銷（表3 中K-PAKE-1 的計(jì)算開(kāi)銷不包括簽名驗(yàn)簽的時(shí)間開(kāi)銷）的同時(shí)，解決了K-PAKE-1 不能在超多項(xiàng)式模數(shù)下應(yīng)用的問(wèn)題.

表3 協(xié)議效率對(duì)比

6.2 協(xié)議通信與存儲(chǔ)開(kāi)銷評(píng)估

為評(píng)估協(xié)議的通信與存儲(chǔ)開(kāi)銷，本文假設(shè)l=k=128 bit，n=256 bit，m=6400 bit，logq=12.表4 總結(jié)了不同協(xié)議的通信、存儲(chǔ)復(fù)雜度及開(kāi)銷.

表4 通信與存儲(chǔ)開(kāi)銷對(duì)比

本文協(xié)議在客戶端具有最低的存儲(chǔ)開(kāi)銷，這得益于本文的公共參考序列（CRS）及密文長(zhǎng)度較短.在服務(wù)器端，本文協(xié)議與K-PAKE-1 協(xié)議選用了相同的加密算法，但其存儲(chǔ)開(kāi)銷約是本文協(xié)議的1.17倍，這主要是因?yàn)楸疚膮f(xié)議在客戶端的密文以及投射密鑰的長(zhǎng)度更低.在通信開(kāi)銷方面，K-PAKE-1 協(xié)議約是本文協(xié)議的2.98 倍，這是因?yàn)楸疚膮f(xié)議不需要傳遞簽名公鑰及簽名，且客戶端的密文長(zhǎng)度低.此外，本文糾正L-PAKE-1協(xié)議設(shè)計(jì)中的一個(gè)錯(cuò)誤：在客戶端計(jì)算hC時(shí)采用Reg.Hash算法，在服務(wù)器端計(jì)算hS時(shí)采用MP.Hash 算法，才能保證協(xié)議的正確性.

7 總結(jié)

本文提出了一種格上基于KV 密文標(biāo)準(zhǔn)語(yǔ)言和一種基于GPV 密文標(biāo)準(zhǔn)語(yǔ)言的平滑投射哈希函數(shù)，解決了基于格的平滑投射哈希函數(shù)不能在超多項(xiàng)式模數(shù)下應(yīng)用的問(wèn)題；且所提出的SPHFs 還可以應(yīng)用在零知識(shí)證明、不經(jīng)意傳輸和證據(jù)加密等領(lǐng)域.在此基礎(chǔ)上，本文提出了一種格上可證明安全的兩輪PAKE 協(xié)議，可抵抗量子攻擊；不需要基于SS-NIZK，具有較高的計(jì)算效率；降低了客戶端所需的安全性假設(shè)，提高了協(xié)議的實(shí)際安全性；協(xié)議只需要兩輪通信，具有更優(yōu)的通信輪次復(fù)雜度，這可以提高協(xié)議效率、簡(jiǎn)化協(xié)議設(shè)計(jì)和安全分析過(guò)程.最后，本文基于更準(zhǔn)確的標(biāo)準(zhǔn)安全模型對(duì)所提出的協(xié)議進(jìn)行了嚴(yán)格的安全性證明，安全性證明不需要隨機(jī)預(yù)言機(jī)（基于隨機(jī)預(yù)言機(jī)設(shè)計(jì)協(xié)議可能會(huì)導(dǎo)致PAKE 遭受離線口令猜測(cè)攻擊）.實(shí)驗(yàn)證明，本文協(xié)議具有較高的計(jì)算效率；且在不增加通信開(kāi)銷和存儲(chǔ)開(kāi)銷的前提下解決了協(xié)議不能在超多項(xiàng)式模數(shù)下應(yīng)用的問(wèn)題.