基于可拆分倒排索引的可搜索加密方案

孫曉玲，楊光，沈焱萍，楊秋格，陳濤

（防災(zāi)科技學(xué)院信息工程學(xué)院，河北三河 065201）

0 引言

隨著云計(jì)算技術(shù)［1-2］的快速發(fā)展以及大數(shù)據(jù)時(shí)代的到來，越來越多的用戶選擇將數(shù)據(jù)存儲(chǔ)到云服務(wù)器，以節(jié)省自身的開銷，實(shí)現(xiàn)便捷的多點(diǎn)訪問。

為了保護(hù)數(shù)據(jù)安全，數(shù)據(jù)擁有者通常將數(shù)據(jù)加密后存儲(chǔ)在云端。用戶對(duì)數(shù)據(jù)進(jìn)行檢索和更新時(shí)，需要將所有密文數(shù)據(jù)從云端下載到本地，再進(jìn)行解密、檢索和更新，隨著數(shù)據(jù)資源的激增，這種方案是無法滿足時(shí)效要求的。因此，如何在用戶提交檢索請(qǐng)求時(shí)，實(shí)現(xiàn)云端對(duì)密文數(shù)據(jù)的檢索是云數(shù)據(jù)安全存儲(chǔ)的重要需求。為了解決這一問題，提出了可搜索加密的概念。具體地，數(shù)據(jù)擁有者對(duì)文件進(jìn)行加密，并提取文件中的關(guān)鍵詞加密以建立安全索引，將密文和索引外包給服務(wù)器，當(dāng)用戶需要訪問含有某個(gè)關(guān)鍵詞的文件時(shí)，計(jì)算該關(guān)鍵詞的搜索憑證發(fā)送給云服務(wù)器，云服務(wù)器根據(jù)搜索憑證查詢索引，獲得文件標(biāo)識(shí)符，將對(duì)應(yīng)文件的密文返回給用戶。

可搜索加密思想最早由文獻(xiàn)［3］提出。第一個(gè)實(shí)際的對(duì)稱可搜索加密方案由文獻(xiàn)［4］提出。文獻(xiàn)［5］提出了一個(gè)基于前向索引（Forward Index）的對(duì)稱可搜索加密方案，采用為每個(gè)文件建立一個(gè)布隆過濾器（Bloom filter）的方法來建立索引。文獻(xiàn)［6-7］均采用建立前向索引的方法構(gòu)建可搜索加密方案。與前向索引結(jié)構(gòu)相對(duì)應(yīng)的是倒排索引（Inverted Index）結(jié)構(gòu)，該索引結(jié)構(gòu)由文獻(xiàn)［8］提出。文獻(xiàn)［9］設(shè)計(jì)了一個(gè)完全支持動(dòng)態(tài)操作的基于倒排索引的對(duì)稱可搜索加密方案。文獻(xiàn)［10］在文獻(xiàn)［9］的基礎(chǔ)上使用紅黑樹提出了一個(gè)支持并行和動(dòng)態(tài)操作的對(duì)稱可搜索加密方案。文獻(xiàn)［11-13］分別提出了不同的動(dòng)態(tài)可搜索加密方案，都是對(duì)文件和關(guān)鍵詞配對(duì)進(jìn)行處理，文獻(xiàn)［14］中提出了一種在云端創(chuàng)建搜索索引的方案，該方案首先由用戶創(chuàng)建一個(gè)存儲(chǔ)了文件-關(guān)鍵詞映射的文件索引和一個(gè)用于存儲(chǔ)關(guān)鍵詞-文件映射的空的搜索索引，并提交給云端，云端在用戶提交檢索憑證時(shí)查詢文件索引獲取檢索結(jié)果，并將檢索結(jié)果添加到搜索索引中，搜索索引只存儲(chǔ)了已被搜索過的關(guān)鍵詞及其所在文件集合，該方案將搜索索引的構(gòu)建時(shí)間分?jǐn)偟搅嗣看螜z索過程中，同時(shí)提高了檢索效率，節(jié)省了存儲(chǔ)空間，但動(dòng)態(tài)更新的效率不高。文獻(xiàn)［15］在文獻(xiàn)［14］的基礎(chǔ)上由云端增加了一個(gè)刪除索引，用以存儲(chǔ)已被搜索過的文件-關(guān)鍵詞映射，在刪除文件時(shí)，可迅速查找出被刪除文件在搜索索引中的位置，極大提高了搜索索引的更新效率。近年來，研究學(xué)者設(shè)計(jì)了許多不同功能的可搜索加密算法，比如：支持模糊搜索［16］，支持多關(guān)鍵詞搜索［17］，支持近似搜索［18］，支持搜索結(jié)果排序［19-20］，支持分塊處理［21-22］。

