一個可抵抗關(guān)鍵詞猜測攻擊的可搜索加密方案

王 波,鄧倫治

(貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴州 貴陽 550025)

0 引言

云存儲服務(wù)由于其諸多優(yōu)勢(如數(shù)據(jù)可訪問性、數(shù)據(jù)共享性等)提高了用戶的體驗(yàn)質(zhì)量，并且允許用戶在任意地點(diǎn)遠(yuǎn)程訪問云中的數(shù)據(jù)，因而被大量的公司或個人接受以減輕本地數(shù)據(jù)存儲和管理的沉重負(fù)擔(dān)。盡管云存儲服務(wù)為用戶提供了很多便利，但也面臨很多問題和挑戰(zhàn)。當(dāng)用戶將其敏感數(shù)據(jù)外包給云服務(wù)器后，在用戶失去了有效控制數(shù)據(jù)能力的同時，云服務(wù)器和非法用戶可以嘗試獲取數(shù)據(jù)中包含的信息，用戶的隱私安全問題面臨著巨大的挑戰(zhàn)。為了保護(hù)敏感數(shù)據(jù)的安全，用戶在外包之前通常會將數(shù)據(jù)加密。但是，當(dāng)用戶想要搜索某個數(shù)據(jù)時，如何搜索加密數(shù)據(jù)成為一個棘手的問題。

在2000年，由Song等[1]首先提出可搜索加密的概念，并且第一次提出了在密文上進(jìn)行搜索的對稱可搜索加密(Symmetric searchable encryption，SSE)方案，但是該方案存在密鑰分配和檢索效率較低的問題。2004年，由 Boneh 等[2]提出了第一個公鑰可搜索加密(Public key encryption with keyword search，PEKS)方案，并將其運(yùn)用到郵件路由的場景中。他們在方案中定義了IND-CKA (Indistinguishability against chosen keyword attack)安全模型，并證明了該方案的安全性。由于PEKS克服了SSE密鑰分配的問題，因此PEKS更加適合數(shù)據(jù)分享的場景。在此之后，各種應(yīng)用于區(qū)塊鏈、物聯(lián)網(wǎng)、智能電網(wǎng)、電子醫(yī)療和電子郵件系統(tǒng)等場景的PEKS方案被不斷提出。

在 2006 年, Byun 等[3]發(fā)現(xiàn)當(dāng)前的公鑰可搜索加密體制存在嚴(yán)重的安全隱患:關(guān)鍵詞往往是從一些小的關(guān)鍵詞空間中選取出來(比如一些學(xué)科中的專業(yè)名詞),因此攻擊者通過發(fā)起離線關(guān)鍵詞猜測攻擊(Off-Line keyword guessing attacks)能夠輕松獲取關(guān)鍵詞密文和搜索陷門中的關(guān)鍵詞信息。2008年，Baek 等[4]提出了一個無安全信道的PEKS(Secure-channel-free PEKS,SCF-PEKS)方案，該方案移除了傳統(tǒng)PEKS方案在關(guān)鍵詞陷門傳輸過程中對安全信道的需求。然而，Yau等[5]指出在公共信道上傳輸?shù)年P(guān)鍵詞陷門容易被一個外部敵手(通常指服務(wù)器和用戶之外的實(shí)體)截取，外部敵手通過發(fā)起離線關(guān)鍵詞猜測攻擊可以揭露關(guān)鍵詞陷門中的關(guān)鍵詞信息，并對Baek 等[4，6]提出的兩個方案進(jìn)行了詳細(xì)的離線關(guān)鍵詞猜測攻擊分析。

