關(guān)于云數(shù)據(jù)的多關(guān)鍵字權(quán)值安全查詢仿真研究

李曉會(huì)，白雨靚，劉 峰

(1.遼寧工業(yè)大學(xué)電子與信息工程學(xué)院，遼寧 錦州 121001；2.中國(guó)科學(xué)院沈陽計(jì)算技術(shù)研究所，遼寧 沈陽 110168)

1 引言

云存儲(chǔ)為用戶的文件持久化提供了便捷可靠的實(shí)現(xiàn)方案，為了保護(hù)數(shù)據(jù)隱私，存儲(chǔ)到云服務(wù)器的文件將會(huì)被轉(zhuǎn)換為密文形式[1]，安全性提高的同時(shí)，也帶來了數(shù)據(jù)查詢困難的問題。如何精確高效查詢數(shù)據(jù)，同時(shí)又防止信息泄露[2-4]，是當(dāng)前研究面臨的主要難點(diǎn)。

文獻(xiàn)[5]針對(duì)密文查詢效率，設(shè)計(jì)了屬性基安全查詢方法，利用屬性基加密增強(qiáng)索引的描述性，該方法具有良好的隱私保障，但是查詢精度欠佳；文獻(xiàn)[6]引入合數(shù)階雙線性群對(duì)數(shù)據(jù)進(jìn)行加密，并通過兩級(jí)系統(tǒng)完成數(shù)據(jù)的查詢?nèi)蝿?wù)，該方法著重優(yōu)化查詢的安全性，雖然密文長(zhǎng)度減小，但是兩次線性運(yùn)算仍然無法保證多關(guān)鍵字查詢時(shí)的效率；文獻(xiàn)[7]針對(duì)關(guān)鍵字設(shè)計(jì)了相關(guān)度計(jì)算，根據(jù)排序情況截取相關(guān)度較好的文件作為查詢結(jié)果，同時(shí)采用虛假陷門對(duì)保護(hù)數(shù)據(jù)安全，該方法實(shí)現(xiàn)了關(guān)鍵字模糊查詢，但是由于沒有考慮關(guān)鍵字的特性，查詢結(jié)果精確度較差；文獻(xiàn)[8]針對(duì)語義與容錯(cuò)問題，利用輸入關(guān)鍵字的模糊音與近義詞設(shè)計(jì)了模糊查詢，同時(shí)引入了偽隨機(jī)函數(shù)來管理私鑰，取得了較好的查詢精度與安全性。現(xiàn)有方法大多基于多關(guān)鍵字的模糊查詢進(jìn)行相應(yīng)的改進(jìn)優(yōu)化，但卻忽視了用戶輸入的多關(guān)鍵字彼此之間可能存在的主次和語法相關(guān)性，因此本文提出關(guān)鍵字權(quán)值計(jì)算，控制查詢的傾向。另外由于現(xiàn)有關(guān)鍵字?jǐn)U展方法針對(duì)的是所有關(guān)鍵字，導(dǎo)致計(jì)算向量與構(gòu)建時(shí)間大幅增加，查詢結(jié)果精確性能下降，為此，提出了核心詞擴(kuò)展方法。另外，設(shè)計(jì)了子矩陣加密與索引動(dòng)態(tài)更新，增加了查詢安全性的同時(shí)，也有效控制了算法復(fù)雜度。

2 云數(shù)據(jù)安全查詢模型

如圖1所示，云存儲(chǔ)數(shù)據(jù)安全查詢系統(tǒng)通?？梢詣澐譃槿齻€(gè)部分，包括云服務(wù)器，數(shù)據(jù)用戶與授權(quán)用戶。數(shù)據(jù)用戶首先把需要上傳到云系統(tǒng)上的文件F=(f1，f2…fm)采取加密處理，得到結(jié)果C=(c1，c2…cm)，然后從文件中抽取出包含的關(guān)鍵字W=(ω1，ω2，…ωm)，并利用其建立陷門和索引，最終將其傳入服務(wù)器。服務(wù)器負(fù)責(zé)存儲(chǔ)文件，以及利用索引查詢出用戶密文。而授權(quán)用戶會(huì)通過請(qǐng)求取得陷門對(duì)應(yīng)的密鑰，從而查詢出服務(wù)器中的密文。

圖1 云存儲(chǔ)數(shù)據(jù)安全查詢系統(tǒng)描述圖

3 多關(guān)鍵字?jǐn)U展權(quán)值的安全密文查詢?cè)O(shè)計(jì)

3.1 多關(guān)鍵字的權(quán)值計(jì)算

