一種結(jié)合可驗證數(shù)據(jù)庫的屬性可搜索加密方案*

陳立全, 張林樾, 陳 垚

1. 東南大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院, 南京 210096

2. 網(wǎng)絡(luò)通信與安全紫金山實驗室, 南京 211111

1 引言

隨著數(shù)字經(jīng)濟的發(fā)展, 數(shù)據(jù)已經(jīng)成為受國家、企業(yè)和個人重視的關(guān)鍵戰(zhàn)略性資源. 隨著數(shù)據(jù)規(guī)模的增加, 使用云存儲技術(shù)存儲數(shù)據(jù)資源, 可以有效減少在軟硬件部署與管理環(huán)節(jié)中的大量成本. 因此, 云存儲和云計算技術(shù)已經(jīng)成為業(yè)界學(xué)者研究的重點. 資源受限的客戶端難以處理復(fù)雜的計算任務(wù), 越來越多的企業(yè)和個人選擇將大型加密數(shù)據(jù)庫外包到云存儲服務(wù)中. 但面對半可信的云存儲服務(wù)平臺, 數(shù)據(jù)持有者的數(shù)據(jù)可能面臨被篡改和替換的危險, 特別是在屬性可搜索加密方案中, 數(shù)據(jù)使用者屬性復(fù)雜, 在其對數(shù)據(jù)進行搜索時, 云存儲服務(wù)平臺可能只會將部分搜索結(jié)果返回給用戶, 這影響了搜索結(jié)果的完整性和正確性.

目前, 云存儲系統(tǒng)的數(shù)據(jù)完整性及隱私安全是學(xué)術(shù)界的熱門話題. 2000 年Song 等人[1]首次提出可搜索加密技術(shù)這一概念, 可搜索加密技術(shù)是指在密文域中使用關(guān)鍵詞搜索, 得到相應(yīng)的文件, 其特點是在有效減少本地存儲空間和通信消耗的同時, 也保證了數(shù)據(jù)的保密性, 傳統(tǒng)的可搜索加密技術(shù)主要分為對稱可搜索加密技術(shù)(symmetric searchable encryption, SSE)[1]和公鑰可搜索加密技術(shù)(public-key encryption with keyword search, PEKS)[2]. 數(shù)據(jù)持有者將數(shù)據(jù)加密后上傳至云平臺, 再構(gòu)建合適的搜索索引, 上傳至云平臺, 數(shù)據(jù)使用者在搜索數(shù)據(jù)時, 根據(jù)搜索的關(guān)鍵詞構(gòu)造相應(yīng)的陷門, 將陷門上傳至云平臺, 云平臺執(zhí)行搜索操作, 將匹配到的文件發(fā)送給數(shù)據(jù)使用者, 數(shù)據(jù)使用者接收到密文文件后在本地進行解密, 最終得到想要的明文文件. 近年來, 許多學(xué)者也在關(guān)鍵詞檢索等方面提出了多種方案, 例如單關(guān)鍵詞檢索[3,4]、多關(guān)鍵詞檢索[5–7]、模糊關(guān)鍵詞檢索[6,8]等.

近年來, 隨著對不同場景需求的不斷完善, 更多學(xué)者關(guān)注于數(shù)據(jù)及密鑰的安全性問題. 對稱可搜索加密技術(shù)加解密效率較高, 但需要一條安全信道完成密鑰傳輸, 而公鑰可搜索加密技術(shù)解決了這一問題, 傳統(tǒng)的公鑰加密方案中需要引入可信第三方作為授權(quán)機構(gòu)頒發(fā)公鑰證書,提高了方案的復(fù)雜度. 因此,Boneh等人在2001 年[9]提出了身份基(identity-based encryption, IBE) 可搜索加密方案, 與傳統(tǒng)公鑰加密方案相比, 身份基方案將用戶的唯一身份信息作為生成公鑰的依據(jù), 由私鑰生成中心(private key generator,PKG) 產(chǎn)生用戶的解密私鑰. 為了解決身份基可搜索加密方案在用戶身份模糊或敏感時無法使用的問題,Sahai 等人[10]在此基礎(chǔ)上提出了模糊身份基方案(fuzzy identity-based encryption, FIBE), 該方案將用戶身份分解為一系列模糊身份, 需要擁有d個模糊身份符合條件才能解密密文, 引入訪問結(jié)構(gòu)的概念并進一步提出了屬性基加密(attribute-based encryption, ABE), 而后其他學(xué)者也基于屬性基加密提出了多種可搜索加密方案[11–13].

