云存儲(chǔ)中基于二進(jìn)制向量索引的密文云數(shù)據(jù)排序查詢方法

陳蘭香 周書明

(福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 福建 福州 350108)(福建師范大學(xué)網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室 福建 福州 350108)

云存儲(chǔ)中基于二進(jìn)制向量索引的密文云數(shù)據(jù)排序查詢方法

陳蘭香 周書明

(福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院 福建 福州 350108)(福建師范大學(xué)網(wǎng)絡(luò)安全與密碼技術(shù)重點(diǎn)實(shí)驗(yàn)室 福建 福州 350108)

設(shè)計(jì)一種適用于公共云存儲(chǔ)環(huán)境下的密文云數(shù)據(jù)排序查詢方法，其核心思想是使用二進(jìn)制向量索引，并且使用Hash函數(shù)計(jì)算向量元素為1的位置。這種方法使得建立索引向量非常方便，并且更易于建立查詢向量以及進(jìn)行后續(xù)數(shù)據(jù)更新操作。由用戶對(duì)其文件集構(gòu)建二進(jìn)制向量索引，當(dāng)用戶要求訪問(wèn)包含某些關(guān)鍵詞的文件時(shí),首先根據(jù)查詢關(guān)鍵詞構(gòu)建查詢二進(jìn)制向量,然后根據(jù)查詢二進(jìn)制向量與文件的索引二進(jìn)制向量之間的內(nèi)積判斷該文件是否包含用戶的查詢關(guān)鍵詞。根據(jù)內(nèi)積計(jì)算結(jié)果可知哪些文件的相關(guān)性更強(qiáng)，并且內(nèi)積計(jì)算效率高。實(shí)驗(yàn)表明，該方法的索引創(chuàng)建與查詢效率都非常高。

云存儲(chǔ) 密文檢索 二進(jìn)制向量索引 排序查詢

0 引 言

在云存儲(chǔ)環(huán)境下，要保護(hù)用戶數(shù)據(jù)機(jī)密性和隱私性，加密是一種常用的方法，但是數(shù)據(jù)加密后，密文數(shù)據(jù)檢索問(wèn)題亟待解決。

目前主要有兩種典型的方法來(lái)解決密文云數(shù)據(jù)檢索問(wèn)題：第一種是直接對(duì)密文進(jìn)行線性搜索，第二種方法基于安全索引。線性搜索對(duì)密文中單詞逐個(gè)進(jìn)行比對(duì)，確認(rèn)關(guān)鍵詞是否存在以及出現(xiàn)的次數(shù)；安全索引先對(duì)文檔建立關(guān)鍵詞索引，然后將文檔和索引加密后上傳至云端，搜索時(shí)從索引中查詢關(guān)鍵詞是否存在于某個(gè)文檔中。第一種方法缺點(diǎn)在于搜索效率不高，且無(wú)法應(yīng)對(duì)海量數(shù)據(jù)的搜索場(chǎng)景。第二種方法是目前的研究主流，原因是其查詢效率更好，安全性能更高，適用于大規(guī)模的云存儲(chǔ)密文檢索系統(tǒng)。

對(duì)于大型企業(yè)或組織，當(dāng)其數(shù)據(jù)量很大時(shí)，可以構(gòu)建私有云存儲(chǔ)服務(wù)。但是對(duì)于一些中小企業(yè)或個(gè)人用戶，為了節(jié)省成本及訪問(wèn)方便，更加需要公共云存儲(chǔ)服務(wù)。

用戶的主要數(shù)據(jù)存放在家用或辦公臺(tái)式機(jī)上，而平時(shí)主要使用手機(jī)與平板電腦等手持設(shè)備訪問(wèn)網(wǎng)絡(luò)，這是目前很多用戶的現(xiàn)實(shí)情況。讓用戶可以隨時(shí)隨地使用任意設(shè)備訪問(wèn)其數(shù)據(jù)是用戶最迫切需要實(shí)現(xiàn)的功能，公共云存儲(chǔ)服務(wù)即是一個(gè)最佳選擇。

用戶的數(shù)據(jù)類型很豐富，有文檔、照片、視頻等各種數(shù)據(jù)類型。有些文件，比如用戶的一些私人照片，用戶并不希望被別人看見(jiàn)，因此其文件存放到云端前，用戶需要對(duì)數(shù)據(jù)進(jìn)行加密處理。數(shù)據(jù)一旦加密，如果沒(méi)有可用的檢索機(jī)制，用戶只有將文件全部下載到本地解密后才能找到當(dāng)前需要訪問(wèn)的文件，這種方式顯然不實(shí)用，會(huì)帶來(lái)太大的網(wǎng)絡(luò)與計(jì)算開銷。因此，如果在將所有文件進(jìn)行加密前，對(duì)其按關(guān)鍵詞建立索引，查詢文件時(shí)使用關(guān)鍵詞進(jìn)行搜索，只將符合查詢關(guān)鍵詞的文件下載到本地才是實(shí)用的。

