戴厚樂 楊庚 閔兆娥

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

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

中圖分類號：TP309.2

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

2.1.1 倒排索引

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

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

2.1.2 倒排索引加密

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

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

En（post）對于到排列表的加密是對到排列表中的每一個倒排項的信息進行加密，對于到排列表中的指針信息不加密。

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

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

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

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

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

2.2.1 密文索引切分算法

1）計算切分標準。

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

2）詞典切分。

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

3）倒排列表切分。

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

2.2.2 子索引分發(fā)

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

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

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

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

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

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

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

4）分發(fā)檢索請求，檢索請求切分好之后，主節(jié)點將各個子檢索請求獨立地分發(fā)至對應(yīng)子索引的分布式節(jié)點。

2.3.2 分布式檢索算法

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

算法4 分布式檢索算法。

輸入 子檢索請求Qi。

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

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

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

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

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

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

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

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

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

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

3.1 實驗平臺

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

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

3.2 性能測試與分析

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

參考文獻（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)對策略研究[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ù)安全和隱私保護技術(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ù)安全存儲技術(shù)[J]. 計算機學(xué)報， 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ù)存儲平臺的設(shè)計[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] 楊旸， 楊書略， 蔡圣暐， 等. 排序可驗證的語義模糊可搜索加密方案[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]. 計算機研究與發(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]. 計算機工程與應(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.