在實際應(yīng)用場景中, 搜索結(jié)果的正確性和完整性同樣是非常重要的, 因此就有必要在可搜索加密方案中提供對搜索結(jié)果的驗證功能. Benabbas 等人提出了第一個實用的高階多項式函數(shù)可驗證計算方案, 同時提出了可驗證數(shù)據(jù)庫(verifiable database, VDB) 的概念及方案, 允許客戶端將大型數(shù)據(jù)庫外包給不受信任的云存儲服務(wù)器, 并在數(shù)據(jù)庫中進行檢索和更新, 服務(wù)器在給出搜索結(jié)果的同時還會提供搜索結(jié)果正確性的證明[14]. 不久后Sun 等人提出了一種高效的搜索結(jié)果驗證方法, 該方法允許用戶自行驗證結(jié)果正確性, 同時也支持委托給第三方可信機構(gòu)對搜索結(jié)果進行驗證[15]. 2020 年Liu 等人提出了一種多用戶可驗證的可搜索加密方案, 允許多個用戶執(zhí)行搜索操作, 而不僅僅局限于數(shù)據(jù)擁有者[16].

在基于屬性的可搜索加密方案中, 設(shè)計者通常采用非對稱加密方式來實現(xiàn)屬性之間的區(qū)分. 使用非對稱加密算法會導(dǎo)致數(shù)據(jù)擁有者執(zhí)行更新操作時需要將完整的密文數(shù)據(jù)和索引重新上傳, 效率較低, 同時對于屬性的更新操作也十分困難; 另一方面, 公鑰可搜索加密方案通常在大型數(shù)據(jù)庫場景中難以應(yīng)用. 關(guān)于可驗證性的問題, 當(dāng)前具有可驗證性的方案中, 大部分方案驗證的是搜索結(jié)果的完整性, 這其中并不包括對數(shù)據(jù)庫的驗證, 從而無法保證服務(wù)器給出的搜索結(jié)果是在最新數(shù)據(jù)庫上計算得出的. 針對上述問題,本文提出了一種基于可驗證數(shù)據(jù)庫的屬性可搜索加密方案(attribute-based searchable encryption with verifiable database, VDB-ABSE), 在實現(xiàn)權(quán)限可控功能的同時, 可以確保數(shù)據(jù)的可驗證完整性, 使得可搜索加密方案能夠應(yīng)對更復(fù)雜、安全性能要求更高的場景, 主要貢獻(xiàn)如下:

(1) 使用對稱加密方式對文件進行加密, 使用字典樹結(jié)構(gòu)建立搜索索引, 在搜索過程中先對數(shù)據(jù)使用者的屬性進行識別, 然后在對應(yīng)屬性的子樹中對關(guān)鍵詞進行搜索, 得到目標(biāo)的文件標(biāo)識符. 實現(xiàn)了屬性、關(guān)鍵詞與密文的高效動態(tài)更新, 并滿足前向安全和后向安全.

(2) 構(gòu)造一個可驗證數(shù)據(jù)庫, 在搜索完成后, 服務(wù)器將搜索結(jié)果與證明一起發(fā)送給數(shù)據(jù)使用者, 使用者可以對搜索結(jié)果以及數(shù)據(jù)庫的完整性和正確性進行驗證. 提出了一種結(jié)合屬性權(quán)限與可驗證數(shù)據(jù)庫的屬性可搜索加密方案.

2 VDB-ABSE 方案

VDB-ABSE 方案主要的方案模型如圖1 所示, 主要有三個部分: 云存儲平臺、數(shù)據(jù)持有者以及數(shù)據(jù)使用者.

圖1 VDB-ABSE 方案的系統(tǒng)模型Figure 1 VDB-ABSE scheme system model

云存儲平臺作為系統(tǒng)的核心部分, 具有高效的數(shù)據(jù)計算功能, 可以存儲由數(shù)據(jù)持有者上傳的密文文件集合、文件索引以及哈希樹. 數(shù)據(jù)持有者上傳可供搜索的文件, 預(yù)先使用關(guān)鍵詞分詞技術(shù)生成每個文件對應(yīng)的關(guān)鍵詞. 數(shù)據(jù)使用者首先需要從數(shù)據(jù)持有者處獲得一個屬性認(rèn)證, 標(biāo)志該用戶的屬性權(quán)限.

