可搜索加密的研究進(jìn)展

徐鵬，金海

（1. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；3. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院湖北省大數(shù)據(jù)技術(shù)與系統(tǒng)工程實(shí)驗(yàn)室，湖北 武漢 430074）

可搜索加密的研究進(jìn)展

徐鵬1，2，3，金海1，2，3

（1. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院服務(wù)計(jì)算技術(shù)與系統(tǒng)教育部重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；2. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院集群與網(wǎng)格計(jì)算湖北省重點(diǎn)實(shí)驗(yàn)室，湖北 武漢 430074；3. 華中科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院湖北省大數(shù)據(jù)技術(shù)與系統(tǒng)工程實(shí)驗(yàn)室，湖北 武漢 430074）

可搜索加密是解決云端不可信條件下加密數(shù)據(jù)安全云檢索的重要方法。針對(duì)可搜索公鑰加密、可搜索對(duì)稱加密這2種可搜索加密類型，分別介紹了近幾年來(lái)學(xué)術(shù)界的主要成果及其存在的問(wèn)題、解決方法。在可搜索公鑰加密領(lǐng)域，主要介紹了高安全條件下降低檢索復(fù)雜度的方法；在可搜索對(duì)稱加密領(lǐng)域，主要介紹了高安全條件下支持物理刪除的方法。

可搜索加密；云安全；可搜索公鑰加密；可搜索對(duì)稱加密

在傳統(tǒng)的密文存儲(chǔ)和查詢服務(wù)中，由于云端沒(méi)有檢索功能，不能根據(jù)用戶需求查找數(shù)據(jù)，只能將全部密文都返回給用戶，用戶解密后自行檢索才能得到想要的數(shù)據(jù)。顯然，這種處理方法在實(shí)際應(yīng)用中是不能被接受的。因此，如何在用戶提交檢索請(qǐng)求時(shí)，云端能實(shí)現(xiàn)高效率檢索并返回指定的密文是云數(shù)據(jù)安全存儲(chǔ)的重要問(wèn)題和需求。

2 可搜索加密

為了在保證用戶數(shù)據(jù)機(jī)密性的同時(shí)實(shí)現(xiàn)安全和高效的密文數(shù)據(jù)訪問(wèn)，可搜索加密（SE，searchable encryption）被提出。SE是近年來(lái)快速發(fā)展的一種支持用戶在密文上進(jìn)行關(guān)鍵字查找的密碼學(xué)原語(yǔ)，它能實(shí)現(xiàn)云端在不解密密文的情況下，完成對(duì)密文的檢索工作。SE一般分為如下4個(gè)階段。

1） 數(shù)據(jù)加密階段：數(shù)據(jù)擁有者在本地使用密鑰對(duì)明文數(shù)據(jù)進(jìn)行加密，然后將加密后的數(shù)據(jù)上傳至服務(wù)器。

2） 生成檢索陷門階段：用戶使用密鑰和生成對(duì)應(yīng)的檢索陷門，并將該陷門發(fā)送給云端，其中檢索陷門能保密其包含的

內(nèi)容。

3） 密文檢索階段：根據(jù)收到的檢索陷門，云端對(duì)密文進(jìn)行檢索，并將滿足檢索條件的密文發(fā)送給用戶，執(zhí)行過(guò)程中云端不能獲得除檢索結(jié)果之外的更多信息。

4） 密文解密階段：用戶從云端獲得返回的密文后，使用密鑰解密出相關(guān)數(shù)據(jù)。

目前，根據(jù)密鑰類型的不同，SE可以分為可搜索對(duì)稱加密（SSE，searchable symmetric encryption）和可搜索公鑰加密（PEKS，public-key encryption with keyword search）。

3 可搜索對(duì)稱加密

絕大多數(shù)情況下，SSE也可稱為可搜索對(duì)稱密鑰加密（SEKS，symmetric-key encryption with keyword search）。其核心是以對(duì)稱加密形式生成

的可搜索密文和檢索陷門。

3.1 SSE的定義

SSE的實(shí)例化方案通常基于偽隨機(jī)函數(shù)構(gòu)造，具有計(jì)算量小、算法簡(jiǎn)單、計(jì)算速度快等優(yōu)點(diǎn)。安全的SSE方案能確保關(guān)鍵字的保密性，能抵御外部攻擊和抵御來(lái)自云端的內(nèi)部信息泄露。

SSE的定義［1］。給定空間 Δ=（W1，W2，…，Wn），SSE方案由5個(gè)算法組成，即SSE=（Keygen， Enc， Trapdoor， Search， Dec），各算法含義如下。

1） K=KeyGen（k）：輸入安全參數(shù)k，輸出隨機(jī)產(chǎn)生的密鑰K。

2） （I， C）=Enc（K， D）：輸入密鑰K和明文文件集D=（D1， D2，…，Dn），輸出索引和密文文件集（對(duì)于無(wú)需構(gòu)造索引SSE的方案，如SWP方案［2］，索引為空）。

3） Tw=Trapdoor（K，W）：輸入密鑰K和W，輸出

對(duì)應(yīng)的陷門。

4） D（W）=Search（I，Tw）：輸入索引I和待搜索的陷門Tw，輸出包含

W的文件的標(biāo)識(shí)符集合。

5） Di=Dec（K， Ci）：輸入密鑰K和密文文件Ci，輸出解密后對(duì)應(yīng)的明文文件Di。

3.2 SSE的相關(guān)研究

