云存儲環(huán)境下的密文檢索研究*

陳 元，張昌宏，付 偉

（海軍工程大學，武漢 430033）

0 引言

近些年來，隨著IT行業(yè)和計算機領域的迅速發(fā)展，數(shù)據(jù)量正呈現(xiàn)爆炸式的增長[1]。為高效存儲和處理這些海量數(shù)據(jù)，云計算[2-3]與云存儲技術[4-6]應運而生。用戶可以將數(shù)據(jù)以外包的方式存儲至云服務提供商（CSP，Cloud Service Provider），實現(xiàn)資源存儲云化。對用戶而言，這種存儲模式可以降低存儲和計算成本，而且云服務器具有按需服務和按服務收費等優(yōu)勢，符合當前綠色計算和低碳經(jīng)濟的發(fā)展趨勢[7]。

在云服務快速發(fā)展的同時，其安全性問題也日益突出，尤其是存儲數(shù)據(jù)的安全性與隱私保護問題[8-12]。如果用戶將自身的隱私敏感數(shù)據(jù)完全暴露給云服務器，將存在極大的安全隱患。用戶可以將明文數(shù)據(jù)加密后再上傳至服務器，但這又會影響數(shù)據(jù)的可用性。當用戶需要檢索某個文檔時，需要將云端的數(shù)據(jù)全部下載到本地再進行查詢，浪費了大量的網(wǎng)絡帶寬且效率較低。因此，云存儲環(huán)境下的密文檢索技術是目前的研究熱點之一。

1 密文檢索

1.1 密文檢索的應用場景

本文將CSP視為“忠實但好奇（Honest but Curious）”的半可信敵手模型。一方面，CSP能夠忠實履行與用戶之間的服務等級協(xié)定（SLA，Service Level Agreement）[13]，向其提供穩(wěn)定的數(shù)據(jù)上傳、下載及檢索等服務；另一方面，CSP出于好奇會對用戶的訪問行為和記錄進行分析，因此，用戶隱私敏感信息存在著一定的安全性威脅，例如照片、郵件、通訊錄、個人賬戶等個人用戶信息、政務商務機密，以及醫(yī)療機構中存儲的患者隱私等企業(yè)用戶信息。

同時，SLA實質上只是一種信任契約，沒有統(tǒng)一的標準，缺乏有效的驗證途徑，因此，無法解決目前存在的信任悖論問題。一方面，CSP會信誓旦旦地承諾服務的安全性和可靠性；另一方面，用戶卻無法通過行之有效的技術手段對SLA進行驗證并阻止CSP的不正當行為。由于信息存在不對稱性，用戶很難發(fā)現(xiàn)服務商的違約行為；而當用戶違約時，服務商則能立即發(fā)現(xiàn)并制止其行為。信任悖論問題導致用戶不敢放心地將數(shù)據(jù)上傳至云服務器進行保存。

1.2 密文檢索需求分析

針對云計算與云存儲服務中存在的安全威脅和信任悖論問題，相關學者提出了密文檢索技術。為保證核心隱私敏感數(shù)據(jù)的安全，用戶可以選擇將其加密后再上傳至云服務器上進行存儲。密文檢索技術使得數(shù)據(jù)查詢操作可以直接在密文上進行，既保證了數(shù)據(jù)的機密性，又極大地提高了檢索效率。

1.2.1 密文檢索中數(shù)據(jù)的特點

與傳統(tǒng)數(shù)據(jù)相比，密文檢索中的數(shù)據(jù)通常具有以下幾個特點：

1）海量性（Massive）：由于云存儲用戶數(shù)量眾多，且每個用戶所存儲的隱私數(shù)據(jù)量比較大，因此，密文檢索中的數(shù)據(jù)是海量的，一般可以達到TB級甚至PB級；

2）外包性（Outsourced）：密文數(shù)據(jù)以外包的形式存儲在云端，用戶通過網(wǎng)絡與云存儲服務提供商聯(lián)系，因此，根本無法知道數(shù)據(jù)存儲在哪個網(wǎng)絡節(jié)點上，甚至不知道存儲在哪個國家或地區(qū)；