現(xiàn)有方案對(duì)可搜索加密技術(shù)在安全、效率、功能、存儲(chǔ)空間和動(dòng)態(tài)更新等方面進(jìn)行了不同程度的取舍，以適應(yīng)不同應(yīng)用環(huán)境的需求。隨著大數(shù)據(jù)技術(shù)的發(fā)展，海量密文存儲(chǔ)場(chǎng)景增加，如何有效利用云端資源、快速地批量更新數(shù)據(jù)，成為了新的應(yīng)用需求。

本文采用了文獻(xiàn)［14］中的方案，用戶在本地創(chuàng)建文件索引，由云端在搜索過程中構(gòu)建搜索索引，充分利用了云端資源，將搜索索引的存儲(chǔ)空間和計(jì)算時(shí)間分散到了每次搜索過程中，且對(duì)于已搜索過的關(guān)鍵詞，該方案實(shí)現(xiàn)了近似最優(yōu)的線性搜索時(shí)間。文獻(xiàn)［14-15］方案中索引的存儲(chǔ)采用的是哈希鏈表的形式，索引的更新是單個(gè)節(jié)點(diǎn)的增加和刪除，要逐個(gè)進(jìn)行，故文件的添加和刪除只能單個(gè)進(jìn)行。本文采用了keyvalue 集合形式的存儲(chǔ)結(jié)構(gòu)，可對(duì)索引進(jìn)行合并和拆分，能夠快速實(shí)現(xiàn)文件的批量添加和刪除。本文方案可兼容分布式系統(tǒng)架構(gòu)，應(yīng)用于海量數(shù)據(jù)處理場(chǎng)合。

1 問題描述

1.1 方案對(duì)比

稱文件中的不重復(fù)關(guān)鍵詞為唯一關(guān)鍵詞，設(shè)n為唯一關(guān)鍵詞的總數(shù)，m為所有關(guān)鍵詞的總數(shù)，|F|為文件的總數(shù)，IDw為包含w的文件標(biāo)識(shí)符集合，r為一次查詢中平均返回文件記錄總數(shù)，表1給出了本文方案與其他方案的各方面性能比較。

表1 不同方案的性能比較Tab.1 Performance comparison of different schemes

1.2 系統(tǒng)模型

云環(huán)境下密文檢索系統(tǒng)模型如圖1 所示，包括三個(gè)主體：數(shù)據(jù)擁有者、用戶和云服務(wù)器。

圖1 云環(huán)境下密文檢索系統(tǒng)模型Fig.1 Ciphertext retrieval system model in cloud environment

數(shù)據(jù)擁有者是擁有原始數(shù)據(jù)的企業(yè)或組織，要將文件集合F=(f1，f2，…，fn)存儲(chǔ)在云服務(wù)器，為了保障數(shù)據(jù)的安全，先使用對(duì)稱加密算法對(duì)文件進(jìn)行加密，得到密文集合C=(c1，c2，…，cn)，同時(shí)，對(duì)每個(gè)文件提取唯一關(guān)鍵詞構(gòu)成唯一關(guān)鍵詞集合(1 ≤i≤n)，對(duì)文件的唯一關(guān)鍵詞用偽隨機(jī)函數(shù)進(jìn)行變換，構(gòu)造key-value 形式的文件索引If，key 值為文件標(biāo)識(shí)符id(f)，value 為集合形式存儲(chǔ)的唯一關(guān)鍵詞密文，同時(shí)生成一個(gè)空的key-value 形式的搜索索引Iw，key值為由被搜索關(guān)鍵詞生成的搜索憑證，value 為集合形式存儲(chǔ)的包含該關(guān)鍵詞的文件的標(biāo)識(shí)符，數(shù)據(jù)擁有者將密文集合C、文件索引If、空的搜索索引Iw一起提交給云服務(wù)器。當(dāng)用戶想要獲取某些文件時(shí)，需利用關(guān)鍵詞對(duì)文件進(jìn)行搜索，用戶從數(shù)據(jù)擁有者獲取陷門密鑰，由關(guān)鍵詞生成搜索憑證，將搜索憑證提交給云服務(wù)器。云服務(wù)器首先查找搜索索引Iw中是否有該關(guān)鍵詞的key值，有則直接返回對(duì)應(yīng)的value值，若沒有，則根據(jù)搜索憑證對(duì)文件索引If進(jìn)行搜索，記錄包含該關(guān)鍵詞的文檔編號(hào)集合，并在搜索索引Iw中添加該項(xiàng)記錄，最后返回搜索結(jié)果中的文件密文給用戶。

