胡震宇，鄧倫治，高 巖，施虹宇，武亞穎

(1.貴州師范大學(xué) 大數(shù)據(jù)與計算機(jī)科學(xué)學(xué)院，貴州 貴陽 550025；2.貴州師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，貴州 貴陽 550025)

0 引言

如今，信息技術(shù)的發(fā)展帶來了數(shù)據(jù)量的迅速膨脹，對于各種機(jī)構(gòu)和網(wǎng)絡(luò)個人用戶，云存儲服務(wù)的廣泛應(yīng)用成為一種必然趨勢。雖然云存儲的使用極大方便了數(shù)據(jù)的管理和分享，但是上傳到云服務(wù)器上的數(shù)據(jù)面臨丟失、惡意修改和泄露的風(fēng)險，因此上傳到云服務(wù)器上的數(shù)據(jù)常為加密數(shù)據(jù)。大量的加密數(shù)據(jù)帶來了密文檢索困難的問題，而對所有密文進(jìn)行解密并在明文上進(jìn)行檢索不符合現(xiàn)實需求。因此，在密文上進(jìn)行檢索是一項必要的研究內(nèi)容。

為了解決密文檢索問題，Song等[1]在2000年提出了可搜索加密(Searchable encryption,SE)的概念并給出了一個具體方案。在可搜索加密體制中，存在數(shù)據(jù)發(fā)送者、數(shù)據(jù)接收者和云服務(wù)器(即數(shù)據(jù)驗證者)3個實體。數(shù)據(jù)發(fā)送者將作為加密文件索引的關(guān)鍵詞密文與該文件一同上傳至云服務(wù)器。在檢索密文時，數(shù)據(jù)接收者對所需文件關(guān)鍵詞生成搜索陷門并提交給云服務(wù)器，云服務(wù)器使用驗證算法驗證搜索陷門是否與現(xiàn)存關(guān)鍵詞密文匹配，若匹配成功則返回搜索陷門所成功匹配關(guān)鍵詞密文對應(yīng)的文件，否則搜索失敗。在檢索過程中，關(guān)鍵詞明文信息不會被泄露。但文獻(xiàn)[1]的方案是一個對稱加密方案，由此帶來的密鑰分配復(fù)雜性使其不適合數(shù)據(jù)分享情景。為此，Boneh等[2]在2004年提出了第一個公鑰可搜索加密(Searchable public key encryption,SPE)。之后，Baek 等[3]進(jìn)一步提供了一個無安全信道的SPE框架，數(shù)據(jù)接收者可以通過公共信道向服務(wù)器發(fā)送搜索陷門。但是為了認(rèn)證用戶公鑰，基于傳統(tǒng)公鑰設(shè)施構(gòu)建的SPE方案需要一個第三方可信機(jī)構(gòu)來為用戶發(fā)放證書。由此，Abdalla等[4]擴(kuò)展了Shamir[5]提出的基于身份公鑰密碼學(xué)概念，提出一個基于身份的可搜索加密(Identity-based SE,IBSE)方案，在該密碼體制中，私鑰生成中心(Private key generator,PKG)利用用戶的身份信息(如工號、證件號碼、姓名等)為用戶生成公鑰和私鑰，省去了證書發(fā)放的問題。隨后，一系列基于身份的可搜索加密方案被提出。[6-7]

由于日常語言習(xí)慣，用來作為加密文件索引的關(guān)鍵詞空間較小。當(dāng)截獲一個關(guān)鍵詞搜索陷門時，擁有匹配測試權(quán)限的敵手可以利用數(shù)據(jù)接收者的公鑰為所有可能的關(guān)鍵詞生成關(guān)鍵詞密文并嘗試與所截獲陷門匹配，直到成功為止。這種攻擊被稱為關(guān)鍵詞猜測攻擊(Keywords guessing attacks,KGA)[8-9]。抵御KGA的一種可行方案是指定驗證者，即只有被指定的實體才能進(jìn)行匹配測試算法。但是該方法必須保證指定驗證者是可信的，否則其仍可進(jìn)行如上描述的關(guān)鍵詞猜測攻擊。為了解決這個問題，Huang等[10]提出了可搜索認(rèn)證加密(Searchable authenticated encryption,SAE)概念。在該類方案[10-11]中，關(guān)鍵詞加密算法要用到數(shù)據(jù)發(fā)送者的私鑰，因此只有數(shù)據(jù)發(fā)送者才能生成有效密文。2019年，Li等[12]提出了一個指定驗證者的基于身份可搜索認(rèn)證加密(Designated tester identity-based SAE,DIBSAE)，在該方案中，只有指定驗證者才能進(jìn)行匹配測試算法，但指定驗證者無法生成有效密文來進(jìn)行KGA，即可以抵御內(nèi)部關(guān)鍵詞猜測攻擊。