3）機密性（Confidential）：出于對數(shù)據(jù)安全性的考慮，用戶將其核心隱私敏感數(shù)據(jù)加密后再發(fā)送給云存儲服務提供商；

4）可用性（Available）：數(shù)據(jù)的可用性是服務商必須首先解決的問題，也是用戶最關心的問題?？蓹z索性也是可用性的一個方面；

5）異構性（Heterogeneous）：數(shù)據(jù)的存儲、使用、授權方式和訪問控制策略都不盡相同，因此，存在明顯的異構性；

6）混雜性（Mixed）：云存儲平臺通常采用多租戶機制，因此，一個存儲節(jié)點上可能同時存儲多個用戶的數(shù)據(jù)，一個用戶的數(shù)據(jù)也可能存儲在不同的節(jié)點上。

1.2.2 密文檢索中數(shù)據(jù)的安全需求

相比于傳統(tǒng)的數(shù)據(jù)存儲方式，云存儲具有諸多優(yōu)勢，但是出于安全方面的因素，用戶仍然不敢將隱私數(shù)據(jù)存儲在云服務器上。目前密文檢索中的數(shù)據(jù)主要有以下幾個安全需求：

1）數(shù)據(jù)的隱私保護能力需要進一步提高。由于在云存儲環(huán)境下用戶數(shù)據(jù)具有外包性，如果沒有可靠的技術手段對數(shù)據(jù)進行隱私保護，而只是單純地依靠SLA協(xié)定對服務商的行為進行約束，這顯然不能滿足數(shù)據(jù)的安全需求；此外，由于數(shù)據(jù)具有混雜性，在一個節(jié)點上會同時存儲多個用戶的數(shù)據(jù)，而不是絕對的物理隔離，同樣會帶來安全隱患；

2）數(shù)據(jù)的完整性驗證機制有待進一步增強。完善和增強數(shù)據(jù)的完整性驗證機制也是目前需要迫切解決的問題。保證數(shù)據(jù)的完整性是服務雙方合作的基礎，用戶數(shù)據(jù)在存儲和處理的過程中，不能被惡意修改或破壞；

3）數(shù)據(jù)的可用性需要得到更強大的技術保障。傳統(tǒng)的明文數(shù)據(jù)檢索技術通常無法適用于密文的檢索，為保證加密后數(shù)據(jù)的可用性，服務商需要給用戶提供安全有效的可檢索加密技術。

1.3 密文檢索中的挑戰(zhàn)性問題

密文檢索方法主要分為兩種：一種是基于密文的檢索方法，用戶直接將加密后的文件上傳至云端，檢索時需要對密文全文進行掃描匹配，得到與關鍵詞相同或相近的密文；另一種是基于索引的檢索方法，用戶需要事先提取明文中的關鍵詞，構建索引結構，然后將加密后的密文和索引文件上傳至云端，檢索時只需比對關鍵詞和索引文件即可得到相應的密文。

密文檢索中的挑戰(zhàn)性問題主要是如何在保證用戶核心隱私敏感數(shù)據(jù)安全性的同時，實現(xiàn)高效的檢索匹配以得到相應的密文數(shù)據(jù)。同時，如何實現(xiàn)密文數(shù)據(jù)的多用戶檢索、多關鍵字檢索、模糊檢索、區(qū)間檢索以及支持結果集排序的Top-k檢索，也是密文檢索中的一個挑戰(zhàn)性問題。

2 密文檢索的通用模型與基本框架

本文對現(xiàn)有的密文檢索方案進行研究和分析，提出云存儲環(huán)境下的密文檢索通用模型與基本框架。

2.1 通用模型

圖1 云存儲環(huán)境下的密文檢索通用模型

如圖1所示，云存儲環(huán)境下的密文檢索通用模型主要由3個角色組成：數(shù)據(jù)擁有者（DO，Data Owner）、云存儲服務提供商（CSP，Cloud Storage Provider）和數(shù)據(jù)檢索者（DS，Data Searcher）。

1）DO：如果采用基于密文的檢索方法，數(shù)據(jù)擁有者可以直接將自身的核心隱私敏感數(shù)據(jù)加密后發(fā)送給CSP；如果采用基于索引的檢索方法，則用戶需要事先從明文中提取關鍵詞，并構建索引結構，然后將加密后的密文和索引文件一起上傳至CSP；同時DO可以向CSP提出密文檢索請求；

