可搜索加密的研究進展

徐鵬，金海

（1. 華中科技大學計算機科學與技術學院服務計算技術與系統教育部重點實驗室，湖北 武漢 430074；2. 華中科技大學計算機科學與技術學院集群與網格計算湖北省重點實驗室，湖北 武漢 430074；3. 華中科技大學計算機科學與技術學院湖北省大數據技術與系統工程實驗室，湖北 武漢 430074）

可搜索加密的研究進展

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

（1. 華中科技大學計算機科學與技術學院服務計算技術與系統教育部重點實驗室，湖北 武漢 430074；2. 華中科技大學計算機科學與技術學院集群與網格計算湖北省重點實驗室，湖北 武漢 430074；3. 華中科技大學計算機科學與技術學院湖北省大數據技術與系統工程實驗室，湖北 武漢 430074）

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

可搜索加密；云安全；可搜索公鑰加密；可搜索對稱加密

在傳統的密文存儲和查詢服務中，由于云端沒有檢索功能，不能根據用戶需求查找數據，只能將全部密文都返回給用戶，用戶解密后自行檢索才能得到想要的數據。顯然，這種處理方法在實際應用中是不能被接受的。因此，如何在用戶提交檢索請求時，云端能實現高效率檢索并返回指定的密文是云數據安全存儲的重要問題和需求。

2 可搜索加密

為了在保證用戶數據機密性的同時實現安全和高效的密文數據訪問，可搜索加密（SE，searchable encryption）被提出。SE是近年來快速發展的一種支持用戶在密文上進行關鍵字查找的密碼學原語，它能實現云端在不解密密文的情況下，完成對密文的檢索工作。SE一般分為如下4個階段。

1） 數據加密階段：數據擁有者在本地使用密鑰對明文數據進行加密，然后將加密后的數據上傳至服務器。

2） 生成檢索陷門階段：用戶使用密鑰和生成對應的檢索陷門，并將該陷門發送給云端，其中檢索陷門能保密其包含的

內容。

3） 密文檢索階段：根據收到的檢索陷門，云端對密文進行檢索，并將滿足檢索條件的密文發送給用戶，執行過程中云端不能獲得除檢索結果之外的更多信息。

4） 密文解密階段：用戶從云端獲得返回的密文后，使用密鑰解密出相關數據。

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

3 可搜索對稱加密

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

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

3.1 SSE的定義

SSE的實例化方案通常基于偽隨機函數構造，具有計算量小、算法簡單、計算速度快等優點。安全的SSE方案能確保關鍵字的保密性，能抵御外部攻擊和抵御來自云端的內部信息泄露。

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

1） K=KeyGen（k）：輸入安全參數k，輸出隨機產生的密鑰K。

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

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

對應的陷門。

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

W的文件的標識符集合。

5） Di=Dec（K， Ci）：輸入密鑰K和密文文件Ci，輸出解密后對應的明文文件Di。

3.2 SSE的相關研究

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

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

4 本文提出的SSE方案

本文調研了當前SSE領域的研究現狀，詳細分析了近年來提出的方案和知名的SSE方案的優缺點，提出了支持低泄露和物理刪除的DSSE方案。本文的SSE方案在檢索效率、動態更新的粒度、可搜索密文的刪除能力和安全性方面均達到了同類方案的最優。

4.1 核心思想

在標準的DSSE方案應用案例中，每個文件都有一個標識符和幾個對應的。通常使用一個文件標識符—1、K2、K3。這3個可搜索密文分別對應搜索、刪除文件和刪除1密文構成一條隱藏的關系鏈，和同一個文件的標識符的所有 K2密文也構成一條隱藏關系鏈。K3密文之間不存在任何隱藏關系。

這3個功能的實現。包含相同

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

的所有K

對（id， W），表示標識符為id的文件包含

W。假設數據庫DB就是由所有的標識符—

對組成的。在本文的方案中，對于每一個數據庫中的標識符—

對，都會為其生成3種可搜索密文，分別是K

圖1—標識符對（id， W）生成的密文

圖2 密文之間隱藏關系鏈