2000年，Song等［2］提出了第一個(gè)基于對(duì)稱加密的密文檢索方案，但無(wú)法實(shí)現(xiàn)可證明的安全性，而且檢索性能與數(shù)據(jù)庫(kù)規(guī)模線性相關(guān)。隨后，很多工作［3～6］遵循這一研究路線并且不斷改善 Song等的初始方案。Goh等［3］提出了用布隆過(guò)濾器為每個(gè)文件構(gòu)造一個(gè)索引的方法。該方法將文件包含的關(guān)鍵詞映射到碼字存儲(chǔ)的索引中，通過(guò)布隆過(guò)濾器的運(yùn)算，就能判定密文文件是否包含某個(gè)特定關(guān)鍵詞，從而將搜索請(qǐng)求的計(jì)算代價(jià)減少到和密文文件數(shù)量成正比。Chang等［4］提出了一個(gè)和Goh類似的方案，不同的是他們沒(méi)有采用布隆過(guò)濾器。這些后續(xù)工作雖然提高了搜索效率，但依然無(wú)法實(shí)現(xiàn)主動(dòng)攻擊下的可證明的語(yǔ)義安全性。在強(qiáng)可證明安全的條件下，2006年，Curtmola等［1］提出了目前性能最優(yōu)的可檢索對(duì)稱加密，但該方案的檢索陷門長(zhǎng)度和文檔的最大數(shù)量線性相關(guān)，因此增加了通信開(kāi)銷。除了致力于可證明安全性或者更好的檢索性能，實(shí)現(xiàn)檢索的多樣化逐漸受到人們的重視。Waters等［7］的工作展示了SEKS的實(shí)際運(yùn)用，并且利用它實(shí)現(xiàn)了安全和可搜索的審計(jì)日志系統(tǒng)。文獻(xiàn)［8～11］將SSE應(yīng)用到加密數(shù)據(jù)庫(kù)。文獻(xiàn)［12］指出早期的這類工作在安全性上存在無(wú)法衡量的問(wèn)題。文獻(xiàn)［13，14］將 SSE方案拓展到多發(fā)送者。文獻(xiàn)［15，16］對(duì)這些多樣化查詢方案進(jìn)行了有效的改進(jìn)。文獻(xiàn)［17～19］實(shí)現(xiàn)了關(guān)鍵字的模糊搜索。文獻(xiàn)［20～23］實(shí)現(xiàn)了多關(guān)鍵字排列查詢和多維范圍查詢。Lu等［24］通過(guò)構(gòu)建索引結(jié)構(gòu)提高了范圍檢索的搜索效率。Boldyreva等［25］首次研究了對(duì)稱加密原語(yǔ)并提出了可證明安全的保序方案。Chase等［26］首次研究了結(jié)構(gòu)化數(shù)據(jù)的可搜索對(duì)稱加密。

近幾年來(lái)，動(dòng)態(tài)的SSE研究受到了廣泛關(guān)注。2012年，Kamara等［27］首次提出了支持動(dòng)態(tài)更新的可搜索對(duì)稱加密（DSSE，dynamic searchable symmetric encryption）方案，并且形式化定義了DSSE的安全性。DSSE不僅支持密文檢索，還支持可搜索密文的動(dòng)態(tài)更新操作，如密文添加、密文刪除、關(guān)鍵字添加刪除。然而，文獻(xiàn)［27］的方案在添加和刪除操作中存在較多隱私信息泄露。針對(duì)這個(gè)問(wèn)題，Kamara等在文獻(xiàn)［28］中提出基于紅黑二叉樹(shù)的DSSE方案，該方案通過(guò)構(gòu)造樹(shù)型索引解決了文獻(xiàn)［27］存在的問(wèn)題，但該方案增加了可搜索密文長(zhǎng)度并且降低了檢索效率。Cash等在文獻(xiàn)［29］中采用累加器的思想構(gòu)造了一個(gè)新的方案，保證了檢索效率和可搜索密文在動(dòng)態(tài)更新時(shí)的安全性。由于累加器自增不自減的天然特性，可搜索密文的數(shù)量會(huì)只增不減。2014年，Hahn等［30］提出了新的DSSE方案來(lái)解決已有方案存在的問(wèn)題，該方案在初始化時(shí)不構(gòu)建可搜索密文結(jié)構(gòu)，而是在檢索和更新過(guò)程中不斷更新可搜索密文索引結(jié)構(gòu)。

4 本文提出的SSE方案

本文調(diào)研了當(dāng)前SSE領(lǐng)域的研究現(xiàn)狀，詳細(xì)分析了近年來(lái)提出的方案和知名的SSE方案的優(yōu)缺點(diǎn)，提出了支持低泄露和物理刪除的DSSE方案。本文的SSE方案在檢索效率、動(dòng)態(tài)更新的粒度、可搜索密文的刪除能力和安全性方面均達(dá)到了同類方案的最優(yōu)。

4.1 核心思想

在標(biāo)準(zhǔn)的DSSE方案應(yīng)用案例中，每個(gè)文件都有一個(gè)標(biāo)識(shí)符和幾個(gè)對(duì)應(yīng)的。通常使用一個(gè)文件標(biāo)識(shí)符—1、K2、K3。這3個(gè)可搜索密文分別對(duì)應(yīng)搜索、刪除文件和刪除1密文構(gòu)成一條隱藏的關(guān)系鏈，和同一個(gè)文件的標(biāo)識(shí)符的所有 K2密文也構(gòu)成一條隱藏關(guān)系鏈。K3密文之間不存在任何隱藏關(guān)系。

這3個(gè)功能的實(shí)現(xiàn)。包含相同

的可搜索密文和相同文件的可搜索密文會(huì)各形成一條隱藏鏈結(jié)構(gòu)。以（id， W）作為例子，圖1展示了如何生成3種密文的過(guò)程，包括它們之間的隱藏關(guān)系鏈。圖2展示了同一個(gè)

的所有K

對(duì)（id， W），表示標(biāo)識(shí)符為id的文件包含

W。假設(shè)數(shù)據(jù)庫(kù)DB就是由所有的標(biāo)識(shí)符—

對(duì)組成的。在本文的方案中，對(duì)于每一個(gè)數(shù)據(jù)庫(kù)中的標(biāo)識(shí)符—

對(duì)，都會(huì)為其生成3種可搜索密文，分別是K

圖1—標(biāo)識(shí)符對(duì)（id， W）生成的密文

