楊清琳,黃治國(guó),錢(qián)文標(biāo),楊曉雷
(1.廣西財(cái)經(jīng)學(xué)院 現(xiàn)代教育技術(shù)部,廣西 南寧 530003;2.河南工程學(xué)院 計(jì)算機(jī)學(xué)院,河南 鄭州 451191)
隨著云計(jì)算技術(shù)的日趨成熟和快速發(fā)展,把數(shù)據(jù)存儲(chǔ)在云端,只需較小的代價(jià)就能享受高效快捷的文件存儲(chǔ)和處理服務(wù)已經(jīng)成為當(dāng)下數(shù)據(jù)存儲(chǔ)的一種重要選擇。然而,數(shù)據(jù)安全和隱私保護(hù)如何有效地得到保障仍然是很多用戶(hù)所擔(dān)心的問(wèn)題。常見(jiàn)的解決方法是將用戶(hù)數(shù)據(jù)先進(jìn)行加密,再將加密后的密文數(shù)據(jù)上傳到云端,當(dāng)用戶(hù)需要使用某個(gè)數(shù)據(jù)時(shí),再?gòu)挠脩?hù)密文中檢索出需要的文檔。如何對(duì)加密數(shù)據(jù)執(zhí)行檢索等操作,是近年來(lái)可搜索加密(searchable encryption,SE)技術(shù)[1-2]研究的內(nèi)容。
針對(duì)國(guó)內(nèi)外學(xué)者可搜索加密技術(shù)的相關(guān)研究,大致可以分為單關(guān)鍵詞可搜索加密、多關(guān)鍵詞可搜索加密和模糊加密搜索。單關(guān)鍵詞可搜索加密[3-5]是基于對(duì)稱(chēng)密碼學(xué)的精確的單關(guān)鍵字搜索機(jī)制,用戶(hù)只能在一次搜索過(guò)程中發(fā)送1個(gè)單詞,很難實(shí)現(xiàn)用戶(hù)的個(gè)性化需求,無(wú)法滿(mǎn)足用戶(hù)多關(guān)鍵詞查詢(xún)需求,因此支持多關(guān)鍵詞的可搜索加密被提出。Cao等[6]提出了MRSE(multi-keyword ranked search over encrypted cloud data)算法,該算法基于安全KNN(k-nearest neighbor)查詢(xún)技術(shù)創(chuàng)建文檔向量,增強(qiáng)了隱私數(shù)據(jù)保護(hù),并利用可逆矩陣與文檔向量間“內(nèi)積相似度”來(lái)實(shí)現(xiàn)多關(guān)鍵字的排序查詢(xún)。文獻(xiàn)[7]提出的多關(guān)鍵字的排序搜索方案利用樹(shù)構(gòu)建索引結(jié)構(gòu),減少了搜索時(shí)間。文獻(xiàn)[8]基于同義詞查詢(xún)技術(shù),提出了一種多關(guān)鍵字排序搜索算法,實(shí)現(xiàn)了在加密云數(shù)據(jù)上進(jìn)行多關(guān)鍵詞排序搜索的功能。文獻(xiàn)[9]提出一種安全且高效的多關(guān)鍵詞密文排序檢索方案,同時(shí)支持動(dòng)態(tài)更新和并行檢索。以上方法只有查詢(xún)關(guān)鍵詞跟預(yù)置的關(guān)鍵字完全匹配時(shí),才能有檢索結(jié)果返回。為解決實(shí)際應(yīng)用中用戶(hù)輸入的搜索請(qǐng)求會(huì)出現(xiàn)拼寫(xiě)錯(cuò)誤或格式不匹配的問(wèn)題,模糊搜索方案被提出,實(shí)現(xiàn)了當(dāng)用戶(hù)輸入的查詢(xún)關(guān)鍵字與預(yù)置的關(guān)鍵字不能精確匹配時(shí),也能找到相關(guān)文檔。文獻(xiàn)[8,10]提出了一種將LSH(locality sensitive hashing)和安全KNN方法結(jié)合的新型多關(guān)鍵詞模糊搜索方案。文獻(xiàn)[11]基于布隆過(guò)濾器使用對(duì)偶編碼函數(shù)和位置敏感Hash函數(shù)來(lái)構(gòu)建文件索引,并使用距離可恢復(fù)加密算法加密索引,實(shí)現(xiàn)了對(duì)多關(guān)鍵字的密文模糊搜索。文獻(xiàn)[12]將計(jì)數(shù)型布隆過(guò)濾器與MinHash算法結(jié)合,實(shí)現(xiàn)了一種可以減少索引構(gòu)建和查詢(xún)陷門(mén)生成時(shí)間的模糊多關(guān)鍵詞檢索方案。然而,現(xiàn)有的模糊搜索方法中,針對(duì)的只是字符串上的模糊,而沒(méi)有實(shí)現(xiàn)關(guān)鍵詞語(yǔ)義上的搜索。例如,當(dāng)用戶(hù)輸入關(guān)鍵詞“搜索”時(shí),基于字符串匹配的方案只能返回那些包含有關(guān)鍵詞“搜索”的文檔,而實(shí)際應(yīng)用中,包含了“檢索”或者“查詢(xún)”關(guān)鍵詞的文檔也有可能是用戶(hù)需要的結(jié)果。
針對(duì)現(xiàn)有的可搜索加密方案沒(méi)有對(duì)查詢(xún)關(guān)鍵詞進(jìn)行語(yǔ)義擴(kuò)展,導(dǎo)致用戶(hù)查詢(xún)意圖與返回結(jié)果存在語(yǔ)義偏差,無(wú)法滿(mǎn)足人們對(duì)智能搜索的要求,文中提出了一種支持語(yǔ)義的可搜索加密方法。利用本體知識(shí)庫(kù)對(duì)用戶(hù)查詢(xún)進(jìn)行語(yǔ)義拓展,并引入了語(yǔ)義相似度和關(guān)鍵詞不同域加權(quán)評(píng)分,實(shí)現(xiàn)了對(duì)拓展后的關(guān)鍵詞進(jìn)行權(quán)重計(jì)算并根據(jù)用戶(hù)需求設(shè)定閾值,防止因拓展詞過(guò)多而語(yǔ)義相似度較大時(shí),影響檢索的精確度。并基于向量空間模型,利用文檔向量、查詢(xún)向量分塊技術(shù)構(gòu)造出對(duì)應(yīng)的標(biāo)記向量,以過(guò)濾大量的無(wú)關(guān)文檔,并將語(yǔ)義相似度、關(guān)鍵詞不同位置加權(quán)評(píng)分及關(guān)鍵詞-文檔相關(guān)度等影響因子引入到查詢(xún)-文檔的相似度計(jì)算得分中,實(shí)現(xiàn)了檢索結(jié)果的有效排序。
文中設(shè)定的系統(tǒng)框架模型如圖1所示。其中密鑰管理中心負(fù)責(zé)密鑰的生成和發(fā)放。數(shù)據(jù)用戶(hù)一方面將明文文檔及文檔索引加密成密文文檔及安全索引,并發(fā)送至公有云服務(wù)器,另一方面從明文文檔構(gòu)造出文檔標(biāo)記向量,發(fā)送至私有云。授權(quán)用戶(hù)根據(jù)自身需要輸入查詢(xún)關(guān)鍵詞,通過(guò)本體知識(shí)庫(kù)對(duì)關(guān)鍵詞進(jìn)行語(yǔ)義擴(kuò)展,再將擴(kuò)展后的查詢(xún)生成查詢(xún)標(biāo)記向量上傳給私有云,并使用密鑰對(duì)擴(kuò)展后的查詢(xún)構(gòu)造出陷門(mén)上傳給公有云服務(wù)器。私有云服務(wù)器的主要責(zé)任是存儲(chǔ)文檔標(biāo)記向量,并根據(jù)授權(quán)用戶(hù)提交的查詢(xún)標(biāo)記向量生成可能滿(mǎn)足授權(quán)用戶(hù)查詢(xún)請(qǐng)求的候選索引標(biāo)識(shí)符, 提交給公有云,由公有云執(zhí)行進(jìn)一步的檢索操作。公有云服務(wù)器的主要責(zé)任是存儲(chǔ)密文文檔及安全索引,并根據(jù)授權(quán)用戶(hù)的查詢(xún)請(qǐng)求執(zhí)行檢索服務(wù)。公有云通過(guò)私有云提交的候選索引標(biāo)識(shí)符找出與之相應(yīng)的安全索引,并用找出的安全索引與授權(quán)用戶(hù)提交的陷門(mén)來(lái)計(jì)算查詢(xún)-文檔相關(guān)度得分,返回得分最高的前Top-k篇文檔給授權(quán)用戶(hù)。
圖1 云計(jì)算下支持語(yǔ)義的可搜索加密系統(tǒng)模型
從圖1的系統(tǒng)模型中可以看出,用戶(hù)數(shù)據(jù)通過(guò)網(wǎng)絡(luò)上傳到云服務(wù)器中儲(chǔ)存,存在網(wǎng)絡(luò)攻擊者截取竊聽(tīng)用戶(hù)數(shù)據(jù)的可能,但由于用戶(hù)數(shù)據(jù)上傳前是經(jīng)過(guò)加密的,即使攻擊者盜取用戶(hù)數(shù)據(jù),如果沒(méi)有獲取解密密鑰,也不能破解加密文件,因此該類(lèi)攻擊對(duì)系統(tǒng)的威脅較弱。
另外公有云服務(wù)器具有“誠(chéng)實(shí)而好奇”的特征[13-14],它會(huì)正確地執(zhí)行授權(quán)用戶(hù)提交的陷門(mén)完成查詢(xún)請(qǐng)求,并會(huì)根據(jù)私有云上傳的候選索引標(biāo)識(shí)符找出與之相對(duì)的安全索引,完成檢索服務(wù)后會(huì)如實(shí)返回檢索結(jié)果,但是無(wú)法保證公有云不會(huì)采取一些措施去分析用戶(hù)數(shù)據(jù)、索引及查詢(xún)請(qǐng)求以獲取額外的用戶(hù)隱私信息。
文中探討的為已知密文模型,假設(shè)公有云在知道數(shù)據(jù)用戶(hù)上傳的加密文檔、加密索引和授權(quán)用戶(hù)發(fā)送的查詢(xún)陷門(mén)的前提下,無(wú)法利用查詢(xún)陷門(mén)構(gòu)造出一個(gè)新的查詢(xún)陷門(mén),并且私有云不會(huì)對(duì)外泄露標(biāo)記向量信息,會(huì)如實(shí)地完成授權(quán)用戶(hù)提交的查詢(xún)請(qǐng)求并提交給公有云。并假定數(shù)據(jù)用戶(hù)和授權(quán)用戶(hù)是完全可信的,對(duì)存儲(chǔ)在公有云上的加密文檔有權(quán)限共享,不會(huì)通過(guò)其已了解的部分?jǐn)?shù)據(jù)、索引、陷門(mén)、密鑰等信息來(lái)試圖攻擊其他用戶(hù)隱私信息,且密鑰已經(jīng)安全分發(fā),即數(shù)據(jù)用戶(hù)與授權(quán)用戶(hù)之間的密鑰授權(quán)已經(jīng)完成。
(1)
本體是以樹(shù)狀層次結(jié)構(gòu)對(duì)概念進(jìn)行描述和組織,從而構(gòu)建出概念的語(yǔ)義空間,并使得概念樹(shù)中任意兩個(gè)概念節(jié)點(diǎn)之間的語(yǔ)義距離具有可計(jì)算性。
定義1:文中使用兩個(gè)節(jié)點(diǎn)間的語(yǔ)義距離來(lái)計(jì)算其語(yǔ)義相似度,對(duì)于已知的有向邊A→B,節(jié)點(diǎn)A的深度Deep(A)代表有向邊A→B的深度,則該A→B的語(yǔ)義距離定義為:
(2)
定義2:兩個(gè)概念節(jié)點(diǎn)Vi,Vj之間的語(yǔ)義距離定義為:
Dist(Vi,Vj)=Dist(Vi,Can(Vi,Vj))+
Dist(Vj,Can(Vi,Vj))
(3)
(4)
其中,MaxDeep為本體層次結(jié)構(gòu)的最大深度。
文中使用關(guān)鍵詞詞頻*逆文檔率來(lái)計(jì)算關(guān)鍵詞與文檔的相關(guān)度,計(jì)算公式為:
tf-idf=tf(f,t)*idf(t)
(5)
其中,tf(f,t)為關(guān)鍵詞t在文檔f中出現(xiàn)的頻率,idf的計(jì)算公式為:
(6)
其中,N表示整個(gè)文檔集D中包含的所有文檔個(gè)數(shù),n表示整個(gè)文檔集D中包含有關(guān)鍵詞t的文檔個(gè)數(shù)。
不難發(fā)現(xiàn)上述公式存在如下問(wèn)題:一般情況下,文檔集中會(huì)包含長(zhǎng)短不一的各類(lèi)文檔,而長(zhǎng)文檔(即大文檔)所包含的詞條個(gè)數(shù)通常會(huì)大于短文檔(小文檔)中所包含的詞條個(gè)數(shù),如果同一個(gè)關(guān)鍵詞在長(zhǎng)文檔(10 000個(gè)分詞)和短文檔(100個(gè)分詞)中的詞頻都為10次,顯然上述公式的計(jì)算方法不利于短文檔中關(guān)鍵詞對(duì)文檔的相關(guān)度得分計(jì)算。為公平起見(jiàn),將對(duì)詞頻做歸一化處理,以保證詞頻計(jì)算權(quán)重公式更加合理。
(7)
gf_idf=gf(f,t)*idf(t)
(8)
文中基于向量空間模型實(shí)現(xiàn)文檔檢索,每個(gè)文檔構(gòu)造一個(gè)文檔向量,其維度為文檔集抽取的關(guān)鍵詞集合的個(gè)數(shù),從文檔中抽取的每個(gè)關(guān)鍵詞對(duì)應(yīng)向量的每一維,每一維的值設(shè)置為相應(yīng)關(guān)鍵詞的權(quán)重。用戶(hù)的查詢(xún)也被構(gòu)造成一個(gè)查詢(xún)向量,維度與文檔向量一致。用查詢(xún)向量與文檔向量進(jìn)行內(nèi)積來(lái)計(jì)算查詢(xún)-文檔的相關(guān)度得分并用該相關(guān)度分?jǐn)?shù)對(duì)文檔進(jìn)行排序。文中支持語(yǔ)義的可搜索加密算法描述如下:
Step1:數(shù)據(jù)用戶(hù)從整個(gè)文檔集D=(d1,d2,…,di,…,dm)中使用分詞工具提取出關(guān)鍵詞集合T=(t1,t2,…,tj,…,tn)。
Step2:KMS生成對(duì)稱(chēng)密鑰K,生成的密鑰用三元組形式表示:{S,M1,M2},其中S為n維隨機(jī)比特指示向量,M1、M2為n維可逆矩陣,并將密鑰K安全分發(fā)到數(shù)據(jù)用戶(hù)和授權(quán)用戶(hù)手中。
Step3:數(shù)據(jù)用戶(hù)用式(1)計(jì)算關(guān)鍵詞的位置加權(quán)評(píng)分L,用式(8)計(jì)算出關(guān)鍵詞在文檔中的相關(guān)度得分gf_idf。
Step4:數(shù)據(jù)用戶(hù)為每個(gè)文檔di構(gòu)造出相應(yīng)的文檔向量DVi,若tj∈di,則DVi[j]=1,否則為0。
Step5:數(shù)據(jù)用戶(hù)將文檔向量DVi平均分成u塊,u滿(mǎn)足條件u|n,生成文檔標(biāo)記向量DMVi=(DMVi1,DMVi2,…,DMVij,…,DMViu),方法是如果某塊全為0,則DMVij=0,否則為1。并生成對(duì)應(yīng)索引標(biāo)識(shí)符IMi=(DMVi,idi),后將文檔標(biāo)記向量DMVi及其對(duì)應(yīng)的索引標(biāo)識(shí)符IMi上傳到私有云。
Step7:數(shù)據(jù)用戶(hù)使用加密密鑰K對(duì)文檔集合進(jìn)行D=(d1,d2,…,di,…,dm)加密,生成密文文檔集合C=(c1,c2,…,ci,…,cm),然后提交至公有云上存儲(chǔ)。
Step8:授權(quán)用戶(hù)輸入初始查詢(xún)關(guān)鍵字Q=(q1,q2,…,qi,…,qn),再使用本體知識(shí)庫(kù)進(jìn)行語(yǔ)義擴(kuò)展,并使用語(yǔ)義相似度公式(4)計(jì)算初始關(guān)鍵字與擴(kuò)展詞的語(yǔ)義相似度,選擇相似度排前的s個(gè)擴(kuò)展詞(c1,c2,…,cs)加入到初始查詢(xún)來(lái)構(gòu)成最終的查詢(xún)關(guān)鍵字集合Q'=(q1,q2,…,qi,…,qn,c1,c2,…,cs),其對(duì)應(yīng)的語(yǔ)義相似度為SC=(sc1,sc2,…,scn,scn+1,…,scn+s)。
Step9:根據(jù)語(yǔ)義擴(kuò)展后的查詢(xún)關(guān)鍵字集合Q'構(gòu)造查詢(xún)向量QV,方法是若ti∈Q',則QV[i]=1,否則為0。將查詢(xún)向量QV平均分成u塊,u滿(mǎn)足條件u|n,生成查詢(xún)標(biāo)記向量QMV=(QMV1,QMV2,…,QMVi,…,QMVu),方法是如果某塊全為0,則QMVi=0,否則為1。將查詢(xún)標(biāo)記向量上傳至私有云。
Step11:私有云對(duì)查詢(xún)標(biāo)記向量QMV中的每一位1的值與文檔標(biāo)記向量DMVi進(jìn)行匹配,相同位置上都為1,則說(shuō)明該文檔對(duì)應(yīng)的塊包含有查詢(xún)關(guān)鍵詞,則將文檔標(biāo)記向量DMVi對(duì)應(yīng)的索引標(biāo)識(shí)符上的idi記錄下來(lái),最終得到所有可能包含查詢(xún)關(guān)鍵詞的候選索引標(biāo)識(shí)集合ID'={…,idi,…,idj},并將其提交至公有云。公有云根據(jù)ID'找到對(duì)應(yīng)的安全索引Ii,將對(duì)應(yīng)的SVi與陷門(mén)T進(jìn)行內(nèi)積來(lái)計(jì)算查詢(xún)與文檔的相似度得分。
Step12:對(duì)查詢(xún)-文檔的相似度得分進(jìn)行排序,將前Top_k篇文檔返回給授權(quán)用戶(hù)。
Step13:授權(quán)用戶(hù)使用密鑰K對(duì)返回的文檔進(jìn)行解密,得到原始的明文文檔。
文中實(shí)驗(yàn)環(huán)境為:Windows 7,CPU:i7四核3.4 GHz,內(nèi)存:8 GB,硬盤(pán)空間:1 TB,仿真實(shí)驗(yàn)編程語(yǔ)言:Java。建立了一個(gè)計(jì)算機(jī)領(lǐng)域本體知識(shí)庫(kù),并從Web上抓取計(jì)算機(jī)領(lǐng)域網(wǎng)頁(yè)3 000 個(gè)作為測(cè)試數(shù)據(jù)集,使用ICTCLAS分詞系統(tǒng)抽取出文檔關(guān)鍵詞。實(shí)驗(yàn)的目的是驗(yàn)證在用戶(hù)初始查詢(xún)中加入了本體語(yǔ)義推理的擴(kuò)展詞及在查詢(xún)-文檔的相關(guān)度分?jǐn)?shù)中引入了語(yǔ)義相似度、關(guān)鍵詞不同位置加權(quán)評(píng)分及關(guān)鍵詞-文檔相關(guān)度得分影響因子后,密文檢索效率(用F_measure來(lái)衡量)是否被提高。
(9)
當(dāng)參數(shù)α取值為1時(shí),就是常用的F1調(diào)和平均考慮了precision和recall的結(jié)果,F(xiàn)1值較高則證明文中方法的有效性。
圖2給出了文中方法與MRSE方法創(chuàng)建索引所花費(fèi)時(shí)間的變化趨勢(shì),可以看出隨著文檔關(guān)鍵詞數(shù)量的增加,兩種方法創(chuàng)建索引的時(shí)間都與之成正比,但由于文中方法需要對(duì)文檔向量進(jìn)行分塊標(biāo)記,因此創(chuàng)建索引的時(shí)間略有增加。但是對(duì)數(shù)據(jù)用戶(hù)來(lái)說(shuō)創(chuàng)建索引是外源到云端前的操作,因此對(duì)時(shí)間上的要求不是很高。
圖2 索引創(chuàng)建時(shí)間對(duì)比分析
由于文中方法基于文檔向量和查詢(xún)向量的分塊技術(shù),因此所分塊的數(shù)量u的取值直接決定了標(biāo)記向量的維度,u的取值與檢索時(shí)間成反比。因?yàn)閡值越大,那么文檔向量所分的塊數(shù)越多,每塊的維度“u|n”越小,塊全為0的概率越大,私有云對(duì)查詢(xún)標(biāo)記向量與文檔標(biāo)記向量匹配時(shí),能過(guò)濾掉更多的無(wú)關(guān)文檔,從而會(huì)節(jié)省花費(fèi)在計(jì)算不相關(guān)文檔相關(guān)度分?jǐn)?shù)和文檔排序上的時(shí)間。但是查詢(xún)標(biāo)記向量與文檔標(biāo)記向量是明文保存在私有云上的,u值越大,每塊的維度“u|n”越小,越會(huì)暴露查詢(xún)向量與文檔向量的信息,因此,需要在考慮檢索時(shí)間和保護(hù)隱私兩者間權(quán)衡u的取值。
圖3 檢索時(shí)間對(duì)比分析
圖3給出了文中方法與MRSE方法檢索時(shí)間的變化趨勢(shì),可以看出隨著文檔關(guān)鍵詞數(shù)量的增加,兩種方法的查詢(xún)時(shí)間都與之成正比,但是文中方法比MRSE方法大大降低了檢索時(shí)間。因?yàn)槲闹蟹椒ɑ跇?biāo)記向量,提前過(guò)濾了不相關(guān)文檔,從而節(jié)省了花費(fèi)在計(jì)算不相關(guān)文檔相關(guān)度分?jǐn)?shù)和文檔排序上的時(shí)間。
圖4給出了文中方法與MRSE方法的F1比較,其中相關(guān)性的判斷采用專(zhuān)家評(píng)判的方法??梢钥闯鑫闹蟹椒ㄈ〉昧孙@著結(jié)果,獲得了更高的F1值,也即相關(guān)度得分更高。因?yàn)镸RSE采用的是關(guān)鍵詞精確匹配,沒(méi)有上升到語(yǔ)義層面的檢索,必然不會(huì)檢索出與關(guān)鍵詞語(yǔ)義上相似的文檔。
圖4 F-measure(F1)對(duì)比分析
針對(duì)傳統(tǒng)的可搜索加密算法基于關(guān)鍵詞精確匹配,查全查準(zhǔn)率低,對(duì)檢索結(jié)果沒(méi)有進(jìn)行合理的相關(guān)度排序,無(wú)法滿(mǎn)足用戶(hù)對(duì)智能搜索的要求,提出了一種支持語(yǔ)義的可搜索加密方法。該方法利用本體知識(shí)庫(kù)對(duì)用戶(hù)查詢(xún)進(jìn)行了語(yǔ)義拓展,通過(guò)語(yǔ)義相似度來(lái)控制擴(kuò)展詞的規(guī)模,防止因拓展詞過(guò)多產(chǎn)生“查詢(xún)漂移”。結(jié)合向量空間模型實(shí)現(xiàn)文檔檢索,通過(guò)文檔向量、查詢(xún)向量分塊技術(shù)構(gòu)造出對(duì)應(yīng)的標(biāo)記向量,過(guò)濾無(wú)關(guān)文檔,提高了檢索效率,并通過(guò)引入語(yǔ)義相似度、關(guān)鍵詞不同位置加權(quán)評(píng)分及關(guān)鍵詞-文檔相關(guān)度得分來(lái)構(gòu)造索引,在查詢(xún)-文檔的相似度得分函數(shù)中也引入這三個(gè)影響因子,進(jìn)一步改善了排序效果,從而滿(mǎn)足了授權(quán)用戶(hù)對(duì)檢索結(jié)果排序的需求。