戴厚樂 楊庚 閔兆娥

摘 要：對(duì)于可搜索加密需要均衡數(shù)據(jù)的安全性和檢索效率。針對(duì)SSE-1密文檢索方案中檢索性能低、單關(guān)鍵詞檢索模式不足和傳統(tǒng)單服務(wù)器架構(gòu)中的單機(jī)資源局限性等問題，設(shè)計(jì)并實(shí)現(xiàn)了一種多關(guān)鍵詞并行密文檢索系統(tǒng)。該系統(tǒng)采用不同的索引加密方式提高密文檢索性能;通過對(duì)密文倒排索引的切分實(shí)現(xiàn)倒排索引的分塊檢索，克服了單機(jī)資源的局限性并提高了檢索效率;通過結(jié)合分布式特點(diǎn)擴(kuò)展了傳統(tǒng)單機(jī)檢索架構(gòu)并實(shí)現(xiàn)了多關(guān)鍵詞的并行檢索。實(shí)驗(yàn)結(jié)果表明，與SSE-1方案相比，在保證密文數(shù)據(jù)安全性的前提下所提方案能夠提高檢索、更新等操作的效率，實(shí)現(xiàn)多關(guān)鍵詞的檢索，同時(shí)動(dòng)態(tài)擴(kuò)展系統(tǒng)分布式架構(gòu)以提高系統(tǒng)負(fù)載能力。

關(guān)鍵詞： 可搜索加密;多關(guān)鍵詞;分布式檢索;倒排索引;索引切分

中圖分類號(hào)：TP309.2

文獻(xiàn)標(biāo)志碼：A

Abstract：? For searchable encryption， balancing the security and retrieval efficiency of data is important. Aiming at the low retrieval performance and the lack of single keyword search mode in SSE-1 ciphertext retrieval scheme， and the problems such as the limitation of single-machine resources in the traditional single-server architecture， a multi-keyword parallel ciphertext retrieval system was designed and implemented. Different index encryption strategies were used to improve the ciphertext retrieval performance. The block search of the inverted index was realized by partitioning the ciphertext inverted index， which solves the limitation of single-machine resources and improves the retrieval efficiency. The traditional single-machine retrieval architecture was extended and the parallel retrieval of multiple keywords was realized by combining the characteristic of distribution. Experimental? results show that compared with the SSE-1 scheme， the proposed scheme has the efficiency of retrieval and update operations improved under the premise of ensuring ciphertext data security and realizes multi-keyword retrieval. At the same time， the distributed architecture of the system is dynamically expanded to improve the system load capacity.

Key words：? searchable encryption; multi-keyword; distributed search; inverted index; index partition

0 引言

隨著信息技術(shù)的發(fā)展，人們?cè)谌粘Ｉ詈凸ぷ髦挟a(chǎn)生和使用的數(shù)據(jù)規(guī)模不斷增大。數(shù)據(jù)量由PB的規(guī)模向著EB和ZB的規(guī)模發(fā)展。為了能夠從海量的數(shù)據(jù)中高效地篩選出有意義的數(shù)據(jù)，文件檢索技術(shù)得到了廣泛的應(yīng)用。近年來，數(shù)據(jù)規(guī)模的爆發(fā)式增長(zhǎng)導(dǎo)致用戶本地的計(jì)算和存儲(chǔ)資源已經(jīng)無法滿足對(duì)龐大數(shù)據(jù)量的存儲(chǔ)和管理需求。由于云服務(wù)方便、快捷和靈活的特點(diǎn)，越來越多的用戶選擇將本地的數(shù)據(jù)遷移到云端存儲(chǔ)和管理[1]，以此來節(jié)省本地?cái)?shù)據(jù)管理開銷。然而由于云服務(wù)的開放性、分布性等特性，數(shù)據(jù)脫離了用戶的物理控制而存儲(chǔ)在云端，使得數(shù)據(jù)的安全性和隱私性問題日益突出，大數(shù)據(jù)的安全性越來越受到關(guān)注和重視[2-3]。數(shù)據(jù)加密存儲(chǔ)可以在一定程度上保證數(shù)據(jù)的安全隱私[4]，但加密數(shù)據(jù)使得檢索操作變得十分困難[5-7]。為了在保證數(shù)據(jù)安全性和用戶隱私的基礎(chǔ)上實(shí)現(xiàn)數(shù)據(jù)的檢索操作，可搜索加密技術(shù)（Searchable Encryption，SE）應(yīng)運(yùn)而生。

可搜索加密作為當(dāng)前隱私保護(hù)機(jī)制之一，得到了廣泛的研究和應(yīng)用。針對(duì)非結(jié)構(gòu)化數(shù)據(jù)的可搜索加密，基于構(gòu)造索引的SE方案[8]能夠高效地支持關(guān)鍵詞檢索，因而成為了SE方案的主要構(gòu)造策略。在開放系統(tǒng)中，由用戶或者可信第三方生成文檔的索引，并將密文數(shù)據(jù)和密文索引上傳至服務(wù)器。用戶通過檢索安全索引獲得目標(biāo)文檔，整個(gè)檢索過程是在不解密文檔數(shù)據(jù)和索引文件的情況下進(jìn)行的。因此，基于索引的可搜索加密方案既保證了密文數(shù)據(jù)的安全性，又利用索引實(shí)現(xiàn)了數(shù)據(jù)的高效可檢索性。近年來，倒排索引作為最高效的索引結(jié)構(gòu)之一，由于其高效的檢索特性被廣泛應(yīng)用于明文數(shù)據(jù)的檢索。同時(shí)，倒排索引結(jié)構(gòu)在一定程度上能夠節(jié)省磁盤空間，提高檢索效率，并且支持增量更新和刪除。因此，基于倒排索引的可搜索加密方案[13-15]也已成為目前主要的可搜索加密方案之一。