在依賴隨機(jī)諭言模型的安全性證明中，哈希函數(shù)被一個人為構(gòu)造的列表所替代，此類方案在現(xiàn)實中可能是不安全的[13-14]，而標(biāo)準(zhǔn)模型允許通過直接運(yùn)算哈希函數(shù)來獲得哈希值，因此在現(xiàn)實中有更高的安全性。本文提出了一個基于強(qiáng)安全模型的DIBSAE方案并在標(biāo)準(zhǔn)模型下證明了其安全性。另外，由于新方案不使用雙線性對運(yùn)算和哈希到點(diǎn)運(yùn)算，因此該方案與同類方案相比具有更高效率。

1 準(zhǔn)備知識

2 方案定義

本節(jié)我們將給出本方案的方案模型和安全性模型。

2.1 方案模型

一個DIBSAE方案由如下5個多項式時間算法組成：

1)系統(tǒng)參數(shù)生成算法Setup：輸入安全參數(shù)δ，PKG通過此算法生成并公布系統(tǒng)參數(shù)parm。

2)用戶密鑰生成算法UserKeyGen：輸入系統(tǒng)參數(shù)parm、實體地址IDi，PKG利用此算法為用戶IDi生成并發(fā)送公鑰RIDi和私鑰dIDi。

3)關(guān)鍵詞密文生成算法dIBSAE：輸入全局參數(shù)parm、數(shù)據(jù)發(fā)送者地址IDS及其私鑰dIDS、數(shù)據(jù)接收者的地址IDR及其公鑰RIDR、指定驗證者地址IDdS及其公鑰RIDdS和索引關(guān)鍵詞w,數(shù)據(jù)發(fā)送者IDS通過該算法生成關(guān)鍵詞密文Cw作為相關(guān)加密文件的索引與該文件一起上傳指定服務(wù)器IDdS。

4)搜索陷門生成算法Trapdoor：輸入全局參數(shù)parm、數(shù)據(jù)發(fā)送者地址IDS及其公鑰RIDS、數(shù)據(jù)接收者地址IDR及其私鑰dIDR、指定驗證者地址IDdS及其公鑰RIDdS和搜索關(guān)鍵詞w′,數(shù)據(jù)接收者IDR利用該算法輸出搜索陷門Tw′。

5)匹配測試算法MatchTest：輸入全局參數(shù)parm、數(shù)據(jù)發(fā)送者地址IDS、數(shù)據(jù)接收者地址IDR、指定驗證者地址IDdS及其私鑰dIDdS、關(guān)鍵詞密文Cw和搜索陷門Tw′，指定服務(wù)器IDdS通過該算法輸出結(jié)果"0"或"1"。其中，"0"代表搜索失敗，"1"代表搜索成功。若搜索成功，IDdS將對應(yīng)加密文件發(fā)送給數(shù)據(jù)接收者IDR。

2.2 安全性模型

本部分我們將給出dIBSAE方案的安全模型。

在DIBSAE中存在內(nèi)部和外部兩類敵手，其分別定義為：

1)AO(外部敵手)：具體指除指定服務(wù)器IDdS之外的任何人。

2)AI(內(nèi)部敵手)：具體指指定服務(wù)器IDdS。

