支持多關(guān)鍵字搜索的條件代理重加密

秦璐璐，周李京，王 敏

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院,江蘇 南京 211100)

0 引 言

云計(jì)算技術(shù)的快速發(fā)展極大地促進(jìn)了互聯(lián)網(wǎng)云服務(wù)的發(fā)展[1]，為了保護(hù)用戶數(shù)據(jù)的隱私性，用戶在云中存儲(chǔ)的數(shù)據(jù)都是以加密的形式存在的。但是，云環(huán)境中存在著大量數(shù)據(jù)共享的情況。由于數(shù)據(jù)擁有者不完全信任云服務(wù)提供商，因此無法將用于解密密文的密鑰發(fā)送到云端，并且再由云端來解密并分享出去。但是，如果數(shù)據(jù)所有者下載密文并對(duì)其進(jìn)行解密，再用需要接收這些消息的用戶的公鑰加密并分享給這些用戶，這無疑給數(shù)據(jù)所有者帶來了很多麻煩，失去了云數(shù)據(jù)共享的意義。這個(gè)問題的一個(gè)很好的解決方案是使用代理重新加密。Blaze等人[2]在1998年首先提出了代理重加密(Proxy Re-Encryption, PRE)的概念，該技術(shù)可以實(shí)現(xiàn)云端密文數(shù)據(jù)的共享，而且是在不泄露數(shù)據(jù)所有者解密密鑰的情況下。

在實(shí)際問題中，數(shù)據(jù)所有者并不希望接收數(shù)據(jù)的用戶解密所有的密文，所以如果數(shù)據(jù)所有者可以選擇由代理重新加密的密文，這當(dāng)然是可取的。Weng等人[3]首次提出了條件代理重加密(Conditional Proxy Re-Encryption, CPRE)的概念，只有滿足特定條件的密文才能被代理轉(zhuǎn)化，對(duì)密文實(shí)現(xiàn)了細(xì)粒度委托。Fang等人[4]提出了一種新的、高效的、滿足匿名條件的CPRE方案，這是Weng等人的遺留問題。隨后，Weng等人[5]又提出了在不需要隨機(jī)預(yù)言機(jī)的情況滿足選擇密文攻擊(Chosen Cipher-text Attack， CCA)安全性的代理重加密。雖然雙線性對(duì)是構(gòu)建PRE方案的一個(gè)很重要的元素，但是它在資源受限的設(shè)備中實(shí)現(xiàn)的速度慢，所以文獻(xiàn)[6-8]又提出了不使用雙線性對(duì)的PRE方案。

Shao等人[9]在2010年首次提出了帶關(guān)鍵字搜索的代理重加密(Proxy Re-Encryption with Keyword Search, PRES)的概念，將公鑰加密與關(guān)鍵字搜索與代理重加密相結(jié)合，并證明該方案是安全的。但是，Shao等人的方案不能抵抗合謀攻擊。Chen等人[10]在2011年指出Shao等人的方案是在犧牲計(jì)算效率的前提下提高了安全性的。2014年，Lee等人[11]改進(jìn)了文獻(xiàn)[10]中的PRES方案，并將它應(yīng)用于存儲(chǔ)外包環(huán)境中，雖然搜索速度有所提高，但方案的安全性卻沒有證明。Guo等人[12]構(gòu)造了一個(gè)有效的單向PRE方案，不使用一次性強(qiáng)不可偽造簽名，并證明該方案是CCA安全的。文獻(xiàn)[13]提出了一種細(xì)粒度訪問控制的PRES方案，以限制用戶的權(quán)限，從而抵抗合謀攻擊。文獻(xiàn)[14]提出了一種新的可證明安全的PRES方案，證明了方案對(duì)適應(yīng)性選擇關(guān)鍵字攻擊具有不可區(qū)分語(yǔ)義安全性，而且在計(jì)算效率上也有所提高。