盡管基于倒排索引的可搜索加密方案具備一定的優(yōu)勢(shì)，但該方案仍然存在著一些明顯的不足：一方面是SSE-1方案中的局限性。方案中對(duì)索引指針加密導(dǎo)致檢索過程中產(chǎn)生過多的計(jì)算量影響了檢索性能，同時(shí)單關(guān)鍵詞的檢索模式已無法滿足用戶的檢索需求。另一方面是單機(jī)資源的局限性。當(dāng)索引文件的規(guī)模隨著數(shù)據(jù)量的增長(zhǎng)而增長(zhǎng)，索引可檢索數(shù)據(jù)規(guī)模受限于單機(jī)內(nèi)存資源，檢索效率受限于單機(jī)計(jì)算資源。最后是倒排索引結(jié)構(gòu)的局限性：對(duì)于多關(guān)鍵詞的檢索請(qǐng)求，倒排索引結(jié)構(gòu)的串行檢索，嚴(yán)重影響了多關(guān)鍵詞的檢索效率。

針對(duì)上述不足，本文使用了不同的索引加密方式，擴(kuò)展了傳統(tǒng)的單服務(wù)器模型架構(gòu)，設(shè)計(jì)并實(shí)現(xiàn)了一種基于倒排索引的多關(guān)鍵詞并行檢索的可搜索加密方案。在本文方案中設(shè)計(jì)了倒排索引的分布式管理和檢索架構(gòu)，相較于傳統(tǒng)的單機(jī)模型架構(gòu)，這種架構(gòu)模型能夠提高單機(jī)資源的有效利用率，具有良好的可擴(kuò)展性，能避免可檢索數(shù)據(jù)規(guī)模的局限性問題。同時(shí)，本文方案能夠在一定程度上實(shí)現(xiàn)多關(guān)鍵詞的并行檢索，彌補(bǔ)倒排索引結(jié)構(gòu)在多關(guān)鍵詞檢索效率中的不足。

1 相關(guān)工作

可搜索加密技術(shù)不僅僅實(shí)現(xiàn)了密文數(shù)據(jù)的可檢索性，同時(shí)豐富了密文數(shù)據(jù)的檢索形式、檢索結(jié)構(gòu)和用戶管理等功能以滿足更加安全、精準(zhǔn)、高效的檢索需求。2000年，文獻(xiàn)[9]首次研究了可搜索加密問題，并且提出了SWP的線性密文掃描方案。

雖然該方案能夠基本上實(shí)現(xiàn)單詞搜索，但該方案需要通過對(duì)所有文檔進(jìn)行線性掃描，造成的開銷與文件大小呈線性關(guān)系，因而其檢索效率低下。針對(duì)文獻(xiàn)[9]中提出的SE方案檢索效率低下等缺陷，后續(xù)的加密可搜索方案通常是構(gòu)建一個(gè)安全的可搜索索引，通過密鑰生成匹配索引的陷門，用陷門匹配隱藏在云端的索引內(nèi)容從而獲得密文的檢索結(jié)果?；谶@一思想，文獻(xiàn)[10]設(shè)計(jì)了新的索引結(jié)構(gòu)，而文獻(xiàn)[13-15]則基于倒排索引構(gòu)建了安全索引結(jié)構(gòu)。2003年，文獻(xiàn)[10]提出了一種基于安全索引的Z-IDX方案來快速實(shí)現(xiàn)對(duì)海量密文數(shù)據(jù)的搜索。文獻(xiàn)[11]使用布隆過濾器（Bloom Filter）構(gòu)建每篇文檔的索引。該方案雖然具有高效檢索的優(yōu)點(diǎn)，但是由于Hash函數(shù)具有碰撞性（Collision）導(dǎo)致此方案存在誤識(shí)別。針對(duì)這一問題，文獻(xiàn)[12]提出了一種安全性定義和結(jié)構(gòu)的替代方案，這一方案彌補(bǔ)了誤碼率的缺陷。2006年，文獻(xiàn)[13]規(guī)范化了對(duì)稱可搜索加密（Symmetric Searchable Encryption， SSE）及其安全目標(biāo)，首次提出了基于倒排索引的加密可搜索方案。該方案中每個(gè)關(guān)鍵詞對(duì)應(yīng)的文檔列表都要經(jīng)過加密和模糊處理成一個(gè)數(shù)組;但是關(guān)鍵詞檢索之后，對(duì)應(yīng)的倒排列表的位置和內(nèi)容將暴露給云服務(wù)器。因此在重新生成索引之前，一個(gè)關(guān)鍵詞只能檢索一次?；谖墨I(xiàn)[13]方案的不足，文獻(xiàn)[15]中提出了動(dòng)態(tài)可搜索加密的概念，并構(gòu)建了一個(gè)加密的反向索引，支持動(dòng)態(tài)操作，如文檔更新等。2016年，文獻(xiàn)[16]中提出了一個(gè)可以動(dòng)態(tài)進(jìn)行文件的增、刪、改、查的多關(guān)鍵詞檢索方案。