本文的目標(biāo)就在于設(shè)計(jì)一種適用于以上場(chǎng)景的密文云數(shù)據(jù)查詢方法。

本文設(shè)計(jì)一種適用于公共云存儲(chǔ)環(huán)境下的密文云數(shù)據(jù)排序查詢方法，該方法基于二進(jìn)制向量索引，使用向量?jī)?nèi)積計(jì)算判斷某文件是否包含指定關(guān)鍵詞。該方法的優(yōu)點(diǎn)如下：(1) 完全基于對(duì)稱密碼技術(shù)，效率很高；(2) 支持多關(guān)鍵詞查詢；(3) 查詢基于內(nèi)積計(jì)算，計(jì)算效率高；(4) 該方法易于進(jìn)行數(shù)據(jù)更新。最后用戶的文件可以是任何類型，比如可以是壓縮文件、多媒體文件等，只需事前建立二進(jìn)制向量索引。

1 相關(guān)工作

2000年，Song等[1]第一次提出基于對(duì)稱密碼的可檢索加密方法SSE(Searchable Symmetric Encryption)，并提出一個(gè)非交互式的基于單關(guān)鍵詞的檢索方案。該方案主要是在加密結(jié)果中增加一種基于流密碼的信息檢索算法的驗(yàn)證機(jī)制，具有極強(qiáng)的抵抗統(tǒng)計(jì)分析的能力。但在海量數(shù)據(jù)環(huán)境下，復(fù)雜的驗(yàn)證過(guò)程會(huì)消耗大量的服務(wù)器資源。

為了改進(jìn)效率，Goh[2]提出使用安全索引的方法實(shí)現(xiàn)對(duì)海量密文數(shù)據(jù)的快速檢索，并基于Bloom Filters構(gòu)建了一種適應(yīng)性選擇關(guān)鍵字攻擊安全的稱為Z-IDX的安全索引。在該索引上進(jìn)行查詢時(shí)處理每個(gè)文檔的時(shí)間為O(1)，并且能夠處理任意長(zhǎng)度單詞。但是BloomFilters的引入使得該方法的檢索結(jié)果具有一定的錯(cuò)誤率。Chang等[3]構(gòu)造了一個(gè)相似的查詢時(shí)間為O(n)而沒(méi)有誤報(bào)的文件索引方案。

Curtmola等[4]提出第一個(gè)子線性搜索時(shí)間的方案SSE-1和SSE-2。所提方案為整個(gè)文檔集關(guān)聯(lián)一個(gè)加密的倒序索引，每個(gè)入口由關(guān)鍵詞的門陷和相關(guān)文檔標(biāo)識(shí)符的加密集組成。方案的搜索時(shí)間是O(r)，r是包含關(guān)鍵詞的文件數(shù)量。他們利用廣播加密實(shí)現(xiàn)多用戶環(huán)境下的查詢授權(quán)，并在Song[1]的基礎(chǔ)上給出更嚴(yán)格的安全性定義。Kurosawa等[5]研究了可驗(yàn)證的通用可組合安全的SSE方案。

以上方案都沒(méi)有考慮數(shù)據(jù)更新。

Wang等[6]考慮關(guān)鍵詞詞頻信息，提出基于對(duì)稱密碼保序加密技術(shù)OPSE(OrderPreservingSymmetricEncryption)的單關(guān)鍵詞分級(jí)密文排序檢索方法RSSE(RankedSSE)，利用信息檢索中的統(tǒng)計(jì)排序方法，在建立索引的同時(shí)為每個(gè)文件嵌入權(quán)重信息，從而能夠按用戶的要求返回前N個(gè)符合要求的結(jié)果。由于服務(wù)器知道相關(guān)性得分信息，所以O(shè)PSE雖然可以提高效率但沒(méi)有SSE安全。

Li等[7]針對(duì)關(guān)鍵詞精確匹配的不足提出基于編輯距離的加密字符串模糊檢索方案。所提方案使用編輯距離量化字符串的相似度，并為每個(gè)字符串附加一個(gè)基于通配符的模糊字符串組，用多個(gè)精確匹配來(lái)實(shí)現(xiàn)模糊檢索。

