基于聚類索引的多關鍵字排序密文檢索方案

杜瑞忠 李明月 田俊峰

(河北大學網絡空間安全與計算機學院 河北保定 071002) (河北省高可信信息系統重點實驗室(河北大學) 河北保定 071002) (drzh@hbu.edu.cn)

云計算被認為是企業IT基礎設施的新模式，該模式可以組織龐大的計算，提供可用的、便捷的、按需的網絡訪問，進入可配置的計算資源共享池存儲和應用資源.盡管云服務具有各種優勢，但將敏感信息外包給遠程服務器也帶來了隱私問題.這些隱私安全威脅嚴重阻礙了云計算的發展.現有的加密技術可以保障云環境下的數據在可預見時間里的安全性，但這些復雜的加密技術使搜索加密數據變得困難，限制了外包數據的可用性[1].因此，如何在保護用戶隱私的同時，使云數據獲得有效的檢索是亟待解決的問題.

可搜索的加密方案使客戶能夠將加密的數據存儲到云中，并通過密文域執行關鍵字搜索.文獻[2]提出了第1個基于密文掃描思想的可搜索加密方案，該方案對單個關鍵詞的查詢需要掃描整個文件，因此檢索的效率低.文獻[3]提出了對稱可搜索加密的正式安全定義，并設計了一個基于Bloom過濾器的方案.該方案搜索時間是O(m)，m是文檔數量.文獻[4]提出了實現最優搜索時間的2種方案(SSE-1和SSE-2).其中，SSE-1方案對于選擇關鍵字攻擊是安全的，SSE-2對于自適應選擇關鍵字攻擊是安全的.但上述方案只是用于單關鍵字的查詢，即用戶在一次查詢中僅能提交1個查詢檢索詞，在功能方面非常簡單.

相對于單關鍵字查詢，多關鍵字查詢允許用戶輸入多個查詢關鍵字來請求需要的文檔，可以更好地滿足用戶的查詢需求.文獻[5]提出了多關鍵字排序密文檢索問題，通過計算文件向量和查詢向量內積的結果進行排序.但是此方案沒有考慮關鍵字權重的問題，查詢向量與結果集文件的相關度不高，即檢索精度不高.文獻[6]在文件排序時用余弦相似度代替內積來計算文件向量與查詢向量的相似度，同時引入TF/IDF(term frequency/inverse document frequency)算法，提高了檢索精度，但缺乏對頻率信息和實際搜索性能的安全性分析.文獻[7]應用了稀疏矩陣的方法實現了安全的大規模方程.文獻[8]提出細粒度的多關鍵字檢索方案，采用分類子詞典技術以及偏好因子提高了檢索效率.為了方便用戶查看檢索結果，文獻[9]提出了一個支持排名搜索安全的多關鍵字密文排序檢索方案，該方案基于二叉平衡樹構建了索引，但在生成索引樹時該方案隨機選取2個結點生成父結點，將文檔之間的相關性忽略，降低了檢索精度，同時為了得到top-K個文件在最壞的情況下要遍歷整個索引樹.

受到以上工作的激勵，本文在多關鍵字密文檢索框架上提出基于聚類索引的多關鍵字排序密文檢索方案(multi-keyword ranked ciphertext retrieval scheme based on clustering index, CTMRSE).在構建索引樹前用改進的Chameleon算法對文件進行動態聚類，通過制定閾值來限制聚類的過程，最后按照聚類結果構建索引樹，直到生成根結點.查詢的過程利用檢索算法自上而下查詢.當訪問的結點不是葉子結點時，選擇與查詢向量相似度最高的結點訪問；當訪問的結點為葉子結點時，利用排序算法按相似度高低將文件插入列表；如果列表中文件數量少于K，回溯到其父親結點訪問，否則直接返回列表.該檢索方法降低了查詢的時間復雜度，提高了檢索效率.

本文的主要貢獻體現在3個方面：

1) 在聚類前通過記錄關鍵字位置對文件向量進行降維，降低了聚類過程中不必要的計算消耗，減少了聚類時間.

2) 在動態聚類Chameleon算法中引入了杰卡德相似系數來計算高維文件向量之間的相似度以及設定合適的k值與minMex值來提高在高維空間中聚類結果的質量，從而提高檢索精度.

