云計(jì)算中基于身份的雙服務(wù)器密文等值判定協(xié)議

吳黎兵 張宇波 何德彪

1(軟件工程國家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)) 武漢 430072) 2(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072) (wu@whu．edu．cn)

2017-06-11；

2017-07-28

國家自然科學(xué)基金項(xiàng)目(61472287)；湖北省自然科學(xué)基金重點(diǎn)項(xiàng)目(2015CFA068) This work was supported by the National Natural Science Foundation of China (61472287) and the Key Program of Natural Science Foundation of Hubei Province of China (2015CFA068).

何德彪(hedebiao@whu.edu.cn)

云計(jì)算中基于身份的雙服務(wù)器密文等值判定協(xié)議

吳黎兵1,2張宇波2何德彪1,2

1(軟件工程國家重點(diǎn)實(shí)驗(yàn)室(武漢大學(xué)) 武漢 430072)2(武漢大學(xué)計(jì)算機(jī)學(xué)院 武漢 430072) (wu@whu．edu．cn)

隨著云存儲的快速普及以及公眾隱私保護(hù)意識的提升，越來越多的隱私數(shù)據(jù)被加密存儲在云上.因而，如何對密文數(shù)據(jù)特別是采用公鑰密碼體制加密的數(shù)據(jù)進(jìn)行高效檢索成為了一個重要研究內(nèi)容.帶密文等值判定的公鑰加密協(xié)議是其中一種檢索方法,它可以在不泄漏明文內(nèi)容的情況下判定2段密文對應(yīng)的明文是否相同.最近，一系列帶密文等值判定的公鑰加密協(xié)議被提出.然而，在這些協(xié)議中，只用了一個服務(wù)器來執(zhí)行等值判定操作,不能抵抗惡意服務(wù)器的內(nèi)部關(guān)鍵字猜測攻擊.為了解決這個問題，首次提出了基于雙服務(wù)器的帶密文等值判定的公鑰加密協(xié)議，并在隨機(jī)預(yù)言機(jī)模型下證明了它的安全性.同時，也對設(shè)計(jì)的協(xié)議進(jìn)行了性能分析，分析表明:該協(xié)議適合資源受限的移動設(shè)備.

等值判定；基于身份加密；云計(jì)算；雙服務(wù)器；可搜索加密

近年來，隨著云計(jì)算的快速發(fā)展和普及，越來越多的用戶將自己的數(shù)據(jù)存放在云端(如Dropbox、亞馬遜云、阿里云、百度云等).數(shù)據(jù)上傳到云端后，用戶可以通過網(wǎng)絡(luò)遠(yuǎn)程操作自己的數(shù)據(jù)(包括新增、修改、刪除、檢索).同時，為了保護(hù)用戶的數(shù)據(jù)隱私，數(shù)據(jù)上傳到云端之前會進(jìn)行加密.但這使得數(shù)據(jù)檢索，甚至是在同一用戶上傳的數(shù)據(jù)中檢索變得困難.解決方法之一是將所有數(shù)據(jù)下載下來，解密之后再進(jìn)行檢索.顯然，此方法在數(shù)據(jù)量大、網(wǎng)絡(luò)帶寬小、響應(yīng)時延要求高的環(huán)境中不具有可行性.另一種解決方法是使用可搜索加密(searchable encryption)技術(shù).

可搜索加密技術(shù)是一種允許第三方對用戶上傳的密文數(shù)據(jù)進(jìn)行檢索，同時不會泄漏除搜索模式和搜索結(jié)果以外的任何信息的技術(shù).可分為可搜索對稱加密和可搜索公鑰加密技術(shù).前者適合對用戶自己擁有的數(shù)據(jù)進(jìn)行加密；后者可以搜索不同用戶用不同公鑰加密的數(shù)據(jù)，由Boneh等人首次提出[1].隨后，很多相關(guān)的研究成果陸續(xù)被發(fā)布[2-11];最近，一些新型的帶密文等值判定的可搜索公鑰加密方案[12-17]被提出.但是這些方案都是基于單服務(wù)器的，容易遭受內(nèi)部關(guān)鍵字猜測攻擊.

Fig. 1 A typical MHSN scenario圖1 典型的移動健康社交網(wǎng)絡(luò)場景