2）CSP：向用戶DO和DS提供數(shù)據(jù)存儲、下載及檢索服務；

3）DS：數(shù)據(jù)檢索者經(jīng)DO授權后可以向CSP提出密文檢索請求并獲取相應的數(shù)據(jù)信息。

2.2 基本框架

本文以基于索引的密文檢索方法為例，對云存儲環(huán)境下的密文檢索基本框架進行描述，框架主要由以下幾個多項式時間的算法構成：

1）Setup（k；sp，sk）：概率密鑰生成算法。由數(shù)據(jù)擁有者DO執(zhí)行，對系統(tǒng)進行初始化。輸入：安全參數(shù)k，輸出：系統(tǒng)參數(shù)sp和系統(tǒng)密鑰sk；

2）BuildIndex（D；I）：確定性索引構建算法。由數(shù)據(jù)擁有者DO執(zhí)行，提取明文關鍵詞并構建文檔索引結構。輸入：明文文檔D，輸出：索引結構I；

3）Enc（D，I，sk；ED，EI）：確定性加密算法。由數(shù)據(jù)擁有者DO執(zhí)行，加密明文文檔和索引結構。輸入：明文文檔D、索引結構I和系統(tǒng)密鑰sk，輸出：密文文檔ED和密文索引結構EI；

4）Trapdoor（w，sk；Tw）：確定性陷門生成算法。由數(shù)據(jù)檢索者DS執(zhí)行，生成關鍵詞陷門。輸入：檢索關鍵詞w和系統(tǒng)密鑰sk，輸出：關鍵詞陷門Tw；

5）Search（Tw，EI；ED）：確定性檢索算法。由云存儲服務提供商CSP執(zhí)行，檢索關鍵詞對應的密文文檔。輸入：關鍵詞陷門Tw和密文索引結構EI，輸出：關鍵詞w對應的密文文檔ED；

6）Dec（ED，sk；D）：確定性解密算法。由數(shù)據(jù)檢索者DS執(zhí)行，得到檢索到的明文文檔。輸入：密文文檔ED和系統(tǒng)私鑰sk，輸出：明文文檔D。

在基于密文的檢索方法中，不存在文檔索引結構，因此，其基本框架中不存在第二步；另外，檢索時需要對密文全文進行掃描匹配，得到與關鍵詞相同或相近的密文文檔。

3 密文檢索方案的評價體系

國內外專家學者提出許多針對云存儲應用場景下的密文檢索方案，其評價指標主要包括以下幾個方面：

1）安全性：要求數(shù)據(jù)的上傳、下載和檢索都是在密文狀態(tài)下進行，以保證用戶核心隱私敏感數(shù)據(jù)的安全性，包括明文、關鍵詞索引及陷門和檢索過程的安全性。高安全性的方案能夠抵御統(tǒng)計分析攻擊，具有適應性不可區(qū)分安全、適應性語義安全和抵抗非自適應性選擇關鍵詞攻擊的語義安全（IND-CKA、IND-CKA2）等[14]；

2）高效性：符合綠色計算的要求，既要減小存儲空間，又要保證密文檢索的效率，這里所說的存儲空間主要是指關鍵詞索引所占的存儲空間。高效性的衡量標準主要包括時間復雜度和空間復雜度；

3）正確性驗證：方案支持檢索結果的正確性驗證，通常采用正確率和召回率作為檢索結果的驗證參數(shù)，其中正確率是指檢索結果中與檢索陷門相關的文檔數(shù)占檢索結果總文檔數(shù)的比例，召回率是指檢索結果中與檢索陷門相關的文檔數(shù)占用戶云端密文總文檔數(shù)的比例；

4）可靠性：方案能夠給用戶提供可靠的數(shù)據(jù)存儲和密文檢索服務。

4 不同類型的密文檢索方案對比分析

根據(jù)檢索方法的不同，可以將其分為基于密文全文的檢索方法和基于密文索引的檢索方法。

4.1 基于密文全文的檢索方法