3) 提出新型密文檢索結構CTMRSE及相應的算法，通過理論分析與實驗驗證了該方案提升了多關鍵字密文檢索的效率和精度.

1 背景介紹

1.1 系統模型

本文的系統模型如圖1所示，將云服務按功能不同可以分為3個實體：數據擁有者、數據使用者和云服務器.

1) 數據擁有者.數據擁有者即數據的屬主方，要搜集數據、數據分類、建立聚類索引以及加密和上傳數據與索引.此外，數據擁有者需要給數據使用者合理授權，分享密鑰.

2) 數據使用者.數據使用者為數據擁有者授權的用戶，要設定返回的文檔數K，然后將查詢的內容生成陷門TD發送給云服務器，在獲得返回的K個文檔后，使用共享密鑰對文檔進行解密.

3) 云服務器.云服務器為密文檢索提供了大量的計算和存儲資源,接到數據使用者合法的查詢請求時,云服務器需要根據查詢算法以及利用索引樹進行計算，返回和查詢最相關的前K個文檔.

Fig. 1 The architecture of search over encrypted cloud data圖1 密文檢索的系統架構圖

1.2 模型威脅分析

為了規范研究范圍，本文假設云服務器誠實但是好奇，即云服務器會按著用戶的要求執行操作，但它會試圖分析用戶的數據與索引從而獲取用戶的隱私信息.主要考慮2種威脅模型[10]：

1) 密文已知

云服務器只知道數據擁有者上傳到云端的加密后的文檔集C、索引樹T和陷門TD.

2) 背景已知

在背景已知模型中，云服務器不僅知道密文已知模型中的信息，還配備統計信息功能，可以通過分析相應頻率分布的直方圖，進行TF統計攻擊，推斷甚至識別某些關鍵詞.

1.3 主要符號說明

本文使用的主要符號說明如下.

F: 明文文檔集合{f1,f2,…,fm}；

C: 密文文檔集合{c1,c2,…,cm}；

W: 關鍵詞集合{w1,w2,…,wn}；

I: 安全索引集合{I1,I2,…,In}；

QW: 查詢向量；

TD: 查詢關鍵詞陷門；

m: 文檔集合文檔數量；

EK: 返回的結果集；

k: 最近鄰數量；

M: 一個聚類中最多容納文件個數；

u: 為了文檔的安全性添加的維數；

n: 關鍵詞集合中關鍵詞的個數；

K: 用戶指定返回的文檔個數.

1.4 Chameleon算法

Chameleon算法[11]是一種層次聚類算法，其運作模型如圖2所示，圖2中的每個頂點代表1個文件對象，每個文件對象用n維向量來表示，連接2個頂點邊的權值為這2個文件之間的相似度.聚類過程分為3個步驟：用k最近鄰算法構建稀疏圖，k值對算法的結果會產生很大影響，要設定適當的取值；在保證割邊最小化的情況下，將圖劃分成多個小簇；使用凝聚層次聚類算法，基于子簇的相似度反復合并子簇，其中，minMex(度量函數閾值)取值過小容易發生過擬合，較大則導致近似誤差增大，因此也要設定合理值.其中，度量函數為RI(ci,cj)×RC(ci,cj)α.當α>1時，表示更重視相對近似性；當α<1時，表示更重視相對互連性；當α=1時，表示2個量度標準有相等的權重.

Fig. 2 The operation model of Chameleon algorithm圖2 Chameleon算法的運作模型

1.5 結果集排序隱私度

排名隱私度[12]可以量化搜索結果向云服務器的信息泄漏量：

/K2，

(1)

2 改進的Chameleon算法

2.1 向量降維

在建立索引前對文件集向量進行聚類用到的是Chameleon聚類算法.選擇該算法來聚類是因其在聚類的過程中不僅考慮每個簇之間的互聯性，而且考慮簇的鄰近性，動態聚類結果質量高，可提高后期檢索效率與精度.但Chameleon算法聚類代價較高，為了降低聚類時間對文檔向量進行降維處理.