為此，我們設(shè)計(jì)了一個基于雙服務(wù)器的帶密文等值判定的公鑰加密協(xié)議(dual server identity-based encryption scheme with equality test, DS-IBEET).該協(xié)議的典型應(yīng)用場景如圖1所示. 在一個移動健康社交網(wǎng)絡(luò)(MHSN)中，用戶(比如病人)想要通過醫(yī)療服務(wù)器和其他擁有相同癥狀的人建立聯(lián)系，同時不泄漏他們的隱私信息.例如，Alice和Bob是2個有相同癥狀的病人，他們彼此不認(rèn)識，但是想要建立聯(lián)系，以交流病情或相互鼓勵. Alice用她醫(yī)生的公鑰IDDA加密她的癥狀信息得到(IDA,IBEET(IDDA,Symptom))生成Symptom的陷門tdA， 發(fā)送(IDA,IBEET(IDDA,Symptom),tdA)給服務(wù)器SA.同理，Bob發(fā)送(IDB,IBEET(IDDB,Symptom),tdB))給服務(wù)器SA.服務(wù)器SA首先進(jìn)行初步判定，判定結(jié)果再發(fā)送給服務(wù)器SB，SB完成密文等值判定，可以得到Alice和Bob有相同的癥狀Symptom，但是服務(wù)器SA和SB都不知道Symptom的具體內(nèi)容是什么.最后，服務(wù)器SB將判定結(jié)果發(fā)送給Alice和Bob，讓他們建立聯(lián)系.顯然，此協(xié)議也適用于多用戶環(huán)境.

本文的主要貢獻(xiàn)有3個方面:

1) 首次提出基于雙服務(wù)器的密文等值判定協(xié)議，解決了傳統(tǒng)的單服務(wù)器環(huán)境不能抵抗惡意服務(wù)器攻擊的問題;

2) 在隨機(jī)預(yù)言機(jī)模型下證明了該協(xié)議的安全性;

3) 分析了該協(xié)議的性能，表明其可以適用于資源受限的移動設(shè)備.

1 相關(guān)工作

Yang等人首次提出帶密文等值判定功能的公鑰加密協(xié)議(public key encryption with equality test, PKEET)[13]，用來比較2段密文對應(yīng)的明文是否相同，且在比較過程中不泄露任何明文信息.然而，該協(xié)議沒有對參與密文等值判定的用戶進(jìn)行授權(quán)，任何用戶都可以進(jìn)行密文等值判定；為了解決這一問題，Tang提出了一種改進(jìn)的帶密文等值判定的公鑰加密協(xié)議(FG-PKEET)[12]，該協(xié)議僅允許獲得授權(quán)的用戶在可信第三方的幫助下執(zhí)行細(xì)粒度密文等值判定，即用戶可以通過授權(quán)來控制誰能對自己的密文進(jìn)行等值判定,控制誰的密文可以和自己的密文進(jìn)行比對；隨后，為了抵抗離線消息恢復(fù)攻擊，Tang將FG-PKEET擴(kuò)展到了雙代理版本(ADG-PKEET)[15]；同時，為了達(dá)到粗粒度控制的目的，Tang提出了AoN-PKEET協(xié)議[14]，在該協(xié)議中，用戶一旦授權(quán)第三方代理進(jìn)行密文等值判定，則該用戶的所有密文都能被該代理用來進(jìn)行等值判定.

Ma等人提出了一個帶委托密文等值判定的公鑰加密協(xié)議(PKE-DET)[16]，該協(xié)議中的等值判定操作被委托給第三方；Huang等人提出了一個帶密文等值判定授權(quán)的公鑰加密協(xié)議[17]，該協(xié)議的授權(quán)方式分為對用戶授權(quán)和對密文授權(quán)；對用戶授權(quán)模式下，測試者可以對授權(quán)用戶的所有密文進(jìn)行等值判定查詢，對密文授權(quán)模式下，測試者只能對授權(quán)的特定密文進(jìn)行等值判定查詢；隨后，Ma等人又提出了一種支持彈性授權(quán)的帶密文等值判定的公鑰加密方案[18]，該方案擁有4種類型的授權(quán)方式.

上述方案都是基于傳統(tǒng)公鑰加密的方案，當(dāng)用戶數(shù)量較大時，存在證書管理問題.為了解決這個問題，Ma首次提出了一種基于身份的帶密文等值判定的公鑰加密方案[19]，隨后，在Ma的協(xié)議基礎(chǔ)上，Wu設(shè)計(jì)了一個更高效的方案[20]，該方案減少了HashToPoint的使用.