Song等人[15]首次提出可搜索加密（SE，Searchable Encryption）的概念，并設計實現(xiàn)了一種基于對稱密碼體制的密文檢索方案。方案用由偽隨機數(shù)和校驗數(shù)生成的流密碼對用戶數(shù)據(jù)進行加密，只有加密后的用戶數(shù)據(jù)、檢索陷門和檢索結果會暴露給不可信的服務商，保證了數(shù)據(jù)的安全性，同時證明了方案具有一定的可行性。但是方案采用基于密文全文的檢索方法，直接將陷門關鍵字與密文全文進行線性比對，效率比較低，方案只適用于單用戶、單關鍵字的精確檢索，且不支持結果集排序。

文獻[15]方案主要由以下幾個步驟組成：

1）Setup（k；sp，sk）：概率密鑰生成算法。由數(shù)據(jù)擁有者DO執(zhí)行，對系統(tǒng)進行初始化。輸入：安全參數(shù)k，輸出：系統(tǒng)參數(shù)sp和系統(tǒng)密鑰sk；

2）Enc（D，sk；ED）：確定性加密算法。由數(shù)據(jù)擁有者DO執(zhí)行，加密明文文檔。輸入：明文文檔D和系統(tǒng)密鑰sk，輸出：密文文檔ED；具體做法如下：首先將明文單詞的長度均轉換為n bit，采用分組加密函數(shù)和系統(tǒng)密鑰加密明文單詞；通過流密碼生成一組長度為n-m bit的偽隨機數(shù)；將加密后的明文單詞分成長度為n-m bit和m bit的L和R兩部分；通過散列函數(shù)處理L得到密鑰sk’；通過偽隨機函數(shù)和密鑰sk’處理n-m比特位的偽隨機數(shù)，得到長度為m bit的數(shù)，然后將其填充到n-m位的偽隨機數(shù)后，得到長度為n bit的數(shù)；最后將其與加密后的明文單詞按位異或，得到密文ED；

3）Trapdoor（w，sk；Tw）：確定性陷門生成算法。由數(shù)據(jù)檢索者DS執(zhí)行，生成關鍵詞陷門。輸入：檢索關鍵詞w和系統(tǒng)密鑰sk，輸出：關鍵詞陷門Tw；采用步驟2）中的分組加密函數(shù)和系統(tǒng)密鑰加密檢索關鍵詞w得到關鍵詞陷門Tw；

4）Search（Tw；ED）：確定性檢索算法。由云存儲服務提供商CSP執(zhí)行，檢索關鍵詞對應的密文文檔。輸入：關鍵詞陷門Tw，輸出：關鍵詞w對應的密文文檔ED；依次將關鍵詞陷門Tw與密文中的單詞按位異或；

5）Dec（ED，sk；D）：確定性解密算法。由數(shù)據(jù)檢索者DS執(zhí)行，得到檢索到的明文文檔。輸入：密文文檔ED和系統(tǒng)私鑰sk，輸出：明文文檔D；首先將n-m位的偽隨機數(shù)與密文的前n-m位按位異或，得到L；然后由散列函數(shù)和L得到sk’，最后解密密文得到密文D。

上述方案雖然實現(xiàn)了基本的密文檢索功能，但是安全性和效率都比較低，不能抵御統(tǒng)計分析攻擊，不支持檢索結果的正確性驗證；同時，采用由偽隨機數(shù)和校驗數(shù)生成的流密碼作為密鑰，給密鑰的管理帶來了困難。

Dan Boneh等人[16]提出一種基于公鑰加密的關鍵詞檢索方案，同樣需要對關鍵詞和密文進行掃描匹配，適用范圍較小且效率較低。為了提高檢索效率，Bethencourt等人[17-18]在文獻[15]方案的基礎上提出了基于Paillier加解密算法[19]的密文檢索方案，方案采用非對稱密碼體制，并通過緩存器來存儲一些數(shù)據(jù)流，檢索效率比較高且算法具有部分同態(tài)加密的性質。Curtmola等人[20]在文獻[15]方案的基礎上，提出了可搜索對稱加密方案SSE1、SSE2，通過增加和優(yōu)化索引結構提高了檢索效率，同時方案將應用場景由單用戶檢索擴展到多用戶檢索，密文檢索用戶不再限制于數(shù)據(jù)擁有者，授權用戶同樣可以對云端密文進行檢索。

