基于身份的抗內(nèi)部猜測(cè)攻擊的關(guān)鍵字搜索方案

郭麗峰,李智豪

(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,山西 太原 030006)

0 引言

隨著信息和網(wǎng)絡(luò)的發(fā)展,由于云計(jì)算提供給用戶便利的數(shù)據(jù)存儲(chǔ)和高效的處理服務(wù),越來(lái)越多的個(gè)人和企業(yè)趨向?qū)?shù)據(jù)上傳到云服務(wù)器,由其來(lái)處理數(shù)據(jù)。但是云服務(wù)器并不完全可信。在通信過(guò)程中,惡意的云服務(wù)器可能非法竊取用戶的隱私,導(dǎo)致信息泄露。所以數(shù)據(jù)擁有者需要將數(shù)據(jù)加密后再上傳到云平臺(tái),以密文的形式保障數(shù)據(jù)的安全性,但同時(shí)也加大了數(shù)據(jù)搜索的難度。

Boneh等[1]在2004年第一次提出了帶關(guān)鍵字搜索的公鑰加密方案(public key encryption with keyword search,PEKS),它的思想主要是發(fā)送者首先加密數(shù)據(jù)和關(guān)鍵字,并上傳至云服務(wù)器。此后接收者發(fā)送一個(gè)由關(guān)鍵字生成的陷門給云服務(wù)器,最后云服務(wù)器執(zhí)行關(guān)鍵字密文和陷門的匹配算法,成功后再將密文數(shù)據(jù)發(fā)送給接收方,此過(guò)程云服務(wù)器不能獲得關(guān)鍵字和密文數(shù)據(jù)的任何信息。但是在該過(guò)程中需要建立接收者和服務(wù)器之間的安全信道。Baek等[2]人提出了無(wú)安全信道的可搜索加密方案(secure-channel free PEKS,SCF-PEKS),其方法是通過(guò)引入服務(wù)器的公私鑰對(duì)來(lái)消除安全信道,只有指定的服務(wù)器才能夠?qū)﹃P(guān)鍵字密文與陷門進(jìn)行匹配。此后Rhee等[3-5]提高了Baek的安全模型,并提出了一系列指定檢驗(yàn)者的關(guān)鍵字搜索方案(designated test PEKS,dPEKS)。此前的方案都是在隨機(jī)諭言模型下證明安全的。Fang等[6]基于Gentry[7]的基于身份加密方案構(gòu)造了標(biāo)準(zhǔn)模型下的帶關(guān)鍵字搜索方案。

2006年,Byun等[8]第一次提出離線的關(guān)鍵字猜測(cè)攻擊(KGA)的概念,并對(duì)Boneh的方案進(jìn)行了攻擊,他的攻擊依據(jù)是關(guān)鍵字個(gè)數(shù)相對(duì)比較有限(約有225 000個(gè)),可以使用窮舉搜索的方法來(lái)進(jìn)行攻擊。Rhee等[5]提出了陷門不可區(qū)分性,證明陷門不區(qū)分性是抵抗關(guān)鍵字猜測(cè)攻擊的充分條件,并提出了一個(gè)具體的方案。Fang等[9]在非對(duì)稱雙線性映射下構(gòu)造出一個(gè)可抵抗外部敵手進(jìn)行關(guān)鍵字猜測(cè)攻擊的方案,并在標(biāo)準(zhǔn)模型下證明安全性。

2015年,Shao等[10]在Fang等[9]的方案中引入了發(fā)送者的身份,并通過(guò)RSA算法對(duì)身份進(jìn)行簽名,其不允許非法生成的密文進(jìn)行匹配測(cè)試,之后,接收者通過(guò)認(rèn)證機(jī)構(gòu)認(rèn)證身份信息。此方案抵抗了內(nèi)部的關(guān)鍵字猜測(cè)攻擊,但該方案依賴與簽名技術(shù)和認(rèn)證機(jī)構(gòu)。2017年,Huang等[11]、Lu等[12]、Sun等[13]引入了發(fā)送者的公私鑰,惡意的服務(wù)器和外部的攻擊者因無(wú)法掌握發(fā)送者的私鑰而不能生成合法的關(guān)鍵字密文,但是它們的方案有個(gè)共同的問(wèn)題,增加了發(fā)送者的計(jì)算負(fù)擔(dān)。