1.3 變量和定義

文中所用到的變量和相應(yīng)定義如表2所示。

表2 所用到的變量和相應(yīng)定義Tab.2 Used variables and corresponding definitions

定義1基于可拆分倒排索引的可搜索加密方案由一個(gè)五元組SIISE構(gòu)成，SIISE=(Keygen，Indexgen，Search，Add，Delete)，具體如下。

1）SIISE.Keygen。用戶端根據(jù)安全參數(shù)λ生成密鑰集K，分別為對(duì)稱加密和解密、帶密鑰的偽隨機(jī)算法提供不同密鑰。

2）SIISE.Indexgen。用戶端根據(jù)文件集合F和密鑰集K，生成文件索引If、空的搜索索引Iw、空的搜索歷史集合σ和加密后的密文集合C，將If、Iw和C提交給云端。

3）SIISE.Search。用戶端根據(jù)檢索關(guān)鍵詞w和密鑰集K，生成檢索憑證提交云端，并更新搜索歷史σ，云端檢索得到包含此關(guān)鍵詞的文件標(biāo)識(shí)符集合IDw，同時(shí)更新搜索索引Iw。其中，未被檢索過的關(guān)鍵詞先通過搜索文件索引If獲得檢索結(jié)果并將結(jié)果添加到Iw中，已搜索過的關(guān)鍵詞可直接檢索搜索索引Iw。云端返回密文集合Cw，用戶解密得到文件集合Fw。

4）SIISE.Add。用戶端根據(jù)要添加的文件集合Fa、唯一關(guān)鍵詞集合Wa、搜索歷史σ和密鑰集K，生成文件索引Ifa、搜索索引Iwa和密文集合Ca，將Ifa、Iwa、Ca提交給云端。云端將已有的If、Iw分別與Ifa、Iwa合并，將Ca添加到密文集合中。

5）SIISE.Delete。用戶端根據(jù)要?jiǎng)h除的文件集合Fd、唯一關(guān)鍵詞集合Wd、搜索歷史σ和密鑰集K，生成索引Iwa，將Iwa和要?jiǎng)h除的文件標(biāo)識(shí)符集合IDS提交給云端。云端從If中刪除由IDS中的標(biāo)識(shí)符作為key 值的記錄，從Iw中拆除Iwa，從密文集合中刪除IDS中標(biāo)識(shí)符對(duì)應(yīng)的密文。

稱可搜索加密方案SIISE是有效的，如果對(duì)任意λ∈N，由算法Keygen生成的密鑰集K，文件集合F，對(duì)稱加密所得密文集合C，以及所有基于索引I所進(jìn)行的添加、刪除等操作，任一搜索操作返回的結(jié)果都是正確的。

理想情況下，可搜索加密方案應(yīng)避免云端獲取有關(guān)文件和搜索內(nèi)容的相關(guān)信息，但如此高安全性的實(shí)現(xiàn)是以存儲(chǔ)消耗和搜索效率為代價(jià)的，可以允許泄露少量信息來構(gòu)建更加有效的方案。采用文獻(xiàn)［10］中給出的方法，使用泄露函數(shù)（leakage function）來驗(yàn)證方案的安全性。