在目前的PRES方案中，大多數(shù)方案都處理了一個(gè)關(guān)鍵字搜索的問題，在文獻(xiàn)[15-17]中，雖然提出了在加密的數(shù)據(jù)中實(shí)現(xiàn)多個(gè)關(guān)鍵字搜索，但是計(jì)算代價(jià)實(shí)在是太高了。同時(shí)，大部分方案中的代理都能夠轉(zhuǎn)換授權(quán)者的所有的原始密文。在實(shí)際環(huán)境中，希望僅將滿足特定條件的密文轉(zhuǎn)化為受理者公鑰加密的密文[18]。假設(shè)A是銀行的負(fù)責(zé)人，現(xiàn)在僅想讓B閱讀具有關(guān)鍵字“緊急，重要”的郵件，讓C閱讀具有關(guān)鍵字“保險(xiǎn)”的文件，但是在傳統(tǒng)的代理重加密中做不到這一點(diǎn)。Wang等人[19]提出了一種帶聯(lián)合關(guān)鍵字搜索的有約束的代理重加密，但是計(jì)算效率很低。本文引入一種使用滿足條件樹構(gòu)造的帶多關(guān)鍵字搜索的條件代理重加密(Conditional Proxy Re-Encryption with Multi-keyword Search, CPRES)的方案，只有滿足授權(quán)者指定條件的密文，才能由代理進(jìn)一步處理，這種先搜索再重加密的構(gòu)造更加符合實(shí)際環(huán)境，而且提高了計(jì)算效率。

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

1.1 雙線性映射

令G1和G2是具有素?cái)?shù)階p的乘法循環(huán)群，g1和g2是G1的生成元。e:G1×G1→G2是具有以下性質(zhì)的雙線性映射：

非退化性：e(g1,g2)≠1。

可計(jì)算性：對(duì)任意的g1,g2∈G1，存在高效的算法計(jì)算e(g1,g2)。

1.2 3-QDBDH假設(shè)

e:G1×G1→G2是一個(gè)雙線性對(duì)，g是G1的生成元，x,y∈Zp。敵手B解決3-QDBDH問題的優(yōu)勢(shì)定義為：

1.3 滿足訪問樹

設(shè)T是表示訪問結(jié)構(gòu)的樹，樹的每個(gè)非葉節(jié)點(diǎn)代表一個(gè)陷門[20]。如果numx是節(jié)點(diǎn)x的子節(jié)點(diǎn)數(shù)，kx是其陷門值，則kx∈(0,numx]。當(dāng)kx=1時(shí)，陷門為或門，當(dāng)kx=numx時(shí)，陷門為和門。為了便于使用訪問樹，定義函數(shù)att(x)，不過只有當(dāng)x是葉節(jié)點(diǎn)并且表示與葉節(jié)點(diǎn)x相關(guān)聯(lián)的條件時(shí)才定義[21]。以Tx表示根植于節(jié)點(diǎn)x的T的子樹，如果一組關(guān)鍵字W滿足訪問樹Tx，則將其表示為Tx(W)=1。遞歸地計(jì)算Tx(W)。如果x是一個(gè)非葉節(jié)點(diǎn)，則對(duì)節(jié)點(diǎn)x所有的子節(jié)點(diǎn)x′計(jì)算Tx′(W)，當(dāng)且僅當(dāng)至少kx個(gè)子節(jié)點(diǎn)返回1時(shí)，Tx(W)才返回1。如果x是葉節(jié)點(diǎn)，則當(dāng)且僅當(dāng)att(x)∈W時(shí)，Tx(W)才返回1。

2 支持多關(guān)鍵字搜索的條件代理重加密方案的定義及其構(gòu)造

2.1 方案的定義

CPRES方案由如下7個(gè)多項(xiàng)式時(shí)間算法組成：

系統(tǒng)建立GlobSetup(1K)：輸入安全參數(shù)1K，生成系統(tǒng)參數(shù)GlobSetup(1K)→param。

密鑰生成KeyGen(1K)：系統(tǒng)為用戶i生成公私鑰對(duì)Keygen(param)→(pki,ski)。

條件重加密密鑰生成ReKeyGen(ski,W,pkj)：輸入發(fā)送方的私鑰ski，條件關(guān)鍵字W和接收方的公鑰pkj，生成條件重加密密鑰ReKeyGen(ski,W,pkj)→rki→j。

陷門生成算法Trapdoor(ski,W)：由發(fā)送方i執(zhí)行。輸入私鑰ski和條件關(guān)鍵字W，輸出條件關(guān)鍵字W的陷門Trapdoor(ski,W)→Tw。

加密算法Enc(pki,W,m):輸入用戶i公鑰pki，消息m∈M，條件關(guān)鍵字W，此算法生成原始密文Enc(pki,W,m)→Ci。