早期的SE機(jī)制只能支持單個(gè)關(guān)鍵詞的檢索，因此這些方案具有相同的局限性：不支持聯(lián)合多關(guān)鍵字檢索。為了對(duì)查詢方式進(jìn)行擴(kuò)展實(shí)現(xiàn)更精確的查詢，文獻(xiàn)[17]分別基于對(duì)稱密碼學(xué)和公鑰密碼學(xué)提出了兩種實(shí)現(xiàn)連接關(guān)鍵字搜索的高效SE機(jī)制，但是都需要保證檢索請(qǐng)求中沒有重復(fù)的關(guān)鍵字。在基于對(duì)稱密碼學(xué)的SE機(jī)制中，要求陷門的大小和文件數(shù)量呈線性關(guān)系。而基于公鑰密碼學(xué)的SE機(jī)制，通過使用雙線性映射使得陷門的大小固定，解決了這個(gè)問題。之后，文獻(xiàn)[18]的工作能夠讓服務(wù)器在多關(guān)鍵詞檢索的基礎(chǔ)上，根據(jù)每個(gè)文件對(duì)于所請(qǐng)求關(guān)鍵字的相關(guān)度排序，并將相關(guān)度最高的k個(gè)文件返回給用戶，實(shí)現(xiàn)更準(zhǔn)確的檢索。2017年，文獻(xiàn)[19]中引入加權(quán)平均分的概念，對(duì)文件中不同區(qū)域的關(guān)鍵詞設(shè)置不同的權(quán)重表示重要程度，針對(duì)文獻(xiàn)[18]方案的不足，提出了更加高效的多關(guān)鍵詞排序檢索方案。對(duì)于多關(guān)鍵詞的檢索除了相關(guān)度排序查詢，文獻(xiàn)[19-21]中提出的模糊查詢也是可搜索加密研究的重要的一部分。為了豐富可搜索加密方案的應(yīng)用場(chǎng)景，文獻(xiàn)[22-24]中對(duì)于多用戶共享場(chǎng)景的密文檢索提出了相關(guān)方案。

上述方案都是基于單服務(wù)器模型架構(gòu)的SE機(jī)制，隨著索引文件規(guī)模的增大，單服務(wù)器架構(gòu)模型的內(nèi)存、計(jì)算資源已經(jīng)不能滿足如今龐大的數(shù)據(jù)量的檢索和管理，導(dǎo)致檢索效率降低。2016年，文獻(xiàn)[25]中提出了對(duì)于并行密文倒排索引的相關(guān)研究，利用分布式框架在服務(wù)器端并行構(gòu)建密文倒排索引。雖然提高了索引構(gòu)建和檢索效率，但密文索引構(gòu)建過程中將明文數(shù)據(jù)和密鑰暴露給服務(wù)器，缺乏安全性;并且檢索模式為單用戶單關(guān)鍵字，應(yīng)用場(chǎng)景具有局限性。同時(shí)對(duì)于多關(guān)鍵詞的檢索方案，更加嚴(yán)重的影響了檢索效率。針對(duì)這一問題，多關(guān)鍵字的并行可搜索加密方案成為熱點(diǎn)研究方向。2013年，文獻(xiàn)[26]在文獻(xiàn)[15]方案的基礎(chǔ)上，引入了紅黑樹結(jié)構(gòu)作為索引結(jié)構(gòu)，使動(dòng)態(tài)的SSE能夠支持多處理器的并行檢索。

針對(duì)基于倒排索引結(jié)構(gòu)的多關(guān)鍵詞檢索效率問題，本文提出了一種分布式并行檢索方案，從計(jì)算機(jī)資源的局限性和數(shù)據(jù)檢索的安全性出發(fā)，充分利用有限的單機(jī)計(jì)算和內(nèi)存資源實(shí)現(xiàn)數(shù)據(jù)檢索規(guī)模的擴(kuò)展和檢索效率的優(yōu)化。

2 分布式多關(guān)鍵詞并行密文檢索方案設(shè)計(jì)

云端數(shù)據(jù)規(guī)模的急劇增長(zhǎng)嚴(yán)重影響了密文數(shù)據(jù)的檢索效率，而單服務(wù)器模型架構(gòu)的可搜索加密方案由于單機(jī)資源的局限性已經(jīng)無法適用于大數(shù)據(jù)環(huán)境下的密文檢索。在此基礎(chǔ)上，本章利用倒排索引切分和分布式模型架構(gòu)實(shí)現(xiàn)了分布式環(huán)境下多關(guān)鍵詞并行密文檢索方案。利用分布式平臺(tái)實(shí)現(xiàn)可搜索加密模型架構(gòu)的擴(kuò)展，提高多關(guān)鍵詞檢索的效率。

分布式多關(guān)鍵詞并行密文檢索系統(tǒng)結(jié)構(gòu)如圖1所示，該方案基于倒排索引的檢索結(jié)構(gòu)實(shí)現(xiàn)，由客戶端、服務(wù)器端組成，服務(wù)器端包含了一個(gè)主節(jié)點(diǎn)和多個(gè)分布式從節(jié)點(diǎn)?？蛻舳藰?gòu)建密文索引、提交檢索請(qǐng)求;服務(wù)器端實(shí)現(xiàn)索引的分布式管理和檢索。其中服務(wù)器主節(jié)點(diǎn)切分索引和檢索請(qǐng)求，并將子索引和子請(qǐng)求分發(fā)至分布式平臺(tái)各個(gè)從節(jié)點(diǎn)，交由各個(gè)從節(jié)點(diǎn)實(shí)現(xiàn)索引的管理和檢索。各從節(jié)點(diǎn)將檢索結(jié)果交由主節(jié)點(diǎn)處理結(jié)果集，主節(jié)點(diǎn)將處理結(jié)果返回給客戶端。

對(duì)于多關(guān)鍵詞的檢索請(qǐng)求，依據(jù)關(guān)鍵詞切分成多個(gè)獨(dú)立且不重疊的檢索請(qǐng)求，分發(fā)檢索請(qǐng)求至相應(yīng)分布式節(jié)點(diǎn)實(shí)現(xiàn)并行檢索。為了實(shí)現(xiàn)倒排索引的分布式管理，需要完成四個(gè)步驟：用戶端基于對(duì)稱密鑰構(gòu)建密文倒排索引與數(shù)據(jù)加密;提交密文倒排索引與密文數(shù)據(jù)至服務(wù)端主節(jié)點(diǎn);服務(wù)器端主節(jié)點(diǎn)將密文倒排索引切分成多個(gè)完整且獨(dú)立的子索引;分發(fā)子索引由各個(gè)計(jì)算節(jié)點(diǎn)分布管理。