一個DIBSAE方案應(yīng)該滿足在關(guān)鍵詞猜測攻擊下的關(guān)鍵詞密文不可區(qū)分性(Ciphertext indistinguishability under the keyword guessing attacks,CIND-KGA)和在關(guān)鍵詞猜測攻擊下的陷門不可區(qū)分性(Trapdoor indistinguishability under the keyword guessing attacks,TIND-KGA)。這兩類安全性分別保證多項式敵手無法通過關(guān)鍵詞猜測攻擊從關(guān)鍵詞密文和搜索陷門中獲得有用的關(guān)鍵詞信息。

CIND-KGA和TIND-KGA以如下幾個對抗游戲定義。

定義2 (CIND-KGA)沒有多項式時間敵手AO或AI可以以不可忽略的優(yōu)勢贏得以下游戲，則稱一個dIBSAE方案滿足CIND-KGA。

游戲1 (針對AO的CIND-KGA)挑戰(zhàn)者C與dIBSAE中的敵手AO進(jìn)行如下游戲：

初始化挑戰(zhàn)者C設(shè)置安全參數(shù)δ，輸出主密鑰s和系統(tǒng)參數(shù)parm并發(fā)送parm給AO。

第一階段本階段敵手AO適應(yīng)性地向挑戰(zhàn)者C做一系列查詢，具體描述如下：

UPK-Query：當(dāng)AO提交實體IDi時，C返回IDi的公鑰RIDi。

SK-Query：當(dāng)AO提交IDi時，C返回IDi的私鑰dIDi。

dIBSAE-Query：AO提交元組(IDS,IDR,IDdS,w)時，C返回發(fā)送者為IDS，接收者為IDR，指定驗證者為IDdS的關(guān)于關(guān)鍵詞w的關(guān)鍵詞密文Cw。

TD-Query：當(dāng)AO提交元組(IDS,IDR,IDdS,w)時，C返回發(fā)送者為IDS，接收者為IDR，指定驗證者為IDdS的關(guān)于關(guān)鍵詞w的搜索陷門Tw。

猜測敵手AO提交ω′，若ω′=ω，則稱敵手AO在游戲1中獲勝。

敵手AO在游戲1中的優(yōu)勢被定義為：

游戲2 (針對AI的CIND-KGA)挑戰(zhàn)者C與dIBSAE中的敵手AI進(jìn)行如下游戲：

初始化挑戰(zhàn)者C設(shè)置安全參數(shù)δ，輸出主密鑰s和系統(tǒng)參數(shù)parm并發(fā)送parm給AI。

第一階段本階段敵手AI適應(yīng)性地向挑戰(zhàn)者C做一系列如游戲1中AO可做的查詢。

第二階段AI繼續(xù)進(jìn)行一系列第一階段的各項操作，條件是：

猜測敵手AI提交ω′，若ω′=ω，則稱敵手AI在游戲2中獲勝。

敵手AI在游戲2中的優(yōu)勢被定義為：

定義3 (TIND-KGA)沒有多項式時間敵手AO和AI可以以不可忽略的優(yōu)勢贏得以下游戲，則稱一個dIBSAE方案滿足TIND-KGA。

游戲3 (針對AO的TIND-KGA)挑戰(zhàn)者C與dIBSAE中的敵手AO進(jìn)行如下游戲：

初始化同游戲1。

第一階段同游戲1。

猜測敵手AO提交ω′，若ω′=ω，則稱敵手AO在游戲3中獲勝。

敵手AO在游戲3中的優(yōu)勢被定義為：

游戲4 (針對AI的TIND-KGA)挑戰(zhàn)者C與dIBSAE中的敵手AI進(jìn)行如下游戲：

初始化同游戲2。

第一階段同游戲2。

第二階段AI繼續(xù)進(jìn)行一系列第一階段的各項操作，條件是：

猜測敵手AI提交ω′，若ω′=ω，則稱敵手AI在游戲4中獲勝。

敵手AI在游戲4中的優(yōu)勢被定義為：

3 方案描述

3.1 具體方案

公布系統(tǒng)參數(shù)parm=(δ,q,G,P,P0,h0,h1,h2,h3)。

(3)DIBSAE(parm,IDS,dIDS,IDR,RIDR,IDdS,RIDdS,w)：輸入元組(parm,IDS,dIDS,IDR,RIDR,IDdS,RIDdS,w)，數(shù)據(jù)發(fā)送者IDS做如下操作：