為了抵御由外部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊,在 2009年，Rhee 等[7]提出了一種指定測試者的可搜索加密 (Searchable public key encryption with a designated tester，DPEKS)方案, 方案中的匹配算法只能由指定的服務(wù)器來執(zhí)行。該方案還引入了陷門不可區(qū)分(Trapdoor indistinguishability)的概念, 加強(qiáng)了PEKS方案中的陷門安全。后來，Rhee 等[8]又提出了一個變體方案，該方案可以抵抗由外部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊。然而，不久之后， Hu等[9-10]指出文獻(xiàn)[7-8]的方案無法抵御由惡意服務(wù)器發(fā)起的離線關(guān)鍵詞猜測攻擊，并提出了相應(yīng)的改進(jìn)方案。之所以會發(fā)起該攻擊，原因是執(zhí)行匹配算法的服務(wù)器往往是“誠實(shí)且好奇”的，即服務(wù)器會按照用戶的指令執(zhí)行操作，但也會對用戶數(shù)據(jù) “感興趣”。在2013年，Yau等[11]對關(guān)鍵詞猜測攻擊進(jìn)行了更深層次的研究，提出了一種稱為“在線關(guān)鍵詞猜測攻擊(On-Line keyword guessing attacks)”的新攻擊方式。該攻擊之所以能夠?qū)崿F(xiàn)，主要原因是只有公鑰參與關(guān)鍵詞加密算法或陷門生成算法，使得任意一個敵手都可以假冒成數(shù)據(jù)擁有者或用戶去生成關(guān)鍵詞密文或陷門。

2015年，基于雙服務(wù)器的公鑰可搜索加密(Dual-server PEKS，DS-PEKS)方案被Chen等[12]提出。在該方案安全模型中，前服務(wù)器(Front Server)與后服務(wù)器(Back server)都是“半誠實(shí)”的，但兩者不能串謀。雖然基于兩個服務(wù)器的模型可以增強(qiáng)方案安全性，不能串謀的條件也使得方案看似可以抵抗來自內(nèi)部敵手的關(guān)鍵詞猜測攻擊，但是該方案的關(guān)鍵詞加密算法與陷門生成算法都是使用前服務(wù)器與后服務(wù)器的公鑰加密，所以任意一個敵手依然可以實(shí)施在線關(guān)鍵詞猜測攻擊。后來，Huang等[13]指出了Chen等[12]的方案的缺陷，同時提出了一個新的DS-PEKS方案，并聲稱新方案能夠抵抗來自內(nèi)部敵手的關(guān)鍵詞猜測攻擊。雖然該方案的安全模型中假定至少有一個服務(wù)器是“誠實(shí)”的，但遺憾的是，Huang等[13]提出的方案和文獻(xiàn)[12]的方案一樣，在關(guān)鍵詞加密算法與陷門生成算法中都是使用服務(wù)器的公鑰加密，所以一個惡意的內(nèi)部敵手仍然可以發(fā)起在線關(guān)鍵詞猜測攻擊。與此同時，黃海平等[14]也提出了一個“基于云存儲的多服務(wù)器多關(guān)鍵詞可搜索加密方案”，該方案中需要將密文文檔按照某種規(guī)則等分成N份分別發(fā)送給N個服務(wù)器。雖然該方案可以抵抗在線關(guān)鍵詞猜測攻擊，但是該方案需要安全信道去傳輸密鑰，且計算成本較高。