然而，在已有方案中，不論是傳統(tǒng)的公鑰加密方案還是基于身份的加密方案，都不能抵抗惡意服務(wù)器的內(nèi)部關(guān)鍵字猜測攻擊.特別是在關(guān)鍵字?jǐn)?shù)量有限的情況下，攻擊更容易成功.

2 數(shù)學(xué)基礎(chǔ)

在本節(jié)中，我們主要介紹雙線性對和CDH(computational Diffie-Hellman problem)困難問題.

2.1雙線性對

設(shè)G1是加法循環(huán)群，G2是乘法循環(huán)群，且G1、G2的階都為素?cái)?shù)q.P是群G1的一個生成元.如果e:G1×G1→G2滿足3個條件，則稱其為雙線性對.

3) 可計(jì)算性.對于任意2個點(diǎn)Q,R∈G1，e(Q,R)是易計(jì)算的.

2.2CDH問題

設(shè)P是群G1的一個生成元，x,y∈Z*是2個未知隨機(jī)數(shù)，若已知{P,xP,yP}，則在多項(xiàng)式時間內(nèi)計(jì)算出xyP是困難的.

3 模 型

3.1系統(tǒng)模型

本文的系統(tǒng)模型如圖2所示.系統(tǒng)有5個參與者:

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

1) 密鑰生成中心.負(fù)責(zé)生成系統(tǒng)主密鑰、醫(yī)生和病人的公私鑰對以及系統(tǒng)參數(shù)，并將醫(yī)生和病人的私鑰通過安全信道分別發(fā)送給他們.

2) 病人.病人需要先在密鑰生成中心注冊，獲得私鑰.將隱私信息(例如癥狀)加密后發(fā)送給服務(wù)器.同時，發(fā)送一個陷門給服務(wù)器，用來執(zhí)行等值判定操作.病人加密的信息只有他的醫(yī)生可以解密.

3) 醫(yī)生.醫(yī)生需要先在密鑰生成中心注冊，獲得私鑰.醫(yī)生可以解密自己的病人加密的信息.

4) 前服務(wù)器SF.負(fù)責(zé)接收病人的密文等值判定請求，并將獲得的中間結(jié)果發(fā)送給服務(wù)器SB.

5) 后服務(wù)器SB.負(fù)責(zé)接收服務(wù)器SF的中間結(jié)果，完成后續(xù)密文等值判定工作，并返回最終的結(jié)果給病人.

3.2協(xié)議架構(gòu)

協(xié)議包含7個算法：

1) 初始化算法Setup(1k).輸入安全參數(shù)k，產(chǎn)生系統(tǒng)參數(shù)params.

2) 密鑰生成算法KeyGen(params).輸入系統(tǒng)參數(shù)和身份ID，輸出解密鑰dk.

3) 陷門生成算法TrapGen(dk).此算法由用戶執(zhí)行，根據(jù)解密鑰生成陷門td.

4) 加密算法Encrypt(params,dk,M).此算法由用戶執(zhí)行.用戶對明文M進(jìn)行加密得到密文C.

5) 解密算法Decrypt(params,dk,C).此算法由用戶執(zhí)行，對密文C進(jìn)行解密.

3.3安全模型

我們分別定義DS-IBEET協(xié)議面向惡意前服務(wù)器和惡意后服務(wù)器的安全模型.

3.3.1 惡意前服務(wù)器

本節(jié)我們定義惡意前服務(wù)器下的安全性.包括在選擇關(guān)鍵字攻擊下的IBEET密文語義安全和關(guān)鍵字猜測攻擊下的陷門不可區(qū)分性.

1) 選擇關(guān)鍵字攻擊下的語義安全(SS-CKA).選擇關(guān)鍵字攻擊下的語義安全保證了敵手不能通過關(guān)鍵字對應(yīng)的IBEET密文來區(qū)分關(guān)鍵字.即IBEET密文不會泄漏對應(yīng)關(guān)鍵字的任何信息.我們用以下游戲來定義選擇關(guān)鍵字攻擊下的密文語義安全模型.

② 查詢階段1(Query-phase-Ⅰ).敵手可以適應(yīng)性地對任意關(guān)鍵字和任意IBEET密文向挑戰(zhàn)者發(fā)送查詢請求.挑戰(zhàn)者返回0或者1給敵手.