用戶輸入的查詢關(guān)鍵字，在主次和語義方面通常具有一定的區(qū)別和聯(lián)系，也各自具有不同的查詢重點(diǎn)，因此，這里引入權(quán)值來描述每個(gè)關(guān)鍵字的重要程度。假定系統(tǒng)將任意關(guān)鍵字ω的原始重要程度默認(rèn)是1，在輸入的其它關(guān)鍵字中，如果ω1其具有語法相關(guān)性，則ω此時(shí)的重要程度應(yīng)該提升至1+r(·)，增量表達(dá)式為

(1)

式中，d代表ω與ω1對(duì)應(yīng)的語法距離，d1代表ω至公共節(jié)點(diǎn)的最小距離。假定系統(tǒng)輸入的原始關(guān)鍵字集合表示為Q={ω1，ω2，ωn}，則查詢關(guān)鍵字的累計(jì)權(quán)值是n，于是其中任一關(guān)鍵字ω的權(quán)值表達(dá)式可以描述為

(2)

3.2 擴(kuò)展查詢核心詞

輸入的關(guān)鍵字集合中，每一個(gè)關(guān)鍵字都可能存在一個(gè)或多個(gè)近義詞，考慮到近義詞模糊 搜索可以增加查詢的完整性，這里設(shè)計(jì)擴(kuò)展查詢方法，但是如果對(duì)所有關(guān)鍵字都進(jìn)行近義詞的檢索，則會(huì)產(chǎn)生大量的擴(kuò)展關(guān)鍵字，從而需要大量的陷門去處理，這無疑提高了查詢開銷，因此，這里首先確定關(guān)鍵字集合中的核心詞，然后針對(duì)核心詞采取近義詞擴(kuò)展，降低查詢次數(shù)的同時(shí)，也避免了出現(xiàn)大量無用查詢結(jié)果。利用前述方法計(jì)算得到每個(gè)關(guān)鍵字的對(duì)應(yīng)權(quán)值，即可表示各自在結(jié)果查詢時(shí)的重要程度，將權(quán)值進(jìn)行排序，從中截取若干權(quán)值較大的作為查詢核心詞擴(kuò)展。

在確定查詢核心詞后，對(duì)核心詞進(jìn)行語義擴(kuò)展，此時(shí)需要計(jì)算出擴(kuò)展詞的對(duì)應(yīng)權(quán)值。這里，采取語義相似度作為權(quán)值計(jì)算的基礎(chǔ)，即先要得到擴(kuò)展的近義詞和核心詞之間的相似程度，影響相似度的主要因素為編輯距離和特征信息，因此相似度計(jì)算公式設(shè)計(jì)如下

fsim=adwi+(1-a)iωft，f

(3)

其中，dw′i表示擴(kuò)展詞ω′i與ωi的編輯距離，iωft，f表示特征信息，它的計(jì)算公式為

(4)

式中ftt，f代表詞項(xiàng)特征信息量，通過文件特征計(jì)算得到，根據(jù)相似度公式，由于編輯距離dw′i的范圍不超過檢索出的文件數(shù)量，且iωft，f∈(0，1)，所以，在計(jì)算相似度時(shí)，應(yīng)該保證dw′i的權(quán)值高于iωft，f。

3.3 空間向量轉(zhuǎn)換

在采用關(guān)鍵字查詢?cè)茢?shù)據(jù)時(shí)，需要在向量空間進(jìn)行實(shí)現(xiàn)，即將索引與查詢信息建立為空間向量，因此，這里針對(duì)索引向量與查詢向量依次進(jìn)行處理。將查詢文檔集內(nèi)所有文檔分別標(biāo)記為具有nbit元素的向量Ii，n表示文檔中包含的關(guān)鍵字?jǐn)?shù)量，如果Ii中的某關(guān)鍵字出現(xiàn)在字典內(nèi)，就將Ii中該關(guān)鍵字設(shè)置成1，反之設(shè)置成0，從而將索引轉(zhuǎn)換為向量形式。當(dāng)?shù)玫揭唤M輸入關(guān)鍵字時(shí)，也將其標(biāo)記為具有nbit元素的向量Q，如果其中某關(guān)鍵字出現(xiàn)在字典內(nèi)，就將Q中該關(guān)鍵字設(shè)置成1，否則設(shè)置成0。據(jù)此，完成查詢輸入的空間向量轉(zhuǎn)換，通過空間向量的操作，完成輸入查詢與文件索引的相關(guān)處理。

3.4 相關(guān)性操作