2.1 倒排索引構(gòu)建與加密

在本文檢索方案中，利用倒排索引實(shí)現(xiàn)高效的檢索。為了保證數(shù)據(jù)的安全傳輸與檢索，在上傳數(shù)據(jù)和索引文件之前需要完成兩個(gè)操作：一是用戶在客戶端對(duì)待上傳的文檔數(shù)據(jù)構(gòu)建倒排索引;二是在上傳數(shù)據(jù)之前，利用本地密鑰對(duì)文檔數(shù)據(jù)和索引文件進(jìn)行加密。

2.1.1 倒排索引

倒排索引由詞典（Lexicon）和倒排列表文件（Inverted Lists）構(gòu)成。詞典中保存了所有的關(guān)鍵詞以及指向倒排列表的邏輯指針和其他一些信息。倒排列表由包含了關(guān)鍵詞的所有文檔標(biāo)識(shí)構(gòu)成。通過查找詞典，找到對(duì)應(yīng)檢索關(guān)鍵詞的邏輯指針，遍歷相關(guān)倒排列表即可獲取目標(biāo)文檔。倒排索引結(jié)構(gòu)如圖2所示。

從倒排索引的結(jié)構(gòu)來看，攻擊者很可能通過詞典文件的關(guān)鍵詞和倒排列表的文檔標(biāo)識(shí)等索引信息來重現(xiàn)整個(gè)文檔的內(nèi)容。為了保證數(shù)據(jù)檢索的安全性，必須要對(duì)倒排索引文件進(jìn)行加密上傳。

2.1.2 倒排索引加密

針對(duì)明文倒排索引的安全性威脅，需要將倒排索引加密上傳，從而保證密文數(shù)據(jù)檢索的安全性。基于數(shù)組、鏈表、查找表等一些數(shù)據(jù)結(jié)構(gòu)，對(duì)于索引文件的加密，要利用對(duì)稱加密將索引加密形成安全倒排索引，從而在不改變索引結(jié)構(gòu)的基礎(chǔ)上對(duì)文檔相關(guān)信息加密，隱藏索引中的信息，以此實(shí)現(xiàn)密文數(shù)據(jù)的檢索。密文倒排索引的結(jié)構(gòu)如圖3所示。

En（term）對(duì)詞典的加密是對(duì)詞典中的關(guān)鍵詞進(jìn)行加密，對(duì)于索引中關(guān)鍵詞與到排列表的關(guān)聯(lián)指針不加密;

En（post）對(duì)于到排列表的加密是對(duì)到排列表中的每一個(gè)倒排項(xiàng)的信息進(jìn)行加密，對(duì)于到排列表中的指針信息不加密。

雖然密文倒排索引文件保證了檢索過程中數(shù)據(jù)的安全性，但數(shù)據(jù)量的增長(zhǎng)和索引的加密都會(huì)造成索引文件規(guī)模的增長(zhǎng)，導(dǎo)致內(nèi)存與計(jì)算資源影響和限制了檢索效率;所以對(duì)于大規(guī)模密文數(shù)據(jù)的檢索，有必要實(shí)現(xiàn)索引文件的分布式管理和檢索。

2.1.3 密文倒排索引的構(gòu)建算法

Luence是一個(gè)全文檢索引擎的架構(gòu)，提供了完整的查詢引擎、索引引擎和部分文本分析引擎，由Apache軟件基金會(huì)支持和提供。Lucene提供了一個(gè)簡(jiǎn)單卻強(qiáng)大的應(yīng)用程序接口，能夠做全文索引和檢索。本文利用Luence實(shí)現(xiàn)文本數(shù)據(jù)的倒排索引的構(gòu)建與數(shù)據(jù)檢索，并在此基礎(chǔ)上利用加密處理構(gòu)建密文倒排索引。

2.2 倒排索引的切分與分發(fā)

針對(duì)大規(guī)模索引文件中單機(jī)資源的局限性，將倒排索引切分成多個(gè)子索引，實(shí)現(xiàn)索引文件的分布式管理和檢索。每一個(gè)計(jì)算節(jié)點(diǎn)負(fù)責(zé)一部分索引文件，可以在有限的單機(jī)計(jì)算機(jī)資源的基礎(chǔ)上擴(kuò)展檢索的數(shù)據(jù)規(guī)模和提高系統(tǒng)負(fù)載能力，從而充分提高單機(jī)內(nèi)存和計(jì)算資源的有效利用率。為了實(shí)現(xiàn)索引文件分布式管理，需要完成兩個(gè)操作：一是將整體的密文倒排索引依據(jù)關(guān)鍵詞切分成多個(gè)完整且獨(dú)立的子索引;二是將子索引分發(fā)至各個(gè)分布式節(jié)點(diǎn)。

2.2.1 密文索引切分算法

1）計(jì)算切分標(biāo)準(zhǔn)。

計(jì)算倒排索引文件中所有倒排列表Pi（1≤i≤n）中包含的倒排項(xiàng)p的總數(shù)量，根據(jù)式（1）計(jì)算出每一個(gè)子索引中包含的倒排項(xiàng)的數(shù)量，以確定切分標(biāo)準(zhǔn)。

2）詞典切分。

以SLoad（Sm）為切分標(biāo)準(zhǔn)，依據(jù)關(guān)鍵詞有序編號(hào)和對(duì)應(yīng)倒排列表中的倒排項(xiàng)的數(shù)量|Pi|，根據(jù)式（2）將詞典中的關(guān)鍵詞順序切分成k個(gè)集合，構(gòu)成k個(gè)關(guān)鍵詞詞典。

3）倒排列表切分。

依據(jù)對(duì)詞典關(guān)鍵詞的切分方案和關(guān)鍵詞ti與倒排列表Pi的映射關(guān)系，實(shí)現(xiàn)對(duì)倒排列表文件的范圍切分。

2.2.2 子索引分發(fā)