每個文件對應1個n維的文檔向量，文件包含的關鍵詞在向量中對應的位置為1，其他位置都為0.一個文件一般只會包含極少量的關鍵詞[13]，即每個n維的文檔向量中包含大量的0，文檔向量之間的相似度計算會帶來不必要的開銷.因此，將高維向量通過記錄關鍵詞的位置進行降維處理可減少不必要的計算消耗，從而提高聚類的效率.假設關鍵詞數n=1 000，則每個文檔向量的維度為1 000，通過記錄關鍵詞的位置降維，每個位置只需要用10位二進制來表示.如圖3所示，向量D1和D2分別為文件1與文件2的文件向量，D1向量中的1對應的位置為8,35,255,985，即文件1包含關鍵詞集中的4個關鍵詞{w8,w35,w255,w985}.D2向量中的1對應的位置為8,35,129,255,768，即文件2含有關鍵詞集中的5個關鍵詞{w8,w35,w129,w255,w768}.圖3為通過記錄關鍵詞位置將向量D1和D2轉化為向量A1和A2的過程，隨著文件向量的維數增加，基于位置降維效果會更明顯，聚類效率相應提高.

Fig. 3 The dimensionality reduction process of D1 and D2圖3 文件向量D1與D2的降維過程

2.2 相似度

在Chameleon算法中利用k鄰近算法構建稀疏圖時，連接2個邊的權值是2個文件向量的相似度(鄰近圖中的文件向量是經過降維處理的).為了在高維空間得到有意義的簇，提高聚類結果的質量，引入杰卡德相似系數計算經過降維處理的文件向量之間的相似度.杰卡德相似系數是衡量2個集合相似度的一種指標，用杰卡德相似系數計算高維向量之間的相似系數時，用J(D1,D2)表示：

(2)

其中，p是文件1與文件2包含相同關鍵字的個數；q是文件1包含文件2不包含關鍵字的個數；r是文件2包含文件1不包含關鍵字的個數；s是文件1與文件2都不包含關鍵字的個數.

文件向量D1與D2經過降維后得到A1與A2，如圖3所示，J(D1,D2)可以通過向量A1與A2來計算，由于A1與A2記錄著文件1與文件2包含關鍵字的位置，且相同的關鍵字在文檔向量中對應的位置相同，可通過對比記錄的關鍵詞的位置即可迅速的計算出p,q,r,s的值，不需要對比向量A1與A2的每個比特位，在提高聚類質量的同時也提升了聚類效率.例如圖3中文件向量D1和文件向量D2之間的杰卡德相似系數為14.

2.3 改進的Chameleon算法

在Chameleon算法中引入杰卡德相似系數來計算文件向量之間的相似度以及在聚類過程中通過記錄關鍵字位置對文件向量進行降維處理后的算法如下.

算法1. 改進的Chameleon算法.

輸入: 文件集合F；

輸出: 聚類結果.

① for each filefiin clusterCido

Di←RedDimPro(fi)；

d←JaccardCoef(Di,Dj)；

if (d=MinDistance&&Num≤k) then

Connection(Di,Dj)；

Num++；

end if

end for

② Builtk-nearest graph；

③ for each clusterCiinClusterList

Ci,Cj←EC(Ci)；

EC(Ci,Cj)←AbsolutInter(Ci,Cj)；

EC(Ci)←Inter(Ci)；

RI(Ci,Cj)←Relative(Ci,Cj)；

SEC{Ci,Cj}←AbsolutClose(Ci,Cj)；

SEC{Ci}←InterClose(Ci);

RC(Ci,Cj)←RelativeClose(Ci,Cj)；

tempMetric=max{RI(Ci,Cj)×RC(Ci,Cj)}；

minMex←SetThreshold；

if (tempMetric>minMex) then

NewCi←Merge(Ci,Cj)；

else

DeleteCifromClusterList；

end if

end for

在算法1中，RedDimPro(fi)為文件fi生成文檔向量，并對文檔向量進行降維的函數；JaccardCoef(Di,Dj)為用杰卡德相似系數來計算文件向量Di和Dj之間相似度的算法.RI(Ci,Cj)定義為簇Ci和Cj的互聯度:

(3)

RC(Ci,Cj)定義為簇Ci和Cj相對近似度:

(4)

利用改進的Chameleon算法對文件向量聚類可提高聚類質量，從而提高檢索精度.此外先聚類再建立索引可提高檢索的效率.

Fig. 4 The process of clustering圖4 聚類過程

2.4 聚類結果