2)計算C1=tP，

μ=h1(IDS,IDR,IDdS,dIDS(RIDR+αIDRP0),w)，

ρ=t(RIDdS+αIDdSP0)，

C2=h2(C1,IDS,IDR,IDdS,ρ,μ)。

3)輸出關(guān)鍵詞密文Cw=(C1,C2)。

(4)Trapdoor(parm,IDS,RIDS,IDR,dIDR,IDdS,RIDdS,w′)：輸入元組(parm,IDS,RIDS,IDR,dIDR,IDdS,RIDdS,w′)，數(shù)據(jù)接收者IDR做如下操作：

2)計算T1=l1P，ρ′=l1(RIDdS+αIDdSP0)，

μ′=h1(IDS,IDR,IDdS,dIDR(RIDS+αIDSP0),w′)，

T2=l2h3(T1,IDS,IDR,IDdS,ρ′)，T3=l2+μ′。

3)輸出搜索陷門Tw′=(T1,T2,T3)。

(5)MatchTest(parm,IDS,IDR,IDdS,dIDdS,Cw,Tw′)：輸入元組(parm,IDS,IDR,IDdS,dIDdS,Cw,Tw′)指定服務(wù)器IDdS做如下操作：

1)計算h=h3(T1,IDS,IDR,IDdS,dIDdST1)，θ1=dIDdSC1，θ2=T3-T2h-1。

2)驗證C2=h2(C1,IDS,IDR,IDdS,θ1,θ2)是否成立。若等式成立，輸出結(jié)果"1"，否則，輸出結(jié)果"0"。

3.2 正確性

θ1=dIDdSC1=(rIDdS+αIDdSs)tP=t(RIDdS+αIDdSP0)=ρ,dIDdST1=(rIDdS+αIDdSs)l1P=l1(RIDdS+αIDdSP0)=ρ′,dIDR(RIDS+αIDSP0)=dIDRdIDSP=dIDS(RIDR+αIDRP0),θ2=T3-T2h-1=μ′。

易知，當(dāng)w′=w時C2=h2(C1,IDS,IDR,IDdS,θ1,θ2)成立，因此本方案是正確的。

4 安全性證明

定理1 在DDH問題下，新方案滿足CIND-KGA，該定理將分引理1和引理2在標(biāo)準(zhǔn)模型下證明。

證明假設(shè)有一個DDH問題的元組(P,aP,bP,X)，C將在游戲1中擔(dān)當(dāng)挑戰(zhàn)者來判斷X=abP是否成立。

初始化輸入安全參數(shù)δ，C通過Setup算法生成主密鑰s和系統(tǒng)參數(shù)parm=(δ,q,G,P,P0,h0,h1,h2,h3)然后發(fā)送系統(tǒng)參數(shù)parm給AO。

第一階段C對AO所做的一系列如下操作進(jìn)行回應(yīng)。在A的每一次其他查詢前都需要進(jìn)行UPK-Query。C維護(hù)幾張初始為空的列表來存儲查詢和回復(fù)(該要求在本節(jié)均適用)。

UPK-Query：C維護(hù)元組形式為(IDi,rIDi,RIDi)的列表LU，當(dāng)AO輸入IDi時，C在列表LU中查找(IDi,RIDi)并返回RIDi。如果沒有對應(yīng)條目，C做如下操作：

1)在第j次創(chuàng)建條目時，C添加(IDj,⊥,aP)到LU。

SK-Query：當(dāng)AO提交IDi時，若IDi=IDj，游戲中止。否則，C通過調(diào)用UserKeyGen算法返回dIDi給AO。

dIBSAE-Query：當(dāng)AO提交(IDS,IDR,IDdS,w)，C調(diào)用dIBSAE算法得到Cw并將其返回給AO。

TD-Query：當(dāng)AO提交(IDS,IDR,IDdS,w)，C調(diào)用Trapdoor算法得到Tw并將其返回給AO。

2)計算

第二階段AO可以在滿足游戲1要求的情況下重新進(jìn)行第一階段中的各項查詢。