考慮到只有公鑰參與關(guān)鍵詞密文生成算法或陷門生成算法是在線關(guān)鍵詞猜測攻擊得以實(shí)施的原因，因此，如果想要成功抵抗在線關(guān)鍵詞猜測攻擊，關(guān)鍵詞密文生成算法與陷門生成算法都必須使用私鑰。2018年，Huang等[15]提出了一個公鑰認(rèn)證可搜索加密(Public-key authenticated encryption with keyword search，PAEKS)方案，該方案加入了認(rèn)證功能：關(guān)鍵詞密文需要數(shù)據(jù)擁有者的私鑰來生成，其他個體不能偽造出該數(shù)據(jù)擁有者才能生成的有效關(guān)鍵詞密文，這一性質(zhì)對于用戶生成陷門也一樣。結(jié)果表明，該方案可以成功抵抗在線關(guān)鍵詞猜測攻擊。2019年，Chen等[16]提出了一個基于雙服務(wù)器的公鑰認(rèn)證可搜索加密(Dual-server public-key authenticated encryption with keyword search，DPAEKS)方案。該方案是基于兩個不能串謀的雙服務(wù)器模型，同樣可以成功抵抗在線關(guān)鍵詞猜測攻擊。與此同時，張玉磊等[17]提出一個基于多服務(wù)器的密鑰聚合可搜索加密方案。雖然該方案可以抵抗在線關(guān)鍵詞猜測攻擊，但是需要安全信道去傳輸加密鑰和授權(quán)密鑰；Lu等[18]提出了一個可抵抗兩類關(guān)鍵詞猜測攻擊的DPEKS方案一般構(gòu)造方法，該方案的關(guān)鍵一步是：利用Diffie-Hellman密鑰協(xié)商方案，數(shù)據(jù)擁有者和用戶之間可以得到一個相同的密鑰，該密鑰只有兩者知道，這就相當(dāng)于數(shù)據(jù)擁有者和用戶之間在沒有使用安全信道的條件下就得到了一個對稱密鑰,同時實(shí)現(xiàn)了認(rèn)證功能； Lu等[19]還將關(guān)鍵詞猜測攻擊分為3種類型(來自外部敵手的離線關(guān)鍵詞猜測攻擊、來自外部敵手的在線關(guān)鍵詞猜測攻擊和來自內(nèi)部敵手的離線關(guān)鍵詞猜測攻擊)，并提出了一個應(yīng)用于電子醫(yī)療記錄的PEKS方案，該方案在標(biāo)準(zhǔn)模型下被證明實(shí)現(xiàn)了關(guān)鍵詞密文不可區(qū)分性和陷門不可區(qū)分性。同時，Lu等[20-21]又提出2個新的PEKS方案，且方案[21]適用于計算能力有限的場景，并在新的安全模型下證明了安全性。后來，Qin等[22]提出了一個PAEKS方案，并在新的安全模型下實(shí)現(xiàn)了“多密文”不可區(qū)分性。在該方案安全模型的挑戰(zhàn)階段，敵手會挑選2個關(guān)鍵詞組發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者也會隨機(jī)對某一個關(guān)鍵詞組中所有關(guān)鍵詞加密來生成挑戰(zhàn)密文，這是與其它方案的安全模型最顯著的區(qū)別。楊寧濱等[23]提出了一個無配對公鑰可搜索加密方案，也實(shí)現(xiàn)了多關(guān)鍵詞密文不可區(qū)分性；郭麗峰等[24]提出了一個SCF-PEKS方案,但是由于關(guān)鍵詞加密算法是用公鑰加密，并沒有私鑰參與，所以并不能有效抵抗在線關(guān)鍵詞猜測攻擊。在2021年，陳寧江等[25]提出了一個可以抵御內(nèi)部關(guān)鍵字猜測攻擊的PEKS方案，該方案引入了一種叫做“倒排索引”的技術(shù)，并實(shí)現(xiàn)次線性搜索，其搜索效率只與包含相關(guān)查詢關(guān)鍵字的密文數(shù)成正比。與此同時，Nayak等[26]也提出了一個PEKS方案，該方案需要指定的服務(wù)器執(zhí)行匹配算法且可以抵抗關(guān)鍵詞猜測攻擊； Pan等[27]提出了一個實(shí)現(xiàn)多密文不可區(qū)分性與多陷門不可區(qū)分性的PEKS方案；Zhang等[28]提出了一個可以實(shí)現(xiàn)搜索由其他用戶或自己分享的加密郵件的PEKS方案；鄭東等[29]提出了一個基于區(qū)塊鏈的多用戶環(huán)境下的可搜索加密方案，該方案基于判定性雙線性 Diffie-Hellman 假設(shè)和修改的判定性雙線性 Diffie-Hellman 假設(shè)被證明可以抵御內(nèi)部關(guān)鍵詞猜測攻擊；張鍵紅等[30]提出了一個云環(huán)境下安全的可驗(yàn)證多關(guān)鍵詞搜索加密方案，該方案雖然實(shí)現(xiàn)了數(shù)據(jù)完整性驗(yàn)證的功能并且能夠抵抗關(guān)鍵詞猜測攻擊，然而該方案中的用戶只能搜索自己的數(shù)據(jù)，沒有實(shí)現(xiàn)搜索他人數(shù)據(jù)的功能。