Wang等[8]提出一個(gè)隱私保護(hù)的相似性檢索機(jī)制，利用壓縮技術(shù)建立存儲(chǔ)高效的相似關(guān)鍵詞集合，使用編輯距離作為相似性度量。通過(guò)建立基于遍歷樹的索引實(shí)現(xiàn)常量時(shí)間復(fù)雜度的相似檢索功能，并且自然地支持模糊檢索，用于容忍用戶輸入時(shí)的拼寫錯(cuò)誤或表示的不一致。

黃汝維等[9]設(shè)計(jì)了一個(gè)基于矩陣和向量運(yùn)算的可計(jì)算加密方案CESVMC。該方案將云數(shù)據(jù)分為字符串和數(shù)值數(shù)據(jù)兩大類，通過(guò)運(yùn)用向量和矩陣的各種運(yùn)算，實(shí)現(xiàn)了對(duì)數(shù)據(jù)的加密。支持對(duì)加密字符串的模糊檢索和對(duì)加密數(shù)值數(shù)據(jù)的加、減、乘、除四種算術(shù)運(yùn)算，并保證了數(shù)據(jù)存儲(chǔ)、運(yùn)算過(guò)程中的隱私安全性。

Liesdonk等[10]第一次明確地提出動(dòng)態(tài)性的SSE方案，但他們的方案只支持有限次的更新。Kamara等[11]擴(kuò)展Curtmola等[4]的倒排索引的方法，提出動(dòng)態(tài)SSE的形式化的安全定義，并構(gòu)造第一個(gè)動(dòng)態(tài)的、CKA2安全的SSE方案。接下來(lái)，在文獻(xiàn)[12]中，他們基于關(guān)鍵詞紅黑樹KRB(keywordred-black)構(gòu)造可并行并且支持更新的SSE方案。他們的研究結(jié)果表明使用KRB樹可以建立文檔索引，使得關(guān)鍵詞檢索可以在O(rlogn)串行時(shí)間和O(r/plogn)并行時(shí)間完成。

Hahn等[13]提出一個(gè)子線性檢索時(shí)間的對(duì)稱密碼可搜索加密方案，實(shí)現(xiàn)了數(shù)據(jù)動(dòng)態(tài)更新，其更新只泄露數(shù)據(jù)訪問(wèn)模式。Stefanov等[14]使用文檔關(guān)鍵字對(duì)的對(duì)數(shù)級(jí)層次結(jié)構(gòu)實(shí)現(xiàn)數(shù)據(jù)更新。Kurosawat等[15]提出一種可驗(yàn)證的更新方案。但該方案需要為每個(gè)關(guān)鍵詞生成一個(gè)MAC，所以修改文件的效率比較低。Naveed等[16]引入一個(gè)新的元語(yǔ)：盲存儲(chǔ)，允許用戶存儲(chǔ)一組文件在遠(yuǎn)程服務(wù)器上，但服務(wù)器并不知道存儲(chǔ)了多少文件，也不知道單個(gè)文件的長(zhǎng)度，當(dāng)文件被檢索時(shí)，服務(wù)器只是知道文件的存在，但不知道文件名及內(nèi)容。

以上都是針對(duì)單關(guān)鍵詞的方案，關(guān)于多關(guān)鍵詞密文搜索也有一些方案。

Cao等[17]提出一個(gè)多關(guān)鍵詞排序檢索方案，擴(kuò)展了Wang等[6]的工作以支持多關(guān)鍵詞查詢，并基于安全kNN(k-nearestneighbor)查詢技術(shù)中索引向量與查詢向量間“內(nèi)積相似度”來(lái)實(shí)現(xiàn)排序查詢并進(jìn)行隱私保護(hù)增強(qiáng)。

Sun等[18]提出一種支持相似度排序的多關(guān)鍵詞文本檢索方案，基于詞頻和向量空間模型構(gòu)建索引，并利用余弦相似性度量來(lái)實(shí)現(xiàn)更高的搜索精度。該方案基于樹的索引結(jié)構(gòu)及多維算法，從而得到比線性搜索更好的檢索效率。Moatazt等[19]提出一種基于關(guān)鍵詞域上的格拉姆-施密特正交化過(guò)程的布爾檢索方案，檢索時(shí)只需進(jìn)行簡(jiǎn)單的內(nèi)積計(jì)算，并且對(duì)查詢進(jìn)行隨機(jī)化處理，從而隱藏搜索模式。