重加密算法ReEnc(Ci,rki→j)：輸入重加密密鑰rki→j和密文Ci，重加密算法ReEnc輸出用公鑰pkj加密的重加密密文Cj。

解密Dec(Cj,skj)：輸入公鑰pkj下的密文Cj和對(duì)應(yīng)的私鑰skj，輸出消息m或⊥。

2.2 安全模型

支持多關(guān)鍵字搜索的條件代理重加密方案的選擇密文安全性可通過敵手B和挑戰(zhàn)者C之間的游戲來定義[22]：

系統(tǒng)建立：挑戰(zhàn)者C模擬算法Globstepup(1K)，生成系統(tǒng)參數(shù)param并發(fā)送給敵手B。

第1階段：敵手B可以詢問C以下的預(yù)言機(jī)：

未攻陷密鑰詢問Opk：挑戰(zhàn)者運(yùn)行KeyGen(1K)獲得(pk,sk)，但是只把pk返回給敵手。

攻陷密鑰詢問Osk：挑戰(zhàn)者運(yùn)行KeyGen(1K)獲得(pk,sk)，把(pk,sk)返回給敵手B。

當(dāng)進(jìn)行重加密密鑰Ork、重加密Ore、解密Odec詢問時(shí)，要求輸入的密鑰都是在之前的Opk或者Osk中產(chǎn)生。

挑戰(zhàn)階段：當(dāng)敵手決定結(jié)束階段1，它輸出2個(gè)等長(zhǎng)的明文m0,m1∈M，條件關(guān)鍵字W和目標(biāo)公鑰pk*。限制是pk*由Opk生成，而且如果敵手以(pk*,pkj,W)詢問Ork，則不能以pkj詢問Osk。挑戰(zhàn)者選擇一個(gè)隨機(jī)比特b∈{0,1}，設(shè)置C*=Enc(pk*,W,mb)返回給敵手。

第2階段：和第1階段相同，限制是如果敵手以(Ci,pk*,pkj,W)詢問Ore，則pkj沒有詢問過Osk。而且敵手也不能對(duì)(Ci,pk*,W)做解密詢問。

猜測(cè)：敵手B輸出猜測(cè)b′∈{0,1}，若b′=b，則B贏得游戲。敵手B獲勝的優(yōu)勢(shì)為Adv=|Pr [b=b′-1/2]|。

2.3 方案的具體描述

Globstepup(1K)：全局設(shè)置算法以安全參數(shù)1K作為輸入，p是長(zhǎng)度為K的參數(shù)，G1和G2是素?cái)?shù)階為p的循環(huán)群，g是G1中的生成元，e:G1×G1→G2是一個(gè)雙線性映射。哈希函數(shù)H:{0,1}n→G1，其中n根據(jù)K確定，消息空間M={0,1}n。Sig=(G,S,V)是一個(gè)強(qiáng)大且不可偽造的一次性簽名方案。最后輸出系統(tǒng)全局參數(shù)param=(p,G1,G2,e,g,n,H,Sig)。

ReKeyGen(ski,W,pkj)：輸入用戶i的私鑰ski、用戶j的公鑰pkj、條件關(guān)鍵字W，并輸出重加密密鑰rki→j=H(pkj1/ski,W)。

Trapdoor(ski,W)：根據(jù)輸入，調(diào)用滿足訪問樹進(jìn)行陷門搜索，當(dāng)且僅當(dāng)TDw=1時(shí)，用戶i將陷門TDw和條件重加密密鑰rki→j發(fā)送給代理，否則返回。

Enc(pki,W,m)：輸入用戶i的公鑰pki、條件關(guān)鍵字W和消息m∈M。

1)選擇一對(duì)一次簽名的公私鑰對(duì)G(1K)→(svk,ssk)，并設(shè)置A=svk。

3)運(yùn)行簽名算法S(ssk,(C,D,E))，要簽名的信息元組為(C,D,E)，簽名結(jié)果表示成S。

4)輸出密文Ci=(A,B,C,D,E,S)。

ReEnc(Ci,rki→j)：輸入一個(gè)重加密密鑰rki→j=H(pkj1/ski,W)和密文Ci=(A,B,C,D,S)。

1)首先執(zhí)行以下步驟：

①運(yùn)行V(A,(C,D,E),S)，以驗(yàn)證簽名S是否是在公鑰A下加密的消息(C,D,E)的簽名。

②檢查e(D,pki)=e(B,gA)。