當進行搜索時，輸入待搜索1密文；通過解密K1密文，獲得包含查詢1密文不同于KPR'12中提到的隱藏關系鏈，因為初始化隱藏關系鏈時，并不需要生成確定性的關系鏈頭部。在本文的DSSE方案中，當某在本文的方案中，每一條隱藏關系鏈的頭部就是一個密文，因此，節約了關系鏈頭部的存儲空間。

第一次出現時，其對應的隱藏關系鏈的頭部才生成。換言之，

的文件標識符。本文生成的K

陷門后，尋找到對應的

的隱藏關系鏈；在隱藏關系鏈的引導下，能快速查找到該

匹配的剩余K

當給已經存在的文件id添加一個新的W'時，將會生成1密文添加到鏈的末尾；同樣地，生成的K2密文將會被添加到W'鏈的末尾。總的來說，本文的方案在添加密文時，采取的都是將生成的密文添加到隱藏鏈的尾部，而不是在中部添加。因此，不同于KPR'12采取的在中部添加密文的方案，本文的方案泄露信息較少。

—標識符對（id， W'）3個對應的密文；并將生成的 K

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

隱藏鏈中的第2個密文被刪除后，為了修復破壞的隱藏關系鏈，就必須知道 L

當需要刪除一個標識符—對（id， W）的所有可搜索密文時，服務器快速發現3密文，通過解密后得到指向K1密文和K2密文的索引；再通過將對應密文標志位置“1”的方式實現對這2個K1和K2密文的邏輯刪除；最后，物理刪除上述K3密文。

對應的K

當需要刪除指定文件的所有可搜索密文時，服務器快速查找到文件id的隱藏鏈；根據這個隱藏關系鏈，所有的K2密文將被快速查找到。從圖1可看出，每個K2密文可解密出2個索引，分別指向K1和K3密文；最后，K2密文指向的K1密文都會被邏輯刪除，K2密文和 K3密文都將被物理刪除。

本文目的是實現K1密文的物理刪除。在檢索階段，若檢測到某 K1密文的邏輯刪除標簽位為“1”，則將K1進行物理刪除，并修復隱藏關系鏈。這樣的方法不會泄露額外信息，因為搜索過程本身的泄露信息足以用來修復由于物理刪除所破壞的隱藏關系鏈。簡而言之，在本文提出的方案中，可搜索密文的完整刪除過程包含有2個隊伍：在刪除階段僅實現密文的邏輯刪除；在檢索階段實現密文的物理刪除。邏輯刪除和物理刪除相配合使用，保證刪除操作的高安全性。

4.2 方案對比

本文提出的支持低泄露和物理刪除的 DSSE方案實現了更細致的功能。表 1對比了已有的DSSE方案和本文提出的方案。本文提出方案在檢索效率和存儲開銷方面均達到了目前最優的指標；在功能性方面，實現了文件添加、關鍵字添加、文件和關鍵字的物理刪除。

5 可搜索公鑰加密

在SSE中，由于對稱密碼體制自身的限制，通常在多用戶場景下，用戶之間具有事前構建某種安全信道來傳遞秘密信息，進而實現數據的加密上傳與檢索。相比之下，基于公鑰密碼體制的可搜索加密則無需事先建立安全信道就可以實現用戶在公共網絡中的保密通信和安全檢索。

5.1 PEKS的提出

2004年，Boneh［31］以加密郵件系統的檢索問題為出發點，首次提出了PEKS的概念和實例化方案，從而初步實現了在不泄露郵件內容和關鍵字的條件下，郵件服務器對加密郵件的關鍵字檢索。圖3所示為PEKS在郵件加密系統中的一個應用場景。

表1 DSSE方案功能對比方案 檢索開銷 存儲開銷 文件添加添加 文件刪除

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

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

圖3 PEKS應用場景

5.2 PEKS的概念

以圖3所示的應用場景為例，PEKS由以下4個多項式時間算法組成。

1） 系統初始化算法：輸入一個安全參數，系統生成接收方的一組公私密鑰對，私鑰由接收方秘密保存，公鑰公開。

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

可搜索密文。

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

陷門。

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

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

。當接收者需要檢索包含某個

的密文時，向服務器提交一個檢索陷門；然后服務器在不知道文件和

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

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

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

。