1 基礎(chǔ)知識(shí)

定義1雙線性映射

設(shè)p是一素?cái)?shù),G1和G2是兩個(gè)階為p的循環(huán)群,g是G1上的一個(gè)生成元,雙線性映射e:G1×G1→G2,若e滿足如下的性質(zhì):

(1) 雙線性:對(duì)于?a,b∈Zp,有e(ga,gb)=e(g,g)ab成立;

(2) 非退化性:?h∈G1,使得e(h,h)≠1G2,其中1G2是G2中的單位元;

(3) 可計(jì)算性:對(duì)于?g,h∈G1,存在一個(gè)有效的算法計(jì)算e(g,h)。

定義2判定Bilinear Diffie-Hellman Inversion(BDHI)問(wèn)題

給定一個(gè)三元組(g,gx,Z),其中隨機(jī)選取x∈Zp,g是G1中的一個(gè)生成元,要求判斷Z=e(g,g)1/x是否成立。

定義3判定Bilinear Diffie-Hellman(DBDH)問(wèn)題

給定一個(gè)五元組(g,gx,gy,gz,Z),其中隨機(jī)選取x,y,z∈Zp,g是G1中的一個(gè)生成元,要求判斷Z=e(g,g)xyz是否成立。

定義4判定Division Diffie-Hellman(DDH)問(wèn)題

給定一個(gè)四元組(g,gx,gy,Z),其中隨機(jī)選取x,y∈Zp,g是G1中的一個(gè)生成元,要求判斷Z=gx/y是否成立。

2 無(wú)安全信道的關(guān)鍵字搜索方案分析

2.1 Baek等[2]的模型描述

(1)Setup(1k)→{GP}:輸入安全參數(shù)k,產(chǎn)生全局參數(shù)GP。

(2)KeyGenS(GP)→{pkS,skS}:輸入全局參數(shù)GP,產(chǎn)生服務(wù)器的公私鑰pkS,skS。

(3)KeyGenR(GP)→{pkR,skR}:輸入全局參數(shù)GP,產(chǎn)生接收者的公私鑰pkR,skR。

(4)PEKS(GP,pkS,pkR,w)→CT:發(fā)送者對(duì)關(guān)鍵字w進(jìn)行加密產(chǎn)生密文CT,并發(fā)送給云服務(wù)器。

(5)Trapdoor(GP,w,skR,pkS)→Tw:接受者對(duì)關(guān)鍵字w進(jìn)行加密產(chǎn)生陷門Tw,并發(fā)送給云服務(wù)器。

(6)Test(GP,CT,Tw,pkR,sks)→yes,no:云服務(wù)器進(jìn)行匹配算法,判斷密文CT和陷門Tw是否包含相同的關(guān)鍵字。

2.2 內(nèi)部的關(guān)鍵字猜測(cè)攻擊分析

當(dāng)敵手是一個(gè)惡意的云服務(wù)器時(shí),它可以執(zhí)行匹配算法。想要抵抗內(nèi)部的關(guān)鍵字猜測(cè)攻擊需要滿足兩個(gè)條件,一是陷門本身不能泄露關(guān)鍵字的信息,二是服務(wù)器自己不能產(chǎn)生合法的密文。Shao等[10]在Fang等[9]的方案的基礎(chǔ)上進(jìn)行了改進(jìn),通過(guò)對(duì)發(fā)送者的身份進(jìn)行數(shù)字簽名達(dá)到服務(wù)器不能產(chǎn)生合法密文的目的。但是Lu等[12]指出Fang等[9]的方案陷門本身會(huì)泄露關(guān)鍵字的信息,即當(dāng)敵手是惡意的云服務(wù)器時(shí),Fang等[9]的方案不滿足陷門不可區(qū)分性。在Huang等[11]的方案中,在產(chǎn)生關(guān)鍵字密文時(shí)引入了發(fā)送者的私鑰,進(jìn)行授權(quán)加密,但是在其方案中,陷門是固定的,不具有隨機(jī)性。且發(fā)送者也可以計(jì)算出該陷門,他們的方案雖然可以抵抗服務(wù)器進(jìn)行關(guān)鍵字猜測(cè)攻擊,但是引入了一個(gè)新的敵手——發(fā)送者。