圖2 密文之間隱藏關(guān)系鏈

當(dāng)進(jìn)行搜索時(shí)，輸入待搜索1密文；通過(guò)解密K1密文，獲得包含查詢1密文不同于KPR'12中提到的隱藏關(guān)系鏈，因?yàn)槌跏蓟[藏關(guān)系鏈時(shí)，并不需要生成確定性的關(guān)系鏈頭部。在本文的DSSE方案中，當(dāng)某在本文的方案中，每一條隱藏關(guān)系鏈的頭部就是一個(gè)密文，因此，節(jié)約了關(guān)系鏈頭部的存儲(chǔ)空間。

第一次出現(xiàn)時(shí)，其對(duì)應(yīng)的隱藏關(guān)系鏈的頭部才生成。換言之，

的文件標(biāo)識(shí)符。本文生成的K

陷門后，尋找到對(duì)應(yīng)的

的隱藏關(guān)系鏈；在隱藏關(guān)系鏈的引導(dǎo)下，能快速查找到該

匹配的剩余K

當(dāng)給已經(jīng)存在的文件id添加一個(gè)新的W'時(shí)，將會(huì)生成1密文添加到鏈的末尾；同樣地，生成的K2密文將會(huì)被添加到W'鏈的末尾。總的來(lái)說(shuō)，本文的方案在添加密文時(shí)，采取的都是將生成的密文添加到隱藏鏈的尾部，而不是在中部添加。因此，不同于KPR'12采取的在中部添加密文的方案，本文的方案泄露信息較少。

—標(biāo)識(shí)符對(duì)（id， W'）3個(gè)對(duì)應(yīng)的密文；并將生成的 K

與KPR'12相比較，本文工作面臨的最大的挑戰(zhàn)就是實(shí)現(xiàn)文件和其某個(gè)的物理刪除，并且確保低泄露和隱私安全。簡(jiǎn)單來(lái)說(shuō)，這2種刪除功能都是用于將密文從隱藏關(guān)系鏈中刪除。如果直接實(shí)現(xiàn)物理刪除，那么在刪除后必須修復(fù)由于刪除而破壞的隱藏關(guān)系鏈。例如，圖2展示的和L的具體值，然后設(shè)置L= L。這些操作將會(huì)泄露一些信息，如標(biāo)簽 L、L和待刪除的標(biāo)簽 L處于同一個(gè)隱藏密文鏈中。最壞的情況下，隱藏鏈中所有密文都會(huì)被泄露。為了克服這個(gè)問(wèn)題，本文采用邏輯刪除和物理刪除相配合的方法來(lái)避免泄露較多的信息。

隱藏鏈中的第2個(gè)密文被刪除后，為了修復(fù)破壞的隱藏關(guān)系鏈，就必須知道 L

當(dāng)需要?jiǎng)h除一個(gè)標(biāo)識(shí)符—對(duì)（id， W）的所有可搜索密文時(shí)，服務(wù)器快速發(fā)現(xiàn)3密文，通過(guò)解密后得到指向K1密文和K2密文的索引；再通過(guò)將對(duì)應(yīng)密文標(biāo)志位置“1”的方式實(shí)現(xiàn)對(duì)這2個(gè)K1和K2密文的邏輯刪除；最后，物理刪除上述K3密文。

對(duì)應(yīng)的K

當(dāng)需要?jiǎng)h除指定文件的所有可搜索密文時(shí)，服務(wù)器快速查找到文件id的隱藏鏈；根據(jù)這個(gè)隱藏關(guān)系鏈，所有的K2密文將被快速查找到。從圖1可看出，每個(gè)K2密文可解密出2個(gè)索引，分別指向K1和K3密文；最后，K2密文指向的K1密文都會(huì)被邏輯刪除，K2密文和 K3密文都將被物理刪除。

本文目的是實(shí)現(xiàn)K1密文的物理刪除。在檢索階段，若檢測(cè)到某 K1密文的邏輯刪除標(biāo)簽位為“1”，則將K1進(jìn)行物理刪除，并修復(fù)隱藏關(guān)系鏈。這樣的方法不會(huì)泄露額外信息，因?yàn)樗阉鬟^(guò)程本身的泄露信息足以用來(lái)修復(fù)由于物理刪除所破壞的隱藏關(guān)系鏈。簡(jiǎn)而言之，在本文提出的方案中，可搜索密文的完整刪除過(guò)程包含有2個(gè)隊(duì)伍：在刪除階段僅實(shí)現(xiàn)密文的邏輯刪除；在檢索階段實(shí)現(xiàn)密文的物理刪除。邏輯刪除和物理刪除相配合使用，保證刪除操作的高安全性。

4.2 方案對(duì)比

本文提出的支持低泄露和物理刪除的 DSSE方案實(shí)現(xiàn)了更細(xì)致的功能。表 1對(duì)比了已有的DSSE方案和本文提出的方案。本文提出方案在檢索效率和存儲(chǔ)開(kāi)銷方面均達(dá)到了目前最優(yōu)的指標(biāo)；在功能性方面，實(shí)現(xiàn)了文件添加、關(guān)鍵字添加、文件和關(guān)鍵字的物理刪除。

5 可搜索公鑰加密

在SSE中，由于對(duì)稱密碼體制自身的限制，通常在多用戶場(chǎng)景下，用戶之間具有事前構(gòu)建某種安全信道來(lái)傳遞秘密信息，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)的加密上傳與檢索。相比之下，基于公鑰密碼體制的可搜索加密則無(wú)需事先建立安全信道就可以實(shí)現(xiàn)用戶在公共網(wǎng)絡(luò)中的保密通信和安全檢索。

5.1 PEKS的提出