本文提出了一個可以抵抗關(guān)鍵詞猜測攻擊的可搜索加密方案。該方案具有以下特點(diǎn)：

1)本文提出的方案在隨機(jī)預(yù)言模型下實(shí)現(xiàn)了關(guān)鍵詞密文的不可區(qū)分性、陷門的不可區(qū)分性、關(guān)鍵詞密文的不可偽造性與陷門的不可偽造性。關(guān)鍵詞密文的不可區(qū)分性與陷門的不可區(qū)分性保證了方案可以抵抗由外部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊；關(guān)鍵詞密文的不可偽造性與陷門的不可偽造性保證了方案可以抵抗由外部敵手發(fā)起的在線關(guān)鍵詞猜測攻擊；而以上4種安全性質(zhì)保證了方案可以抵抗由內(nèi)部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊。總之，我們的方案可以抵抗現(xiàn)已知的3種關(guān)鍵詞猜測攻擊。

2)關(guān)鍵詞加密算法和陷門生成算法都沒有使用雙線性對，這使得數(shù)據(jù)發(fā)送者和接收者只需承擔(dān)較低的計算成本。

1 預(yù)備知識

1.1 雙線性映射

定義1(雙線性映射[19]):設(shè)G1和G2是兩個p階循環(huán)群，p是素數(shù)，g是G1的生成元。映射e:G1×G1→G2是滿足以下性質(zhì)的雙線性映射：

2)非退化性:e(g，g)≠1;

1.2 困難問題

2 系統(tǒng)框架與安全模型

2.1 系統(tǒng)模型

我們方案的系統(tǒng)模型包括4個參與方：可信中心、發(fā)送者、接收者以及云服務(wù)器(圖1)。

圖1 系統(tǒng)模型Fig.1 System model

1)可信中心：可信中心主要負(fù)責(zé)生成和發(fā)布系統(tǒng)參數(shù)。

2)發(fā)送者：發(fā)送者先對關(guān)鍵詞進(jìn)行加密，生成索引，然后將加密后的數(shù)據(jù)以及索引發(fā)送給云服務(wù)器。

3)接收者：接收者生成關(guān)鍵詞陷門，發(fā)送給云服務(wù)器，并將從云服務(wù)器接收到的數(shù)據(jù)進(jìn)行解密。

4)云服務(wù)器：服務(wù)器收到由接收者發(fā)送的關(guān)鍵詞陷門后，執(zhí)行測試算法并將滿足檢索條件的數(shù)據(jù)發(fā)送給接收者。

2.2 方案框架

本文提出的方案由以下算法構(gòu)成：

· Global Setup (λ)：輸入安全參數(shù)λ，算法輸出全局參數(shù)GP。

· KenGen(GP)：輸入GP, 算法輸出發(fā)送者和接收者的公、私鑰對(skS,pkS)和(skR,pkR)。

· PEKS (GP,skS,pkR,w):輸入GP,發(fā)送者的私鑰skS,接收者的公鑰pkR和關(guān)鍵詞w,算法計算關(guān)鍵詞密文Cw。

· Trapdoor (GP,skR,pkS,w′)輸入GP,發(fā)送者的公鑰pkS,接收者的私鑰skR和關(guān)鍵詞w′,算法計算關(guān)鍵詞陷門Tw′。

· Test (GP,Cw,Tw′): 輸入GP,關(guān)鍵詞密文Cw和關(guān)鍵詞陷門Tw′,算法測試等式是否成立：若等式成立輸出1，否則輸出0。

參數(shù)詳情見表1。

表1 符號及其意義Tab.1 Symbol and its meaning

2.3 安全模型