定義2SIISE=(Keygen，Indexgen，Search，Add，Delete)是一個(gè)安全的動(dòng)態(tài)可搜索加密方案。進(jìn)行以下實(shí)驗(yàn)，假設(shè)A是一個(gè)有狀態(tài)攻擊者、S為有狀態(tài)模擬器，LSearch，LAdd為泄露函數(shù)，有：

稱SIISE對(duì)自適應(yīng)動(dòng)態(tài)選擇關(guān)鍵詞攻擊是（LSearch，LAdd）安全的，如果對(duì)任意概率多項(xiàng)式算法A，存在概率多項(xiàng)式時(shí)間模擬器S，使得A的優(yōu)勢(shì)|Pr=1]|對(duì)于λ是可忽略不計(jì)的。

2 倒排索引的構(gòu)建

本文方案的核心設(shè)計(jì)是建立可拆分倒排索引，云端可獨(dú)立合并和拆分索引，實(shí)現(xiàn)文件的批量增加和刪除。采用keyvalue形式存儲(chǔ)索引，key為索引鍵值，value為集合形式的結(jié)果集，假設(shè)有表T，key 值為k，value 值為v，可表示為T[k]=v。實(shí)現(xiàn)的時(shí)候可直接采用哈希表結(jié)構(gòu)，也可使用非關(guān)系型數(shù)據(jù)庫(kù)，與分布式系統(tǒng)結(jié)合，用于大規(guī)模數(shù)據(jù)場(chǎng)合，可獲得更高的檢索效率，更靈活的增量添加和刪除，且云端可在不依賴客戶端的前提下實(shí)現(xiàn)對(duì)索引的更新。

2.1 索引的構(gòu)建

本文方案中，用到了兩個(gè)索引If和Iw，采用key-value 集合形式存儲(chǔ)?？蛻舳耸紫壬梢粋€(gè)文件索引If，用以存儲(chǔ)文件標(biāo)識(shí)符與其唯一關(guān)鍵詞的映射，如圖2 所示，key 為文件標(biāo)識(shí)符id(f)，value 為該文件的唯一關(guān)鍵詞密文集合cˉ=，H為偽隨機(jī)函數(shù)；云端在檢索過程中構(gòu)建搜索索引Iw，如圖3所示，key為由關(guān)鍵詞w生成的搜索憑證τw=G(w)，G為隨機(jī)函數(shù)，value 為包含該關(guān)鍵詞的文件標(biāo)識(shí)符集合IDw={id(f1)，id(f2)，…}，m為文件集合F的唯一關(guān)鍵詞個(gè)數(shù)。

圖2 文件索引If示意圖Fig.2 Schematic diagram of file index If

圖3 搜索索引Iw示意圖Fig.3 Schematic diagram of search index Iw

用戶檢索時(shí)，假設(shè)被檢索關(guān)鍵詞為w，根據(jù)陷門密鑰生成搜索憑證τw，提交給云端，若w不在搜索歷史中，則云端依次搜索If中的每個(gè)關(guān)鍵詞密文進(jìn)行匹配，將含有關(guān)鍵詞w的文件標(biāo)識(shí)符添加到Iw[τw]中，以創(chuàng)建表Iw的一條記錄；否則，已搜索過的關(guān)鍵詞可直接查詢索引Iw獲取搜索結(jié)果。

2.2 索引的動(dòng)態(tài)更新

目前常用的索引構(gòu)建方法主要有倒排索引、樹形索引和前向索引（布魯姆過濾器索引）。大部分方案中的索引構(gòu)建都采用類似鏈表結(jié)構(gòu)，節(jié)點(diǎn)之間存在依賴關(guān)系，索引執(zhí)行添加和刪除操作時(shí)，只能單個(gè)節(jié)點(diǎn)操作，因此無法實(shí)現(xiàn)批量添加和刪除。

本文方案中的索引采用key-value 集合形式存儲(chǔ)，可實(shí)現(xiàn)一次性合并與刪除，適用于批量增加和刪除文件。

批量添加文件時(shí)，在本地生成添加文件集合Fa的文件索引Ifa和添加索引Iwa，這里Iwa中的key 值只需包含那些屬于Wa且已被搜索過的關(guān)鍵詞，因?yàn)樵贫爽F(xiàn)有的Iw中只有已被搜索過的關(guān)鍵詞記錄，只需將這些關(guān)鍵詞對(duì)應(yīng)的新增文件標(biāo)識(shí)符添加到Iw中相應(yīng)的value 集合中即可，同時(shí)將Ifa整個(gè)合并到云端已有的If中。