2004年，Boneh［31］以加密郵件系統(tǒng)的檢索問(wèn)題為出發(fā)點(diǎn)，首次提出了PEKS的概念和實(shí)例化方案，從而初步實(shí)現(xiàn)了在不泄露郵件內(nèi)容和關(guān)鍵字的條件下，郵件服務(wù)器對(duì)加密郵件的關(guān)鍵字檢索。圖3所示為PEKS在郵件加密系統(tǒng)中的一個(gè)應(yīng)用場(chǎng)景。

表1 DSSE方案功能對(duì)比方案 檢索開(kāi)銷 存儲(chǔ)開(kāi)銷 文件添加添加 文件刪除

刪除 信息泄露文獻(xiàn)［12］方案 低 中 √ × 物理刪除 × 大文獻(xiàn)［13］方案 中 高 √ × 物理刪除 × 中文獻(xiàn)［14］方案 低 低 √ √ × 邏輯刪除 小文獻(xiàn)［30］方案 高 中 √ × 物理刪除 × 小本文方案 低 低 √ √ 物理刪除 物理刪除 小

在實(shí)際應(yīng)用中，PEKS的典型應(yīng)用場(chǎng)景由多個(gè)發(fā)送方、一個(gè)服務(wù)器和一個(gè)接收方組成。任意發(fā)送方可以采用接收方的公鑰生成關(guān)鍵字可搜索密文，并發(fā)送給服務(wù)器；接收方可以為指定關(guān)鍵字生成檢索陷門并發(fā)送給服務(wù)器；服務(wù)器檢索出含有指定關(guān)鍵字的密文并返還給接收者。可以看出，由于PEKS的公鑰特點(diǎn)，發(fā)送方不需要和接收方有任何的交互就可以生成關(guān)鍵字可搜索密文。但是，在SSE中，發(fā)送方必須事先和接收方建立安全信道，協(xié)商某種共享秘密，才能生成關(guān)鍵字可搜索密文。因此，在SSE的應(yīng)用中，發(fā)送方和接收方必須同時(shí)在線。相反地，PEKS適用于發(fā)送方和接收方不能保證同時(shí)在線的場(chǎng)景。例如，在郵件系統(tǒng)中發(fā)送方和接收方不需要同時(shí)在線。

圖3 PEKS應(yīng)用場(chǎng)景

5.2 PEKS的概念

以圖3所示的應(yīng)用場(chǎng)景為例，PEKS由以下4個(gè)多項(xiàng)式時(shí)間算法組成。

1） 系統(tǒng)初始化算法：輸入一個(gè)安全參數(shù)，系統(tǒng)生成接收方的一組公私密鑰對(duì)，私鑰由接收方秘密保存，公鑰公開(kāi)。

2） 可搜索密文生成算法：輸入公鑰和，發(fā)送方生成

可搜索密文。

3） 檢索陷門生成算法：接收方輸入私鑰和待檢索的，生成

陷門。

4） 密文檢索算法：輸入公鑰，一條可搜索密文和接收方檢索陷門，服務(wù)器進(jìn)行匹配操作，判斷密文是否包含查詢關(guān)鍵字。

PEKS允許任何知道接收方公鑰的人都可以將可搜索密文提交至服務(wù)器，包含加密后的文件以及提取出來(lái)的

。當(dāng)接收者需要檢索包含某個(gè)

的密文時(shí)，向服務(wù)器提交一個(gè)檢索陷門；然后服務(wù)器在不知道文件和

原始明文的情況下，檢索到包含該

的所有密文，并將文件的密文發(fā)送給接收者；最后接收者將該密文解密后得到自己需要的檢索結(jié)果。通用地說(shuō)，PEKS允許在不泄露

信息的條件下，公鑰生成的密文可以被判定是否含有指定的

。

5.3 PEKS的部分相關(guān)研究

PEKS的概念提出之后，受到了學(xué)者的廣泛關(guān)注，很多出色的相關(guān)研究工作相繼發(fā)表。遵循PEKS的開(kāi)創(chuàng)性工作，Abdella等［32］完善了PEKS的一致性定義，提出了將一個(gè)匿名IBE方案轉(zhuǎn)換為一個(gè)安全的 PEKS方案的通用模型，擴(kuò)展了PEKS的基本方案，進(jìn)而提出了匿名HIBE方案、臨時(shí)關(guān)鍵字的可搜索公鑰加密方案和基于身份的關(guān)鍵字可搜索加密方案。

在實(shí)現(xiàn)PKES的檢索多樣化方面，典型的工作有聯(lián)合檢索［33～38］、范圍檢索［39～41］、子集檢索［41］、時(shí)間范圍檢索［32，42］、相似度檢索［43，44］以及授權(quán)檢索［45］。此外，Yang等［46］還提出了一種能夠測(cè)試2條異構(gòu)密文是否包含相同明文的方案。Arriaga等［47］提出了一個(gè)保護(hù)關(guān)鍵字檢索陷門隱私性的 PEKS方案。Camenisch等［48］構(gòu)造了“不經(jīng)意”的關(guān)鍵字檢索自陷門生成器，以此針對(duì)不可信的陷門生成器來(lái)保護(hù)關(guān)鍵字的隱私。

在以上PKES方案中，檢索復(fù)雜度與所有密文的數(shù)目線性相關(guān)。為了實(shí)現(xiàn)的高效檢索，Camenisch等在文獻(xiàn)［48］中非正式地描述了一種方法，使具有相同

的密文形成一條隱式鏈。如果服務(wù)器正確查找到第一條匹配的密文，他們的方法將會(huì)提高檢索的效率。然而，他們并沒(méi)有解決如何找到第一段匹配密文的問(wèn)題。同時(shí)，他們的加密方案不具備語(yǔ)義安全性。在每一條鏈中，第一條密文和后邊的密文是平凡可區(qū)分的。這種平凡可區(qū)分性使在這個(gè)方案中很難正確定義語(yǔ)義安全。實(shí)際上，他們并沒(méi)有提供任何正式的安全性定義。