依據(jù)對(duì)詞典關(guān)鍵詞的與倒排列表的切分，得到k個(gè)完整且相互獨(dú)立的子索引集合{Enkey（Ω1），Enkey（Ω2），…，Enkey（Ωk）}。索引切分示意圖如圖4所示。圖4中的每行ti代表一個(gè)關(guān)鍵詞，每列dj代表一個(gè)文檔，包含關(guān)鍵詞ti的文檔集合組成了ti的倒排列表。

2.3 數(shù)據(jù)檢索

密文倒排索引的切分與分發(fā)實(shí)現(xiàn)了索引文件的分布式管理，為了實(shí)現(xiàn)完整的多關(guān)鍵詞分布式檢索，需要完成三個(gè)操作：一是對(duì)用戶提交的多關(guān)鍵詞檢索請(qǐng)求切分并封裝成與子索引對(duì)應(yīng)的多個(gè)子檢索請(qǐng)求;二是將子檢索請(qǐng)求分發(fā)至管理對(duì)應(yīng)子索引的節(jié)點(diǎn)，實(shí)現(xiàn)數(shù)據(jù)的分布式檢索，并將結(jié)果集交由主節(jié)點(diǎn)進(jìn)行相關(guān)度處理后返回給用戶;三是用戶端收到檢索結(jié)果后，對(duì)結(jié)果集解密，得到明文數(shù)據(jù)。用戶檢索流程如圖5所示。

2.3.1 多關(guān)鍵詞檢索請(qǐng)求劃分算法

1）切分檢索請(qǐng)求，將用戶提交的檢索請(qǐng)求依據(jù)其中檢索詞順序分解成多個(gè)獨(dú)立的密文關(guān)鍵詞td。

2）關(guān)鍵詞匹配，依據(jù)詞典中關(guān)鍵詞的切分方案，計(jì)算并確定該關(guān)鍵詞td所屬的子索引文件Ωj，其中1≤ j≤k，并將所屬相同子索引的檢索詞組合成檢索詞集合。

3）封裝檢索詞子集，為每一個(gè)檢索關(guān)鍵詞匹配好子索引之后，將各個(gè)檢索詞集合再封裝成子檢索請(qǐng)求Qi={tdi1，tdi2，…，tdim}，得到子檢索請(qǐng)求集合{Q1，Q2，…，Qk}。其中：Qi是與子索引Ωi對(duì)應(yīng)的子檢索請(qǐng)求;tdim表示子檢索請(qǐng)求Qi中的第m個(gè)密文檢索詞。

4）分發(fā)檢索請(qǐng)求，檢索請(qǐng)求切分好之后，主節(jié)點(diǎn)將各個(gè)子檢索請(qǐng)求獨(dú)立地分發(fā)至對(duì)應(yīng)子索引的分布式節(jié)點(diǎn)。

2.3.2 分布式檢索算法

定義4 Ri是第i個(gè)節(jié)點(diǎn)的檢索結(jié)果集，dim是第i個(gè)節(jié)點(diǎn)的結(jié)果集中的第m篇檢索結(jié)果文檔。

算法4 分布式檢索算法。

輸入 子檢索請(qǐng)求Qi。

輸出 檢索結(jié)果集R。

2）各個(gè)分布式節(jié)點(diǎn)得到檢索結(jié)果后，將檢索結(jié)果Ri={di1，di2，…，dim}回送至主節(jié)點(diǎn)。主節(jié)點(diǎn)接收到各節(jié)點(diǎn)檢索結(jié)果集集合{R1，R2，…，Rk}后，對(duì)結(jié)果集取交集操作，得到用戶檢索請(qǐng)求Q的最終檢索結(jié)果集R。

3）回傳檢索結(jié)果，主節(jié)點(diǎn)取得最終檢索結(jié)果集后，將結(jié)果集回傳至客戶端。

2.3.3 數(shù)據(jù)解密

用戶收到檢索得到的密文檢索結(jié)果集數(shù)據(jù)后，利用密鑰對(duì)數(shù)據(jù)解密，得到明文數(shù)據(jù)。

2.4 系統(tǒng)可行性分析

由于密文索引構(gòu)建過程的計(jì)算量較大，需要通過并行計(jì)算提高索引構(gòu)建效率。傳統(tǒng)方案是將數(shù)據(jù)上傳至服務(wù)器端利用分布式平臺(tái)構(gòu)建索引，雖然能夠提高效率，但是需要提供可信的第三方服務(wù)器和安全的通信信道以保證數(shù)據(jù)安全。本文選擇在客戶端進(jìn)行索引的構(gòu)建和加密，基于新的加密方案和檢索方案，使得系統(tǒng)更具有優(yōu)勢(shì)。系統(tǒng)的可行性和優(yōu)勢(shì)主要體現(xiàn)在以下幾個(gè)方面：

1）客戶端構(gòu)建索引和加密能夠在分散服務(wù)器端集中構(gòu)建密文索引的計(jì)算量的同時(shí)保證明文數(shù)據(jù)不對(duì)外暴露，保證了數(shù)據(jù)的安全性，不需要提供可信的第三方服務(wù)器和通信信道。2）本文中的索引加密方案在構(gòu)建過程中只對(duì)詞典中關(guān)鍵詞信息和倒排項(xiàng)中相關(guān)文檔信息加密，保留了倒排索引的索引結(jié)構(gòu)，在密文索引的檢索過程中不需要同SSE-1方案中一樣進(jìn)行相關(guān)解密操作，保證了倒排索引切分方案的可行性，并且使得倒排索引的檢索優(yōu)勢(shì)得以體現(xiàn)。3）索引切分和檢索請(qǐng)求的切分算法使得各個(gè)子索引和檢索詞之間相互獨(dú)立，多關(guān)鍵詞的檢索請(qǐng)求能夠在不同的子索引上并行獨(dú)立地檢索，避免多關(guān)鍵詞耦合造成的重復(fù)性計(jì)算。服務(wù)器端將檢索任務(wù)的調(diào)度和檢索過程的計(jì)算解耦。由于檢索的獨(dú)立性和并行性等特性使得多關(guān)鍵詞的檢索效率提高，系統(tǒng)結(jié)構(gòu)便于隨著數(shù)據(jù)量的增長(zhǎng)而擴(kuò)展。