2.1 VDB-ABSE 算法定義

VDB-ABSE 方案涉及5 個多項式時間的算法, 分別是初始化算法、陷門生成算法、搜索算法、驗證算法和更新算法, 定義如下:

(1) Setup(SK,PP,DB,AttributeList)→VDB,PK,S: 其中SK 為數(shù)據(jù)持有者的私鑰, 公共參數(shù)為PP, 所有文件構(gòu)成的數(shù)據(jù)庫DB, 以及數(shù)據(jù)使用者的屬性列表AttributeList. 輸出為一個構(gòu)建好的可驗證數(shù)據(jù)庫VDB、公開密鑰PK, 以及一些附加信息S.

(2) TrapGen(UA,w,KT)→Tpw: 當(dāng)數(shù)據(jù)使用者想要在VDB 中搜索關(guān)鍵詞為w的文件時, 將自己的屬性UA, 目標(biāo)關(guān)鍵詞w, 以及索引密鑰KT作為該算法的輸入, 通過計算, 輸出為對應(yīng)的搜索陷門Tpw.

(3) Search(Tpw,UA,VDB,PK)→τ,D: 數(shù)據(jù)使用者將生成的陷門Tpw和自己的屬性UA 發(fā)送給云存儲服務(wù), 云存儲服務(wù)器將Tpw、UA 以及可驗證數(shù)據(jù)庫VDB、公開密鑰PK 為輸入. 先進行關(guān)鍵詞搜索, 然后再對應(yīng)屬性權(quán)限索引表, 將該屬性下對應(yīng)的密文文件集DWwUA發(fā)送給數(shù)據(jù)使用者, 附上證明τ.

(4) Verify(τ,DWwUA)→result: 數(shù)據(jù)使用者收到云存儲服務(wù)器返還的密文文件集DWwUA和證明τ后進行驗證, 分別驗證完整性和正確性. 如果通過驗證, 算法輸出result=0, 表示數(shù)據(jù)使用者接受搜索結(jié)果, 否則, 算法輸出result=1, 表示云存儲服務(wù)器的搜索結(jié)果不滿足完整性或正確性,數(shù)據(jù)使用者拒絕云存儲服務(wù)器的搜索結(jié)果.

(5) Update(Utype,w,UAtrribute,Fw,SI)→SI′: 在VDB-ABSE 方案中, 更新算法涉及關(guān)鍵詞更新、文件更新以及屬性更新. 輸入為更新的種類參數(shù)Utype、關(guān)鍵詞w、屬性列表UAtrribute、文件Fw以及索引. 根據(jù)需要更新的類別, 更新索引, 最后將新的索引SI′作為輸出.

在下面幾個小節(jié)中將對這些算法進行詳細(xì)說明, 并給出VDB-ABSE 方案的構(gòu)造方法. 本文中使用的符號及其定義如表1 所示.

表1 本文中的符號及定義Table 1 Symbols and their definitions in this paper

2.2 初始化算法

密鑰生成: 數(shù)據(jù)持有者DO 生成密鑰集KF,KS,KA ∈{0,1}256、以及數(shù)據(jù)持有者DO 認(rèn)證密鑰KDO∈{0,1}λ; 選取大素數(shù)q.

參數(shù)選擇: 選擇抗強碰撞哈希函數(shù)H(*,K) :{0,1}λ×{0,1}*={0,1}τ, 其中K ∈{0,1}λ,τ為輸出比特位. 偽隨機函數(shù)F:{0,1}λ×{0,1}λ →{0,1}λ, 和兩個能夠使等式|G1| =|G2| =q成立的兩個群,g是G1的生成器.e是一個雙線性映射, hash 是G1中的安全哈希算法,P是[1,q] 范圍內(nèi)的排列.

明文文件集加密: 加密明文文件集合F={f1,f2,··· ,fn},n為明文文件數(shù)量. 加密采用AES 加密方式, 密鑰使用KF. 加密得到密文集合C={c1,c2,··· ,cn}, 其中ci=AESenc(KF,fi).

