一個指定驗證者的基于身份可搜索認證加密方案

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

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

0 引言

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

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

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

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

1 準備知識

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

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

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

2.2 安全性模型

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

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

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

2)AI(內部敵手)：具體指指定服務器IDdS。

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

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

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

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

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

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

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

SK-Query：當AO提交IDi時，C返回IDi的私鑰dIDi。

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

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

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

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

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

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

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

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

猜測敵手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進行如下游戲：

初始化同游戲1。

第一階段同游戲1。

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

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

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

初始化同游戲2。

第一階段同游戲2。

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

猜測敵手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)輸出關鍵詞密文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′)指定服務器IDdS做如下操作：

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

2)驗證C2=h2(C1,IDS,IDR,IDdS,θ1,θ2)是否成立。若等式成立，輸出結果"1"，否則，輸出結果"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=μ′。

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

4 安全性證明

定理1 在DDH問題下，新方案滿足CIND-KGA，該定理將分引理1和引理2在標準模型下證明。

證明假設有一個DDH問題的元組(P,aP,bP,X)，C將在游戲1中擔當挑戰(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所做的一系列如下操作進行回應。在A的每一次其他查詢前都需要進行UPK-Query。C維護幾張初始為空的列表來存儲查詢和回復(該要求在本節(jié)均適用)。

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

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

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

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

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

2)計算

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

猜測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進行SK-Query。

證明假設有一個DDH問題的元組(P,aP,bP,X)，C將在游戲2中擔當挑戰(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所做的一系列如下操作進行回應。

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

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

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

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

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

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

2)當IDS∈{IDj,IDk}但IDR?{IDj,IDk}時，C獲取Cw的方法同dIBSAE算法，但μ的算法變?yōu)椋?/p>

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

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

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

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

2)當IDR∈{IDj,IDk}但IDS?{IDj,IDk}，C獲取Tw的方法同Trapdoor算法，但μ′的算法變?yōu)椋?/p>

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

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

IC(IDdS,w)→Cw：該算法用于在當{IDS,IDR}={IDj,IDk}時針對指定驗證者IDdS輸出關鍵詞w的密文，為方便表示，此處我們假設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：該算法用于在當{IDS,IDR}={IDj,IDk}時針對指定驗證者IDdS輸出關鍵詞w的搜索陷門，為方便表示，我們假設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要求的情況下重新進行第一階段中的各項查詢。

猜測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}進行SK-Query。

定理2 在DDH問題下，新方案滿足TIND-KGA，該定理將分引理3和引理4在標準模型下證明。

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

初始化同引理1。

階段1 同引理1。

2)計算

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

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

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

初始化同引理2。

第一階段同引理2。

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

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

5 性能對比

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

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

表1 安全性對比

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

表2 計算開銷(毫秒)

6 結論

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