③ 挑戰(zhàn)(challenge).敵手發(fā)送2個關(guān)鍵字(kw0,kw1)給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}并計(jì)算：

④ 查詢階段2(Query-phase-Ⅱ).敵手繼續(xù)查詢除了挑戰(zhàn)關(guān)鍵字(kw0,kw1)之外的任意關(guān)鍵字和IBEET密文.挑戰(zhàn)者返回0或者1給敵手.

⑤ 輸出(output).最后，敵手輸出它對b的猜測b′∈{0,1}.如果b=b′，則敵手贏得這個游戲.

我們稱上述游戲中的惡意服務(wù)器A為SS-CKA敵手，定義它贏得游戲的優(yōu)勢為

2) 關(guān)鍵字猜測攻擊下的不可區(qū)分性(IND-KGA).在這個安全模型中，陷門不會泄漏關(guān)鍵字的任何信息給惡意前服務(wù)器.我們用以下游戲定義安 全模型：

② 查詢階段1(Query-phase-Ⅰ).敵手可以適應(yīng)性的對任意關(guān)鍵字和密文向挑戰(zhàn)者發(fā)送查詢請求.挑戰(zhàn)者返回0或者1給敵手.

③ 挑戰(zhàn)(challenge).敵手發(fā)送2個關(guān)鍵字(kw0,kw1)給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}并計(jì)算：

④ 查詢階段2(Query-phase-Ⅱ).敵手繼續(xù)查詢除了挑戰(zhàn)關(guān)鍵字(kw0,kw1)之外的任意關(guān)鍵字和IBEET密文.挑戰(zhàn)者返回0或者1給敵手.

⑤ 輸出(output).最后，敵手輸出它對b的猜測b′∈{0,1}.如果b=b′，則敵手贏得這個游戲.

我們稱上述游戲中的惡意服務(wù)器A為IND-KGA敵手，定義它贏得游戲的優(yōu)勢為

3.3.2 惡意后服務(wù)器

惡意后服務(wù)器的安全模型和惡意前服務(wù)器的安全模型類似.

3) 關(guān)鍵字猜測攻擊下的不可區(qū)分性(IND-KGA-Ⅱ).為了保證惡意服務(wù)器SB不能從內(nèi)部測試狀態(tài)信息獲取關(guān)鍵字的任何信息，我們通過如下游戲定義安全模型：

② 查詢階段1(Query-phase-Ⅰ).敵手可以適應(yīng)性地對任意關(guān)鍵字和密文的內(nèi)部測試狀態(tài)向挑戰(zhàn)者發(fā)送查詢請求.挑戰(zhàn)者返回(XA,XB)給敵手.

③ 挑戰(zhàn)(challenge).敵手發(fā)送3個不同的關(guān)鍵字(kw0,kw1,kw2)給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇{b1,b2}?{0,1,2}并計(jì)算:

我們稱上述游戲中的惡意后服務(wù)器A為IND-KGA-Ⅱ敵手，定義它贏得游戲的優(yōu)勢為

在以上游戲中，b1和b2可以相等.此時，敵手可以獲知IBEET密文和陷門對應(yīng)的關(guān)鍵字是相同的，而敵手的攻擊目標(biāo)是猜測3個關(guān)鍵字(kw0,kw1,kw2)中哪2個被挑戰(zhàn)者選定了.根據(jù)以上5個游戲，我們給出DS-IBEET協(xié)議的安全性定義如下：

4 基于身份的雙服務(wù)器等值判定協(xié)議

4.1協(xié)議具體內(nèi)容

該協(xié)議由7個算法組成：初始化算法、密鑰生成算法、陷門生成算法、加密算法、解密算法、前服務(wù)器測試算法、后服務(wù)器測試算法.

4.1.1 初始化算法Setup(1k)

4.1.2 密鑰生成算法KeyGen(Params,s1,s2)

4.1.3 陷門生成算法TrapGen(Params,s1)

4.1.4 加密算法Encrypt(Params,M)

4.1.5 解密算法Decrypt(Params,C)

4.1.7 后服務(wù)器測試算法TestSB(CA,XA,CB,XB)

此算法由服務(wù)器SB執(zhí)行，計(jì)算并比較下列等式是否成立：

若成立，則輸出1，表明MA=MB，否則輸出0.

4.2協(xié)議正確性分析

同理:

由于:

5 安全性分析

本節(jié)我們分析上述協(xié)議的安全性.

定理1. 本文提出的DS-IBEET協(xié)議在選擇關(guān)鍵字攻擊下是語義安全的.

上述定理能夠通過下述引理1和引理2證明.

證明. 首先定義下列游戲：

Game0. 這是針對惡意前服務(wù)器的初始版本SS-CKA游戲.

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T).此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh.返回h(T).

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密:

C←Encrypt(Params,kw),

其中：

并將〈kw,C〉添加到列表LEnc中，挑戰(zhàn)者返回C給敵手.

3) 挑戰(zhàn)(challenge).敵手A選擇2個關(guān)鍵字(kw0,kw1)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}并計(jì)算密文Ckwb，將Ckwb發(fā)送給敵手A.

4) 查詢階段2(Query-phase-Ⅱ).此階段與查詢階段1一致.

5) 輸出(output).最終，敵手A輸出對b的猜測值b′.如果b=b′，則A贏得游戲.

Game1. Game1與Game0基本相同，區(qū)別在于，在Game1中，挑戰(zhàn)者用隨機(jī)數(shù)W1替換了Hash函數(shù)h:GT→{0,1}*.具體游戲過程如下：

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T): 此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh.返回h(T).

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密：

C←Encrypt(Params,kw),

其中：

挑戰(zhàn)者返回C給敵手.

3) 挑戰(zhàn)(challenge).敵手A選擇2個關(guān)鍵字(kw0,kw1)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}并計(jì)算密文Ckwb，將Ckwb發(fā)送給敵手A.

4) 查詢階段2(Query-phase-Ⅱ).此階段與查詢階段1一致，但不可查詢(kw0,kw1)的密文，若kw=kw0或者kw=kw1，則返回⊥并結(jié)束游戲，記為事件Event1.

5) 輸出(output).最終，敵手A輸出對b的猜測值b′.如果b=b′，則A贏得游戲.

根據(jù)隨機(jī)預(yù)言模型(random oracle model)的性質(zhì)以及Difference Lemma[21]，在事件Event1不發(fā)生的情況下，敵手A贏得游戲Game1的優(yōu)勢滿足：

由于H2是隨機(jī)預(yù)言機(jī)，W1是隨機(jī)選擇的，且在查詢過程中未返回給敵手，故根據(jù)CDH假設(shè)，Pr[Event1]是可忽略的.

Game2. Game2與Game1基本相同，區(qū)別在于，在Game2中，挑戰(zhàn)者用隨機(jī)數(shù)W2替換了C3.具體游戲過程如下：

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T): 此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh.返回h(T).

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密：

C←Encrypt(Params,kw),

其中：

挑戰(zhàn)者返回C給敵手.

3) 挑戰(zhàn)(challenge).敵手A選擇2個關(guān)鍵字(kw0,kw1)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇b∈{0,1}并計(jì)算密文Ckwb，將Ckwb發(fā)送給敵手A.

4) 查詢階段2(Query-phase-Ⅱ).此階段與查詢階段1一致，但不可查詢(kw0,kw1)對應(yīng)的密文，若kw=kw0或者kw=kw1，則返回⊥并結(jié)束游戲，記為事件Event2.

5) 輸出(output).最終，敵手A輸出對b的猜測值b′.如果b=b′，則A贏得游戲.

根據(jù)隨機(jī)預(yù)言模型的性質(zhì)以及Difference Lemma[21]，在事件Event2不發(fā)生的情況下，敵手A贏得游戲Game2的優(yōu)勢滿足：

由于W2是隨機(jī)選擇的，且在查詢過程中未返回給敵手，故根據(jù)CDH假設(shè)，Pr[Event2]是可忽略的.

證畢.

證明. 引理 2的證明過程與引理 1類似.這里不再贅述.

定理2. 我們的DS-IBEET協(xié)議在關(guān)鍵字猜測攻擊下是不可區(qū)分的.

上述定理可以通過引理3、引理4和引理5證明.

證畢.

證明. 引理 4的證明過程與引理 3類似.這里不再贅述.

證明. 首先定義下列游戲：

Game0.這是針對惡意后服務(wù)器的初始版本游戲.

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T): 此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh.返回$h(T)$.

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密：

C←Encrypt(Params,kw),

其中：

并將〈kw,C〉添加到列表LEnc中.挑戰(zhàn)者返回C給敵手.