當(dāng)系統(tǒng)輸入查詢關(guān)鍵字后，要將每個(gè)關(guān)鍵字對(duì)應(yīng)的權(quán)值追加在查詢向量?jī)?nèi)，同時(shí)，在追加過程中將關(guān)鍵字采取排序處理?？紤]到關(guān)鍵字的重要程度，根據(jù)相關(guān)性來做序列重排，比較查詢向量，當(dāng)其中的元素出現(xiàn)在字典時(shí)，把該元素對(duì)應(yīng)位置的1改寫成它的權(quán)值，而通過查詢與索引內(nèi)積計(jì)算可以得到累計(jì)權(quán)值，由于相關(guān)性分別受關(guān)鍵字權(quán)值與相似度影響，于是將相關(guān)性公式描述為

(5)

根據(jù)該公式，便可以計(jì)算得到查詢與索引之間的相關(guān)性。

3.5 密鑰操作

在對(duì)加密的云存儲(chǔ)數(shù)據(jù)進(jìn)行查詢時(shí)，引入子矩陣來產(chǎn)生密鑰，從而使系統(tǒng)能夠動(dòng)態(tài)更新處理。首先利用最近加入字典里的Z個(gè)關(guān)鍵字組成z×z矩陣Mz和Mz′，同時(shí)組成zbit向量Sz；然后根據(jù)Mz、Mz′和Sz更新得到矩陣：

由于處理矩陣被切割成易于計(jì)算的子矩陣，在動(dòng)態(tài)更新時(shí)，不僅能夠保證加密安全性，而且能夠改善加密處理的效率。以n維矩陣為例，它的復(fù)雜度是o(n2)，當(dāng)拆分成兩個(gè)n/2維子矩陣后，其復(fù)雜度是o(2*(n2/2))=o(n2/2)，可見復(fù)雜度被壓縮了一半。

4 多關(guān)鍵字?jǐn)U展權(quán)值安全查詢流程

1)初始化密鑰：云存儲(chǔ)系統(tǒng)針對(duì)字典里的關(guān)鍵字矩陣與向量產(chǎn)生相應(yīng)的密鑰，描述為K(M1，M2，S)，這里的M1和M2均為可逆矩陣，且維度為(n+u+1)×(n+u+1)，n代表關(guān)鍵字個(gè)數(shù)。

(6)

(7)

3)擴(kuò)展查詢向量：針對(duì)系統(tǒng)輸入查詢向量Q={ω1，ω2…ωi}，采取權(quán)值計(jì)算，同時(shí)篩選出其中的核心詞，搜索出其近義詞構(gòu)建得到新查詢向量Q′={ω1，ω2，…ωi+z}。

(8)

于是，經(jīng)過加密處理后的查詢向量表示為

(9)

這里，采用加密后的Enc_sk(Q)構(gòu)建安全陷門。

5)查詢：查詢過程中，通過求解查詢與索引的內(nèi)積，得到查詢的匹配程度，計(jì)算如下：

(10)

為了保證安全性，εi為隨機(jī)數(shù)，且服從正態(tài)分布，σi表示標(biāo)準(zhǔn)差，它用于調(diào)劑查詢精度與查詢安全。根據(jù)該公式，可以判定文件與查詢關(guān)鍵字的匹配性，從而完成查詢?nèi)蝿?wù)。

5 仿真分析

仿真采用Enron數(shù)據(jù)集作為查詢文件集，它具有的文件數(shù)量達(dá)到了11008個(gè)，并基于Java與大數(shù)據(jù)處理框架的Storn實(shí)現(xiàn)安全查詢算法和功能。為了有效驗(yàn)證本文方法的性能，引入文獻(xiàn)[8]中的關(guān)鍵字模糊查詢作為對(duì)比，分別從查詢精度，安全性，以及時(shí)間效率三方面進(jìn)行仿真與結(jié)果分析。

5.1 查詢精確度結(jié)果分析

查詢精度是衡量查詢性能的首要指標(biāo)，因此首先通過仿真驗(yàn)證本文方法的查詢精確度。假定以Pk代表查詢精度，則它的計(jì)算公式為

PK=k′/k

(11)

其中，k′為查詢結(jié)果里的正確文件量，k為云存儲(chǔ)系統(tǒng)中的全部文件量。通過仿真，得到查詢精度與文件規(guī)模之間的關(guān)系，如圖2所示。根據(jù)結(jié)果曲線可知，本文方法的查詢精度基本不受文件規(guī)模的影響，而且查詢精度顯著高于對(duì)比方法，始終在90%上下輕微波動(dòng)。這是由于方法在查詢過程中，采用了多關(guān)鍵字權(quán)值技術(shù)，通過權(quán)值確定核心詞，并對(duì)其進(jìn)行擴(kuò)展，合理的分配了各關(guān)鍵字對(duì)查詢結(jié)果的影響程度；同時(shí)還采用了匹配程度計(jì)算，通過該計(jì)算中的σ來調(diào)劑查詢精度，當(dāng)合理降低σ值時(shí)，即可避免精度受干擾。