Boneh等［31］在公鑰加密開(kāi)山作中給出了明確的安全性定義，即選擇攻擊下的語(yǔ)義安全性（SS-CKA）。此安全性定義意味著如果服務(wù)器沒(méi)有得到不會(huì)獲取含有對(duì)應(yīng)［49］首次提出了針對(duì)PEKS的［50］證明了任何至少滿足計(jì)算不可區(qū)分的一致性的PKES方案都易遭受 KGA攻擊。為了抵抗外部攻擊者發(fā)起的KGA攻擊，文獻(xiàn)［51，52］分別提出2種方法：一種是為［54］。

檢索陷門建立安全性的傳輸信道；另一種是PEKS的發(fā)送方和接收方通過(guò)協(xié)商

的別名實(shí)現(xiàn)

的匿名性。但是，由于 PEKS的主要優(yōu)點(diǎn)在于發(fā)送方和接收方不需要同時(shí)在線即可以完成可搜索密文的生成，因此，文獻(xiàn)［52］提出的方案在實(shí)際應(yīng)用中失去了PEKS的優(yōu)勢(shì)。解決這個(gè)問(wèn)題的一個(gè)直接的思路是允許發(fā)送者自定義

，從而增大

空間，使KGA攻擊無(wú)法在有效時(shí)間內(nèi)完成。然而，正如文獻(xiàn)［53］所言，這種方法使接收者很難去生成對(duì)應(yīng)的

檢索陷門，并且如果不同的發(fā)送方使用不同的

來(lái)表達(dá)同一個(gè)意思，那么接收方就必須生成多個(gè)

檢索陷門來(lái)檢索密文，大幅度增加了檢索開(kāi)銷。因此，很有必要拓展傳統(tǒng)的 PEKS模型，使得盡管

空間很小，依舊能夠?qū)崿F(xiàn)在 KGA攻擊模式下

的機(jī)密性

猜測(cè)攻擊（KGA，keyword guessing attack）。Jeong等

的密文段中的任何信息。但是，選擇

攻擊下的語(yǔ)義安全性并沒(méi)有論述當(dāng)

檢索陷門被知曉的情況下是否依舊能保障

的機(jī)密性。2006年，Byun等

檢索的檢索陷門，那么服務(wù)器就

6 確定的可搜索公鑰加密

已有的具有語(yǔ)義安全的可搜索公鑰加密方案的檢索時(shí)間是與所有密文的數(shù)量成線性相關(guān)的，這在海量數(shù)據(jù)庫(kù)中肯定會(huì)存在性能問(wèn)題。在公鑰加密體制中，如果密文的生成算法為確定性算法，則該方案為確定公鑰加密，且確定性加密具有更快的檢索效率。因此，在引入了確定性公鑰加密（DPKE，deterministic public-key encryption）后，Bellare等［55］首次提出確定的可搜索公鑰加密（DPEKS，deterministic PEKS），使

檢索十分高效。

Bellare等［55］在提出了DPEKS后，形式化定義了一個(gè)安全性概念，即“盡可能強(qiáng)”（比單向性強(qiáng)，但是比語(yǔ)義安全性弱），進(jìn)而提出了在隨機(jī)預(yù)言機(jī)模型下的滿足該安全性定義的DPEKS方案。經(jīng)過(guò)對(duì)該工作的深入研究，2008年Bellare等［56］公開(kāi)了一個(gè)DPKE方案和一個(gè)在隨機(jī)預(yù)言機(jī)模型下將隨機(jī)性PKE方案轉(zhuǎn)化成DPKE的通用方法。緊接著，Bellare等［56］和Boldyreva等［57］分別在標(biāo)準(zhǔn)模型下提出了DPKE的構(gòu)造方案。前者使用了常用的復(fù)雜性假設(shè)且構(gòu)造方案是通用的，后者使用了特殊的復(fù)雜性假設(shè)且構(gòu)造方案具備更好的效率。Brakerski等［58］提出的DPKE方案具備更好的安全性。到目前為止，DPEKS方案只能在關(guān)鍵字空間先驗(yàn)高熵條件下具有語(yǔ)義安全性，否則，攻擊者容易發(fā)起猜測(cè)攻擊，從而破解出加密的關(guān)鍵字。因此，DPEKS只有在關(guān)鍵字空間具有先驗(yàn)高熵的應(yīng)用場(chǎng)景下才適用。

7 本文提出的PEKS方案

直觀來(lái)看，PEKS具有的語(yǔ)義安全性，使得即使含有相同的 2個(gè)密文之間也相互獨(dú)立，因此，PEKS的檢索復(fù)雜度似乎必須是線性級(jí)（即與密文的總量線性相關(guān)）。而且，現(xiàn)有的語(yǔ)義安全的PEKS實(shí)例化方案也都是這種線性級(jí)的檢索復(fù)雜度。針對(duì)這個(gè)問(wèn)題，本文在文獻(xiàn)［59］中設(shè)計(jì)和實(shí)現(xiàn)了一種帶隱藏結(jié)構(gòu)的可搜索公鑰加密方案（SPCHS，searchable public-key ciphertexts with hidden structures），首次在保證語(yǔ)義安全性的條件下實(shí)現(xiàn)了亞線性級(jí)的檢索效率，降低了PEKS方案的檢索開(kāi)銷；在保證PEKS高安全性的同時(shí)提高其檢索效率，在一定程度上解決了PEKS的低檢索效率問(wèn)題。

7.1 研究思路與技巧

傳統(tǒng)PEKS方案中，由于服務(wù)器需要遍歷完所有的密文才能找到所有的包含檢索的文件，因此服務(wù)器的檢索效率很低。經(jīng)過(guò)研究發(fā)現(xiàn)，如果密文之間存在如圖 4所示的隱藏的星型結(jié)構(gòu)［37］，那么在檢索包含某個(gè)

的密文時(shí)，速度就會(huì)加快。