王尚平等[20]采用授權(quán)用戶和存儲(chǔ)服務(wù)器先后對(duì)關(guān)鍵詞加密的方式提出了一個(gè)基于連接關(guān)鍵詞的可搜索加密方案。該方案使授權(quán)用戶能利用連接關(guān)鍵詞的陷門搜索加密文檔，并證明方案在確定性Diffie-Hellman問(wèn)題假設(shè)下是安全的。

文獻(xiàn)[21,22]圍繞可搜索加密技術(shù)基本定義、典型構(gòu)造和擴(kuò)展研究，對(duì)可搜索加密相關(guān)工作進(jìn)行了綜述。

當(dāng)用戶數(shù)據(jù)豐富，平時(shí)習(xí)慣使用手機(jī)、平板電腦等手持設(shè)備訪問(wèn)其數(shù)據(jù)時(shí)，他們便需要使用公共云存儲(chǔ)服務(wù)來(lái)實(shí)現(xiàn)隨時(shí)隨地任意設(shè)備來(lái)訪問(wèn)其數(shù)據(jù)。本文設(shè)計(jì)一種適用于此場(chǎng)景的密文云數(shù)據(jù)查詢方法，該方法基于二進(jìn)制向量索引，使用向量?jī)?nèi)積計(jì)算判斷某文件是否包含指定關(guān)鍵詞。該方法完全基于對(duì)稱密碼技術(shù)，效率很高；數(shù)據(jù)查詢基于內(nèi)積計(jì)算，計(jì)算效率高；支持多關(guān)鍵詞查詢，并且該方法易于進(jìn)行數(shù)據(jù)更新。

2 二進(jìn)制向量索引

2.1 符號(hào)定義

F={f1,f2,…,fm}：用戶文件集合；

W={w1,w2,…,wn}：關(guān)鍵詞集合；

R=Qt·I：內(nèi)積運(yùn)算，符號(hào)“·”表示求兩個(gè)向量的內(nèi)積；

g:{0,1}t×{0,1}l→{0,1}l，偽隨機(jī)函數(shù)PRF(Pseudo-randomFunction)，用作偽隨機(jī)數(shù)生成器；

h:{0,1}k×{1,2,…,n}→{1,2,…,n}，偽隨機(jī)置換PRP(Pseudo-randomPermutation)，用于確定關(guān)鍵詞的位置。

其中，k是密鑰長(zhǎng)度，關(guān)鍵詞wi在數(shù)組中的存放位置p=hk(wi) modq，q為比n略大的素?cái)?shù)。

2.2 二進(jìn)制向量索引構(gòu)建方法

用戶使用已有分詞算法對(duì)其文件集提取關(guān)鍵詞，構(gòu)建關(guān)鍵詞集合，并構(gòu)建所有文件的二進(jìn)制向量索引。然后對(duì)文件使用對(duì)稱密碼機(jī)制進(jìn)行加密，如果是基于數(shù)據(jù)塊，還要將文件按設(shè)定數(shù)據(jù)塊大小進(jìn)行分塊，最后將加密的文件發(fā)送到云端。

二進(jìn)制向量索引構(gòu)建方法如下：用戶根據(jù)每個(gè)文件中是否包含關(guān)鍵詞集合中的對(duì)應(yīng)關(guān)鍵詞來(lái)構(gòu)建二進(jìn)制向量索引，將每個(gè)文件提取的關(guān)鍵詞進(jìn)行Hash計(jì)算，并模一個(gè)素?cái)?shù)q作為存放該關(guān)鍵詞的二進(jìn)制向量的下標(biāo)，即關(guān)鍵詞wi在向量中的下標(biāo)為p=hk(wi) modq(q為比n大的素?cái)?shù))，將此位置1，其余所有位全部置0。

為了有效地實(shí)現(xiàn)數(shù)據(jù)更新，在有效關(guān)鍵詞基礎(chǔ)上增加20%的空余位，假設(shè)有1 000個(gè)關(guān)鍵詞，每個(gè)二進(jìn)制索引向量將占1 200bits。

查詢某個(gè)關(guān)鍵詞是否在關(guān)鍵詞集合中時(shí)，只須將該關(guān)鍵詞進(jìn)行Hash計(jì)算并模一個(gè)素?cái)?shù)以查詢?cè)撓聵?biāo)的向量元素值，如果為1，表明該關(guān)鍵詞存在關(guān)鍵詞集合中，否則不存在。

舉一個(gè)簡(jiǎn)單的例子，如圖1所示，假設(shè)關(guān)鍵詞集合為{云計(jì)算，云存儲(chǔ)，加密，數(shù)據(jù)檢索，二進(jìn)制向量}，關(guān)鍵詞總數(shù)為5，那么增加20%的bit位，最接近的素?cái)?shù)q可以設(shè)為7。文件1包含關(guān)鍵詞{云計(jì)算，加密}，則其索引二進(jìn)制向量計(jì)算方法如下：