在基于密文全文的檢索方法中，用戶數(shù)據(jù)加密、陷門生成和數(shù)據(jù)解密都是在客戶端完成，只有密文檢索部分是在服務器上執(zhí)行，因此，CSP不會獲得明文信息，保證了用戶數(shù)據(jù)的機密性。但是檢索時需要將陷門關鍵詞與密文全文進行線性地掃描匹配比對，效率較低，不能滿足云存儲場景下海量數(shù)據(jù)的應用需求。

4.2 基于密文索引的檢索方法

針對基于密文全文的檢索方法不能滿足云存儲場景下海量數(shù)據(jù)的應用需求問題，相關學者提出基于密文索引的檢索方法。用戶需要事先提取明文中的關鍵詞，構建索引結構，然后將加密后的密文和索引文件上傳至云端，檢索時只需比對陷門關鍵詞和索引文件即可得到相應的密文。

Goh等人[21]定義了一種基于偽隨機函數(shù)和布隆過濾器的安全索引—Z索引，構建了安全模型，并形式化地證明了模型具有可以抵御非自適應選擇關鍵字攻擊的語義安全，方案效率較高并且可以抵抗選擇明文攻擊。

文獻[21]方案主要由以下幾個步驟組成：

1）Setup（k；sp，sk）：概率密鑰生成算法。由數(shù)據(jù)擁有者DO執(zhí)行，對系統(tǒng)進行初始化。輸入：安全參數(shù)k，輸出：系統(tǒng)參數(shù)sp和系統(tǒng)密鑰sk；sk由偽隨機函數(shù)映射生成；

2）BuildIndex（D，sk；I）：確定性索引構建算法。由數(shù)據(jù)擁有者DO執(zhí)行，提取明文關鍵詞w并構建文檔索引結構。輸入：明文文檔D和系統(tǒng)密鑰sk，輸出：索引結構I；索引結構通過布隆過濾器存儲；D中包含文檔的唯一標識符 Did；計算和；然后將y插入到布隆過濾器中，并將其作為文檔的索引結構；

3）Enc（D，sk；ED）：確定性加密算法。由數(shù)據(jù)擁有者DO執(zhí)行，加密明文文檔。輸入：明文文檔D和系統(tǒng)密鑰sk，輸出：密文文檔ED；

4）Trapdoor（sw，sk；Tw）：確定性陷門生成算法。由數(shù)據(jù)檢索者DS執(zhí)行，生成關鍵詞陷門。輸入：檢索關鍵詞sw和系統(tǒng)密鑰sk，輸出：關鍵詞陷門Tw；為查詢單射函數(shù)；

5）Search（Tw，I；ED）：確定性檢索算法。由云存儲服務提供商CSP執(zhí)行，檢索關鍵詞對應的密文文檔。輸入：關鍵詞陷門Tw和密文索引結構I，輸出：關鍵詞w對應的密文文檔ED；計算和，然后查詢y是否在索引結構布隆過濾器中，完成檢索；

6）Dec（ED，sk；D）：確定性解密算法。由數(shù)據(jù)檢索者DS執(zhí)行，得到檢索到的明文文檔。輸入：密文文檔ED和系統(tǒng)私鑰sk，輸出：明文文檔D。

上述方案的第 1、2、3、4、6 步均在客戶端完成，只有第5步檢索部分是在服務器上執(zhí)行，因此，CSP不會獲得明文信息，保證了用戶數(shù)據(jù)的機密性。同時，布隆過濾器的存儲空間較小且存儲和檢索效率較高，但是查詢比對時存在誤判率和假陽性，不適合對檢索匹配精度要求比較高的場景。