③這些檢查中任何一個(gè)失敗，則輸出0，否則輸出1。

2)計(jì)算B′=e(g,g)r·w，輸出一個(gè)新的密文Cj=(A,B′,C,D,E,S)。

Dec(skj,Cj)：重加密密文解密。輸入私鑰skj和密文Cj=(A,B′,C,D,E,S)，首先驗(yàn)證V(A,(C,D,E),S)=1和e(D,gw)=e(g,g)A·B′，如果這2個(gè)等式都為真，就輸出m=C/B′1/w；若有一個(gè)等式不成立，就輸出⊥。原始密文解密：輸入私鑰ski和密文Ci=(A,B,C,D,E,S)，輸出m=C/e(B,g)1/ski。

3 方案分析

3.1 正確性分析

密文的正確性：

對(duì)于重加密密文Cj，C/B′1/w=e(g,g)r·m/e(g,g)r·w·1/w=m；

所以密文都是有效的。

3.2 安全性分析

在隨機(jī)預(yù)言模型下將方案的安全性規(guī)約到3-QDBDH問題，證明支持多關(guān)鍵字搜索的條件代理重加密方案是滿足選擇密文攻擊不可區(qū)分(Indistinguishability against Chosen Ciphertext Attack, IND-CCA)安全性的。

本文的密文不可區(qū)分性的證明是基于3-QDBDH困難性問題的。給定一個(gè)3-QDBDH實(shí)例(g,ga,ga2,ga3,gb)，然后將ga、gb分別嵌入到發(fā)送者的公鑰pki和挑戰(zhàn)密文C中，將敵手的優(yōu)勢(shì)規(guī)約到3-QDBDH困難性問題上，證明出該方案滿足IND-CCA安全性。

3.3 性能分析

將本文提出的CPRES方案與文獻(xiàn)[14]和文獻(xiàn)[19]提出的2個(gè)有代表性的PRES方案進(jìn)行比較。設(shè)Tp為一個(gè)雙線性配對(duì)運(yùn)算，Te為一個(gè)模指數(shù)運(yùn)算，比較結(jié)果如表1所示。

表1 方案性能比較

對(duì)比內(nèi)容文獻(xiàn)[14]方案文獻(xiàn)[19]方案本文方案加密2Tp+Te6TeTp+3Te重加密Tp+Te2Tp+Te2Tp+Te解密Tp2Tp+5Te2Tp+3Te困難假設(shè)HDHq-BDHI3-QDBDH安全性CKAWCCACCA

由表1可知，本文方案在計(jì)算代價(jià)上明顯低于文獻(xiàn)[19]方案，和文獻(xiàn)[14]方案在計(jì)算代價(jià)上不相上下。但本文利用滿足訪問樹實(shí)現(xiàn)了多關(guān)鍵字搜索，并且該方案是先搜索后重加密，也更具有實(shí)用性，因此本文的方案優(yōu)于文獻(xiàn)[14]和文獻(xiàn)[19]的方案。

4 CPRES的應(yīng)用

目前，對(duì)數(shù)據(jù)加密是保護(hù)數(shù)據(jù)隱私安全的一種重要的方法，但是只要一個(gè)數(shù)據(jù)集包括了敏感數(shù)據(jù)，這整個(gè)數(shù)據(jù)集都會(huì)被加密[23]。本文提出的CPRES方案對(duì)解決實(shí)際環(huán)境問題起著很大作用。比如在金融業(yè)中，不同職責(zé)的部門只能閱讀關(guān)于自己職責(zé)所在的數(shù)據(jù)信息；在政府機(jī)關(guān)中，不同部門只能閱讀需要處理的公文，這種先搜索后重加密的結(jié)構(gòu)既保護(hù)了數(shù)據(jù)隱私，也提高了數(shù)據(jù)利用率。

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

本文介紹了支持多關(guān)鍵字搜索的代理重加密的概念，提出了一種特定的CPRES方案，并將其效率與以前的經(jīng)典方案進(jìn)行了比較。此外，還給出了CPRES在金融業(yè)等行業(yè)中的應(yīng)用。但是支持多關(guān)鍵字搜索的代理重加密仍然有一些問題需要解決，例如設(shè)計(jì)不使用雙線性對(duì)的CPRES方案和旨在證明在標(biāo)準(zhǔn)模型中安全的CPRES方案。