在本文中，我們要求提出的方案滿足關(guān)鍵詞密文的不可區(qū)分性、陷門的不可區(qū)分性、關(guān)鍵詞密文的不可偽造性和陷門的不可偽造性，并以游戲的方式定義安全模型。其中，關(guān)鍵詞密文的不可區(qū)分性和陷門的不可區(qū)分性保證了方案可以抵抗由外部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊；關(guān)鍵詞密文的不可偽造性和陷門的不可偽造性保證了方案可以抵抗由外部敵手發(fā)起的在線關(guān)鍵詞猜測攻擊；而以上4種安全性質(zhì)保證了方案可以抵抗由內(nèi)部敵手發(fā)起的離線關(guān)鍵詞猜測攻擊?？傊?，我們的方案可以抵抗現(xiàn)已知的3種關(guān)鍵詞猜測攻擊。

游戲1關(guān)鍵詞密文的不可區(qū)分性

設(shè)置給定安全參數(shù)λ,挑戰(zhàn)者C生成全局參數(shù)GP,然后將參數(shù)GP發(fā)送給敵手A。

階段1 在此階段，多項(xiàng)式時間敵手A適應(yīng)性地查詢以下預(yù)言機(jī)：

Opk查詢：當(dāng)敵手A提交1個身份IDi,挑戰(zhàn)者C返回公鑰pki給敵手A；

Osk查詢：當(dāng)敵手A提交1個身份IDi,挑戰(zhàn)者C返回私鑰ski給敵手A；

OC查詢：當(dāng)敵手A提交2個身份(IDi,IDj)和1個關(guān)鍵詞w,挑戰(zhàn)者C返回發(fā)送者身份為IDi而接收者身份為IDj的、關(guān)于關(guān)鍵詞w的密文Cw；

OT查詢：當(dāng)敵手A提交2個身份(IDi,IDj)和1個關(guān)鍵詞w,挑戰(zhàn)者C返回發(fā)送者身份為IDi而接收者身份為IDj的、關(guān)于關(guān)鍵詞w的陷門Tw；

OM查詢：敵手A提交1個關(guān)鍵詞密文Cw和1個關(guān)鍵詞陷門Tw′,挑戰(zhàn)者C返回Test (GP,Cw,Tw′)的結(jié)果。

定義2 如果概率多項(xiàng)式時間敵手A贏得游戲1的優(yōu)勢是可以忽略的，則稱該方案滿足關(guān)鍵詞密文的不可區(qū)分性。

游戲2 陷門的不可區(qū)分性

設(shè)置同游戲1。

階段1 同游戲1。

定義3 如果概率多項(xiàng)式時間敵手A贏得游戲2的優(yōu)勢是可以忽略的，則稱該方案滿足陷門的不可區(qū)分性。

游戲3 關(guān)鍵詞密文的不可偽造性

設(shè)置同游戲1。

階段1 同游戲1。

挑戰(zhàn)敵手A輸出2個身份(IDi*,IDj*)和關(guān)鍵詞w*的偽造密文Cw*發(fā)送給挑戰(zhàn)者C,這里要求敵手A沒有對(IDi*,IDj*,w*)進(jìn)行過OC查詢。隨后，C對(IDi*,IDj*,w*)進(jìn)行OT查詢，并獲得關(guān)鍵詞w*的陷門Tw*。最后，挑戰(zhàn)者C對(Cw*,Tw*)進(jìn)行OM查詢，可以得到結(jié)果0或1。如果OM輸出結(jié)果為1，則敵手A獲勝。定義敵手A贏得這一游戲的優(yōu)勢為Adv(A)=|Pr[OM→1]|。

定義4 如果概率多項(xiàng)式時間敵手A贏得游戲3的優(yōu)勢是可以忽略的，則稱該方案滿足關(guān)鍵詞密文的不可偽造性。

游戲4 關(guān)鍵詞陷門的不可偽造性

設(shè)置同游戲1。

階段1 同游戲1。

挑戰(zhàn)敵手A輸出2個身份(IDi*,IDj*)和關(guān)鍵詞w*的偽造陷門Tw*發(fā)送給挑戰(zhàn)者C,這里要求敵手A沒有對(IDi*,IDj*,w*)進(jìn)行過OT查詢。隨后，C對(IDi*,IDj*,w*)進(jìn)行OC查詢，并獲得關(guān)鍵詞w*的密文Cw*。最后，挑戰(zhàn)者C對(Cw*,Tw*)進(jìn)行OM查詢，可以得到結(jié)果0或1。如果OM輸出結(jié)果為1，則敵手A獲勝。定義敵手A贏得這一游戲的優(yōu)勢為Adv(A)=|Pr[OM→1]|。