為了抵抗服務(wù)器進(jìn)行關(guān)鍵字猜測(cè)攻擊,大部分的方案都增加了發(fā)送者的計(jì)算量,我們引入了一個(gè)身份管理服務(wù)器對(duì)發(fā)送者的身份和關(guān)鍵字進(jìn)行重加密來(lái)減輕發(fā)送者的計(jì)算量,另外,在接收者計(jì)算陷門時(shí),包含了身份管理服務(wù)器的公鑰來(lái)保障了陷門不可區(qū)分性。

3 基于身份的抗內(nèi)部關(guān)鍵字猜測(cè)攻擊的關(guān)鍵字搜索方案

3.1 系統(tǒng)模型

基于身份的關(guān)鍵字搜索方案有四個(gè)實(shí)體,如圖1,分別是數(shù)據(jù)發(fā)送者(DS),身份管理服務(wù)器(MS),云存儲(chǔ)服務(wù)器(CS),數(shù)據(jù)接收者(DR)。

DS首先對(duì)明文數(shù)據(jù)和關(guān)鍵字w進(jìn)行加密。隨后把加密的明文數(shù)據(jù)發(fā)送給CS,把預(yù)加密的關(guān)鍵字

發(fā)送給MS。

MS首先對(duì)發(fā)送者進(jìn)行身份認(rèn)證,若發(fā)送者身份是合法的。則對(duì)關(guān)鍵字和發(fā)送者身份id進(jìn)行重加密,并將結(jié)果發(fā)送給CS。

DR對(duì)關(guān)鍵字和發(fā)送者的身份id進(jìn)行加密生成陷門,并發(fā)送給CS。

CS進(jìn)行匹配算法,若成功則把關(guān)鍵字對(duì)應(yīng)的密文發(fā)送給DR。

在此過(guò)程中,MS,CS都不會(huì)得到關(guān)于關(guān)鍵字的任何信息。

3.2 方案的構(gòu)造

在我們?cè)O(shè)計(jì)的基于身份的關(guān)鍵字搜索方案中,只關(guān)注關(guān)鍵字加密的部分,具體方案如下:

(1)Setup(1k)→{GP}:參數(shù)生成算法進(jìn)行如下設(shè)置:選擇兩個(gè)階為p的兩個(gè)循環(huán)群G1和GT,雙線性映射e:G1×G1→GT,g是G1中的一個(gè)生成元,選擇抗碰撞的哈希函數(shù)H1:{0,1}*→G1,H2:{0,1}*→G1,H3:G2→{0,1}λ。輸出全局參數(shù)GP={G1,GT,p,g,H1,H2,H3}。

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

3.3 計(jì)算一致性驗(yàn)證

H3[e(H1(w),gt)e(H1(id)yβ,gα)]=

H3[ct2e(H2(id)skMβ,pkS)]=C4。

4 安全性證明

我們的安全目標(biāo)是要求身份管理服務(wù)器,云存儲(chǔ)服務(wù)器,外部的攻擊者都不能獲得關(guān)于關(guān)鍵字的任何信息,包括進(jìn)行選擇關(guān)鍵字攻擊(IND-CKA)和關(guān)鍵字猜測(cè)攻擊(IND-KGA)。

引理1 假設(shè)1-BDHI問(wèn)題是困難的,當(dāng)敵手是一個(gè)惡意云服務(wù)器,我們的方案是抵抗選擇關(guān)鍵字攻擊(IND-CKA)安全的。

證明假設(shè)敵手A1是云存儲(chǔ)服務(wù)器時(shí),它最多進(jìn)行qT次陷門詢問(wèn),且有ε的優(yōu)勢(shì)去攻擊方案,則我們可以構(gòu)造一個(gè)算法B有忽略的優(yōu)勢(shì)ε/eqT去解決1-BDHI問(wèn)題。

(1)敵手A1首先宣布一個(gè)想要挑戰(zhàn)的身份id*。

作為陷門進(jìn)行回復(fù)。

(7)猜測(cè)。敵手A1輸出它的猜測(cè)δ′∈{0,1},如果δ′=δ,輸出1,即Z=e(g,g)1/x。否則輸出0。