P11=hk(“云計(jì)算”) mod 7,P12=hk(“加密”) mod 7，假設(shè)計(jì)算結(jié)果P11=2，P12=4，則文件1的二進(jìn)制索引向量為I1=(0,0,1,0,1,0,0)，文件2包含關(guān)鍵詞{云存儲(chǔ)，加密，數(shù)據(jù)檢索，二進(jìn)制向量}，則P21=hk(“云存儲(chǔ)”) mod 7,P22=hk(“加密”) mod 7，P23=hk(“數(shù)據(jù)檢索”) mod 7，P24=hk(“二進(jìn)制向量”) mod 7，假設(shè)計(jì)算結(jié)果P21=3，P22=4，P23=1，P24=6，則文件2的索引二進(jìn)制向量為I2=(0,1,0,1,1,0,1)。

圖1 二進(jìn)制向量索引圖

對(duì)于有10 000個(gè)關(guān)鍵詞的文件集，每個(gè)文件的二進(jìn)制向量索引只占12Kbits，100個(gè)文件占150KB，相比于倒排索引，每個(gè)關(guān)鍵詞一個(gè)索引表，10 000個(gè)關(guān)鍵詞將產(chǎn)生10 000個(gè)索引表。

3 基于二進(jìn)制向量索引的密文排序查詢方案

3.1 方案設(shè)計(jì)

用戶根據(jù)查詢關(guān)鍵詞與關(guān)鍵詞集合構(gòu)建查詢二進(jìn)制向量，并使用查詢二進(jìn)制向量與所有文件的索引二進(jìn)制向量進(jìn)行內(nèi)積計(jì)算以判斷文件是否包含查詢關(guān)鍵詞，然后向云端請(qǐng)求包含查詢關(guān)鍵詞的文件密文。

構(gòu)建查詢二進(jìn)制向量方法如下：用戶根據(jù)查詢關(guān)鍵詞是否在關(guān)鍵詞集合中構(gòu)建查詢二進(jìn)制向量，設(shè)Ii是文檔Fi的二進(jìn)制索引向量，其中Ii[j]∈{0, 1}表示關(guān)鍵詞wj是否在文檔中存在；Q是一個(gè)查詢向量，其中Q[j]∈{0, 1}表示關(guān)鍵詞wj是否在查詢關(guān)鍵詞集合中。文檔Fi與查詢關(guān)鍵詞集合的相似性得分通過(guò)內(nèi)積方式計(jì)算出來(lái)，即IQ。當(dāng)內(nèi)積計(jì)算結(jié)果為非0時(shí)，表明該文件包含查詢關(guān)鍵詞，當(dāng)內(nèi)積計(jì)算結(jié)果為0時(shí)，表明該文件不包含查詢關(guān)鍵詞。并且內(nèi)積計(jì)算結(jié)果的值越大，表明包含的關(guān)鍵詞越多。

可以將算法形式化地表示為一個(gè)五元算法(Setup，IndxStrc，Enc，Query，Dec)，簡(jiǎn)單描述如下。

初始化階段Setup()：用戶使用偽隨機(jī)函數(shù)g生成隨機(jī)數(shù)s∈{0, 1}l，并生成文件加密密鑰。

索引構(gòu)建IndxStrc()：用于構(gòu)建索引，對(duì)每個(gè)文件fj，用戶為其生成二進(jìn)制索引Ij，滿足：如果文件fj包含關(guān)鍵詞wi，則Ij[p]=1，否則為Ij[p]=0，其中p=hs(wi) modq，q為比n略大的素?cái)?shù)。

加密Enc()：使用文件加密密鑰對(duì)文件F={f1,f2,…,fm}進(jìn)行對(duì)稱加密，得到密文C={c1,c2,…,cm}，用戶將加密文件集C存放于云存儲(chǔ)服務(wù)器。

解密文件Dec()：使用相應(yīng)文件密鑰解密返回的文件，就是按相關(guān)度排序后的文件。

用戶只需將關(guān)鍵詞集合、所有文件的二進(jìn)制向量索引及文件密鑰存于所使用的任何訪問(wèn)設(shè)備上便可實(shí)現(xiàn)隨時(shí)隨地訪問(wèn)。

3.2 數(shù)據(jù)更新

數(shù)據(jù)更新涉及到多種操作，包括修改、增加、刪除等。