Cao等人[22]首次定義并解決了云計算環(huán)境下基于隱私保護的密文多關鍵字排序查詢問題，方案將密文索引和檢索陷門通過編碼的方式轉換為向量，并將兩者的內積作為匹配相似值，雖然實現(xiàn)了多關鍵字的密文排序檢索，但是由于檢索過程中需要線性掃描密文索引，所以效率較低，同時查詢前需要檢索用戶掌握索引的列表及位置信息。Fu等人[23]提出支持同義詞查詢的密文多關鍵字排序檢索方案，在文獻[22]方案的基礎上引入了二叉樹結構存儲密文索引及其向量，檢索效率有所提高。楊旸等人[24]提出基于域加權和語義相似度的多關鍵字密文排序檢索方案，通過域加權評分和語義相似度評分構建索引，創(chuàng)建文檔向量并將其分塊處理，通過匹配文檔向量和查詢向量實現(xiàn)了密文排序檢索，方案的效率比較高但是安全性有所降低。那海洋等人[25]將B+樹形結構的思想引入索引構建方案中，降低了索引空間的復雜度并提高了檢索效率，方案通過關鍵字匹配和相關度分數(shù)實現(xiàn)了檢索結果集排序，但是安全性不高且不支持檢索結果的正確性驗證。

在基于密文索引的檢索方法中，用戶的核心隱私敏感數(shù)據(jù)、索引結構以及檢索陷門都是以密文的形式發(fā)送給CSP，保證了數(shù)據(jù)的機密性。與基于密文全文的檢索方法相比，基于密文索引的檢索方法安全性和效率都比較高，更適用于云存儲環(huán)境下的密文檢索場景。

5 密文檢索的發(fā)展趨勢分析

1）目前大多數(shù)密文檢索方案只適用于單用戶檢索，但是在云存儲環(huán)境下，數(shù)據(jù)通常都是由多個授權用戶共享的，因此，設計適用于多用戶的密文檢索方案是十分必要的。

2）在云存儲環(huán)境下，由于用戶數(shù)據(jù)規(guī)模較大，如果密文檢索方案只支持單關鍵字檢索，將會檢索出大量與用戶需求無關的文檔；多關鍵字檢索可以設置多個檢索條件和陷門，可以檢索出更符合用戶需求的文檔，而且可以節(jié)省網(wǎng)絡帶寬。因此，密文檢索由單關鍵字檢索逐漸向多關鍵字檢索擴展。

3）根據(jù)檢索匹配精度的不同，可以將密文檢索技術分為精確密文檢索和模糊密文檢索。在傳統(tǒng)的明文檢索技術中，由于檢索用戶掌握的數(shù)據(jù)與真實數(shù)據(jù)之間存在著誤差，僅僅依靠精確匹配無法完成相應的檢索功能，因此，支持模糊匹配是十分必要的。同樣，在密文檢索中，即使明文數(shù)據(jù)之間存在較小的誤差，加密后的密文之間的誤差也會變得很大，因此，需要服務器檢索系統(tǒng)支持模糊檢索功能。

4）區(qū)間檢索是對數(shù)據(jù)進行檢索的主要方式之一。在明文區(qū)間檢索中，用戶向服務器提供檢索區(qū)間，然后服務器將關鍵字在檢索區(qū)間內的所有數(shù)據(jù)反饋給用戶。但是在密文區(qū)間檢索中，為保證敏感數(shù)據(jù)的機密性，用戶需將加密后的檢索區(qū)間陷門發(fā)送給服務器，服務器運行檢索算法后將符合條件的密文反饋給用戶，由私鑰解密后得到相應的明文數(shù)據(jù)。由于檢索需要在密文狀態(tài)下進行，所以如何在保證安全性的同時實現(xiàn)高效的區(qū)間檢索是目前的主要難題。

5）由于在云端存儲的用戶密文文檔是海量的，而且檢索成功的文檔也比較多，因此，需要對檢索結果集進行排序，以返回最符合用戶需求的Top-K個結果，同時可以節(jié)省網(wǎng)絡帶寬和資源開銷，降低用戶成本。

6 結論

本文首先介紹了云存儲環(huán)境下密文檢索的應用場景，分析了密文檢索中數(shù)據(jù)的特點和安全需求，并提出了其中的挑戰(zhàn)性問題。通過研究現(xiàn)有的密文檢索方案，提出了云存儲環(huán)境下的密文檢索通用模型與基本框架，并構建了方案的評價體系。根據(jù)檢索方法的不同，將密文檢索分為基于密文全文的檢索方法和基于密文索引的檢索方法，并詳細分析了其中的一些經(jīng)典方案。最后，指出了當前密文檢索方案中主要存在的問題，并對密文檢索的發(fā)展趨勢進行分析。