定義5 如果概率多項(xiàng)式時間敵手A贏得游戲4的優(yōu)勢可以忽略的，則稱該方案滿足陷門的不可偽造性。

3 提出的方案

3.1 方案構(gòu)造

Cw=(C1,C2)=(C1=H1(w)kgr,C2=hr)

其中k=H2((pkR)skS)=H2((gb)a)=H2(gab)。

Tw′=(T1,T2)=(T1=(H1(w′)k)-1gs,T2=hs)

其中k=H2((pkS)skR)=H2((ga)b)=H2(gab)。

· Test (GP,Cw,Tw′): 輸入GP,關(guān)鍵詞密文Cw=(C1,C2)和關(guān)鍵詞陷門Tw′=(T1,T2),算法測試等式

e(C1·T1,h)=e(g,C2·T2)

如果等式成立，則輸出1;否則，輸出 0。

3.2 安全性分析

定理1 在隨機(jī)預(yù)言模型下，若 HDH問題是困難的，則該方案滿足關(guān)鍵詞密文的不可區(qū)分性。

給定HDH問題實(shí)例(g,ga,gb,X),C將扮演游戲中的挑戰(zhàn)者去判斷X=H2(gab)是否成立。

設(shè)置輸入安全參數(shù)λ,C通過Global Setup (λ) 算法生成系統(tǒng)參數(shù)GP={p,G1,G2,e,g,h,H1,H2},然后將參數(shù)GP發(fā)送給A。

階段1敵手A將在多項(xiàng)式時間內(nèi)進(jìn)行以下查詢。不失一般性，假定每次查詢互不相同，且在沒有進(jìn)行Opk查詢前不能進(jìn)行其它查詢。

Opk查詢：C以的格式設(shè)置列表Lpk。當(dāng)敵手A輸入IDi時，C查找列表Lpk,若已經(jīng)存在于列表Lpk,則返回pki；否則，C按照如下方式進(jìn)行回應(yīng)：

若i=I,C將=添加進(jìn)列表Lpk,并返回pkI給A；

若i=J,C將=添加進(jìn)列表Lpk,并返回pkJ給A；

Osk查詢：C以的格式設(shè)置列表Lsk。當(dāng)敵手A輸入IDi時，若i=I或者i=J,則游戲終止；否則，C查找列表Lsk,并返回ski給A。

H1查詢:C以的格式設(shè)置列表L1。當(dāng)敵手A輸入w時，若已經(jīng)存在于列表L1,則返回h1；否則，C隨機(jī)選取h1∈G1,將保存至列表L1,并把H1(w)=h1返回給敵手A。

Cw=(C1,C2)=(C1=H1(w)X*gr,C2=hr)

其中，X*的取值如表2所示。

Tw=(T1,T2)=(T1=(H1(w)X*)-1gs,T2=hs)

其中，X*的取值如表2所示。

表2 X*的值Tab.2 The value of X*

OM查詢：敵手A提交1個關(guān)鍵詞密文Cw和1個關(guān)鍵詞陷門Tw′,挑戰(zhàn)者C返回Test (GP,Cw,Tw′)的結(jié)果。

如果{i*,j*}≠{I,J},游戲終止；

當(dāng)X≠H2(gab),那么當(dāng)b=0或b=1時，密文各部分具有相同的概率分布。因而A在區(qū)分b上不具有任何的優(yōu)勢。所以

因此:

概率分析設(shè)事件E1：在階段1游戲終止；事件E2：挑戰(zhàn)階段游戲終止；事件E：游戲終止。則

定理2在隨機(jī)預(yù)言模型下，如果HDH問題是困難的，那么我們的方案滿足關(guān)鍵詞陷門的不可區(qū)分性。

給定HDH問題實(shí)例(g,ga,gb,X),C將扮演游戲中的挑戰(zhàn)者去判斷X=H2(gab)是否成立。