關(guān)鍵詞提取: 采用關(guān)鍵詞提取技術(shù), 根據(jù)明文文件集合F={f1,f2,··· ,fn}, 提取出關(guān)鍵詞集合W={w1,w2,··· ,wm}.

屬性權(quán)限劃分: 數(shù)據(jù)持有者根據(jù)實際情況將數(shù)據(jù)使用者根據(jù)屬性進行劃分得到屬性集合UAttribute.對每項屬性進行權(quán)限劃分, 計算UAi,wj條件下的可搜索的文件列表Fi,j, 即屬性UAi可以搜索的關(guān)鍵詞和關(guān)鍵詞所對應(yīng)的文件, 構(gòu)成屬性表AttributeList, 如式(1)所示:

構(gòu)建可驗證數(shù)據(jù)庫: 數(shù)據(jù)持有者DO 將需要上傳到云存儲平臺CSP 的文件先構(gòu)建成可驗證數(shù)據(jù)庫VDB. 數(shù)據(jù)庫DB 包含用戶屬性、文檔標(biāo)識符和關(guān)鍵詞的對應(yīng)關(guān)系, DBw表示關(guān)鍵詞為w的所有文檔標(biāo)識符, DBUAw則表示DBw中屬性為UA 可以搜索的所有文檔標(biāo)識符.

在初始化階段的具體操作如下:

(1) 數(shù)據(jù)持有者隨機選擇q個元素zi ∈RZp, 計算hi=gzi,hi,j=gzizj, 其中1≤i/=j ≤q, 然后生成密鑰y ∈RZp, 計算Y=gy. 公開參數(shù)為式(2):

其中, 信息域為M=Zp.

(2) 構(gòu)建索引結(jié)構(gòu), 明文字典樹構(gòu)建規(guī)則如下:

(a) 根節(jié)點為空節(jié)點, 不存儲數(shù)據(jù), 僅作為搜索入口.

(b) 深度為1 的節(jié)點存儲屬性, 用于在搜索時匹配用戶屬性.

(c) 深度大于1 的節(jié)點代表關(guān)鍵詞中的字符, 從根節(jié)點到該子節(jié)點的路徑代表該節(jié)點對應(yīng)的關(guān)鍵詞, 節(jié)點存儲以下數(shù)據(jù){μ,Np,DBs}. 其中,s代表該節(jié)點對應(yīng)的字符串;μ代表s是否為關(guān)鍵詞,μ= 1 時代表s是關(guān)鍵詞; Np={np1,np2,··· ,npθ}代表該節(jié)點的子節(jié)點; DBs代表關(guān)鍵詞s的屬性權(quán)限索引表, 該表使用二維數(shù)組的結(jié)構(gòu)存儲屬性與文檔之間的訪問權(quán)限, 1代表該屬性有權(quán)限訪問相關(guān)文檔, 構(gòu)建的二維數(shù)組結(jié)構(gòu)如表2 所示.

表2 二位數(shù)組DBs 的結(jié)構(gòu)圖Table 2 Structure of two-dimensional array DBs

這個索引數(shù)組對于攻擊者和云存儲服務(wù)器沒有任何意義, 為了提高安全性和索引的隱私安全, 可以在索引中添加一些假關(guān)鍵詞和文檔標(biāo)識符, 進一步防止攻擊者利用統(tǒng)計方法獲取文檔信息.

圖2 給出了根據(jù)規(guī)則構(gòu)建出的索引結(jié)構(gòu)在明文狀態(tài)下的示例. 在本方案中, 將對字典樹加密生成搜索索引, 數(shù)據(jù)持有者通過密鑰KS,KA,KI, 對字典樹進行加密, 得到搜索索引SI, 并構(gòu)建樹MHT, 具體方法如下:

圖2 索引結(jié)構(gòu)在明文狀態(tài)下的示例圖Figure 2 Sample of index structure in plaintext

(a) 對于關(guān)鍵詞w, 假設(shè)其每個字符為αi, 計算βi=F(KI,αi), 數(shù)據(jù)持有者對于每個屬性下的關(guān)鍵詞w ∈W進行式(3)計算, 該映射關(guān)系記作SI[UA,stagw]=eUAw.

(b) 數(shù)據(jù)持有者生成兩個布隆過濾器BFw和BFUA, 把所有關(guān)鍵詞標(biāo)記stagw插入BFw, 以確保搜索的可驗證性, 把所有的屬性標(biāo)記stagUA插入BFUA, 以保證用戶屬性的可驗證性.