5.3 PEKS的部分相關研究

PEKS的概念提出之后，受到了學者的廣泛關注，很多出色的相關研究工作相繼發表。遵循PEKS的開創性工作，Abdella等［32］完善了PEKS的一致性定義，提出了將一個匿名IBE方案轉換為一個安全的 PEKS方案的通用模型，擴展了PEKS的基本方案，進而提出了匿名HIBE方案、臨時關鍵字的可搜索公鑰加密方案和基于身份的關鍵字可搜索加密方案。

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

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

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

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

檢索陷門建立安全性的傳輸信道；另一種是PEKS的發送方和接收方通過協商

的別名實現

的匿名性。但是，由于 PEKS的主要優點在于發送方和接收方不需要同時在線即可以完成可搜索密文的生成，因此，文獻［52］提出的方案在實際應用中失去了PEKS的優勢。解決這個問題的一個直接的思路是允許發送者自定義

，從而增大

空間，使KGA攻擊無法在有效時間內完成。然而，正如文獻［53］所言，這種方法使接收者很難去生成對應的

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

來表達同一個意思，那么接收方就必須生成多個

檢索陷門來檢索密文，大幅度增加了檢索開銷。因此，很有必要拓展傳統的 PEKS模型，使得盡管

空間很小，依舊能夠實現在 KGA攻擊模式下

的機密性

猜測攻擊（KGA，keyword guessing attack）。Jeong等

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

攻擊下的語義安全性并沒有論述當

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

的機密性。2006年，Byun等

檢索的檢索陷門，那么服務器就

6 確定的可搜索公鑰加密

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

檢索十分高效。

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

7 本文提出的PEKS方案

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

7.1 研究思路與技巧

傳統PEKS方案中，由于服務器需要遍歷完所有的密文才能找到所有的包含檢索的文件，因此服務器的檢索效率很低。經過研究發現，如果密文之間存在如圖 4所示的隱藏的星型結構［37］，那么在檢索包含某個

的密文時，速度就會加快。

在圖4的結構中，包含相同的可搜索密文形成一條隱藏鏈結構，所有的鏈都有一個公共的頭部。服務器在獲得了進而找到下一條符合檢索條件的密文。按照同樣的方法，就可以找到所有符合檢索條件的密文。可以看出，上述方法的檢索復雜度與包含被檢索

的密文數量成線性相關的，而不是與所有密文的數量線性相關。

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

圖4 可搜索密文的星型結構

在提高效率的同時，應當保證適當的安全性，之間隱藏的星型結構是需要保證語義安全性的，即僅僅在知道對應的

檢索陷門時泄露部分關系。語義安全性表現在以下兩點：1） 在不知道

檢索陷門的條件下，所有密文都是不可區分的，且結構的任何信息都不泄露；2） 已知某

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

7.2 具體貢獻

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

8 結束語

目前，SSE的研究是密碼學領域的熱點研究方向之一。現有的研究成果離實際應用還存在明顯的差距，如多樣化檢索模式下的檢索效率問題、檢索完備性的可證明問題和多SSE方案的融合問題等。本文的已有工作為這些問題的解決部分指明了方向，但依然存在難點和挑戰。

［［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-），男，湖北武漢人，博士，華中科技大學副教授，主要研究方向為公鑰密碼學、基于身份密碼學、可搜索加密、格密碼、云安全。

金海（1966-），男，上海人，博士，華中科技大學教授，主要研究方向為高性能計算、分布式計算、云計算、大數據、云安全。

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 引言

近年來，云計算和網絡的快速發展使用戶可以將自身的數據存放在云端，以節省自身的開銷、實現便捷的多點訪問。同時，為了保證數據安全和用戶隱私，用戶敏感數據通常需要加密后以密文存儲在云端服務器中。例如，采用代理重加密和基于屬性加密實現云數據的加密存儲與共享等。這些加密方法可以在云端不可信的條件下，實現用戶數據的保密性。但是，加密云存儲的方法也使用戶無法便捷地從云端提取出滿足某查詢條件的云密文。

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

國家重點基礎研究發展計劃（“973”項目）基金資助項目（No.2014CB340600）；國家自然科學面上基金資助項目（No.61472156）