猜測AO輸出ω′，如果ω′=ω，則稱AO在游戲1中獲勝。

解決DDH問題如果AO獲勝C輸出"1"，否則輸出"0"。如果X=abP，有

ρ=X+αIDjsbP=b(aP+αIDjP0)

概率分析 令QU，QSK分別為UPK-Query，SK-Query的次數(shù)，一些事件定義如下：

E1：AO沒有對IDj進(jìn)行SK-Query。

證明假設(shè)有一個DDH問題的元組(P,aP,bP,X)，C將在游戲2中擔(dān)當(dāng)挑戰(zhàn)者來判斷X=abP是否成立。

初始化 輸入安全參數(shù)δ，C通過Setup算法生成主密鑰s和系統(tǒng)參數(shù)parm=(δ,q,G,P,P0,h0,h1,h2,h3)然后發(fā)送系統(tǒng)參數(shù)parm給AI。

第一階段C對AI所做的一系列如下操作進(jìn)行回應(yīng)。

UPK-Query：C維護(hù)元組形式為(IDi,rIDi,RIDi)的列表LU，當(dāng)AI輸入IDi時，C在列表LU中查找(IDi,RIDi)并返回RIDi。如果沒有對應(yīng)條目，C做如下操作：

1)在第j次創(chuàng)建條目時，C添加(IDj,⊥,aP)到LU。

2)在第k(≠j)次創(chuàng)建條目時，C添加(IDk,⊥,bP)到LU。

SK-Query：當(dāng)AI提交IDi時，若IDi∈{IDj,IDk}，游戲中止。否則，C通過調(diào)用UserKeyGen算法返回dIDi給AI。

dIBSAE-Query：當(dāng)AI提交(IDS,IDR,IDdS,w)，C做如下操作：

1)當(dāng)IDS?{IDj,IDk}時,C調(diào)用dIBSAE算法得到Cw并將其返回給AI。

2)當(dāng)IDS∈{IDj,IDk}但I(xiàn)DR?{IDj,IDk}時，C獲取Cw的方法同dIBSAE算法，但μ的算法變?yōu)椋?/p>

μ=h1(IDS,IDR,IDdS,dIDR(RIDS+αIDSP0),w)，然后C將Cw返回給AI。

3)當(dāng){IDS,IDR}={IDj,IDk}時，C輸入(IDdS,w)，調(diào)用挑戰(zhàn)階段的IC算法獲得Cw并將其返回給AI。

TD-Query：當(dāng)AI提交(IDS,IDR,IDdS,w)，C做如下操作：

1)當(dāng)IDR?{IDj,IDk}時,C調(diào)用Trapdoor算法得到Tw并將其返回給AI。

2)當(dāng)IDR∈{IDj,IDk}但I(xiàn)DS?{IDj,IDk}，C獲取Tw的方法同Trapdoor算法，但μ′的算法變?yōu)椋?/p>

μ′=h1(IDS,IDR,IDdS,dIDS(RIDR+αIDRP0),w)，然后C將Tw返回給AI。

3)當(dāng){IDS,IDR}={IDj,IDk}時，C輸入(IDdS,w)，調(diào)用挑戰(zhàn)階段的IT算法獲得Tw并將其返回給AI。

IC(IDdS,w)→Cw：該算法用于在當(dāng){IDS,IDR}={IDj,IDk}時針對指定驗證者IDdS輸出關(guān)鍵詞w的密文，為方便表示，此處我們假設(shè)IDS=IDj，IDR=IDk，C做如下操作：

1)在列表LU中找出(IDj,aP)，(IDk,bP)和(IDdS,RIDdS)。

2)計算

αIDj=h0(IDj,aP)，αIDk=h0(IDk,bP)，

αIDdS=h0(IDdS,RIDdS)。

C1=tP，ρ=t(RIDdS+αIDdSP0)，

τ=X+αIDksaP+αIDjsbP+αIDkαIDjsP0，

μ=h1(IDj,IDk,IDdS,τ,w)，

C2=h2(C1,IDj,IDk,IDdS,ρ,μ)。

4)輸出密文Cw=(C1,C2)。