在圖4的結(jié)構(gòu)中，包含相同的可搜索密文形成一條隱藏鏈結(jié)構(gòu)，所有的鏈都有一個(gè)公共的頭部。服務(wù)器在獲得了進(jìn)而找到下一條符合檢索條件的密文。按照同樣的方法，就可以找到所有符合檢索條件的密文?？梢钥闯?，上述方法的檢索復(fù)雜度與包含被檢索

的密文數(shù)量成線性相關(guān)的，而不是與所有密文的數(shù)量線性相關(guān)。

檢索陷門后，先通過(guò)與公共頭部計(jì)算，從而找到第一條符合檢索條件的密文；通過(guò)該密文可以解密出一個(gè)指針，

圖4 可搜索密文的星型結(jié)構(gòu)

在提高效率的同時(shí)，應(yīng)當(dāng)保證適當(dāng)?shù)陌踩?，之間隱藏的星型結(jié)構(gòu)是需要保證語(yǔ)義安全性的，即僅僅在知道對(duì)應(yīng)的

檢索陷門時(shí)泄露部分關(guān)系。語(yǔ)義安全性表現(xiàn)在以下兩點(diǎn)：1） 在不知道

檢索陷門的條件下，所有密文都是不可區(qū)分的，且結(jié)構(gòu)的任何信息都不泄露；2） 已知某

的檢索陷門，僅有相關(guān)的隱藏關(guān)系會(huì)被泄露，而且符合檢索條件的密文并沒(méi)有泄露其他密文的任何信息（除了這些密文不滿足檢索條件之外）。

7.2 具體貢獻(xiàn)

本文提出了SPCHS及其語(yǔ)義安全性的定義，然后根據(jù)這個(gè)定義在隨機(jī)預(yù)言機(jī)模型下構(gòu)造了一個(gè)簡(jiǎn)單的SPCHS方案。此方案會(huì)生成帶隱藏星型結(jié)構(gòu)的可搜索關(guān)鍵字密文。它的搜索性能取決于包含檢索關(guān)鍵字的密文數(shù)量。它的安全性基于判定雙線性映射假設(shè)，在隨機(jī)預(yù)言機(jī)模型下是語(yǔ)義安全的。隨后，本文基于身份加密（IBE，identity-based encryption）［60］和無(wú)碰撞全身份可展的基于身份密鑰封裝機(jī)制（IBKEM，identity-based key encapsulation mechanism）［61］構(gòu)造了一個(gè)通用的SPCHS方案，使如果存在具有語(yǔ)義安全性和匿名性的 IBE和 IBKEM方案，那么由此構(gòu)造的SPCHS方案也是語(yǔ)義安全的。最后，本文構(gòu)造了標(biāo)準(zhǔn)模型下可證明安全的SPCHS方案。

8 結(jié)束語(yǔ)

目前，SSE的研究是密碼學(xué)領(lǐng)域的熱點(diǎn)研究方向之一?，F(xiàn)有的研究成果離實(shí)際應(yīng)用還存在明顯的差距，如多樣化檢索模式下的檢索效率問(wèn)題、檢索完備性的可證明問(wèn)題和多SSE方案的融合問(wèn)題等。本文的已有工作為這些問(wèn)題的解決部分指明了方向，但依然存在難點(diǎn)和挑戰(zhàn)。

［［1］ CURTMOLA R， GARAY J， KAMARA S， et al. Searchable sym-metric encryption: improved definitions and efficient constructions［J］. Journal of Computer Security， 2011， 19（5）:79-88.

［2］ SONG D X， WAGNER D， PERRIG A. Practical techniques for searches on encrypted data［C］//IEEE Symposium on Security & Privacy. 2000:44-55.

［3］ GOH E J. Secure indexes. Cryptography ePrint archive［R］. 2003.

［4］ CHANG Y C， MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data［M］//Applied Cryptography and Network Security. Berlin Heidelberg: Springer， 2015:442-455.

［5］ BELLOVIN S M， CHESWICK W R. Privacy-enhanced searches using encrypted bloom filters［J］. Department of Computer Science Columbia University， 2004.

［6］ AGRAWAL R， KIERNAN J， SRIKANT R， et al. Order preserving encryption for numeric data［C］//ACM Sigmod. 2004: 563-574.

［7］ WATERS B R， BALFANZ D， DURFEE G， et al. Building an encrypted and searchable audit log［J］. Annual Network & Distributed System Security Symposium， 2003.

［8］ BRINKMAN R， DOUMEN J， JONKER W. Using secret sharing for searching in encrypted data［J］. Lecture Notes in Computer Science， 2004， 3178:18-27.

［9］ DAMIANI E， VIMERCATI S D C， JAJODIA S， et al. Balancing confidentiality and efficiency in untrusted relational DBMSs［C］// ACM CCS. 2003:93-102.

［10］ HACIGüMüS H， IYER B R， LI C， et al. Executing SQL over encrypted data in the database-service-provider model［C］// SIGMOD. 2002:216-227.

［11］ HACIGüMü? H， IYER B， MEHROTRA S. Efficient execution of aggregation queries over encrypted relational databases［J］. Lecture Notes in Computer Science， 2004， 2973:125-136.

［12］ KANTARCIOGLU M， CLIFTON C. Security issues in querying encrypted data［M］// Data and Applications Security XIX. Berlin Heidelberg: Springer， 2005:325-337.

［13］ BAO F， DENG R H， DING X， et al. Private query on encrypted data in multi-user settings［J］. Lecture Notes in Computer Science，2008， 4991:71-85.

［14］ JARECKI S， JUTLA C， KRAWCZYK H， et al. Outsourced symmetric private information retrieval［C］//ACM Sigsac Conference on Computer & Communications Security. 2013:875-888.

［15］ KATZ J， SAHAI A， WATERS B. Predicate encryption supporting disjunctions， polynomial equations， and inner products［J］. Journal of Cryptology， 2008: 191-224.

［16］ CASH D， JARECKI S， JUTLA C， et al. Highly-scalable searchable symmetric encryption with support for boolean queries［M］// Advances in Cryptology-CRYPTO 2013. Berlin Heidelberg: Springer，2013:353-373.