3) 挑戰(zhàn)(challenge).敵手A選擇3個不同的關(guān)鍵字(kw0,kw1,kw2)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇{b1,b2}?{0,1,2}并計(jì)算：

Game1. Game1與Game0基本相同，區(qū)別在于，在Game1中，挑戰(zhàn)者用隨機(jī)數(shù)W1,W2替換了Hash函數(shù)H2:GT→G1.具體游戲過程如下：

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T): 此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh,返回h(T).

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密：

C←Encrypt(Params,kw),

其中：

挑戰(zhàn)者返回C給敵手.

3) 挑戰(zhàn)(challenge).敵手A選擇3個不同的關(guān)鍵字(kw0,kw1,kw2)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇{b1,b2}?{0,1,2}并計(jì)算：

4) 查詢階段2(Query-phase-Ⅱ).此階段與查詢階段1一致，但不可查詢(kw0,kw1)的密文，若kw=kw0或者kw=kw1，則返回⊥并結(jié)束游戲，記為事件Event3.

根據(jù)隨機(jī)預(yù)言模型的性質(zhì)以及Difference Lemma[21]，在事件Event3不發(fā)生的情況下，敵手A贏得游戲Game1的優(yōu)勢滿足：

由于W1,W2是隨機(jī)選擇的，且在查詢過程中未返回給敵手，故根據(jù)CDH假設(shè)，Pr[Event3]是可忽略的.

Game2. Game2與Game1基本相同，區(qū)別在于，在Game2中，挑戰(zhàn)者用隨機(jī)數(shù)W3,W4替換了XA,XB.具體游戲過程如下：

2) 查詢階段1(Query-phase-Ⅰ).敵手向挑戰(zhàn)者發(fā)送下列查詢：

①h-query(T): 此預(yù)言機(jī)維護(hù)一個初始為空的列表Lh，給定參數(shù)T，隨機(jī)選擇H∈G1并將〈T,H〉添加到列表Lh.返回h(T).

⑤Encrypt-query(Params,kw).此預(yù)言機(jī)維護(hù)一個初始為空的列表LEnc=〈kw,C〉，給定參數(shù)和明文，對明文關(guān)鍵字kw進(jìn)行加密：

C←Encrypt(Params,kw),

其中：

挑戰(zhàn)者返回C給敵手.

XA=W3，
XB=W4.

3) 挑戰(zhàn)(challenge).敵手A選擇3個不同的關(guān)鍵字(kw0,kw1,kw2)，并將它們發(fā)送給挑戰(zhàn)者，挑戰(zhàn)者隨機(jī)選擇{b1,b2}?{0,1,2}并計(jì)算:

4) 查詢階段2(Query-phase-Ⅱ).此階段與查詢階段1一致，但不可查詢(kw0,kw1)的密文，若kw=kw0或者kw=kw1，則返回⊥并結(jié)束游戲，記為事件Event4.

根據(jù)隨機(jī)預(yù)言模型的性質(zhì)以及Difference Lemma[21]，在事件Event4不發(fā)生的情況下，敵手A贏得游戲Game2的優(yōu)勢滿足：

由于W3,W4是隨機(jī)選擇的，且在查詢過程中未返回給敵手，故根據(jù)CDH假設(shè)，Pr[Event4]是可忽略的.

證畢.

6 性能分析

本文從計(jì)算開銷和通信開銷2個方面對我們設(shè)計(jì)的協(xié)議的性能進(jìn)行分析.

為了對協(xié)議的性能進(jìn)行評估，我們在阿里巴巴的ECS云主機(jī)上調(diào)用 MIRACL庫[22]，獲得一些基本密碼操作的執(zhí)行時間.云主機(jī)的配置環(huán)境如表1所示，橢圓曲線參數(shù)如表2所示.我們使用Tate對，大素?cái)?shù)p為512 b，大素?cái)?shù)階q為160 b.設(shè)M,Exp,BP,H,h和PA分別表示標(biāo)量乘法、群G1上的模指數(shù)運(yùn)算、雙線性對運(yùn)算、HashToPoint運(yùn)算、普通Hash運(yùn)算和點(diǎn)加運(yùn)算.這些基本操作的執(zhí)行時間如表3所示.

Table 1 System Information

Table 2 Parameters of Elliptic Curve

Table 3 Execution Time of Basic Operations