3 系統(tǒng)實(shí)現(xiàn)及性能分析

本文首先在單機(jī)模型架構(gòu)中對(duì)比了SSE-1方案與本文方案中索引加密方案的檢索效率;單索引檢索方案和切分多索引檢索方案在單關(guān)鍵詞下的密文檢索效率。同時(shí)對(duì)比了兩種方案下，每個(gè)索引文件大小隨著數(shù)據(jù)量增長(zhǎng)的變化趨勢(shì)。之后在分布式模型架構(gòu)中實(shí)現(xiàn)了多關(guān)鍵詞的分布式檢索方案，對(duì)比了不同數(shù)量的檢索詞的檢索效率，驗(yàn)證了本文提出的分布式方案的可行性。

3.1 實(shí)驗(yàn)平臺(tái)

本文基于Luence4.10實(shí)現(xiàn)了密文倒排索引的構(gòu)建和檢索，數(shù)據(jù)和索引使用AES對(duì)稱加密，系統(tǒng)編程采用Java實(shí)現(xiàn)。計(jì)算機(jī)配置為CPU Inter Celeron 2955U 1.40GHz，內(nèi)存4GB，硬盤500GB，操作系統(tǒng)為Windows 7。實(shí)驗(yàn)數(shù)據(jù)來自網(wǎng)絡(luò)中各大故事網(wǎng)站文本數(shù)據(jù)，包含了各種類型的名著與小說故事，數(shù)據(jù)的格式為txt文本。

分布式架構(gòu)模型包括了一個(gè)Broker主節(jié)點(diǎn)和多個(gè)Search-server子節(jié)點(diǎn)。Broker主節(jié)點(diǎn)負(fù)責(zé)檢索任務(wù)的監(jiān)控和調(diào)度，倒排索引的切分與管理。子節(jié)點(diǎn)為計(jì)算節(jié)點(diǎn)，負(fù)責(zé)數(shù)據(jù)的檢索與索引文件的管理。其配置均為CPU Inter Celeron 2955U 1.40GHz，內(nèi)存4GB，硬盤500GB，操作系統(tǒng)為Windows 7。

3.2 性能測(cè)試與分析

密文數(shù)據(jù)的檢索效率是可搜索加密方案中的一個(gè)非常重要的性能指標(biāo)，本文首先對(duì)于不同數(shù)量的文檔集合分別進(jìn)行SSE-1索引方案和本文索引加密方案在單索引文件、單關(guān)鍵詞場(chǎng)景下的檢索效率對(duì)比，實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

通過圖6可發(fā)現(xiàn)：1）本文中的加密方案檢索時(shí)間要少于SSE-1方案。這是因?yàn)镾SE-1方案中倒排索引的指針也要加密，檢索過程中，必須要首先解密前一個(gè)節(jié)點(diǎn)才能訪問下一個(gè)節(jié)點(diǎn)的內(nèi)容;而本文方案只對(duì)倒排索引中的關(guān)鍵詞和文檔信息加密，整個(gè)索引的指針和結(jié)構(gòu)不加密，從而能實(shí)現(xiàn)更高效的檢索。2）隨著文檔數(shù)量的增加，本文中的索引加密方案檢索效率優(yōu)勢(shì)更加明顯，這是因?yàn)槲臋n數(shù)量的增加使得檢索詞相關(guān)的文檔增多，倒排索引中的倒排項(xiàng)鏈表更長(zhǎng)，導(dǎo)致SSE-1方案中對(duì)指針的解密計(jì)算量增加，降低了檢索效率。對(duì)不同數(shù)據(jù)量的文檔集合在本文的索引加密方案下分別基于單索引方案和切分多索引方案在單機(jī)單關(guān)鍵詞下的文檔檢索效率進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果如圖7所示。

通過圖7可發(fā)現(xiàn)：檢索時(shí)間消耗隨著文檔數(shù)量的增加而不斷增大，這是由于文檔數(shù)量的增加導(dǎo)致索引文件規(guī)模增大，造成索引加載和檢索的時(shí)間消耗增多。此外，基于索引切分的多索引檢索方案檢索的效率更高，而且隨著文檔數(shù)據(jù)量的增加和切分?jǐn)?shù)量的增加，檢索的優(yōu)勢(shì)也更加明顯。這是因?yàn)樵跈z索過程中，單索引方案需要加載完整的索引文件進(jìn)行計(jì)算處理，而基于索引切分的檢索方案只需要在內(nèi)存中精確加載檢索詞對(duì)應(yīng)的子索引，減少了索引數(shù)據(jù)的加載和計(jì)算時(shí)間消耗，從而實(shí)現(xiàn)了高效率的檢索。

通過對(duì)不同數(shù)據(jù)量的文檔構(gòu)建密文索引，分析在不同索引方案下，數(shù)據(jù)量的規(guī)模對(duì)檢索操作過程中索引文件規(guī)模的變化趨勢(shì)，實(shí)驗(yàn)結(jié)果如圖8所示。

通過圖8可發(fā)現(xiàn)：在單關(guān)鍵詞檢索、單索引方案中，數(shù)據(jù)量的增加導(dǎo)致了索引文件規(guī)模的急劇增長(zhǎng)，而在基于索引切分的方案中，隨著切分?jǐn)?shù)量的增加，每個(gè)子索引文件規(guī)模的增長(zhǎng)速度逐漸緩慢。在同等計(jì)算資源下，基于索引切分的子索引檢索方案在檢索過程中能夠有效提高單機(jī)資源利用率和數(shù)據(jù)檢索規(guī)模的擴(kuò)展，更加適應(yīng)大數(shù)據(jù)的檢索場(chǎng)景。