(c) 按照SI 的結(jié)構(gòu)構(gòu)建哈希樹,根節(jié)點為φ,其他每個葉子節(jié)點中存儲H(UA||w||m),其中w為SI 中相同路徑所表示的關(guān)鍵詞,m為屬性UA 可搜索該關(guān)鍵詞的文件標(biāo)識符數(shù)量, 即DBUAw中1 的個數(shù).

本方案公開密鑰為PK=(PP,Y,CR,C0,BFw,BFUA,MHT,φ), 上傳至云存儲服務(wù)器的輔助信息為S=(PP,aux,DB,SI), 數(shù)據(jù)持有者和數(shù)據(jù)使用者保存的私鑰為SK={y,KS,KI,KA,KF}.

2.3 陷門生成算法

數(shù)據(jù)使用者需要輸入自己的屬性UA, 以及需要搜索的關(guān)鍵詞集Target ={t1,t2,···}. 生成陷門的具體操作如下:

(1) 首先生成屬性陷門, 計算stagUA=F(KA,UA).

(2) 對于每個關(guān)鍵詞wi=(α1,α2,··· ,αl) 中每個字母αi, 進行以下計算βi=F(KI,αi)

(3) 關(guān)鍵詞的陷門為stagw=β1||β2||···, 關(guān)鍵詞集的搜索陷門為式(5):

(4) 最后, 輸出的搜索陷門是Tpw={stagUA,stagT}.

數(shù)據(jù)使用者將搜索陷門Tpw發(fā)送給云存儲服務(wù)平臺對目標(biāo)文件進行請求搜索.

2.4 搜索算法

云存儲平臺在收到搜索請求后, 將搜索陷門Tpw解析為stagUA和stagT, 然后進行搜索, 詳細(xì)的執(zhí)行過程如下:

(1) 驗證數(shù)據(jù)使用者的屬性是否在可以搜索的權(quán)限范圍內(nèi), 首先檢查stagUA是否在BFUA內(nèi), 如果檢查結(jié)果是存在的則再進行下面的步驟, 若不在屬性范圍內(nèi), 則結(jié)束此次搜索請求.

(2) 服務(wù)器收到搜索令牌后, 解析出來每個關(guān)鍵詞的搜索陷門stagw, 通過SI 執(zhí)行搜索, 得到結(jié)果R= SI[UA,stagw]. 云存儲服務(wù)器將R和對應(yīng)的所有加密文件一起發(fā)送給數(shù)據(jù)使用者. 數(shù)據(jù)使用者在接收到R之后, 計算Ke=F(KS,w), 解密DEC(Ke,R)=UA||DBUAw, 得到對應(yīng)關(guān)鍵詞所對應(yīng)的文件標(biāo)識符.

2.5 驗證算法

驗證階段的工作主要分為三部分,先是驗證搜索屬性的正確性,接著驗證搜索結(jié)果的完整性,即DBUAw的完整性, 再解析證明τ. 具體步驟如下:

(1) 當(dāng)搜索結(jié)果為空時, 數(shù)據(jù)使用者檢查BFw(stagw) = 1 是否成立, 如果不成立, 則接受搜索結(jié)果,過程終止.

(2) 當(dāng)結(jié)果不為空時, 數(shù)據(jù)使用者首先計算DEC(Ke,R) = UA||DBUAw, 得到的屬性標(biāo)識符與自身屬性標(biāo)識符進行對比, 檢驗屬性的正確性.

(3) 客戶端通過使用MHT 的根來檢查H(UA||w||m), 來驗證完整性. 其中m是通過對接收到的密文文件e進行解密得到的, 也可以通過DBUAw中文件標(biāo)識符的個數(shù)得到.

(4) 搜索結(jié)果的正確性可以通過向量承諾的特征得到. 數(shù)據(jù)使用者先對證明進行解析τ=(v(T)x ,π(T)x,HT,CT-1,C(T),T,BFw,BFUA,φ). 任何驗證者都可以通過式(6)來檢查證明τ的正確性:

2.6 更新算法

在實際應(yīng)用中, 對存儲的數(shù)據(jù)進行動態(tài)更新十分重要, 本文提出的VDB-ABSE 方案支持對關(guān)鍵詞、屬性以及密文進行動態(tài)更新, 具體更新方法如下:

(1) VDB-ABSE 方案在對關(guān)鍵詞進行更新時包括添加和刪除兩項操作. 數(shù)據(jù)擁有者首先要使用初始化算法中構(gòu)建索引的方法為待操作關(guān)鍵詞構(gòu)建索引結(jié)構(gòu)SI, 并更新公開密鑰中的MHT, 將Utype 設(shè)定為對應(yīng)的操作標(biāo)識, 添加關(guān)鍵詞時僅需將新關(guān)鍵詞的stagw加入BFw中, 刪除關(guān)鍵詞時則需根據(jù)剩余關(guān)鍵詞重新生成BFw, 將(SI,Utype,BFw) 發(fā)送到服務(wù)器. 服務(wù)器在數(shù)據(jù)擁有者通過身份驗證后更新索引結(jié)構(gòu)SI 及布隆過濾器BFw.

(2) VDB-ABSE 方案將數(shù)據(jù)使用者屬性存儲于索引結(jié)構(gòu)中, 因此對屬性的添加、刪除操作與關(guān)鍵詞的更新方法相似. 不同之處在于使用新屬性的stagUA更新或重新生成BFUA, 將(SI, Utype,BFUA) 發(fā)送到服務(wù)器, 由服務(wù)器完成更新.

(3) 對于要更新的密文vx, 數(shù)據(jù)持有者首先獲取相應(yīng)的索引x, 服務(wù)器將最新的數(shù)據(jù)記錄vx和相應(yīng)的證明τ發(fā)送給數(shù)據(jù)持有者. 當(dāng)Verify(PK,x,τ)=vx/=⊥時, 數(shù)據(jù)持有者在T上加1, 并計算出式(8):

2.7 方案運行流程

本節(jié)中VDB-ABSE 方案的運行流程為圖3. 數(shù)據(jù)持有者對于可以對數(shù)據(jù)進行搜索的數(shù)據(jù)使用者進行管理屬性, 能夠掌握他們對文件搜索的不同權(quán)限, 在初始化階段對文件進行加密, 并根據(jù)數(shù)據(jù)使用者的權(quán)限和屬性生成相應(yīng)的搜索索引, 再根據(jù)索引生成相應(yīng)的哈希樹, 構(gòu)建可驗證數(shù)據(jù)庫, 并將可驗證的數(shù)據(jù)庫發(fā)送給云存儲平臺, 由云存儲平臺進行存儲. 圖3 中搜索階段與動態(tài)更新階段均可以進行重復(fù)操作. 在搜索階段數(shù)據(jù)使用者先是根據(jù)自己的屬性生成相應(yīng)的搜索陷門, 向陷門發(fā)送給云存儲平臺, 云存儲平臺在接收到搜索陷門后執(zhí)行搜索操作, 將搜索結(jié)果和證明返還給數(shù)據(jù)使用者, 數(shù)據(jù)使用者在接收到信息后先驗證數(shù)據(jù)的完整性和真實性, 通過驗證后對密文文件進行解密得到自己的目標(biāo)文件. 當(dāng)存儲在云存儲服務(wù)器端的可驗證數(shù)據(jù)庫需要進行更新時, 數(shù)據(jù)持有者將更新指令發(fā)送給云存儲平臺, 云存儲平臺按照指令進行更新并將新的數(shù)據(jù)庫證明發(fā)送給數(shù)據(jù)持有者, 同時將公開密鑰更新.

圖3 VDB-ABSE 方案流程圖Figure 3 VDB-ABSE scheme flow chart

3 方案分析

3.1 安全性分析

定理1 假設(shè)本方案中的F是安全的偽隨機函數(shù), 則本方案中使用的SI 實例Σ 是自適應(yīng)安全的.

證明: 與文獻(xiàn)[17] 類似, 本文通過設(shè)計一個模擬器S來提出安全性分析, 即證明RealΣA(λ) 和RealΣA,S(λ) 在計算上是不可區(qū)分的. RealΣA,S(λ) 實驗實例化一個空的列表并且生成一個計數(shù)器, 對手A選擇一個關(guān)鍵詞集W, 實驗生成索引SI 并發(fā)送給A, 再將生成的陷門stagw發(fā)送給A, 存儲到列表中,并將最后列表發(fā)送給A. 如果存在模擬器對于所有的對手A都能安全地保護索引, 意味著模擬器S僅用泄露信息就可以精確地模擬整個協(xié)議, 從而完成證明, 則證明方案具備自適應(yīng)安全.