設(shè)置輸入安全參數(shù)λ,C通過Global Setup (λ) 算法生成系統(tǒng)參數(shù)GP={p,G1,G2,e,g,h,H1,H2},然后將參數(shù)GP發(fā)送給A。

階段1敵手A可以進(jìn)行H1、H2、Opk、Osk、OC、OT和OM查詢，挑戰(zhàn)者C按照定理1中相同的方式回應(yīng)。

如果{i*,j*}≠{I,J},游戲終止；

因此:

概率分析設(shè)事件E1：在階段1游戲終止；事件E2：挑戰(zhàn)階段游戲終止；事件E：游戲終止。則

定理3 在隨機(jī)預(yù)言模型下，如果HDH問題是困難的，那么我們的方案滿足關(guān)鍵詞密文的不可偽造性。

給定HDH問題實(shí)例(g,ga,gb,X),C將扮演游戲中的挑戰(zhàn)者去判斷X=H2(gab)是否成立。

設(shè)置輸入安全參數(shù)λ,C通過Global Setup (λ) 算法生成系統(tǒng)參數(shù)GP={p,G1,G2,e,g,h,H1,H2},然后將參數(shù)GP發(fā)送給A。

階段1敵手A可以進(jìn)行H1、H2、Opk、Osk、OC、OT和OM查詢，挑戰(zhàn)者C按照定理1中相同的方式回應(yīng)。

挑戰(zhàn)敵手A輸出2個身份(IDi*,IDj*)和關(guān)鍵詞w*的偽造密文Cw*發(fā)送給挑戰(zhàn)者C,這里要求敵手A沒有對(IDi*,IDj*,w*)進(jìn)行過OC查詢。挑戰(zhàn)者C按照如下方式回應(yīng)：

如果{i*,j*}≠{I,J},游戲終止；

如果{i*,j*}={I,J},則C對(IDi*,IDj*,w*)進(jìn)行OT查詢，并獲得關(guān)鍵詞w*的陷門Tw*。然后，挑戰(zhàn)者C對(Cw*,Tw*)進(jìn)行OM查詢，可以得到結(jié)果0或1。如果輸出結(jié)果為1，則挑戰(zhàn)者C返回1，即此時有X=H2(gab)；否則，挑戰(zhàn)者C返回0。

概率分析假設(shè)事件E1：在階段1游戲終止；事件E2：挑戰(zhàn)階段游戲終止；事件E：游戲終止。則

定理4 在隨機(jī)預(yù)言模型下，如果HDH問題是困難的，那么我們的方案滿足關(guān)鍵詞陷門的不可偽造性。

給定HDH問題實(shí)例(g,ga,gb,X),C將扮演游戲中的挑戰(zhàn)者去判斷X=H2(gab)是否成立。

設(shè)置輸入安全參數(shù)λ,C通過Global Setup (λ) 算法生成系統(tǒng)參數(shù)GP={p,G1,G2,e,g,h,H1,H2},然后將參數(shù)GP發(fā)送給A。

階段1 敵手A可以進(jìn)行H1、H2、Opk、Osk、OC、OT和OM查詢，挑戰(zhàn)者C按照定理1中相同的方式回應(yīng)。

挑戰(zhàn)敵手A輸出2個身份(IDi*,IDj*)和關(guān)鍵詞w*的偽造陷門Tw*發(fā)送給挑戰(zhàn)者C,這里要求敵手A沒有對(IDi*,IDj*,w*)進(jìn)行過OT查詢。挑戰(zhàn)者C按照如下方式回應(yīng)：

如果{i*,j*}≠{I,J},游戲終止；

如果{i*,j*}={I,J},則C對(IDi*,IDj*,w*)進(jìn)行OC查詢，并獲得關(guān)鍵詞w*的密文Cw*。然后，挑戰(zhàn)者C對 (Cw*,Tw*)進(jìn)行OM查詢，可以得到結(jié)果0或1。如果輸出結(jié)果為1，則挑戰(zhàn)者C返回1，即此時有X=H2(gab)；否則，挑戰(zhàn)者C返回0。