圖9描述了在不同節(jié)點(diǎn)數(shù)量的分布式檢索系統(tǒng)中，多關(guān)鍵詞的檢索時(shí)間消耗情況。

通過對(duì)圖9的對(duì)比結(jié)果的分析發(fā)現(xiàn)：1）對(duì)于多關(guān)鍵詞的密文檢索，利用索引切分實(shí)現(xiàn)的分布式檢索模型架構(gòu)能夠有效提高檢索效率。這是因?yàn)殡S著計(jì)算節(jié)點(diǎn)和索引切分?jǐn)?shù)量的增多，檢索關(guān)鍵詞更加分散，每個(gè)節(jié)點(diǎn)檢索的關(guān)鍵詞更少，從而以并行的檢索模式提高了檢索效率。2）隨著檢索請(qǐng)求中關(guān)鍵詞的增多，檢索效率逐漸下降。這是因?yàn)殛P(guān)鍵詞的增多導(dǎo)致各個(gè)節(jié)點(diǎn)檢索的計(jì)算量增加;同時(shí)主節(jié)點(diǎn)Broker在切分檢索請(qǐng)求、合并檢索結(jié)果的計(jì)算量增加，從而導(dǎo)致了整體檢索過程的效率降低。3）隨著切分節(jié)點(diǎn)的增多，不同數(shù)量檢索詞的檢索效率趨于穩(wěn)定，這是因?yàn)殡S著節(jié)點(diǎn)的增多，每個(gè)節(jié)點(diǎn)計(jì)算量減少，在各節(jié)點(diǎn)檢索時(shí)間消耗不占主導(dǎo)的情況下，時(shí)間消耗主要集中在主節(jié)點(diǎn)Broker的索引切分和子索引匹配處理階段，因此使總體檢索時(shí)間趨于穩(wěn)定。

通過圖10的對(duì)比結(jié)果發(fā)現(xiàn)，本文中的多關(guān)鍵詞檢索方案比文獻(xiàn)27]方案更具有優(yōu)勢(shì)，并且隨著文檔數(shù)量的增長(zhǎng)，優(yōu)勢(shì)逐漸明顯。這主要是因?yàn)楸疚臋z索方案中多個(gè)檢索詞相互獨(dú)立，并且檢索陷門的生成不依賴于索引文件。而文獻(xiàn)27]中的檢索方案在生成檢索陷門的過程中，需要將多個(gè)檢索詞耦合在一起生成多項(xiàng)式，依據(jù)多項(xiàng)式矩陣來實(shí)現(xiàn)多關(guān)鍵詞的檢索。無論是索引構(gòu)建還是檢索過程，都需要經(jīng)歷大量的多項(xiàng)式矩陣計(jì)算，嚴(yán)重影響了檢索效率;并且檢索陷門的多項(xiàng)式矩陣的計(jì)算依賴于倒排索引的詞典文件，文檔數(shù)量的增加會(huì)導(dǎo)致索引中詞典文件規(guī)模的增長(zhǎng)，從而使得檢索陷門的計(jì)算更為復(fù)雜，導(dǎo)致檢索效率降低，不適用于數(shù)據(jù)量急劇增長(zhǎng)的應(yīng)用場(chǎng)景。

實(shí)驗(yàn)結(jié)果表明，使用索引切分的分布式檢索方案，能夠有效解決單機(jī)資源的局限性問題和提高多關(guān)鍵詞的密文數(shù)據(jù)檢索效率;并且隨著數(shù)據(jù)規(guī)模的不斷增長(zhǎng)，分布式模型架構(gòu)具有良好的可擴(kuò)展性，能更好地適應(yīng)數(shù)據(jù)量急劇增長(zhǎng)的應(yīng)用場(chǎng)景。

4 結(jié)語

可搜索加密是實(shí)現(xiàn)密文數(shù)據(jù)檢索的重要手段。本文基于關(guān)鍵詞的倒排索引切分提出了密文倒排索引的切分方案，通過索引切分與精確加載子索引文件，解決單服務(wù)器模型架構(gòu)中存在的單機(jī)資源局限性問題，提高單機(jī)內(nèi)存資源和計(jì)算的有效利用率。針對(duì)多關(guān)鍵詞的檢索模式，提出了分布式環(huán)境下的多關(guān)鍵詞并行密文檢索方案，實(shí)現(xiàn)了索引文件的分布式管理和關(guān)鍵詞的并行檢索，提高了多關(guān)鍵詞的檢索效率，同時(shí)使得密文檢索模型架構(gòu)具有了可擴(kuò)展性和靈活性等特性。實(shí)驗(yàn)結(jié)果說明，該分布式密文檢索系統(tǒng)可以實(shí)現(xiàn)密文數(shù)據(jù)的高效檢索操作，系統(tǒng)是有效的、可行的。

參考文獻(xiàn)（References）

[1] LIANG K， SUSILO W. Searchable attribute-based mechanism with efficient data sharing for secure cloud storage[J]. IEEE Transactions on Information Forensics and Security， 2015， 10（9）： 1981-1992.

[2] 胡坤， 劉鏑， 劉明輝. 大數(shù)據(jù)的安全理解及應(yīng)對(duì)策略研究[J]. 電信科學(xué)， 2014， 30（2）： 112-117， 122. （HU K， LIU D， LIU M H. Research on security connotation and response strategies for big data[J]. Telecommunications Science， 2014， 30（2）： 112-117， 122.）