［17］ LI J， WANG Q， WANG C， et al. Fuzzy keyword search over encrypted data in cloud computing［J］. Infocom， 2012， 3（9）:1-5.

［18］ BRINGER J， CHABANNE， KINDARJI B. Error-tolerant searchable encryption［C］//IEEE International Conference on Communications. 2009:1-6.

［19］ LIU Z， MA H， LI J， et al. Secure storage and fuzzy query over encrypted databases［C］//International Conference on Network and System Security. 2013:439-450.

［20］ NEPOLEAN D， KARTHIK I， PREETHI MU， et al. Privacy pre-serving ranked keyword search over encrypted cloud data［M］// Recent Trends in Computer Networks and Distributed Systems Security. Berlin Heidelberg: Springer， 2014:396-403.

［21］ WANG C， CAO N， LI J， et al. Secure ranked keyword search over encrypted cloud data［C］// IEEE International Conference on Distributed Computing Systems， IEEE Computer Society. 2010: 253-262.

［22］ WANG C， CAO N， REN K， et al. Enabling secure and efficient ranked keyword search over outsourced cloud data［J］. IEEE Transactions on Parallel & Distributed Systems， 2012， 23（8）:1467-1479.［23］ CAO N， WANG C， LI M， et al. Privacy-preserving multi-keyword ranked search over encrypted cloud data［J］. IEEE Transactions on Parallel & Distributed Systems， 2014， 25（1）:222-233.

［24］ LU Y. Privacy-preserving logarithmic-time search on encrypted data in cloud［C］// NDSS. 2012.

［25］ BOLDYREVA A， CHENETTE N， LEE Y， et al. Order-preserving symmetric encryption［C］//The International Conference on the Theory and Applications of Cryptographic Techniques. 2009: 224-241.

［26］ CHASE M， KAMARA S. Structured encryption and controlled disclosure［M］//Advances in Cryptology-ASIACRYPT 2010. Berlin Heidelberg: Springer， 2010:577-594.

［27］ KAMARA S， PAPAMANTHOU C， ROEDER T. Dynamic searchable symmetric encryption［C］//ACM Conference on Computer & Communications Security. 2015:965-976.

［28］ KAMARA S， PAPAMANTHOU C. Parallel and dynamic searchable symmetric encryption［M］//Financial Cryptography and Data Security. Berlin Heidelberg: Springer， 2013:258-274.

［29］ CASH D， JAEGER J， JARECKI S， et al. Dynamic searchable encryption in very-large databases: data structures and implementation［C］//Network and Distributed System Security Symposium. 2014.

［30］ HAHN F， KERSCHBAUM F. Searchable encryption with secure and efficient updates［C］//ACM CCS. 2014:310-320.

［31］ DAN B， CRESCENZO G D， OSTROVSKY R， et al. Public key encryption with keyword search［M］//Advances in Cryptology -Eurocrypt. Berlin Heidelberg: Springer， 2003:506-522.

［32］ ABDALLA M， BELLARE M， CATALANO D， et al. Searchable encryption revisited: consistency properties， relation to anonymous IBE， and extensions［J］. Journal of Cryptology， 2008， 21（3）: 350-391.

［33］ BALLARD L， KAMARA S， MONROSE F. Achieving efficient conjunctive keyword searches over encrypted data［C］// International Conference on Information and Communications Security. 2005:414-426.

［34］ BAEK J， SAFAVINAINI R， SUSILO W. Public key encryption with keyword search revisited［M］//Computational Science and Its Applications - ICCSA. 2008:1249-1259.

［35］ GOLLE P， STADDON J， WATERS B R. Secure conjunctive keyword search over encrypted data［J］. Lecture Notes in Computer Science， 2004， 3089:31-45.

［36］ HWANG Y H， LEE P J. Public key encryption with conjunctive keyword search and its extension to a multi-user system［M］// Pairing-Based Cryptography - Pairing 2007. Berlin Heidelberg: Springer，2007:2-22.

［37］ DONG J P， KIM K， LEE P J. Public key encryption with conjunctive field keyword search［J］. Lecture Notes in Computer Science，2004， 3325:73-86.

［38］ RYU E K， TAKAGI T. Efficient conjunctive keyword-searchable encryption［C］//The International Conference on Advanced Information Networking and Applications Workshops， IEEE Computer Society. 2007:409-414.

［39］ BETHENCOURT J， CHAN H， PERRIG A， et al. Anonymous multi-attribute encryption with range query and conditional decryption［C］. IEEE Symposium on Security & Privacy. 2006.

［40］ SHI E， BETHENCOURT J， CHAN T H， et al. Multi-dimensional range query over encrypted data［J］. IEEE Computer Society，2007:350-364.

［41］ DAN B， WATERS B. Conjunctive， subset， and range queries on encrypted data［C］//The Theory of Cryptography Conference. 2006: 535--554.

［42］ DAVIS D， MONROSE F， REITER M K. Time-scoped searching of encrypted audit logs［C］//The International Conference on Information and Communications Security（ICICS）. 2004:532-545.

［43］ CHEUNG D W， MAMOULIS N， WONG W K， et al. Anonymous fuzzy identity-based encryption for similarity search［C］// International Symposiumon Algorithms and Computation. 2010:61-72.

［44］ SEDGHI S， LIESDONK P V， NIKOVA S， et al. Searching keywords with wildcards on encrypted data［C］//The International Conference on Security and Cryptography for Networks. 2010: 138-153.

［45］ LUAN I， NIKOVA S， HARTEL P， et al. Public-key encryption with delegated search［M］//Applied Cryptography and Network Security. Berlin Heidelberg: Springer， 2011:532-549.

［46］ YANG G， TAN C H， HUANG Q， et al. Probabilistic public key encryption with equality test［C］//The International Conference on Topics in Cryptology. 2010:119-131.