修改數(shù)據(jù)只需要對(duì)涉及到修改的文件進(jìn)行更新，如果有增加新的關(guān)鍵詞，將關(guān)鍵詞加入關(guān)鍵詞集合，然后重新對(duì)數(shù)據(jù)建立二進(jìn)制向量索引，對(duì)數(shù)據(jù)重新加密，然后將加密的文件發(fā)送至云端，將以前的數(shù)據(jù)刪除。

增加數(shù)據(jù)與修改數(shù)據(jù)類似，對(duì)增加的數(shù)據(jù)構(gòu)建二進(jìn)制向量索引，對(duì)數(shù)據(jù)加密，然后將加密的文件發(fā)送至云端。

添加文件時(shí)，因?yàn)樵谒饕蛄繕?gòu)建時(shí)預(yù)留了20%的空閑空間，因此只需要對(duì)新文件分詞，將原有關(guān)鍵詞集合中沒(méi)有的關(guān)鍵詞(假設(shè)有t個(gè))加入關(guān)鍵詞集合后面，對(duì)新文件構(gòu)建二進(jìn)制向量索引，而其他文件索引均無(wú)須修改。

刪除數(shù)據(jù)時(shí)只需要將云端相應(yīng)數(shù)據(jù)刪除，而將本地的相應(yīng)索引及文件密鑰刪除。

本方法具有以下的優(yōu)勢(shì)：

(1) 數(shù)據(jù)更新方便，建立索引的過(guò)程由用戶完成，關(guān)鍵詞集合信息由用戶保管，當(dāng)有文件需要更新時(shí)，用戶只需要更新文件的二進(jìn)制向量索引，并重新加密文件，然后將加密的文件發(fā)送至云端。

(2) 使用二進(jìn)制向量?jī)?nèi)積計(jì)算非常高效，只需要在用戶端增加少量的存儲(chǔ)就可以實(shí)現(xiàn)高效的檢索。

4 性能分析

因?yàn)閿?shù)據(jù)的加解密及檢索操作均在本地完成，所以不向云端服務(wù)器泄露任何信息，本方法適用于公共云存儲(chǔ)環(huán)境下的密文云數(shù)據(jù)查詢，主要優(yōu)勢(shì)在于其效率。

在訪問(wèn)效率上，通過(guò)以上過(guò)程可以發(fā)現(xiàn)使用密文查詢機(jī)制給用戶帶來(lái)的方便性：首先，用戶不需要為了沒(méi)有包含關(guān)鍵字的文件浪費(fèi)網(wǎng)絡(luò)和存儲(chǔ)資源，提高計(jì)算效率；其次，用戶不必對(duì)不符合條件的文件進(jìn)行解密操作，節(jié)省了本地的計(jì)算資源。

本文提出的二進(jìn)制向量索引方案與已有方案在索引大小、查詢時(shí)間復(fù)雜度等方面的對(duì)比見(jiàn)表1所示，二進(jìn)制向量索引方案均是最優(yōu)的。

表1 二進(jìn)制向量索引方案與其它方案的比較

其中，m是文件集中包含的文件數(shù)，n是關(guān)鍵詞的數(shù)量，|F|是文件集數(shù)據(jù)量的大小。

二進(jìn)制向量索引方案的關(guān)鍵詞與索引的存儲(chǔ)空間需求見(jiàn)表2，為了便于更新，設(shè)置索引預(yù)留20%的空間，設(shè)一個(gè)漢字占2個(gè)字節(jié)，一個(gè)關(guān)鍵詞設(shè)為最多5個(gè)漢字，占10個(gè)字節(jié)，假設(shè)有1 000個(gè)關(guān)鍵詞，存儲(chǔ)關(guān)鍵詞集合只需要約10KB字節(jié)的存儲(chǔ)空間。每個(gè)文件的二進(jìn)制向量索引大小為1 200bits，為15B，1 000個(gè)文件，只需要15KB的索引存儲(chǔ)空間。假設(shè)關(guān)鍵詞總數(shù)為4 000個(gè)，那么每個(gè)文件的索引存儲(chǔ)空間為600B，1 000個(gè)文件就是600KB。相比于倒排索引，每個(gè)關(guān)鍵詞一個(gè)索引表，10 000個(gè)關(guān)鍵詞將產(chǎn)生10 000個(gè)索引表。

表2 關(guān)鍵詞與索引的存儲(chǔ)空間