為了更好地顯示聚類過程，從文件集合{f1,f2,…,fm}中選取了12個文件，根據改進的聚類算法將文件動態聚類得到D,E,F,H,G這5個簇.圖4為文件向量映射在2維平面上的效果圖，其中簇D,E,F相似度分數高，將E,F,D這3個簇聚為一類(即B)，類似地，也可將簇H,G聚為一類(即C),A為B和C的總和.

3 方案構建

3.1 基本方案

1)SK←setup(1n,u)

數據擁有者從{f1,f2,…,fm}中提取出n個關鍵詞集{w1,w2,…,wn}.然后，隨機生成一個(n+u+1)維的向量S作為分割指示向量，同時生成2個(n+u+1)×(n+u+1)可逆矩陣M1和M2，組成密鑰SK={S,M1,M2}.

2)I←Genindex(F,SK)

在生成文檔向量前，數據擁有者計算關鍵詞權重[10]：

(5)

3)TD←GenTrapdoor(QW,SK)

Fig. 5 The process of index tree encryption圖5 索引樹加密過程

Fig. 6 The process of trap generation圖6 陷門生成過程

4)EK←Query(I,TD,K)

通過陷門TD，云服務器利用檢索算法自上而下進行檢索，先計算陷門與根結點所有孩子結點的相關度得到相關度最高的子結點，然后訪問該子結點的所有孩子結點，以此類推直到找到目標簇，如果該簇的文件量小于返回文件數K，回溯到其父親結點，遍歷其兄弟結點的孩子結點，直到找到相似度分數最高的前K個文檔向量，返回給數據使用者.

其中，相關度分數的計算：

(6)

5)FK←Dec(EK,SKf)

數據使用者接收到云服務器返回的密文EK后利用密鑰SKf解密，得到明文FK.

3.2 索引構建

根據聚類結果構建索引樹的算法如下.

算法2. 構建聚類索引的算法.

輸入: 文件集F；

輸出: 根結點rootNode.

MakeIndexTree(F)

①InitQueue(*Q)；

② for each documentfi∈Fdo

v←Di；

EnQueue(SqQueueQ,QElemv)；

end for

③ while ((QueueLength(SqQueueQ)>1)do

for eachdatainQdo

Ci←Chameleon(Q->data)；

end for

end while

④ for each clusterCido

Comput Cluster CenterMi；

ParentNodePN←Mi；

if ((Q->rear+1)%MaxSize=Q->front)then

return 0；

else

EnQueue(SqQueueQ,QElemPN)；

N←QueueLength(SqQueueQ)；

DeQueue(LinkQueue *Q,N,NodeSet)；

end if

end for

rootNode←Q->data；

returnrootNode.

在算法2中，QueueLength(SqQueueQ)為求隊列Q長度的算法；EnQueue(SqQueueQ,QElemPN)是將元素PN插入隊列Q的隊尾；DeQueue(LinkQueue *Q,N,NodeSet)將隊列Q前N個元素全部刪除，然后把刪除的元素插入到NodeSet中.

3.3 檢索過程

利用索引樹查詢的算法如下.

算法3. 查詢算法.

輸入: 索引樹T；

輸出: 搜索結果文件集Rlist.

GDFABTS(IndexTreeNode)

① ifu.childis not a leaf node then

max←0；

while(u.child)do

ComputeRScore(u.child,QW)；

if (u.child>max) then

max←RScore(u.child,QW)；

else

return

end if

end while

GDFABTS(u.child)；

② else

while (u.child) do

SORT(Rlist,u.child,RScore(u.child,QW))；

end while

ifRlist.num=Kthen

returnRlist；

else

GDFABTS(u.rightsib)；

end if

end if

在算法3中，RScore(u.child,QW)為計算結點u.child中存儲的文件向量與查詢向量相關分數的算法；GDFABTS(u.rightsib)為回溯算法；SORT(Rlist,u.child,RScore(u.child,QW))為按照相關分數排序的算法.

圖7是由圖4的聚類結果根據構建索引算法生成的索引樹，以圖7中的索引樹為例，設K=4，n=5，查詢向量QW=(0,1,0,1,1)，圖7中的向量都尚未加密.從根結點A開始搜索，先計算查詢向量和根結點A的2個子結點B與C的相似度分數.由于查詢向量與結點C的相似度分數高，接下來搜索結點C的子結點，經過計算得到查詢向量與結點H，G中G相似度最高，接著查詢結點G的子結點，根據檢索算法，由于G的孩子結點是葉子結點，則用直接插入算法按照相關度分數的大小依次將其插入Rlist中.要求返回4個文件，目前Rlist中只有2個文件，則回溯到結點C查詢另1個孩子結點H.同樣利用直接插入算法將其孩子結點按著相似度分數插入Rlist.最終返回文件的是圖7中的①②③④.

Fig. 7 Index tree圖7 索引樹

4 檢索效率、精度與安全分析

4.1 查詢效率分析

Table 1 Time Complexity of Each Scheme表1 各方案時間復雜度表

4.2 檢索精度分析

文檔之間的關系通常被隱藏在加密過程中[15]，這將導致顯著的搜索精度性能下降.較好的查詢結果應該保持查詢文檔與文檔之間的相似度，相似度越高，檢索精度越高.本方案檢索精度量化為

(7)

其中，K為最終密文檢索返回的前K個文件，K′是明文查詢中返回的前K′個文件，RScore(QW,Di)為查詢向量QW與返回結果集中文檔的相似度.

傳統的MRSE方案在加密Di過程中以及EDMRS方案在索引構建過程的階段將文檔之間的相關性忽略，導致檢索精度性能下降.經3.1節式(6)推導，CTMRSE方案中相關度分數Rscore=TD·Ii=Di·QW，即密文檢索計算的相關度分數與明文檢索的相同.另外，該方案在建立索引之前對文件聚類，經過檢索算法搜索返回結果集的文件在同一個簇或者相鄰簇，而文件的相關度與聚類質量有關，聚類質量越高搜索結果集的文件相關度越高.為了提高聚類質量，在聚類過程中引入杰卡德相似系數來計算文件向量之間的相似度以及設定合適的閾值降低誤差率.因此查詢向量與結果集的文件相關度高.

4.3 安全分析

1) 索引和查詢保密性