［47］ ARRIAGA A， TANG Q， RYAN P. Trapdoor privacy in asymmetric searchable encryption schemes［M］//Progress in Cryptology - AFRICACRYPT 2014. Springer International Publishing， 2014:31-50.

［48］ CAMENISCH J， KOHLWEISS M， RIAL A， et al. Blind and anonymous identity-based encryption and authorised private searches on public key encrypted data［C］//The International Conference on Practice and Theory in Public Key Cryptography. 2009:196-214.

［49］ BYUN J W， LEE D H， LIM J. Efficient conjunctive keyword search on encrypted data storage system［C］//European Conference on Public Key Infrastructure: Theory and Practice. 2006:184-196.

［50］ JEONG I R， KWON J O， HONG D， et al. Constructing PEKSschemes secure against keyword guessing attacks is possible？［J］. Computer Communications， 2009， 32（2）:394-396.

［51］ FANG L， SUSILO W， GE C， et al. A secure channel free public key encryption with keyword search scheme without random oracle［C］//The International Conference on Cryptology and Network Security. 2009:248-258.

［52］ TANG Q， CHEN L. Public-key encryption with registered keyword search［C］// European Workshop on Public Key Infrastructures， Services and Applications. 2009:163-178.

［53］ HARROWER W. Searching encrypted data［R］. 2009.

［54］ XU P， JIN H， WU Q， et al. Public-key encryption with fuzzy keyword search: a provably secure scheme under keyword guessing attack［J］. IEEE Transactions on Computers， 2013， 62（11）: 2266- 2277.

［55］ BELLARE M， BOLDYREVA A， O'NEILL A. Deterministic and efficiently searchable encryption［M］//Advances in Cryptology -CRYPTO 2007. Berlin Heidelberg :Springer， 2007:535-552.

［56］ BELLARE M， BOLDYREVA A， O'NEILL A. Deterministic and efficiently searchable encryption［C］//The International Cryptology Conference on Advances in Cryptology. 2006:535-552.

［57］ BOLDYREVA A， FEHR S， O'NEILL A. On notions of security for deterministic encryption， and efficient constructions without random oracles［C］// Conference on Cryptology: Advances in Cryptology. 2008:335-359.

［58］ BRAKERSKI Z， SEGEV G. Better security for deterministic public-key encryption: the auxiliary-input setting［M］//Advances in Cryptology-CRYPTO 2011. Berlin Heidelberg: Springer， 2011: 543-560.

［59］ XU P， WU Q， WANG W， et al. Generating searchable public-key ciphertexts with hidden structures for fast keyword search［J］. IEEE Transactions on Information Forensics & Security， 2015， 10（9）:1.

［60］ BOYEN X， WATERS B. Anonymous hierarchical identity-based encryption （without random oracles）［C］//The International Conference on Advances in Cryptology. 2006:290-307.

［61］ ABDALLA M， CATALANO D， FIORE D. Verifiable random functions: relations to identity-based key encapsulation and new constructions［J］. Journal of Cryptology， 2014， 27（3）:544-593.

徐鵬（1981-），男，湖北武漢人，博士，華中科技大學(xué)副教授，主要研究方向?yàn)楣€密碼學(xué)、基于身份密碼學(xué)、可搜索加密、格密碼、云安全。

金海（1966-），男，上海人，博士，華中科技大學(xué)教授，主要研究方向?yàn)楦咝阅苡?jì)算、分布式計(jì)算、云計(jì)算、大數(shù)據(jù)、云安全。

Research on the searchable encryption

XU Peng1，2，3， JIN Hai1，2，3

（1. Services Computing Technology and System Lab， School of Computer Science and Technology，Huazhong University of Science and Technology， Wuhan 430074， China；2. Cluster and Grid Computing Lab， School of Computer Science and Technology，Huazhong University of Science and Technology， Wuhan 430074， China；3. Big Data Technology and System Lab， School of Computer Science and Technology，Huazhong University of Science and Technology， Wuhan 430074， China）

Searchable encryption has been recognized as a promising method to achieve the secure cloud search. According to the types of encryption keys， searchable encryption can be divided into searchable public-key and symmetric-key encryptions. The existing and well-known schemes of those two kinds of encryptions， their limitations， and the corresponding solutions were introduced. Specifically， two works under the condition of high security were introduced: one was to reduce the search complexity of searchable public-key encryption； the other one was to achieve the physical deletion of searchable symmetric-key ciphertexts.

searchable encryption， cloud security， searchable public-key encryption， searchable symmetric-key encryption

1 引言

近年來(lái)，云計(jì)算和網(wǎng)絡(luò)的快速發(fā)展使用戶可以將自身的數(shù)據(jù)存放在云端，以節(jié)省自身的開(kāi)銷、實(shí)現(xiàn)便捷的多點(diǎn)訪問(wèn)。同時(shí)，為了保證數(shù)據(jù)安全和用戶隱私，用戶敏感數(shù)據(jù)通常需要加密后以密文存儲(chǔ)在云端服務(wù)器中。例如，采用代理重加密和基于屬性加密實(shí)現(xiàn)云數(shù)據(jù)的加密存儲(chǔ)與共享等。這些加密方法可以在云端不可信的條件下，實(shí)現(xiàn)用戶數(shù)據(jù)的保密性。但是，加密云存儲(chǔ)的方法也使用戶無(wú)法便捷地從云端提取出滿足某查詢條件的云密文。

s: The National Basic Research Program of China （973 Program）（No.2014CB340600）， The National Natural Science Foundation of China （No.61472156）

TP309.2

A

10.11959/j.issn.2096-109x.2016.00101

2016-08-12；

2016-09-27。通信作者：徐鵬，xupeng@mail.hust.edu.cn

國(guó)家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”項(xiàng)目）基金資助項(xiàng)目（No.2014CB340600）；國(guó)家自然科學(xué)面上基金資助項(xiàng)目（No.61472156）