批量刪除文件時(shí)，只需用相同的方法生成要?jiǎng)h除文件集合Fd的刪除索引Iwd，云端直接將要?jiǎng)h除文件的記錄從If中刪除，將Iwd中關(guān)鍵詞對(duì)應(yīng)的刪除文件標(biāo)識(shí)符從Iw中對(duì)應(yīng)的value集合中一次性刪除。

3 方案描述

假設(shè)對(duì)稱加密方案SKE=(Gen，Enc，Dec)是抗不可區(qū)分選擇明文攻擊的，選取一個(gè)偽隨機(jī)數(shù)生成器V：{0，1}λ→{0，1}*，一個(gè)偽隨機(jī)函數(shù)G：{0，1}λ×{0，1}*→{0，1}λ，一個(gè)隨機(jī)函數(shù)H：{0，1}λ×{0，1}*→{0，1}λ，構(gòu)建的方案SIISE=(Keygen，Indexgen，Search，Add，Delete)描述如下。

算法1SIISE.Keygen。

4 安全性分析

方案中的查詢和更新操作會(huì)泄露特定信息給服務(wù)端。與文獻(xiàn)［14-15］相同，采用文獻(xiàn)［5］中提出的安全標(biāo)準(zhǔn)和文獻(xiàn)［10］中提出的泄露函數(shù)來證明可搜索加密方案的安全性。下面用兩個(gè)泄露函數(shù)LSearch、LAdd具體給出泄露的信息內(nèi)容。

5 性能測(cè)試

5.1 存儲(chǔ)空間復(fù)雜度

方案中使用了兩個(gè)索引If、Iw。If中存儲(chǔ)了文件標(biāo)識(shí)符與文件唯一關(guān)鍵詞密文集合的映射，假設(shè)m為If中所有關(guān)鍵詞的總量，則If的空間復(fù)雜度為O（m）。Iw中存儲(chǔ)了關(guān)鍵詞的搜索憑證與文件標(biāo)識(shí)符集合的映射，Iw的空間復(fù)雜度為

5.2 搜索時(shí)間復(fù)雜度

假設(shè)m為If中所有關(guān)鍵詞的總量，n為If中唯一關(guān)鍵詞總量。本文方案中，第一次搜索某個(gè)關(guān)鍵詞時(shí)，其搜索時(shí)間是與m線性相關(guān)的，當(dāng)所有關(guān)鍵詞都被搜索過后，即Iw中有n個(gè)輸入，搜索時(shí)間達(dá)到近似最優(yōu)。此時(shí)，進(jìn)行一次查詢操作，平均返回m/n個(gè)文件。故在搜索時(shí)間達(dá)到最優(yōu)值后，搜索時(shí)間復(fù)雜度為O(m/n)。

5.3 搜索時(shí)間測(cè)試

本文方案的測(cè)試中，所用環(huán)境為AMD 銳龍52400G 整合Radeon Vega Graphics 3.60 GHz，32 GB內(nèi)存，64位Windows 10操作系統(tǒng)，開發(fā)環(huán)境為Python 3.7，IDE 為Pycahrm。使用Enron Email 20150507 測(cè)試數(shù)據(jù)集，此數(shù)據(jù)集包含517401 個(gè)郵件，共1.32 GB。

初始搜索時(shí)，需要遍歷If中幾乎所有的節(jié)點(diǎn)，耗時(shí)較長(zhǎng)，隨著搜索次數(shù)的增加，Iw中記錄條數(shù)增多，搜索歷史中的關(guān)鍵詞可直接返回結(jié)果，平均耗時(shí)逐漸降低。以5000次搜索為遞增單位，給出搜索次數(shù)與搜索歷史關(guān)鍵詞數(shù)及新增關(guān)鍵詞數(shù)的統(tǒng)計(jì)情況，如圖4 所示，同時(shí)給出對(duì)應(yīng)的平均搜索時(shí)間變化情況，如圖5所示。