模擬器算法S可按照以下方式進行:S將泄露信息LT= (|DBw|,N= ∑w∈W|DBw|) 和對手的查詢T[q] 的所有記錄作為輸入. 初始化S(LT), 生成索引SI, 與索引生成算法相似, 不同的是S用相同長度的隨機比特串填充數(shù)組的所有元素. 另外,S生成一個二維數(shù)組T[w,c] 來存儲所有的條記錄, 用來做A的響應(yīng). 然后,S發(fā)送SI 給A, 對于A的每一個查詢q, 檢索一個列表t= (T[q,1],··· ,T[q,|DBq|]). 如果元素F(stagw,c) 在賦值前被查詢過, 則S終止.F是一個偽隨機函數(shù), stagw在RealΣA(λ) 中和被F范圍內(nèi)隨機元素篡改后是無法區(qū)別的. 另一方面, 因為任何給定的T[w,c] 都是隨機分配到SI 的, 所以A每個T[w,c] 的視圖與真實游戲都是相同的. 即滿足式(9):

因此, VDB-ABSE 方案中的索引SI 具備自適應(yīng)安全.

定理2 提出來的VDB-ABSE 方案可以在Squ-CDH 假設(shè)下實現(xiàn)安全的關(guān)鍵詞搜索.

證明: 與文獻(xiàn)[18] 類似, 這里采用還原法提出安全證明. 假設(shè)所提出的VDB 方案在關(guān)鍵詞搜索的情況下不能實現(xiàn)可驗證的更新, 這意味著存在一個對手A, 可以以一個非常小的優(yōu)勢?讓數(shù)據(jù)使用者進行虛假開局, 因此可以建立一個高效的算法A′包含A來打破Squ-CDH 假設(shè). 即在輸入(g,ga) 時,A′可以輸出ga2.

A′首先選擇一個關(guān)鍵詞w, 然后選擇一個相關(guān)的索引i ∈RZq作為對索引i的猜想,A可以打破這個位置綁定.A′隨機選擇zj ∈RZp, 其中,j ∈[1,q] 和j/=i, 并且計算式(10):

假設(shè)(i*,π*) 為A返回的元組, 其中τ*= (v*,π*,ΣT). 如果A可以破解VDB-ABSE 方案的安全性, 即同時滿足式(11):

A′成功的概率為?/q, 幾乎為0, 因此VDB-ABSE 方案在Squ-CDH 假設(shè)下能夠?qū)崿F(xiàn)安全的關(guān)鍵詞搜索.

3.2 理論分析

在本小節(jié)中,將VDB-ABSE 方案與其他方案進行理論分析比較,表3 給出了本文提出的VDB-ABSE方案與文獻(xiàn)[19,20] 提出方案的效率、安全性和功能對比. 其中M為在循環(huán)群G1(或G2) 中的乘法運算,E為在循環(huán)群G1中的冪運算,I為在循環(huán)群G1中的逆元運算,H為哈希運算,F為偽隨機運算,P為雙線性對運算,n為關(guān)鍵詞個數(shù).

表3 方案對比Table 3 Comparison among schemes

3.3 實驗分析

本小節(jié)將對于VDB-ABSE 方案進行實驗仿真, 并且與其他方案進行對比分析, 實驗環(huán)境使用的CPU為Intel?CoreTMi5-7500 CPU@3.40 GHz, 16G 內(nèi)存, 實驗算法、參數(shù)的選擇如表4 所示. 首先從公開數(shù)據(jù)庫IMDB Reviews 中隨機挑選3000 條評論數(shù)據(jù), 并生成數(shù)據(jù)庫, 在分詞后選取400 個使用頻率高的關(guān)鍵詞, 設(shè)置數(shù)據(jù)使用者的屬性個數(shù)為20.

表4 實驗參數(shù)Table 4 Experiment parameters