本實(shí)驗(yàn)在配置為Intel Core i5 CPU 1.6 GHz，4 GB RAM的機(jī)器上基于Java語(yǔ)言使用HMAC-SHA256算法創(chuàng)建索引。創(chuàng)建索引的主要開銷在于計(jì)算關(guān)鍵詞的向量下標(biāo)，所以與每個(gè)文件包含的關(guān)鍵詞平均數(shù)有關(guān)，假設(shè)平均每個(gè)文件包含5個(gè)關(guān)鍵詞。實(shí)驗(yàn)時(shí)，我們假設(shè)關(guān)鍵詞已經(jīng)提取，當(dāng)關(guān)鍵詞總數(shù)為n=2 000，其索引創(chuàng)建時(shí)間與文件數(shù)的關(guān)系如圖2所示，從圖中可以看出創(chuàng)建索引的開銷與文件數(shù)呈線性增長(zhǎng)。設(shè)文件集中包含的文件數(shù)m=1 000，其索引創(chuàng)建時(shí)間與關(guān)鍵詞數(shù)量的關(guān)系如圖3所示。

圖2 索引創(chuàng)建時(shí)間與文件數(shù)的關(guān)系

圖3 索引創(chuàng)建時(shí)間與關(guān)鍵詞數(shù)量的關(guān)系

查詢時(shí)間開銷如圖4和圖5所示，設(shè)查詢關(guān)鍵詞總數(shù)為10個(gè)，查詢時(shí)間開銷與文件數(shù)的關(guān)系如圖4所示，從圖中可以看出查詢時(shí)間開銷與文件數(shù)呈線性增長(zhǎng)。設(shè)文件集中包含的文件數(shù)m=1 000，查詢時(shí)間開銷與查詢關(guān)鍵詞總數(shù)的關(guān)系如圖5所示。

圖4 查詢時(shí)間開銷與文件數(shù)的關(guān)系

圖5 查詢時(shí)間開銷與查詢?cè)~數(shù)量的關(guān)系

5 結(jié) 語(yǔ)

本文提出一種基于二進(jìn)制向量索引的密文云數(shù)據(jù)排序查詢方法，由用戶對(duì)其文件集構(gòu)建二進(jìn)制向量索引，并使用對(duì)稱密碼機(jī)制加密文件集，然后將加密文件集發(fā)送至公共云存儲(chǔ)服務(wù)器上，將索引存放在本地或加密后存放在服務(wù)器上，因?yàn)槎M(jìn)制索引占用存儲(chǔ)空間少，可存于本地。當(dāng)用戶要求訪問(wèn)包含某些關(guān)鍵詞的文件時(shí),根據(jù)查詢關(guān)鍵詞與關(guān)鍵詞集合構(gòu)建查詢二進(jìn)制向量,并將查詢二進(jìn)制向量與每個(gè)文件的索引二進(jìn)制向量進(jìn)行內(nèi)積計(jì)算以判斷該文件是否包含用戶的查詢關(guān)鍵詞。該方法完全基于對(duì)稱密碼技術(shù)，效率很高，并且支持多關(guān)鍵詞查詢，用戶的文件可以是任何類型，比如可以是壓縮文件、多媒體文件等，只需事前建立二進(jìn)制向量索引。本方法能實(shí)現(xiàn)比目前廣泛使用的倒排索引更高效的查詢。

[1]SongDX,WagnerD,PerrigA.Practicaltechniquesforsearchesonencrypteddata[C]//ProceedingofIEEESymposiumonSecurityandPrivacy,2000:44-55.

[2]GohEJ.Secureindexes[R/OL].CryptologyePrintArchive:Report2003/216.http://eprint.iacr.org/2003/216.

[3]ChangYC,MitzenmacherM.Privacypreservingkeywordsearchesonremoteencrypteddata[C]//ProceedingofAppliedCryptographyandNetworkSecurity(ACNS),2005:442-455.

[4]CurtmolaR,GarayJ,KamaraS,etal.Searchablesymmetricencryption:improveddefinitionsandefficientconstructions[C]//ProceedingofTheACMConferenceonComputerandCommunicationsSecurity(CCS),2006:79-88.

[5]KurosawaK,OhtakiY.UC-securesearchablesymmetricencryption[C]//ProceedingofFinancialCryptography,2012:285-298.

[6]WangC,CaoN,LiJ,etal.Enablingsecureandefficientrankedkeywordsearchoveroutsourcedclouddata[J].IEEETransactionsonParallelandDistributedSystems,2012,23(8):1467-1479.

[7]LiJ,WangQ,WangC,etal.Fuzzykeywordsearchoverencrypteddataincloudcomputing[C]//ProceedingofInternationalConferenceonComputerCommunications,2010:441-445.