圖4 歷史搜索關(guān)鍵詞及新增關(guān)鍵詞與總搜索次數(shù)關(guān)系Fig.4 Relationship between historical search keywords，new keywords and total search times

圖5 平均每次搜索耗時(shí)與總搜索次數(shù)關(guān)系Fig.5 Relationship between average time cost in each search and total search times

5.4 動(dòng)態(tài)更新時(shí)間測(cè)試

本文方案相較文獻(xiàn)［14］方案和文獻(xiàn)［15］方案的最大改進(jìn)是采用key-value 結(jié)構(gòu)構(gòu)建索引，索引可一次性批量添加和刪除value 值，可高效實(shí)現(xiàn)文件的批量增刪，下面對(duì)索引添加和刪除操作進(jìn)行對(duì)比測(cè)試。

對(duì)于索引If，本文方案與文獻(xiàn)［14］方案、文獻(xiàn)［15］方案這兩種方案相比，增加和刪除文件的區(qū)別在于一條記錄的增刪和多條記錄增刪，時(shí)間差別在于n次操作和單次操作的區(qū)別。

對(duì)于索引Iw，文獻(xiàn)［14］方案、文獻(xiàn)［15］方案中添加文件操作是相同的，每添加一個(gè)文件f，對(duì)f中已在搜索歷史中的每一個(gè)關(guān)鍵詞w，將id（f）添加到Iw［τw］中，添加多個(gè)文件時(shí)要逐個(gè)添加。本文方案中，對(duì)于要批量添加的文件集合，構(gòu)造Iwa，將Iwa［τw］一次性添加到Iw［τw］中，圖6給出了兩種方案（本文方案和文獻(xiàn)［14-15］方案）的Iw添加文件耗時(shí)對(duì)比。

圖6 Iw添加文件在本文方案與文獻(xiàn)［14-15］方案的耗時(shí)對(duì)比Fig.6 Time consumption comparison of adding files in Iw between proposed scheme and scheme in literature［14-15］

文獻(xiàn)［14］方案每刪除一個(gè)文件，要遍歷Iw中每一項(xiàng)，并逐個(gè)查找Iw［τw］處列表的每個(gè)節(jié)點(diǎn)，直到找到所刪除文件的標(biāo)識(shí)符或者到達(dá)末尾節(jié)點(diǎn)，若要批量刪除文件，也需要逐個(gè)刪除。本文方案中，對(duì)于要批量刪除的文件集合，構(gòu)造Iwd，將Iwd［τw］一次性從Iw［τw］中刪除，圖7給出了本文方案與文獻(xiàn)［14］方案的刪除文件耗時(shí)對(duì)比。

圖7 Iw刪除文件在本文方案與文獻(xiàn)［14］方案的耗時(shí)對(duì)比Fig.7 Time consumption comparison of deleting files in Iw between proposed scheme and scheme in literature［14］

文獻(xiàn)［15］方案每刪除一個(gè)文件，先查找刪除索引以確定該文件中有哪些關(guān)鍵詞已被搜索過，然后直接查找已搜索關(guān)鍵詞在搜索索引中的記錄，依次查找鏈表節(jié)點(diǎn)直到找到文件的標(biāo)識(shí)符并將其刪除。圖8 給出了本文方案與文獻(xiàn)［15］方案的刪除文件耗時(shí)對(duì)比。

圖8 Iw刪除文件在本文方案與文獻(xiàn)［15］方案的耗時(shí)對(duì)比Fig.8 Time consumption comparison of deleting files in Iw between proposed scheme and scheme in literature［15］

6 結(jié)語(yǔ)

在文獻(xiàn)［14］方案的基礎(chǔ)上，基于key-value 結(jié)構(gòu)構(gòu)建倒排索引，本文提出了一種可對(duì)索引進(jìn)行批量更新的可搜索加密方案，適用于批量數(shù)據(jù)的添加和刪除。本文索引的可合并與可拆分特性，支持云端獨(dú)立對(duì)索引進(jìn)行操作，而不依賴于客戶端的狀態(tài)，可進(jìn)一步應(yīng)用于分布式系統(tǒng)，更加高效地實(shí)現(xiàn)海量數(shù)據(jù)處理。本文方案還可用于其他功能下的搜索方案，如多關(guān)鍵字查詢、模糊查詢等。