[3] 呂欣， 韓曉露. 大數(shù)據(jù)安全和隱私保護(hù)技術(shù)架構(gòu)研究[J]. 信息安全研究， 2016， 2（3）： 244-250. （LYU X， HAN X L. Research on the technology architecture of big data security and privacy system[J]. Journal of Information Security Research， 2016， 2（3）： 244-250.）

[4] LI J， LI Y K， CHEN X， et al. A hybrid cloud approach for secure authorized deduplication[J]. IEEE Transactions on Parallel and Distributed Systems， 2015， 26（5）： 1206-1216.

[5] 馮朝勝， 秦志光， 袁丁. 云數(shù)據(jù)安全存儲(chǔ)技術(shù)[J]. 計(jì)算機(jī)學(xué)報(bào)， 2015， 38（1）： 150-163. （FENG C S， QIN Z G， YUAN D. Techniques of secure storage for cloud data[J]. Chinese Journal of Computers， 2015， 38（1）： 150-163.）

[6] FU Z， REN K， SHU J， et al. Enabling personalized search over encrypted outsourced data with efficiency improvement[J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（9）： 2546-2559.

[7] 蔣旭， 孫磊， 譚煒波. 一種安全可靠大數(shù)據(jù)存儲(chǔ)平臺(tái)的設(shè)計(jì)[J]. 信息安全研究， 2018， 4（1）： 63-72. （JIANG X， SUN L， TAN W B. The design of secure reliable big data storage platform[J]. Journal of Information Security Research， 2018， 4（1）： 63-72.）

[8] BONEH D， di CRESCENZO G， OSTROVSKY R， et al. Public key encryption with keyword search[C]// Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques， LNCS 3027. Berlin： Springer， 2004： 506-522.

[9] SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data[C]// Proceedings of the 2000 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2000： 44-55.

[10] GOH E. Secure indexes[EB/OL]. [2018-04-17]. http：//eprint.iacr.org/2003/216.pdf.

[11] BLOOM B H. Space/time trade-offs in Hash coding with allowable errors[J]. Communications of the ACM， 1970， 13（7）： 422-426.

[12] CHANG Y， MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data[C]// Proceedings of the 2005 26th International Conference on Applied Cryptography and Network Security， LNCS 3531. Berlin： Springer， 2005： 442-455.

[13] CURTMOLA R， GARAY J， KAMARA S， et al. Searchable symmetric encryption： Improved definitions and efficient constructions [C]// Proceedings of the 13th ACM Conference on Computer and Communications Security. New York： ACM， 2006： 79-88.

[14] NAVEED M， PRABHAKARAN M， GUNTER C A. Dynamic searchable encryption via blind storage[C]// Proceedings of the 2014 IEEE Symposium on Security and Privacy. Piscataway： IEEE， 2014： 639-654.

[15] KAMARA S， PAPAMANTHOU C， ROEDER T. Dynamic searchable symmetric encryption[C]// Proceedings of the 19th ACM Conference on Computer and Communications Security. New York： ACM， 2012： 965-976.

[16] XIA Z， WANG X， SUN X， et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（2）： 340-352.

[17] BALLARD L， KAMARA S， MONROSE F. Achieving efficient conjunctive keyword searches over encrypted data[C]// Proceedings of the 7th International Conference on Information and Communications Security， LNCS 3783. Berlin： Springer， 2005： 414-426.

[18] CAO N， WANG C， LI M， et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data[C]// Proceedings of the 32th IEEE Conference on Computer Communications. Piscataway： IEEE， 2011： 829-837.

[19] 楊旸， 楊書略， 蔡圣暐， 等. 排序可驗(yàn)證的語義模糊可搜索加密方案[J]. 工程科學(xué)與技術(shù)， 2017， 49（4）： 119-128. （YANG Y， YANG S L， CAI S W， et al. Semantically searchable encryption scheme supporting ranking verification[J]. Advanced Engineering Sciences， 2017， 49（4）： 119-128.）

[20] FU Z， WU X L， GUAN C， et al. Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement[J]. IEEE Transactions on Information Forensics and Security， 2016， 11（12）： 2706-2716.

[21] 王愷璇， 李宇溪， 周福才， 等. 面向多關(guān)鍵字的模糊密文搜索方法[J]. 計(jì)算機(jī)研究與發(fā)展， 2017， 54（2）： 348-360. （WANG K X， LI Y X， ZHOU F C， et al. Multi-keyword fuzzy search over encrypted data[J]. Journal of Computer Research and Development， 2017， 54（2）： 348-360.）

[22] KIM I T， QUAN T H， DUC L V， et al. An efficient searchable encryption scheme in the multi-user environment[C]// Proceedings of the 6th International Conference on Green and Human Information Technology， LNEE 502. Singapore： Springer， 2018： 188-192.

[23] HAHN C， SHIN H J， KWON H， et al. Efficient multi-user similarity search over encrypted data in cloud storage[J]. Wireless Personal Communications， 2018，107（3）： 1337-1353.

[24] ZHANG W， LIN Y， XIAO S， et al. Privacy preserving ranked multi-keyword search for multiple data owners in cloud computing[J]. IEEE Transactions on Computers， 2016， 65（5）： 1566-1577.

[25] 束曉偉， 楊庚， 那海洋. 并行密文倒排索引研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2016， 52（20）： 14-19， 45. （SHU X W， YANG G， NA H Y. Research on parallel crypt inverted index[J]. Computer Engineering and Applications， 2016， 52（20）： 14-19， 45.）

[26] KAMARA S， PAPAMANTHOU C. Parallel and dynamic searchable symmetric encryption[C]// Proceedings of the 2013 International Conference on Financial Cryptography and Data Security， LNCS 7859. Berlin： Springer， 2013： 258-274.

[27] WANG B， SONG W， LOU W， et al. Inverted index based multi-keyword public-key searchable encryption with strong privacy guarantee[C]// Proceedings of the 2015 IEEE Conference on Computer Communications. Piscataway： IEEE， 2015： 2092-2100.