概率分析設(shè)事件E1：在階段1游戲終止；事件E2：挑戰(zhàn)階段游戲終止；事件E：游戲終止。則

4 性能分析

4.1 安全性比較

在表3，我們將本文提出的方案與幾個已經(jīng)提出的公鑰可搜索加密方案作一個安全性對比，對比項(xiàng)目主要包括該方案是否能夠抵抗現(xiàn)已知的3種關(guān)鍵詞猜測攻擊：KGAI: 來自外部敵手的離線關(guān)鍵詞猜測攻擊; KGAII: 來自外部敵手的在線關(guān)鍵詞猜測攻擊; KGAIII: 來自內(nèi)部敵手的離線關(guān)鍵詞猜測攻擊。為了簡便，我們使用“是”表示該行所對應(yīng)的方案可以抵抗該列所對應(yīng)的關(guān)鍵詞猜測攻擊，“否”則表示該行所對應(yīng)的方案不能夠抵抗該列所對應(yīng)的關(guān)鍵詞猜測攻擊。

表3 安全性對比Tab.3 Security comparison

4.2 計算成本比較

為了公平，我們使用Lu等[19]的第三方實(shí)驗(yàn)數(shù)據(jù)，該數(shù)據(jù)是在配置為Interl(R) CoreTMi3-2310M CPU@2.10 GHz 和 4 GB RAM 內(nèi)存的筆記本電腦上運(yùn)行得到，而基準(zhǔn)時間是通過利用PBC(Pairing-based cryptography)庫[31]獲得。為了實(shí)現(xiàn)1 024比特RSA的安全級別，Lu等[19]使用定義在超奇異橢圓曲線E(Fq):y2=x3+x的Type-A配對，并選擇SHA-1作為一般Hash函數(shù)。在效率比較上，我們同樣只考慮關(guān)鍵詞加密算法、陷門生成算法和測試算法的計算成本。其中，計算成本的比較主要考量以下4種運(yùn)算造成的計算成本：雙線性對計算成本(TBP)、映射到群G1的哈希函數(shù)計算成本(THP)、群G1上的冪運(yùn)算成本(TE1)和群G2上冪運(yùn)算成本(TE2)。由文獻(xiàn)[19]，這4種計算單次運(yùn)行時間分別是2.486 ms,0.334 ms,0.311 ms和0.059 ms。于是，在我們的方案中，執(zhí)行一次關(guān)鍵詞加密算法的計算成本是：0.334+4×0.311=1.578 ms；執(zhí)行一次陷門生成算法的計算成本是：0.334+4×0.311=1.578 ms；執(zhí)行一次測試算法的計算成本是：2×2.486=4.972 ms。同理，可以求出其它方案分別執(zhí)行一次關(guān)鍵詞加密算法、陷門生成算法和測試算法的計算成本，并由此得到表4和圖2。 由表4或圖2可知，與其它使用雙線性對的可搜索加密方案相比，本文提出方案的關(guān)鍵詞加密算法和陷門生成算法只需要較低的計算成本。為了更加直觀與符合實(shí)際情況，我們將各個方案的關(guān)鍵詞加密算法和陷門生成算法分別執(zhí)行多次來比較2個算法的計算成本，得到圖3和圖4。其中，橫軸表示算法執(zhí)行次數(shù)，縱軸表示運(yùn)行時間。

表4 計算成本對比Tab.4 Computational cost comparison

圖2 計算成本對比Fig.2 Computational cost comparison

圖3 關(guān)鍵詞加密算法計算成本比較Fig.3 Computational cost comparison of keyword encryption algorithm

圖4 陷門生成算法計算成本比較Fig.4 Computational cost comparison of trapdoor generation algorithm

5 結(jié)論

本文提出了一個可抵抗關(guān)鍵詞猜測攻擊的可搜索加密方案。我們的方案不僅可以抵抗已知的3種關(guān)鍵詞猜測攻擊，而且該方案與某些可以抵抗關(guān)鍵詞猜測攻擊的PEKS方案相比，在執(zhí)行關(guān)鍵詞加密算法和陷門生成算法時都具有較低的計算成本。