圖2 查詢精度實(shí)驗(yàn)結(jié)果曲線

5.2 查詢安全性結(jié)果分析

(12)

圖3 查詢安全性實(shí)驗(yàn)曲線

根據(jù)圖3結(jié)果分析可知，隨著文件規(guī)模的增加，各方法的安全性都受到相應(yīng)的影響，但是本文方法的受影響程度最小，安全性始終保持最好，且下降很慢。其原因是由于加密過程中設(shè)計(jì)了匹配度計(jì)算，通過調(diào)節(jié)σ值，可以有效保護(hù)排序信息，而且設(shè)計(jì)了子矩陣拆分與動(dòng)態(tài)索引更新，提高了加密處理速度，也使得索引能夠符合各種情況的隱私需求。

5.3 查詢時(shí)間結(jié)果分析

為了驗(yàn)證本文方法對(duì)于云數(shù)據(jù)查詢的高效性，在保證字典參數(shù)N=5000不變的前提下，首先只改變?cè)拼鎯?chǔ)文件規(guī)模的大小，仿真得到查詢時(shí)間與文件數(shù)量之間的關(guān)系，如圖4所示。根據(jù)實(shí)驗(yàn)曲線可知，各方法對(duì)于云數(shù)據(jù)的安全查詢效率均受云存儲(chǔ)數(shù)文件數(shù)量的多少影響，但是在同一文件規(guī)模下，本文方法的執(zhí)行時(shí)間要優(yōu)于對(duì)比方法。導(dǎo)致該結(jié)果的原因是：各方法都需要對(duì)文件建立索引，而文件規(guī)模的增加導(dǎo)致索引向量的增加，算法復(fù)雜度隨之增加，但是由于本文方法提出了核心詞擴(kuò)展，無需像對(duì)比方法一樣搜索出所有關(guān)鍵字的近義詞，大幅度節(jié)省了查詢時(shí)間；另外在查詢加密的過程中設(shè)計(jì)了子矩陣拆分，直接將原始矩陣加密處理的復(fù)雜度降低了一半，從而有效提高了查詢效率。

圖4 查詢時(shí)間與文件數(shù)量之間的關(guān)系曲線

在只改變查詢關(guān)鍵字?jǐn)?shù)量的情況下，通過仿真得到查詢時(shí)間與關(guān)鍵字?jǐn)?shù)量之間的關(guān)系，如表1所示。根據(jù)表中結(jié)果數(shù)據(jù)可知，各方法對(duì)于云數(shù)據(jù)的查詢效率基本不受查詢關(guān)鍵字?jǐn)?shù)量的影響，但是本文方法的執(zhí)行時(shí)間具有明顯優(yōu)勢(shì)。導(dǎo)致該結(jié)果的原因是：在查詢過程中，各方法都是基于向量?jī)?nèi)積計(jì)算，由于關(guān)鍵字?jǐn)?shù)量的改變并不影響向量維度，所以不會(huì)影響到查詢執(zhí)行的時(shí)間。

表1 查詢時(shí)間與關(guān)鍵字?jǐn)?shù)量之間的關(guān)系

6 結(jié)束語

為了提高云存儲(chǔ)數(shù)據(jù)的查詢性能，基于現(xiàn)有研究結(jié)果及存在的問題，提出并設(shè)計(jì)了多關(guān)鍵字?jǐn)U展權(quán)值安全查詢方法?？紤]到用戶輸入的多關(guān)鍵字可能存在的主次傾向和語義聯(lián)系，計(jì)算出各關(guān)鍵字的相應(yīng)權(quán)值，并基于權(quán)值搜索出其中的核心詞，對(duì)核心詞采取語義擴(kuò)展，增加搜索范圍的同時(shí)，也避免了對(duì)所有關(guān)鍵字?jǐn)U展可能出現(xiàn)的高負(fù)載。在加密處理時(shí)，設(shè)計(jì)了子矩陣拆分方法計(jì)算密鑰，并引入索引動(dòng)態(tài)更新機(jī)制，提高查詢安全性的同時(shí)也有利于查詢的效率。通過仿真結(jié)果，表明多關(guān)鍵字?jǐn)U展權(quán)值查詢方法能夠有效提高云加密數(shù)據(jù)的查詢精度與查詢效率，同時(shí)顯著改善隱私數(shù)據(jù)查詢的安全性。