CTMRSE方案用隨機的(n+u+1)維向量S對文檔向量Di與查詢向量QW進行分割，可以保障文檔在已知背景攻擊模型中的索引確定性和查詢保密性.同時通過矩陣M1和M2對向量進行變換的難以確定性，使保密性進一步增強.

2) 查詢無關聯性

向量添加了u維同時從中隨機選擇v維置為1，且最后1維的值被置為隨機值，相同的搜索請求將產生不同的查詢向量并接收不同的相關性分數分布，從而更好地保護查詢無關聯性.

3) 關鍵字隱私

云服務器能夠通過分析關鍵詞的TF分布直方圖來推斷識別關鍵詞[16].CTMRSE方案采取添加維度且隨機賦值的加密方式能抵抗已知背景模型中的統計攻擊.

5 性能分析

本文實驗使用國內云存儲提供商阿里云的云存儲平臺(搭載centos 7.3 64位系統、主頻為2.5 GHz的4核CPU、16 GB內存、內網寬帶為0.8 Gbps、公網寬帶為100 Mbps、系統盤為40 GB高效云盤)搭建存儲系統.原型系統的開發和測試環境是基于centos 7的Linux[17]平臺，具體硬件配置是intel?CoreTMi7-6700(3.40 GHz)處理器，配備8 GB內存和網速為1 Gbps的校園網環境.實驗數據使用20 431篇英文新聞作為測試數據集[18]，共有20個類別，類別是非均勻的.然后通過全文檢索工具Lucene[19]用分詞器對純文本字節流進行分詞，濾掉26.1%的停用詞(如as,but)，對這些文檔進行關鍵詞提取形成關鍵詞數為7 200的關鍵詞集合.

5.1 聚類效率與精度

首先為了驗證改進的方案提高了聚類效率，對改進方案與未改進方案的聚類時間進行實驗，實驗使用m=3 000的文件集合，字典大小n=1 000.實驗結果如圖8(a)所示，未改進方案聚類時間比改進方案所需時間明顯長.因此，用改進的方案使得聚類效率有了很大提升.圖8(b)是本文方案與文獻[9]中的EDMRS方案對于構建索引所需時間進行對比的實驗，實驗表明EDMRS方案構建二叉平衡樹與本方案根據聚類結果動態構建索引樹所用的時間基本保持一致.