IT(IDdS,w)→Tw：該算法用于在當(dāng){IDS,IDR}={IDj,IDk}時針對指定驗證者IDdS輸出關(guān)鍵詞w的搜索陷門，為方便表示，我們假設(shè)IDS=IDj，IDR=IDk，C做如下操作

1)在列表LU中找出(IDj,aP)，(IDk,bP)和(IDdS,RIDdS)。

2)計算

αIDj=h0(IDj,aP)，αIDk=h0(IDk,bP)，

αIDdS=h0(IDdS,RIDdS)。

T1=l1P，ρ′=l1(RIDdS+αIDdSP0)，

τ′=X+αIDjsbP+αIDksaP+αIDkαIDjsP0，

μ′=h1(IDj,IDk,IDdS,τ′,w)，

T2=l2h3(T1,IDj,IDk,IDdS,ρ′)，T3=l2+μ′。

4)輸出陷門Tw=(T1,T2,T3)。

第二階段AI可以在滿足游戲2要求的情況下重新進(jìn)行第一階段中的各項查詢。

猜測AI輸出ω′，如果ω′=ω，則稱AI在游戲2中獲勝。

解決DDH問題如果AI獲勝C輸出"1"，否則輸出"0"。如果X=abP，有

τ=X+αIDksaP+αIDjsbP+αIDkαIDjsP0

=(a+αIDjs)(bP+αIDkP0)

概率分析令QU，QSK分別為UPK-Query，SK-Query的次數(shù)，一些事件定義如下：

E1：AI沒有對IDi∈{IDj,IDk}進(jìn)行SK-Query。

定理2 在DDH問題下，新方案滿足TIND-KGA，該定理將分引理3和引理4在標(biāo)準(zhǔn)模型下證明。

證明假設(shè)有一個DDH問題的元組(P,aP,bP,X),C將在游戲3中擔(dān)當(dāng)挑戰(zhàn)者來判斷X=abP是否成立。

初始化同引理1。

階段1 同引理1。

2)計算

第二階段AO可以在滿足游戲3要求的情況下重新進(jìn)行第一階段中的各項查詢。

猜測AO輸出ω′，如果ω′=ω，則稱AO在游戲3中獲勝。

證明假設(shè)有一個DDH問題的元組(P,aP,bP,X)，C將在游戲4中擔(dān)當(dāng)挑戰(zhàn)者來判斷X=abP是否成立。

初始化同引理2。

第一階段同引理2。

第二階段AI可以在滿足游戲4要求的情況下重新進(jìn)行第一階段中的各項查詢。

猜測AI輸出ω′，如果ω′=ω，則稱AI在游戲4中獲勝。

5 性能對比

本節(jié)我們將新方案與另外3個指定驗證者的基于身份可搜索加密方案進(jìn)行性能對比。

安全性方面，我們基于本方案提出的安全模型對新方案和對照方案進(jìn)行安全性對比，其結(jié)果見表1。

表1 安全性對比

效率方面，我們將算法每運(yùn)行1次的各項運(yùn)算時間總和作為效率指標(biāo)，主要統(tǒng)計了新方案與對比方案中所用到的成本較高的3種運(yùn)算，包括雙線性對(Bilinear pairing,BP)運(yùn)算、哈希到點(diǎn)(Hash-to-point,H)運(yùn)算和標(biāo)量乘法(Scalar multiplication,SM)運(yùn)算。為了保證對比的公正性，我們使用了第三方數(shù)據(jù)，Lu等[11]中通過模擬實驗得出上述3種運(yùn)算的單次時間成本分別為：TBP=4.154 ms，TH=4.362 ms，TSM=1.631 ms。具體的對比結(jié)果見表2。

表2 計算開銷(毫秒)

6 結(jié)論

本文提出了一個指定驗證者的基于身份可搜索認(rèn)證加密方案，算法中不使用高成本運(yùn)算，因此與同類方案相比具有更高效率。另外，本文在標(biāo)準(zhǔn)模型下證明了新方案的安全性，所有哈希值都通過直接計算哈希函數(shù)得到，且新方案基于更強(qiáng)的安全模型，因此在現(xiàn)實中有更高的安全性。