根據(jù)統(tǒng)計(jì)，我們的DS-IBEET協(xié)議的各個算法的計(jì)算開銷如表4所示.加密算法、解密算法、前服務(wù)器測試算法和后服務(wù)器測試算法的運(yùn)行時間分別為24.9 ms，17.952 ms，24.692 ms和14.508 ms.顯然，此協(xié)議可以運(yùn)行在資源受限的移動設(shè)備上(如病人的手機(jī)平板電腦等).

Table 4 Computation Cost

本協(xié)議的通信開銷如表5所示.其中，公鑰長度為群G1中元素比特長度的2倍，密文長度為群G1中元素比特長度的4倍加上一個Zq上大數(shù)比特長度.陷門長度為群G1中元素比特長度.

Table 5 Communication Cost

|G1|: The bit length of element inG1.

|Zq|: Bit length of number inZq.

7 結(jié) 論

最近，一些帶密文等值判定的公鑰加密協(xié)議被提出.然而，它們僅有一個服務(wù)器參與密文等值判定過程，這種設(shè)計(jì)容易遭受惡意服務(wù)器內(nèi)部關(guān)鍵字猜測攻擊.為了解決這個問題，本文首次提出了基于雙服務(wù)器的帶密文等值判定的公鑰加密協(xié)議，并在隨機(jī)預(yù)言機(jī)模型下證明了其安全性.同時，我們利用MIRACL大數(shù)庫對其計(jì)算性能進(jìn)行了評估，并分析了其通信開銷，結(jié)果表明我們的DS-IBEET協(xié)議性能良好，且能夠在資源受限的移動設(shè)備上運(yùn)行.

由于基于身份的加密協(xié)議存在密鑰托管問題，我們下一步工作將嘗試研究一個無證書的帶等值判定的公鑰加密協(xié)議.

[1] Boneh D, Di Crescenzo G, Ostrovsky R, et al. Public key encryption with keyword search[C] //Advances in Cryptology—EUROCRYPT 2004. Berlin: Springer, 2004: 506-522

[2] Fang Liming, Willy S, Ge Chunpeng, et al. Public key encryption with keyword search secure against keyword guessing attacks without random oracle[J]. Information Sciences, 2013, 238: 221-241

[3] Abdalla M, Bellare M, Catalano D, et al. Searchable encryption revisited: Consistency properties, relation to anonymous ibe, and extensions[J]. Journal of Cryptology, 2008, 21(3): 350-391

[4] Hwang Y H, Lee P J. Public key encryption with conjunctive keyword search and its extension to a multi-user system[C] //Proc of the 1st Int Conf on Pairing-Based Cryptography. Berlin: Springer, 2007: 2-22

[5] Orencik C, Selcuk A, Savas E, et al. Multi-keyword search over encrypted data with scoring and search pattern obfuscation[J]. International Journal of Information Security, 2016, 15(3): 251-269

[6] Ibraimi L, Nikova S, Hartel P, et al. Public-key encryption with delegated search[C] //Proc of the 9th Int Conf on Applied Cryptography and Network Security (ACNS2011). Berlin: Springer, 2011: 532-549

[7] Byun J W, Rhee H S, Park H A, et al. Off-line key-word guessing attacks on recent keyword search schemes over encrypted data[C] // Proc of the 3rd VLDB Workshop on Secure Data Management (SDM 2006). Berlin: Springer, 2006: 75-83

[8] Shi Jie, Lai Junzuo, Li Yingjiu, et al. Authorized keyword search on encrypted data[C] //Proc of European Symp on Research in Computer Security (ESORICS 2014). Berlin: Springer, 2014: 419-435

[9] Cao Ning, Wang Cong, Li Ming, et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(1): 222-233

[10] Wang Kaixuan, Li Yuxi, Zhou Fucai, et al. Multi-keyword fuzzy search over encrypted data[J]. Journal of Computer Research and Development, 2017, 54(2): 348-360 (in Chinese)

(王愷璇, 李宇溪, 周福才, 等. 面向多關(guān)鍵字的模糊密文搜索方法[J]. 計(jì)算機(jī)研究與發(fā)展, 2017, 54(2): 348-360)

[11] Chen Dongdong, Cao Zhenfu, Dong Xiaolei. Online/offline ciphertext-policy attribute-based searchable encryption[J]. Journal of Computer Research and Development, 2016, 53(10): 2365-2375 (in Chinese)