則

Pr[δ′=δ]=Pr[δ′=δ∧abt]+

Pr[δ′=δ∧abt]=

Pr[δ′=δ|abt]Pr[abt]+

Pr[δ′=δ|abt]Pr[abt]=

引理2 假設(shè)DBDH問(wèn)題是困難的,當(dāng)敵手是一個(gè)外部攻擊者(包括一個(gè)惡意的接收者),則我們的方案是抵抗選擇關(guān)鍵字攻擊(IND-CKA)安全的。

證明假設(shè)敵手A2是一個(gè),它有ε的優(yōu)勢(shì)去攻擊方案。我們可以構(gòu)造一個(gè)算法B也有ε的優(yōu)勢(shì)去解決DBDH問(wèn)題。

(1)敵手A2首先宣布一個(gè)想要挑戰(zhàn)的身份id*。

(4)密文詢問(wèn)1。敵手A2對(duì)任意的關(guān)鍵字和任意身份(wi,idj)進(jìn)行密文詢問(wèn)。算法B運(yùn)行加密算法產(chǎn)生密文CT并發(fā)送給敵手A2。

(7)猜測(cè)。敵手A2輸出它的猜測(cè)δ′∈{0,1},如果δ′=δ,輸出1,即Z=e(g,g)abc。否則輸出0。

引理3 假設(shè)DDH問(wèn)題是困難的,當(dāng)敵手是一個(gè)惡意的云存儲(chǔ)服務(wù)器時(shí),則我們的方案是抵抗關(guān)鍵字猜測(cè)攻擊(IND-KGA)安全的。

證明假設(shè)敵手A3是一個(gè),它最多進(jìn)行qT次陷門詢問(wèn),且有ε的優(yōu)勢(shì)去攻擊方案。我們可以構(gòu)造一個(gè)算法B有ε/eqT的優(yōu)勢(shì)去解決DDH問(wèn)題。

(1)敵手A3首先宣布一個(gè)想要挑戰(zhàn)的身份id*。

(7)猜測(cè)。敵手A3輸出它的猜測(cè)δ′∈{0,1},如果δ′=δ,輸出1,即Z=gab。否則輸出0。

概率分析 和定理1的情況類似,我們可得算法B也有ε/eqT的優(yōu)勢(shì)去解決DDH問(wèn)題。

引理4 假設(shè)1-BDHI問(wèn)題是困難的,當(dāng)敵手是一個(gè)惡意的身份管理服務(wù)器,則我們的方案是抵抗選擇關(guān)鍵字攻擊(IND-CKA)安全的。

5 性能分析

本文實(shí)現(xiàn)了可抵抗內(nèi)部關(guān)鍵字猜測(cè)攻擊的關(guān)鍵字搜索方案。我們和引入發(fā)送者公私鑰的方案[12]進(jìn)行比較,如表1所示。其中P表示指數(shù)運(yùn)算,E表示雙線性對(duì)運(yùn)算,H代表Hash運(yùn)算,n是關(guān)鍵字w的二進(jìn)制展開(kāi)位數(shù)。在表一中,預(yù)加密關(guān)鍵字過(guò)程是發(fā)送者執(zhí)行的,在我們的方案中,發(fā)送者只需要計(jì)算2個(gè)指數(shù)運(yùn)算,1個(gè)雙線性對(duì)運(yùn)算和1個(gè)Hash運(yùn)算,對(duì)比文獻(xiàn)[12],效率得到很大的提高。

表1 方案性能對(duì)比

6 結(jié)論

本文對(duì)原有的帶關(guān)鍵字搜索的公鑰加密方案進(jìn)行改進(jìn),引入發(fā)送者的身份和一個(gè)身份管理服務(wù)器,身份管理服務(wù)器對(duì)所有發(fā)送者的身份進(jìn)行授權(quán),一個(gè)抵抗惡意的云存儲(chǔ)服務(wù)器因其不能產(chǎn)生合法的密文從而不能進(jìn)行關(guān)鍵字猜測(cè)攻擊和選擇關(guān)鍵字攻擊。此外,我們還給出了完整的安全性證明,下一步的工作是把方案部署到云平臺(tái)上,使其應(yīng)用到醫(yī)療和金融等領(lǐng)域。