[8]WangC,RenK,YuS,etal.Achievingusableandprivacy-assuredsimilaritysearchoveroutsourcedclouddata[C]//ProceedingofInternationalConferenceonComputerCommunications,2012:451-459.

[9] 黃汝維,桂小林,余思,等.云環(huán)境中支持隱私保護(hù)的可計(jì)算加密方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(12):2391-2402.

[10]LiesdonkPV,SedghiS,DoumenJ,etal.Computationallyefficientsearchablesymmetricencryption[C]//ProceedingofSIAMInternationalConferenceonDataMining,2010:87-100.

[11]KamaraS,PapamanthouC,RoederT.Dynamicsearchablesymmetricencryption[C]//ProceedingofTheACMConferenceonComputerandCommunicationsSecurity(CCS),2012:965-976.

[12]KamaraS,PapamanthouC.Parallelanddynamicsearchablesymmetricencryption[C]//ProceedingofFinancialCryptography,2013:258-274.

[13]HahnF,KerschbaumF.Searchableencryptionwithsecureandefficientupdates[C]//ProceedingofTheACMConferenceonComputerandCommunicationsSecurity(CCS),2014:310-320.

[14]StefanovE,PapamanthouC,ShiE.Practicaldynamicsearchablesymmetricencryptionwithsmallleakage[C]//ProceedingofTheNetworkandDistributedSystemSecuritySymposium,2014:1-15.

[15]KurosawaK,OhtakiY.Howtoupdatedocumentsverifiablyinsearchablesymmetricencryption[C]//ProceedingofInternationalConferenceonCryptologyandNetworkSecurity,2013:309-328.

[16]NaveedM,PrabhakaranM,GunterCA.Dynamicsearchableencryptionviablindstorage[C]//ProceedingofIEEESymposiumonSecurityandPrivacy,2014:639-654.

[17]CaoN,WangC,LiM,etal.Privacy-preservingmulti-keywordrankedsearchoverencryptedclouddata[C]//ProceedingofInternationalConferenceonComputerCommunications,2011:829-837.

[18]SunW,WangB,CaoN,etal.Privacy-preservingmulti-keywordtextsearchinthecloudsupportingsimilarity-basedranking[C]//ProceedingofTheACMConferenceonComputerandCommunicationsSecurity(CCS),2013:71-82.

[19]MoatazT,ShikfaA.Booleansymmetricsearchableencryption[C]//ProceedingofTheACMSymposiumonInformation,ComputerandCommunicationsSecurity,2013:265-276.

[20] 王尚平,劉利軍,張亞玲.一個(gè)高效的基于連接關(guān)鍵詞的可搜索加密方案[J].電子與信息學(xué)報(bào),2013,35(9):2266-2271.

[21] 沈志榮,薛巍,舒繼武.可搜索加密機(jī)制研究與進(jìn)展[J].軟件學(xué)報(bào),2014,25(4):880-895.

[22] 李經(jīng)緯,賈春福,劉哲理,等.可搜索加密技術(shù)研究綜述[J].軟件學(xué)報(bào),2015,26(1):109-128.

ORDERED ENCRYPTED DATA SEARCHING METHOD BASED ONBINARY-VECTOR INDEX IN CLOUD STORAGE

Chen Lanxiang Zhou Shuming

(SchoolofMathematicsandComputerScience,FujianNormalUniversity,Fuzhou350108,Fujian,China)(KeyLabofNetworkSecurityandCryptology,FujianNormalUniversity,Fuzhou350108,Fujian,China)

A ranking query method of ciphertext cloud data in cloud storage is designed. The basic idea is to build binary vector index, and use the Hash function to calculate the position of the vector in which is filled “1”. This method makes it easy to establish the index vector, and is easier to build the query vector and update the data. Binary vector index is constructed by the user. When the user requests access to a file containing some keywords, the query binary vector is built by the query keywords and the keyword set. Then the inner product of the query vector and index vector is calculated to determine whether the file contains the queried keywords. According to the inner product, it is able to know that which files are more relevant to the query and have higher computational efficiency. The experiments show that the efficiency of index creation and query are very high.

Cloud storage Ciphertext search Binary-vector index Ranked query

2016-01-06。國(guó)家自然科學(xué)基金面上項(xiàng)目(61572010)；福建省自然科學(xué)

2015J01240)；福建省教育廳科技項(xiàng)目(JK2014009)；福州市科技計(jì)劃項(xiàng)目(2014-G-80)。陳蘭香，副教授，主研領(lǐng)域：云存儲(chǔ)，存儲(chǔ)安全。周書明，教授。

TP309.2

A

10.3969/j.issn.1000-386x.2017.03.002