(陳冬冬, 曹珍富, 董曉蕾. 在線/離線密文策略屬性基可搜索加密[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(10): 2365-2375)

[12] Tang Qiang. Towards public key encryption scheme supporting equality test with fine-grained authorization[C] //Proc of Australasian Conf on Information Security and Privacy. Berlin: Springer, 2011: 389-406

[13] Yang Guomin, Tan C H, Huang Qiong, et al. Probabilistic public key encryption with equality test[C] //Proc of Cryptographers’ Track at the RSA Conference. Berlin: Springer, 2010: 119-131

[14] Tang Qiang. Public key encryption supporting plaintext equality test and user-specified authorization[J]. Security and Communication Networks, 2012, 5(12): 1351-1362

[15] Tang Qiang. Public key encryption schemes supporting equality test with authorisation of different granularity[J]. International Journal of Applied Cryptography, 2012, 2(4): 304-321

[16] Ma Sha, Zhang Mingwu, Huang Qiong, et al. Public key encryption with delegated equality test in a multi-user setting[J]. The Computer Journal, 2014, 58(4): 986-1002

[17] Huang Kaibin, Tso R, Chen Y-C, et al. PKE-AET: Public key encryption with authorized equality test[J]. The Computer Journal, 2015, 58(10): 2686-2697

[18] Ma Sha, Huang Qiong, Zhang Mingwu, et al. Efficient public key encryption with equality test supporting flexible authorization[J]. IEEE Trans on Information Forensics and Security, 2015, 10(3): 458-470

[19] Ma Sha. Identity-based encryption with outsourced equality test in cloud computing[J]. Information Sciences, 2016, 328: 389-402

[20] Wu Libing, Zhang Yubo, Choo Kim-Kwang, et al. Efficient and secure identity-based encryption scheme with equality test in cloud computing[J]. Future Generation Computer Systems, 2017, 73: 22-31

[21] Victor S. Sequences of games: A tool for taming complexity in security proofs[OL]. (2004-11-30) [2017-06-10]. https://eprint.iacr.org/2004/332.pdf

[22] CertiVox. MIRACL cryptographic library: Multiprecision integer and rational arithmetic C/C++ library[OL]. (2006-08-01) [2017-06-10]. https://github.com/miracl/MIRACL

DualServerIdentity-BasedEncryptionwithEqualityTestforCloudComputing

Wu Libing1,2, Zhang Yubo2, and He Debiao1,2

1(StateKeyLaboratoryofSoftwareEngineering(WuhanUniversity),Wuhan430072)2(SchoolofComputerScience,WuhanUniversity,Wuhan430072)

With the rapid development of cloud storage and the increasing awareness of privacy, more and more private data are encrypted before outsourcing to the cloud. Thus, how to search in encrypted data has been a new research item in the scope of searchable encryption. One of the solutions is public key encryption with equality test (PKEET). It can check whether the plaintexts of two ciphertexts encrypted under different public keys are the same, without leakage any information about the plaintexts. Recently, many public key encryption schemes with equality test have been proposed. However, in these schemes, there were only one server be used to perform the equality test, which means that they could not withstand the inner keywords guessing attack. To solve this problem, we propose the first dual server identity-based encryption scheme with equality test (DS-IBEET). And we prove the security under random oracle model. In addition, performance evaluation shows that our scheme is suitable for resource-limited mobile devices.

equality test; identity-based encryption; cloud computing; dual server; searchable encryption

his BS and MS degrees in computer science from Central China Normal University, Wuhan, China, in 1994 and 2001, respectively.

his PhD degree in computer science from Wuhan University in 2006. Professor in the School of Computer Science, Wuhan University. Senior member of IEEE and CCF. His main research interests include distributed computing, trusted software and wireless sensor networks.

TP391

ZhangYubo, born in 1988. Received his BS degree in computer science and technology from Wuhan University of Science and Technology, Wuhan, China in 2011. PhD candidate in computer system architecture from Wuhan University. Student member of CCF. His main research interests include cryptography and information security.

HeDebiao, born in 1980. Received his PhD degree in applied mathematics from the School of Mathematics and Statistics, Wuhan University in 2009. Professor of the State Key Laboratory of Software Engineering, School of Computer Science, Wuhan University. His main research interests include cryptography and infor-mation security, in particularly, crypto-graphic protocols.