圖4 給出VDB-ABSE 方案與文獻(xiàn)[19,20] 中方案的查詢性能對比. 從圖中可以看出, VDB-ABSE 方案的搜索用時較文獻(xiàn)[19] 中的方案更長, 優(yōu)于文獻(xiàn)[20] 中的方案, 但文獻(xiàn)[19] 中的方案是可驗證數(shù)據(jù)庫方案, 不支持可搜索加密, 而文獻(xiàn)[20] 中的可搜索方案不支持基于屬性加密. 另外, 文獻(xiàn)[20] 中的方案使用的索引結(jié)構(gòu)是在倒排索引結(jié)構(gòu)的基礎(chǔ)上進行升級, 搜索效率為O(n),n為關(guān)鍵詞個數(shù), VDB-ABSE 方案使用的是字典樹結(jié)構(gòu), 搜索效率為O(1), 同時還需要進行屬性搜索, 屬性搜索的搜索效率為O(n),n為屬性個數(shù). 在現(xiàn)實場景中, 關(guān)鍵詞通常遠(yuǎn)多于屬性數(shù)量, 所以VDB-ABSE 方案的搜索效率比文獻(xiàn)[20] 中的方案更好, 能夠應(yīng)對更加復(fù)雜的應(yīng)用場景.

圖4 VDB-ABSE 方案與其他方案的查詢用時比較Figure 4 Comparison of query time between VDB-ABSE scheme and other schemes

圖5 給出VDB-ABSE 方案與文獻(xiàn)[19,20] 中方案的驗證功能的性能對比. 圖中三種方案的驗證時間均與計算次數(shù)成線性關(guān)系, VDB-ABSE 方案與文獻(xiàn)[20] 中方案需要更多的計算時間, 是因為兩個方案都需要執(zhí)行一個簽名驗證和復(fù)雜度為O(log2q) 的哈希運算以驗證文檔標(biāo)識符的完整性. 此外, VDB-ABSE方案在這一基礎(chǔ)上還要進行一次解密得到用戶屬性的驗證結(jié)果, 所以VDB-ABSE 方案的驗證所用時間會比其他兩個方案更多一些, 但是從實驗結(jié)果來看, 所耗時間還是在可以接受的范圍內(nèi). 在驗證性能差不多的情況下, VDB-ABSE 方案能夠?qū)?shù)據(jù)使用者的屬性進行區(qū)分, 具有更好的普適性.

圖5 VDB-ABSE 方案與其他方案的驗證用時比較Figure 5 Comparison of verify time between VDB-ABSE scheme and other schemes

圖6 給出VDB-ABSE 方案與其他方案的更新功能所用時間對比. 三種方案均具有動態(tài)更新過程, 在更新過程中, VDB-ABSE 方案和文獻(xiàn)[20] 中的方案在更新時除了要更新數(shù)據(jù)庫, 還需要對索引中的信息進行更新, 由前文中對索引結(jié)構(gòu)的分析可知, VDB-ABSE 方案在關(guān)鍵詞個數(shù)更多的場景中的更新效率要略高于文獻(xiàn)[20] 中的方案.

圖6 VDB-ABSE 方案與其他方案的更新用時比較Figure 6 Comparison of update time between VDB-ABSE scheme and other schemes

4 結(jié)束語

本文引入了可驗證數(shù)據(jù)庫的概念, 在屬性可搜索加密技術(shù)的基礎(chǔ)上加入了可驗證功能. 現(xiàn)有可搜索加密方案普遍存在效率較低, 或是不能保障數(shù)據(jù)安全性的問題. 為此, 本文提出了一種基于可驗證數(shù)據(jù)庫的可搜索加密方案(VDB-ABSE), 給出了VDB-ABSE 方案的方案模型, 對方案中的具體算法和構(gòu)造方式進行了詳細(xì)說明, 并對VDB-ABSE 方案進行了安全性分析, 證明了VDB-ABSE 方案是自適應(yīng)安全的,同時證明了可以在Squ-CDH 假設(shè)下實現(xiàn)安全的關(guān)鍵詞搜索. 通過分析VDB-ABSE 方案的性能, 并與其它方案進行比較, 可以看出VDB-ABSE 方案在效率、安全性和功能上表現(xiàn)更加優(yōu)異. 實驗結(jié)果表明,VDB-ABSE 方案能夠應(yīng)用于現(xiàn)實生活中更加復(fù)雜的場景, 具備屬性權(quán)限控制、動態(tài)更新以及可驗證的功能, 彌補了當(dāng)前屬性可搜索加密方案的不足.