由于k值與度量函數取值過小容易發生過擬合，較大則導致近似誤差增大，對聚類結果有巨大影響，實驗通過聚類結果的誤差率來確定k值與minMex取值.文件數量相同時，如圖9(a)當文件數量m=1 000時，k=6時誤差最小.文件數量變化時，k值隨著文件數量變化而改變.對應的k值也通過聚類結果的誤差率來確定；minMex的取值不同得到聚類結果的誤差率不同，如圖9(b)所示，文件數量m=1 000，minMex=0.18時誤差率最小.但minMex取值隨著文件數量的變化保持不變.因此，通過對k值與minMex設定合適的取值可以使聚類結果誤差率降低，提高了聚類結果質量，從而提高檢索的精度.

Fig. 8 Clustering effect圖8 聚類效果

Fig. 9 Error ratio with the increasing thresholds圖9 取不同閾值對應的誤差率

5.2 檢索效率

授權用戶在進行檢索時，總希望快速地得到檢索結果，為了檢測3個方案的檢索效率，分別在文件數量、關鍵詞個數以及授權用戶要求返回文檔數量不同時進行實驗，實驗結果如圖10所示.由于方案MRSE查詢時需要計算所有的密文文檔向量和密文查詢向量之間的相似度，時間復雜度為O(m)，在圖10(a)中，當文檔集合的文檔數量按著指數級增加時，MRSE的方案的查詢響應時間也呈指數級增長.而EDMRS和CTMRSE的方案的時間復雜度與索引樹的層次相關，都是近似線性增長，但是相同的文件數量構建的索引樹的層次CTMRSE方案比EDMRS少，因此CTMRSE方案查詢時間增長更緩慢，檢索效率最高；無論用戶要求返回多少文件，MRSE方案沒有用到索引樹，需要與所有的文件向量計算相似度，再根據相似度大小進行排序，在圖10(b)中檢索時間幾乎不變，但是該方案的檢索時間最長.隨著用戶要求返回文檔數量的增加，查詢時要計算相似度的葉結點數量增多，即θ與的值增大，在圖10(b)中EDMRS和CTMRSE方案的檢索時間都增長，但是比較穩定.由于θ>，CTMRSE方案的查詢時間最少；隨著關鍵詞集合中關鍵字數量的增多，在計算查詢向量與文檔向量的相似度時，計算時間增長，尤其是MRSE方案，要計算與所有文件向量的相似度，在圖10(c)中MRSE方案增長幅度最高，查詢時間最長.EDMRS和CTMRSE方案的查詢時間也會隨著關鍵詞集合中關鍵字數量的增多而增長，圖10(c)中，EDMRS和CTMRSE方案的查詢時間增長的都比較穩定，CTMRSE方案的查詢效率最高.

Fig. 10 Query efficiency圖10 查詢效率

5.3 結果集相似度與排序隱私度對比

用戶不僅看重檢索效率，還在乎檢索的精度和隱私安全.實驗通過查詢向量與結果集的相似度來度量檢索的精度，如圖11(a)所示，當關鍵詞數量變化時，CTMRSE方案相似度最高，具有明顯優勢.實驗通過結果集排序隱私度檢測MRSE，EDMRS，CTMRSE方案的隱私安全性，如圖11(b)所示，CTMRSE方案的排序隱私更好，安全性更高.

Fig. 11 Search precision and rank privacy圖11 結果集相似度與排序隱私度

6 總 結

本文提出了基于聚類索引的多關鍵字排序密文檢索方案(CTMRSE).該方案先聚類再建立索引，聚類時通過記錄關鍵詞位置對向量進行降維，減少聚類過程中不必要的計算消耗.同時，引入了杰卡德相似系數來計算高維向量之間的相似度，并給Chameleon算法設定合適的k值與minMex值減少聚類結果的誤差率，提高聚類質量與檢索精度.該方案還提出了相應的索引結構和相應的算法，并通過建立密文檢索實驗平臺驗證了本方案在保障數據隱私安全的同時，有效的提高了密文檢索的效率與精度.但CTMRSE方案是在文件集不變的情況下進行的實驗，當添加、刪除和修改文件時動態更新索引樹，以及數據改變后驗證檢索結果的真實性、完整性是未來需要進行的工作.