可搜索加密研究進展

董曉蕾 周 俊 曹珍富

(華東師范大學計算機科學與軟件工程學院密碼與網絡安全系 上海 200062)(dongxiaolei@sei.ecnu.edu.cn)

2017-08-31；

2017-09-13

國家自然科學基金項目(61632012，61672239，61602180)；上海市高新技術領域項目(16511101400)；上海市自然科學基金項目(16ZR1409200) This work was supported by the National Natural Science Foundation of China (61632012, 61672239, 61602180), the Shanghai High-Tech Field Project (16511101400), and the Natural Science Foundation of Shanghai (16ZR1409200).

曹珍富(zfcao@sei.ecnu.edu.cn)

可搜索加密研究進展

董曉蕾 周 俊 曹珍富

(華東師范大學計算機科學與軟件工程學院密碼與網絡安全系 上海 200062)(dongxiaolei@sei.ecnu.edu.cn)

隨著大數(shù)據(jù)與云計算的發(fā)展，以可搜索加密為核心技術的安全搜索問題日益成為國內外研究的熱點.圍繞可搜索加密的新理論、新方法和新技術，針對可搜索加密的模式、安全性、表達能力和搜索效率等方面進行綜述.主要內容如下：安全搜索必不可少的新理論研究進展，包括可搜索加密、屬性基加密及其輕量化等相關理論問題的研究情況介紹；基于公鑰密碼算法(包括輕量化公鑰密碼算法)的安全搜索研究中，提出的減少公鑰密碼算法的使用次數(shù)的新方法概述；針對體域網、車載網、智能電網等新興網絡應用服務，介紹了前述新理論、新方法的應用情況.實現(xiàn)安全搜索，通常將不得不多次使用開銷極大的公鑰密碼算法，所以在資源受限的網絡中“怎么使用公鑰密碼算法”就成為一個關鍵問題.因此除了輕量化實現(xiàn)技術，減少使用公鑰密碼算法的次數(shù)(尤其是只使用一次)應成為高效解決這類問題的最為關鍵的步驟.此外，還指出了該領域當前研究中需要解決的公開問題和未來的發(fā)展趨勢.

安全搜索；可搜索加密；輕量化；屬性基加密；高效實現(xiàn)

傳統(tǒng)的信息檢索系統(tǒng)一般是建立在明文系統(tǒng)上的，即服務器在明文上進行搜索操作.因此，服務器對整個數(shù)據(jù)庫的數(shù)據(jù)及搜索的關鍵字一目了然.也即是說，服務器對于用戶來說是完全可信的.之后，在服務器端加上訪問控制功能，解決了合法用戶的授權問題.然而服務器通常工作在半可信或惡意環(huán)境下，前者是指服務器誠實地遵照協(xié)議的規(guī)定執(zhí)行，并通過與用戶的交互最大限度地提取用戶的秘密信息；后者是指服務器通過任意破壞行為來阻礙協(xié)議的執(zhí)行.因此數(shù)據(jù)文件必須先加密再上傳到服務器中外包存儲.如何有效解決密文數(shù)據(jù)上的搜索問題，同時保護搜索的關鍵字隱私成為幾年來亟待解決的重要研究課題.安全搜索也即應運而生.

安全搜索(secure search)通常指對加密數(shù)據(jù)的有效搜索.為了解決當數(shù)據(jù)加密存儲在云端時，服務器不完全可信的前提下如何利用服務器來完成安全的關鍵詞的搜索問題，學者們提出了可搜索加密(searchable encryption, SE)，作為安全搜索的核心技術.可搜索加密作為一種新興的技術，具有廣闊的應用前景，為云計算及大數(shù)據(jù)環(huán)境構造安全、高效的可搜索加密方案具有很強的理論及現(xiàn)實意義.然而，近年來隨著無線通信與移動計算的迅猛發(fā)展，無線體域網、智能電網、車載網等一系列新興網絡應用均具有存儲和計算資源受限的特點，因此，真正實現(xiàn)安全搜索僅依賴可搜索加密技術是不夠的.我們可將安全搜索定義為：“可搜索加密+X”，其中X可定義為輕量化技術、批處理技術等一系列使得安全搜索在新興網絡應用服務中達到高效實例化的各類其他技術.這方面研究主要側重可搜索加密輕量化處理，其基本要求是：在不損失安全性的前提下使之適合各類資源受限的網絡應用.

此外，屬性基加密(attribute-based encryption, ABE)是近10年來的一個重要研究方向，它通過對用戶私鑰設置屬性集(或訪問結構)為數(shù)據(jù)密文設置訪問結構(或屬性集)，由屬性集和訪問結構之間的匹配關系確定其解密能力.特別是密文策略的屬性基加密(CP-ABE)，其密文上的訪問策略本身就是一種搜索策略，訪問策略的表達能力從一定程度上反映了可搜索能力.

對于適用于資源受限的可搜索屬性基加密的研究，主要體現(xiàn)在屬性基加密的高效性和普適性研究上，包括屬性集或訪問結構的表達能力、方案的通信效率及計算效率、屬性特征的研究，以及如何減少使用次數(shù).所以，屬性基加密的研究重點在提供豐富的可搜索功能和確保安全性的情況下，更注重實用性.效率問題是一個密碼系統(tǒng)走向實用化過程中必須考慮并需要解決的問題.當前的屬性基密碼算法都在保證系統(tǒng)安全性的前提下，不斷努力改進其效率，期望為各類資源受限的新興網絡應用提供堅實的基礎.

在本文中，我們側重于對安全搜索的核心技術——可搜索加密——進行較為系統(tǒng)地總結.期望通過總結，提出問題和未來的研究課題.我們的一個觀點是：不管是安全搜索還是其他安全或隱私保護問題，如果頻繁使用開銷極大的公鑰加密，其意義最多只是提供了一個“從無到有”的思路.一個方案要付諸實踐，必須減少公鑰密碼的使用次數(shù).

1 可搜索加密

隨著云計算及大數(shù)據(jù)的流行，越來越多的敏感數(shù)據(jù)集中到云端，信息共享在我們的生活中無處不在，數(shù)據(jù)的安全和用戶的隱私保護就成為一個重要的課題.為了保證數(shù)據(jù)安全和用戶隱私，數(shù)據(jù)一般是以密文形式存儲在云端服務器中，但是用戶將會遇到如何在密文上進行查找的難題.可搜索加密SE是近年來發(fā)展起來的一種支持用戶在密文上進行關鍵字查找的密碼學原語，它能夠為用戶節(jié)省大量的網絡和計算開銷，并充分利用云端服務器龐大的計算資源進行密文上的關鍵字查找.可搜索加密技術主要解決當數(shù)據(jù)加密存儲在云端時，服務器不完全可信的前提下如何利用服務器來完成安全的關鍵詞的搜索.

Fig. 1 Architecture of searchable encryption圖1 可搜索加密基本框架

可搜索加密主要包含對稱可搜索加密(sym-metric searchable encryption, SSE)和非對稱可搜索加密(asymmetric searchable encryption, ASE)兩種類型，二者分別在功能和性能方面有不同的側重點，分別用來解決云計算不同場景下的業(yè)務需求問題.在對稱環(huán)境下，數(shù)據(jù)的產生者、搜索憑證的產生者以及解密者都是同一個用戶.可搜索對稱加密體制使得一個用戶以私有的方式將自己的數(shù)據(jù)遠程存儲在一個半可信的云端服務器上，并保留選擇性恢復所需文件的能力.如圖1所示，可搜索加密的基本框架是：首先數(shù)據(jù)擁有者(發(fā)送者)對數(shù)據(jù)加密并且創(chuàng)建安全索引，然后將加密后的數(shù)據(jù)及其安全索引上傳到云端服務器進行存儲.當用戶(接收者)需要對該文檔進行搜索時，利用密鑰對搜索關鍵字計算其搜索憑證(搜索令牌)發(fā)送給云服務器，云服務器利用搜索憑證為用戶搜索所需要的文件數(shù)據(jù).數(shù)據(jù)擁有者(發(fā)送者)和用戶(接收者)在不同的網絡環(huán)境下可以指定為不同或者相同的用戶實體.在非對稱環(huán)境下，假定數(shù)據(jù)的產生者、搜索憑證的產生者以及解密者是不同的用戶實體，是對對稱環(huán)境下可搜索加密的一種擴展與推廣.

1.1可搜索加密的模式

1) 一對一模式(one-to-one mode)

顧名思義，單寫/單讀模式即指方案僅允許單個數(shù)據(jù)擁有者(發(fā)送者)和單個用戶(接收者)進行相互作用.這種模式的可搜索加密算法大都建立在對稱加密體制上.2000年Song等人[1]首次提出了一對一機制的可搜索加密.如圖2所示，該模式只允許由持有私鑰的用戶對數(shù)據(jù)進行加密，也只能有持有私鑰的用戶對數(shù)據(jù)進行搜索，只相當于一個個人存儲加密系統(tǒng)，在數(shù)據(jù)頻繁交流的今天，這種模式顯然不能滿足人們的需求.

Fig. 2 One-to-one mode searchable encryption圖2 一對一模式的可搜索加密

2) 多對一模式(many-to-one mode)

Fig. 3 Many-to-one mode searchable encryption圖3 多對一模式的可搜索加密

多對一模式的可搜索加密來源于公鑰加密體制.如圖3所示，它允許多個數(shù)據(jù)擁有者分別將各自的加密文件及其安全索引上傳到云端服務器存儲，并由單個用戶發(fā)起基于關鍵詞的查詢.2004年，Boneh等人[2]首次提出多對一模式的可搜索加密.他們給出了基于公鑰的可搜索加密(PEKS)的概念，并定義了公鑰模式下可搜索加密方案的安全性定義.同年，Waters等人[3]提出了一種新的方法構造可搜索的加密審計日志.它可以與任何現(xiàn)有的日志方案相結合,從而達到防篡改的目的.特別是他們還利用Hash鏈來保證數(shù)據(jù)的完整性.此外，Golle等人[4]還提出了一種基于連接關鍵詞的可搜索加密方案，即方案可以搜索同時含有多個關鍵字的文件.但該方案的陷門過于繁瑣，針對此問題，Park等人[5]研究結合域關鍵詞搜索的公鑰加密方案問題.其主要思想是擴展PEKS到允許在公鑰集合中連接關鍵詞搜索.該工作也首次提出了具有常數(shù)陷門大小.

3) 一對多模式(one-to-many mode)

一對多模式的可搜索加密體制為了滿足某種特定背景的應用需求而提出的.如圖4所示，在一對多模式的方案中，允許數(shù)據(jù)擁有者創(chuàng)建可搜索的內容，而搜索陷門由預先設定的用戶群組生成，該種模式可以使得多個用戶對密文進行搜索.該類型的可搜索加密主要使用密鑰共享、代理重加密等其他技術來實現(xiàn).其主要工作由Curtmola等人[6]在2006年基于Naor的廣播加密技術構造出的首個一對多模式下的可搜索加密.但是由于所有用戶中僅共享一個密鑰，因此每次撤銷需要將新密鑰分發(fā)給剩余的用戶，這導致該方案具有極大的撤銷開銷.在其他方案中，每個用戶可能具有其自己的密鑰，這使得用戶撤銷更容易和更有效.

Fig. 4 One-to-many mode searchable encryption圖4 一對多模式的可搜索加密

4) 多對多模式(many-to-many mode)

多對多模式是主要針對大型公司、網絡等實體用戶所設計的可搜索加密模式.如圖5所示，其存儲和搜索查詢都針對預先設定的固定群組，且可以通過秘密共享技術、代理重加密等技術實現(xiàn).2008年Wang等人[7]引入門限隱私保護關鍵字搜索(trapdoor privacy preserving keyword search, TPPKS)，并基于Shamir的秘密共享技術與Boneh and Franklin的基于身份的加密技術構造了第1個這類方案.其主要思想是僅僅允許合作用戶搜索數(shù)據(jù)庫.為保證搜索，每個用戶使用自身的共享秘密生成一個共享陷門.隨后，合作的用戶驗證他們的共享，若驗證成功，則組合他們的共享生成一個目標關鍵詞的陷門.為成功解密，每個用戶生成一個解密共享子塊用于解密.該方案是交互的，僅僅對于固定群的用戶，不能進行用戶添加及刪除.此外，還有Park等人[8]利用代理重加密技術提出了2個多對多模式下的可搜索加密方案，方案中每個用戶有自己唯一的密鑰加密、搜索、加密數(shù)據(jù)，這2個方案均要求一個可信的密鑰管理服務器.

Fig. 5 Many-to-many mode searchable encryption圖5 多對多模式的可搜索加密

模式匹配(字符串匹配)算法是指在一個文本字符串中查找模式串的一個或所有出現(xiàn).考慮到數(shù)據(jù)安全和隱私保護的問題，用戶在云計算環(huán)境中的模式匹配可以看作是可搜索加密的一個特例，模式串相當于關鍵字.密文中的模式匹配我們可稱其為“安全模式匹配”，可應用與云計算中的生物特征匹配、圖像匹配等場景.

近幾年有許多學者提出了各種安全模式匹配的實現(xiàn).Baron等人[9]提出了基于加法同態(tài)加密的安全模式匹配算法，該算法需要O((m+n)k2)帶寬和O(m+n)加密操作(其中m是模式串的長度，n是文本串的長度).Hazay等人[10]提出了基于模擬安全的模式匹配算法，該算法是基于ElGamal加密方案語義安全的前提下提出的，算法復雜度為O(mn).Faust等人[11]在隨機預言機模型下提出了可證明安全的外包模式匹配算法，該算法不依賴于加密的同態(tài)性，而是規(guī)約到子集和問題.無法同時保護文本隱私與模板隱私，且使用一系列零知識證明協(xié)議實現(xiàn)惡意環(huán)境下的防欺詐，效率低下.Chase等人[12]定義了一種新的加密方案——可查詢加密，提出了基于后綴樹的模式匹配算法.Yasuda等人[13]提出了一種基于somewhat同態(tài)加密的安全模式匹配算法，采用somewhat同態(tài)加密可實現(xiàn)密文的有限次加法和乘法運算.Saha等人[14]進一步擴展了Yasuda的算法，提出了一種可實現(xiàn)帶有通配符的安全模式匹配算法.Chase等人[15]構造了一種子字符串可搜索對稱加密方案，采用后綴樹可達到與未加密時相當?shù)臐u近效率.2016年Strizhov等人[16]采用位置堆樹數(shù)據(jù)結構提出一種子字符串可搜索對稱加密方案方案，支持高效地多用戶查詢的場景.

以上4種模式涵蓋了目前可搜索加密體制的主要的系統(tǒng)架構類型，也揭示了可搜索加密的一個發(fā)展歷程.一般來說，可搜索加密體制的主要研究方向分為3個方面：在復雜網絡環(huán)境下可搜索加密方案安全問題、可搜索加密的表達能力問題和可搜索加密方案的搜索效率問題.這3個方面涉及一個方案的底層架構，關乎整個數(shù)據(jù)層的安全性；決定實際應用過程中的通信、與存儲開銷，牽涉到方案的應用前景.目前可搜索加密的實現(xiàn)主要有3個工具：基于數(shù)論的可搜索加密、基于橢圓曲線的可搜索加密以及基于格的可搜索加密.他們都力求在方案安全性、搜索表達能力和搜索效率等方面有所突破.

1.2可搜索加密的安全性

1996年Goldreich和Ostrovsky[17]在期刊《Journal of the ACM》上發(fā)表了重要論文“Software protection and simulation on oblivious RAMs”，文中主要使用Oblivious RAMs研究如何在使用軟件程序的過程中保護程序的隱私，開創(chuàng)了可搜索加密的研究方向.2000年，Song,Wagner和Perrig[1]在會議IEEE Symposium on Security and Privacy上發(fā)表“Practical techniques for searching on encrypted data”，首次提出了在密文環(huán)境下進行關鍵字搜索的概念，第一次實現(xiàn)了對稱的可搜索加密.但該方案沒有提出具體的安全模型，隱含的采用了IND-CPA的安全模型.直觀上理解，IND-CPA要求密文不泄露明文的任何信息.然而，在可搜索加密機制中，信息的泄露大都是通過搜索陷門和搜索操作產生的，因此，IND-CPA不適合作為可搜索加密的安全模型.Song等人[1]將文件看成由等長關鍵字組成的，用對稱算法加密每個單詞.使用流密碼計算掩碼，生成最后密文.搜索時，云服務器對整個密文進行掃描，依次對進行匹配搜索.缺點是該方案的搜索效率很低，時間復雜度和每篇文檔的單詞數(shù)量呈線性關系.為提高搜索效率，Goh[18]提出了安全索引的概念，并將其應用到可搜索加密方案中.在查詢的過程中，服務器只對索引進行搜索，而不需要直接在數(shù)據(jù)密文中進行操作.

在安全性方面，Goh[18]提出了IND-CKA(semantic security against adaptive chose keyword attack)的安全模型，并基于安全索引提出了Z-INX方案，該方案利用布隆過濾器為每個文件建立一個索引.搜索時無需掃描全文，只要在建立的索引上進行匹配即可，因此，搜索復雜度降低為O(n)(n為文件的個數(shù)).然而，布隆過濾器的使用引入了誤報的問題，使得服務器返回的結果不精確.Chang和Mitzenmacher[19]提出了第一個確定性的可搜索加密方案，該方案利用本地存儲的數(shù)據(jù)字典為每個文件建立一個正向索引.每個文件索引的大小為數(shù)據(jù)字典的大小，用來表示該文件是否包含字典中對應的關鍵字.為了克服布隆過濾器帶來的誤報問題，文獻[19]引入關鍵字字典的概念.用戶為每個文件建立一個字典大小的索引，用來表明該文件包含哪些關鍵字.該方案實現(xiàn)了精確查詢，不存在誤報、錯報的情況.倒排索引(inverted index)，也常被稱為反向索引，被用來存儲在全文搜索下某個關鍵字在一個或多個文檔中的映射.通過倒排索引，可以快速的獲取包含這個關鍵字的文檔列表.Curtmola等人[6]將Trapdoor的安全性以及查詢泄露的2個關鍵字是否一樣的信息這2方面同時包含在新的安全模型中，從而針對SSE提出了“適應性安全性”(adaptive security)和“非適應性安全性”(non-adaptive security)兩個新的安全模型.這2個安全模型作為經典的安全模型，之后的工作或是直接使用或是為了設計方案需要，將其稍加修改.

同時，Curtmola等人[6]提出了一個適應性安全的SSE方案，它是目前為止唯一一個符合adaptive security安全模型的方案.適應性SSE方案的設計難度在于，方案證明階段，模擬者需要以一種模棱兩可的方式模擬出文件的索引，即使在沒有得到敵手提出詢問之前.也就是說，在敵手適應性地提出查詢詢問后，模擬者之前為文件建立的索引需要正確的反應出關鍵字和文件之間的關系.Kurosawa等人[20]將MAC添加到索引中，提出了可驗證的可搜索方案，防止服務器的惡意攻擊.通過將MAC值的產生使用文件標示而不使用文件密文，使得方案能夠實現(xiàn)文件的動態(tài)更新，并在UC通用組合模型下證明其安全性.

2016年，Bost等人[21]進一步提出了具有前向安全性的可搜索加密方案.然而，現(xiàn)有的可搜索加密方案，一般來說其保存的密文或索引都會造成不同程度的信息泄露，如每個文件或者數(shù)據(jù)庫所包含的關鍵詞的數(shù)量，文件的長度，文件的數(shù)量，文件的ID或文件的相似性等.因此，設計可搜索加密方案的安全模型，使得無論是陷門還是索引都不泄露有關搜索關鍵詞的任何信息，是我們今后的研究方向之一.

上述方案在設計時僅僅考慮了單用戶模式.在多用戶模式方面，Curtmola等人[6]結合SSE方案和廣播加密方案提出了一個多用戶可搜索方案，數(shù)據(jù)的擁有者動態(tài)的管理搜索憑證接收者的權限.Bao等人[22]在“Private query on encrypted data in multi-user settings”一文中引入了一個可信第三方，即用戶管理者，對搜索憑證接收者進行管理.2016年Sun等人[23]提出了支持布爾查詢的非交互多用戶可搜索加密方案.2017年Rompay等人[24]提出了一個能抵抗泄露攻擊的多用戶可搜索加密方案.

1.3可搜索加密的表達能力

由于支持單詞的SSE機制只允許用戶一次只能發(fā)送一個單詞的搜索憑證，這極不符合現(xiàn)實生活中多詞搜索的應用需求，特別是當單詞無法精確定位到用戶所想要的文件時，單詞搜索的限制可能需要用戶使用不同關鍵字多輪搜索，或者是經過一輪密文搜索后，對返回結果解密，通過在明文上進行搜索來尋找目標文件，而這樣的結果將給用戶帶來極差的操作體驗.針對這些不足，支持連接關鍵字搜索的可搜索加密機制開始得到研究者廣泛的關注和研究.Shen,Shi和Waters[25]提出了基于謂詞的對稱加密方案，此方案可以作為設計可搜索對稱加密方案的子模塊.雖然該方案不是專門為可搜索加密設計的，但是我們可以將其看成可搜索對稱加密的一個通用形式.該方案同時提出了一個基于謂詞加密的安全模型，鑒于其作為可搜索對稱加密的通用形式，其安全模型也較文獻[6]更具一般性.

Golle等人[4]針對之前的搜索機制中只能使用單詞搜索的不足，提出了2種支持連接關鍵字搜索的SSE方案.在他們的方案中，每個文件都有固定的數(shù)量的關鍵字域，每個域中都有特定的關鍵字來表征這些文件的特性.第1個方案能夠達到固定的在線網絡開銷，第2個方案使用固定網絡開銷的搜索憑證，但是依然與關鍵字域數(shù)量線性相關.

由于之前求關鍵字交集的工作時間復雜度都是線性的，Cash等人[26]提出了一個提供布爾查詢的SSE方案.該方案使用了檢索詞頻率的思想，設計了一個搜索時間復雜度為對數(shù)關系的方案，提高了搜索效率.在加密數(shù)據(jù)庫方面，Popa等人[27]構造了適合XML數(shù)據(jù)類型的可搜索加密協(xié)議.

2007年Boneh等人[28]提出了加密數(shù)據(jù)上連接關鍵字搜索、子集搜索與區(qū)間搜索.如圖6所示，該方案允許用戶對關鍵詞賦值位于特定區(qū)間密文文件進行查詢.2016年Li等人[29-37]引入了相關相似度值和首選項的概念，利用超遞增數(shù)列等技術，構造了一系列實現(xiàn)“AND”，“OR”，“NOT”等多功能關鍵字的可搜索加密方案.與此同時，2016年Wan等人[38-39]進一步在多關鍵字可搜索加密的細粒度密文訪問控制與搜索結果正確性可驗證等方面取得了一些重要成果.

Fig. 6 Searchable encryption supporting range query圖6 支持區(qū)間搜索的可搜索加密

屬性基的可搜索加密能實現(xiàn)豐富的表達能力，但應同時考慮效率的問題時，主要存在于表達能力、通信效率、計算效率、屬性特性4方面的優(yōu)化與折中.表達能力直接影響著可搜索能力，在具體應用當中，表達能力越強，則屬性基加密的可搜索能力也越強.在實際應用中，通信效率主要由密文長度決定，而計算效率主要由加解密算法產生的計算開銷決定.由于加解密是“一對多”的關系，在系統(tǒng)中解密對于加密而言是一個高頻行為.另一方面，目前絕大多數(shù)屬性基加密方案都基于橢圓曲線的雙線性群，解密計算中往往都存在雙線性配對計算，雙線性配對計算在實現(xiàn)效率方面要遠遠低于方案所需的其他類型運算(如指數(shù)運算).在傳統(tǒng)構造中，密文長度和解密代價往往都與相關屬性個數(shù)線性相關，當密文中涉及很多屬性時，效率將會變得很低.

根據(jù)屬性的“容量”大小的分類，屬性基加密方案一般可分為2類：支持小屬性集合的方案和支持大屬性集合的方案.支持小屬性集合的方案中的所有屬性在公共參數(shù)建立時已經確定好，不能額外再加入更多的屬性，除非系統(tǒng)進行重構.相反，支持大屬性集合的方案不必對所有屬性進行初始化，可以隨時加入新的屬性.相比而言，支持大屬性集合的方案更加高效，也更貼近實際應用，但其構造的難度也更大.因此，研究支持大屬性集合的屬性基加密是未來發(fā)展的一個趨勢，對于屬性基加密的實際應用有著重要的推動作用.

另外，從屬性是否可重用的角度考慮，屬性基加密方案通常可分為屬性可重用和不可重用2類方案.通常的屬性基加密方案限制每個屬性在訪問結構中至多出現(xiàn)一次.如果需要出現(xiàn)多次，則通常將一個屬性用多個“屬性”來表示，但這樣會導致效率變低.這也是影響屬性基加密效率的一個因素.因此，研究屬性的可重用性，對于屬性基加密的高效實現(xiàn)有著重要的促進作用.

Fig. 7 Searchable encryption supporting fuzzy query圖7 支持模糊關鍵字搜索的可搜索加密

支持精確匹配的單關鍵字可搜索加密會泄露用戶的訪問模式.2007年Boneh等人[28]提出的改進方案中隱藏了用戶的訪問模式，但卻需要更大的查詢消耗.之后，為了解決陷門的安全傳輸問題，Dong等人[40]提出了d-PEKS方案.為應對離線消息恢復攻擊，Tang等人[41]提出了注冊關鍵詞的可搜索(r -PEKS)方案.另外，精確查詢意味著只返回完全匹配所查詢關鍵字的文件.但是，輸入錯誤和格式問題是很常見的，這時如果是支持精確查詢的方案就不能返回正確的結果，基于這種應用場景，Li等人[42]首次提出了支持模糊查詢的方案.如圖7所示，該方案中使用通配符和編輯距離進行匹配，服務器能夠返回與所查關鍵詞相似的結果，但是卻需要更大的存儲空間和計算時間，但是云計算龐大的存儲能力和計算能力是可以容忍的，Kamara等人[43]也對此作了研究，但這類方案依然處于初級階段，有待進一步完善.2017年Yang等人[44]提出了一個支持通配符關鍵字查詢的可搜索加密方案.該方案支持每個查詢關鍵字中包含零個、一個或兩個通配符的多關鍵字查詢與靈活的用戶授權與撤銷，僅需一個搜索令牌便可實現(xiàn)對多個數(shù)據(jù)擁有者的加密文件進行批查詢.Sahai和Waters[45]提出模糊身份加密方案時，只實現(xiàn)了最簡單的訪問表達能力——僅要求身份的交集達到給定的閾值，就將原先身份的匹配關系由原來的“完全匹配”變?yōu)椤跋嗨破ヅ洹保试S存在一些小的誤差.Cheung和Newport[46]在標準模型和標準假設(BDBH假設)下給出了一個可證明安全的方案，但是訪問結構只能支持與門.文獻[46]以訪問策略的表達能力(只支持一個AND關系)為代價、文獻[47]以部分表達能力(有界的訪問策略)和部分性能(較大的密文長度)為代價來設計了可證明安全的密文策略屬性基加密(CP-ABE)系統(tǒng).Emura等人[48]給出了一個常量密文的CP-ABE系統(tǒng)，但該系統(tǒng)的訪問策略只能支持單一的AND關系.Herranz等人[49]則在訪問策略的表達能力方面前進了一步，給出了能夠支持門限策略的常量密文策略屬性基加密系統(tǒng).Lewko等人[50]和Okamoto等人[51]分別給出了屬性個數(shù)完全不受限制的屬性基加密方案，但這2個方案的效率不高且證明相對復雜.Rouselakis和Waters[52]給出了支持大屬性集合的ABE方案，并利用“編程和取消”(program and cancel)證明技術和“q類”(q-type)困難問題假設對其方案給出了選擇性安全性的證明.Green等人[53]結合云計算模型，允許用戶提供給云服務器一個轉換密鑰，允許云服務器轉換成滿足用戶屬性的ElGamal型密文；而云服務器在此過程中并不能讀取用戶的明文.Lewko等人[54]首次在適應性模型下給出了支持屬性在訪問結構中重復出現(xiàn)任意多次的屬性基加密方案.2013年Hohenberger和Waters[55]通過雙線性群上的數(shù)學性質，將一些經典的屬性基加密方案中的解密所需雙線性運算次數(shù)都減小為常數(shù).考慮到屬性基加密在資源受限移動設備上的應用，Hohenberger等人[56]提出了高效的在線/離線屬性基加密方案.Boneh等人[57]給出了基于格和全密鑰同態(tài)加密(fully key-homomorphic encryption)的具有短密鑰的(密鑰策略)屬性基加密系統(tǒng).Yamada等人[58]給出了支持任意個屬性集合和訪問結構的緊湊參數(shù)(compact parameters)的非單調的CP-ABE.短密文屬性基加密的構造，往往會導致弱的安全性——選擇安全性或者需要參數(shù)化的假設.

在屬性基(身份基)加密的可搜索方案方面，Boneh等人[59]針對隱私搜索問題，提出了函數(shù)隱私的身份基加密方案.Zheng等人[60]分別基于KP-ABE及CP-ABE給出了2個可搜索屬性基加密(ABEKS)的方案.這2個方案不僅實現(xiàn)了關鍵字檢索，還實現(xiàn)了驗證服務器端對于用戶給出檢索查詢是否正確回應.隨后Sun等人[61]和Shi等人[62]也分別提出了支持用戶撤銷和支持一定條件下關鍵字組合查詢的方案的ABEKS方案.后來Khader[63]對ABEKS的模型進行了概括，并且定義了5個常規(guī)的參與者(一個中央權威中心、服務器、加密者、檢索者、多個次級權威中心)以及他們各自負責的操作，同時對這種ABEKS的安全性進行了探討.2016年Sun等人[64]進一步提出了具有外包搜索結果正確性可驗證功能的屬性基可搜索加密方案，同時實現(xiàn)了用戶自適應授權查詢與訪問控制機制.同年，我們[65]提出了一種新的密碼學原語：在線/離線密文策略的屬性基可搜索加密(OO-CP-ABSE)，通過利用現(xiàn)有的在線/離線屬性加密技術和屬性基加密的外包解密技術，構造出高效的OO-CP-ABSE方案，使得數(shù)據(jù)擁有者端的在線計算代價最小化，同時使得數(shù)據(jù)用戶端的解密計算代價最低；還給出了在云計算環(huán)境下，OO-CP-ABSE方案在移動設備上的應用.2017年Hu等人[66]在云計算系統(tǒng)中提出了一個支持動態(tài)可搜索的屬性基可搜索加密方案.最近，我們*王海江, 董曉蕾, 曹珍富. 具有快速關鍵字查詢功能的多值獨立的密文策略屬性基加密方案[J]. IEEE Trans on Service Computing, 2017. DOI:10.1109/TSC.2017.2753231. 待發(fā)表.提出了一個高效的、具有多值獨立關鍵字搜索能力的的密文策略屬性基可搜索加密方案.

然而，從當前國內外的研究現(xiàn)狀來看，雖然當前屬性基加密在表達能力、通信效率、計算效率以及屬性特征方面受到了學術界廣泛的研究，并越來越靠近實際應用，但距離資源受限的網絡實際應用還有一定的距離.鑒于屬性基密碼體制在安全可搜索當中的重要作用以及可預見的應用前景，因此，將屬性基密碼的安全可搜索、加密數(shù)據(jù)共享等理念應用于實際網絡環(huán)境當中將是安全搜索與隱私保護的一個必然趨勢，也是研究熱點之一.

1.4可搜索加密的效率

在實際應用中，用戶的數(shù)據(jù)可能需要增加、刪除或修改，這就要求可搜索加密方案支持這方面的需求，但是以上方案都是在用戶數(shù)據(jù)是靜態(tài)環(huán)境下設計的，不能滿足動態(tài)修改的要求.Kamara等人[43]提出了動態(tài)環(huán)境下的可搜索對稱加密方案.方案中，數(shù)據(jù)的加密以一種類似于同態(tài)加密的方法加密數(shù)據(jù)，索引的動態(tài)修改通過Trapdoor進行修改.2016年Xia等人[21,67-72]進一步在動態(tài)環(huán)境下提出了支持分級多關鍵字搜索的密文數(shù)據(jù)安全可搜索加密方案.索引是一個基于平衡二叉樹的樹形索引，搜索時進行深度搜索，具有較高的搜索效率.因為數(shù)據(jù)和索引的動態(tài)修改需要服務器的參與，服務器在動態(tài)修改的過程中，不可避免地會獲取一定的泄露信息.因此，在安全性要求方面要弱于靜態(tài)環(huán)境下的方案.Hahn和Kerschbaum[73]給出一種“懶”的索引建立方法：凡是第一次詢問的關鍵字，其索引使用全文掃描的方法建立；而之前詢問過的關鍵字在原有的索引上更新即可.隨后，Kamara和Papamanthou[74]利用多核結構構造了可并行計算的可搜索加密方案.Kurosawa等人[75]將索引中MAC值直接作用在密文上，使得文件的更新開銷很大.

大多數(shù)的可搜索對稱加密方案假設服務器在密文上進行全文掃描或者直接在索引上進行匹配.Chase和Kamara等人[76]特別研究了具有結構化的數(shù)據(jù)(矩陣、帶標簽的數(shù)據(jù)、圖、樹、帶標簽的圖)的可搜索加密體制，并且將其應用在泄露控制方案中.Wen等人[77]在新興智能電網市場拍賣應用場景中給出了相應的可搜索加密解決方案.Yang等人[78]針對云計算應用場景給出了文件更新代價為常數(shù)的動態(tài)可搜索對稱加密方案.Liu等人[79]研究了可搜索加密中模式搜索泄露攻擊以及相應的解決方案.Arriaga等人[80]研究了非對稱可搜索加密中的陷門隱私問題.Naveed等人[81]通過引入一個新的密碼原語盲化存儲(blind storage)構造了一種動態(tài)可搜索加密方案.隨后，Emura等人[82]給出了適應性安全的可搜索加密的通用構造.Hahn等人[83]基于訪問模式的索引學習提出了可搜索對稱加密機制，該機制并支持了數(shù)據(jù)的高效更新.B?sch等人[84]利用關鍵字字典的概念構造出一個高效的基于內積加密的可搜索方案.Ibraimi等人[85]針對惡意郵件的攔截問題，提出了授權關鍵字搜索的概念，即網關能夠生成由病毒作為關鍵字的陷門，從而可以對惡意郵件進行攔截.Sedghi等人[86]提出了帶通配符的搜索方案.Dong等人[87]基于RSA問題，提出了代理重加密搜索方案，方案需要一個可信第三方存在作為密鑰管理方.云服務器可以將一個用戶的數(shù)據(jù)密文通過代理重加密轉換成另一用戶的數(shù)據(jù)密文，這樣可以實現(xiàn)用戶的數(shù)據(jù)分享，同時，每個用戶只需保有自己密鑰而不用共享密鑰.Kuzu等人[88]利用最小鄰近Hash函數(shù)和Bloom過濾器提出了一個高效的模糊關鍵字可搜索加密方案.2016年Krishna等人[89]在此基礎上進一步提出了隱私保護的多關鍵字分級模糊可搜索加密方案.

現(xiàn)有的隱私保護模式匹配協(xié)議多利用公鑰(全)同態(tài)加密技術實現(xiàn)[90]，其巨大的計算開銷無法適應移動設備存儲、計算資源受限的客觀需求.為了解決上述問題，我們[91]不依賴于公鑰全同態(tài)加密技術，基于任意單向陷門置換提出了高效的隱私保護外包模式匹配協(xié)議.該協(xié)議將外包模式匹配轉化為外包多項式乘法與卷積運算，利用一次任意單向陷門置換在離線狀態(tài)加密對稱密鑰，再用該對稱密鑰在在線狀態(tài)下，通過僅包含簡單加法、乘法運算的對稱全同態(tài)映射對文本與模板中的每一個字符進行批加密；使得公鑰加密在文本發(fā)送端與模板查詢端的計算開銷分別由O(n)和O(m)降低到O(1).然后，處于半可信或惡意模型下的云服務器在密文域上進行隱私保護的多項式運算，即完成外包模式匹配工作.在隱私保護模式匹配的基礎上，我們還進一步提出了隱私保護的外包醫(yī)療圖像特征提取與匹配算法[92]，實現(xiàn)了安全智慧診療系統(tǒng).

2 存在問題與未來研究方向

安全搜索領域的國內外學者，在一對一、多對一、一對多和多對多4種模式下，分別針對可搜索加密的安全性、搜索的表達能力和搜索效率等重要關鍵性問題進行研究，產生了一系列重要研究結果.但仍存在以下問題值得進一步研究.

1) 在可搜索加密的基礎理論研究方面，可搜索加密是近年來發(fā)展起來的一種支持用戶在密文上進行關鍵字查找的密碼學原語，它能夠為用戶節(jié)省大量的網絡和計算開銷，并充分利用云端服務器龐大的計算資源進行密文上的關鍵字查找.因此，可搜索加密機制的基礎理論研究主要集中在研究密文搜索語句的表達能力、可搜索加密方案的安全性、可搜索加密方案的高效性等方面.

① 研究密文搜索語句的表達能力.靈活的密文搜索語句不僅能夠讓用戶可以更加精確地定位到所需要的加密數(shù)據(jù)文件，同時也可以讓用戶能夠更加靈活地表述搜索需求.本項目致力于密文搜索能力的復雜性的探索，研究支持模糊搜索、有序搜索、區(qū)間搜索以及子集搜索等復雜性密文可搜索能力.

② 研究可搜索加密方案的安全性.針對不同需求，結合可搜索方案的不同表達能力，定義不同可搜索加密方案的安全級別.在不同安全級別的基礎上，尋求簡單高效的難題假設證明可搜索加密方案的安全性.

③ 研究可搜索加密方案的高效性.研究可搜索加密方案的搜索憑證、搜索關鍵字與密鑰、密文間的關系，探索用越短的密鑰、密文來實現(xiàn)表達能力越豐富的可搜索加密方案.進一步地，結合不同的需求和安全級別，探索高效安全的可搜索加密.

在利用屬性基加密實現(xiàn)安全搜索方面，在屬性基加密從理論走向實際應用的過程中，效率是一個主要因素.研究屬性基加密以及簽名的安全搜索與隱私保護的一般理論，主要集中在屬性基加密以及簽名的高效性上，包括表達能力、通信效率、計算效率以及屬性特征等方面.

④ 尋求表達能力豐富的屬性基加密方案.屬性基密碼最重要的特色就是具有豐富的表達能力，而表達能力的強弱也直接反映了可搜索能力的強弱.因此，尋求滿足更豐富表達能力的能夠支持任意語言的屬性基加密方案，是研究屬性基密碼的可搜索機制的一個重要內容，也是高效可搜索的基石.

⑤ 尋求更短密文、短密鑰、短公開參數(shù)的屬性基加密方案.在同等安全性假設的基礎上，短密文是密碼方案設計中第一追求的目標.要構造高效的屬性基加密方案，最關鍵的科學問題就是縮短密文的長短.尋求能夠滿足更短密文(密文長度為常數(shù))、更短密鑰(私鑰長度為常數(shù))以及更短公開參數(shù)(公開參數(shù)為常數(shù))以及同時滿足以上3個特點的高效屬性基加解密算法，是基于屬性可搜索機制的高效性的重要保證.

⑥ 尋求高效的解密方案及加密數(shù)據(jù)外包計算方案.配對計算會消耗很多時間，減少配對的使用次數(shù)會提高加密解密的工作效率，尋求快速解密功能的屬性基密碼方案，尤其是配對次數(shù)與屬性數(shù)目相獨立的解密方案；或者是探尋無配對的屬性基密碼方案；提出高效的加密數(shù)據(jù)外包計算方案.

⑦ 尋求簡單的難題假設.假設的簡單與否，也是影響屬性基加密效率的一個因素.在同等安全級別的條件下，尋求越簡單的難題假設，勢必會使屬性基加密在安全可搜索的應用方面起到非常大的促進作用.

⑧ 基于屬性的隱私保護.屬性基加密提供了共享解密權限的機制，本身是對解密者的一種隱私保護.進一步地，研究匿名屬性基加密，以期提高屬性和加密策略的隱私性.

此外，利用格等經典結構，設計抗量子攻擊的可搜索加密方案.鑒于格上困難問題可以抵抗量子攻擊的特性來設計抗量子攻擊的可搜索加密方案.首先構建出可搜索加密方案的基本框架，其次，將方案的安全性歸約到格上的困難問題，確定可以保證格上問題困難性的的相關參數(shù)范圍，將該參數(shù)范圍對應到加密方案中，確定方案中應選取的相關參數(shù).為此我們需要研究可搜索加密方案構造與格結構之間的關系及格上的困難問題的困難性.借助于格上的困難問題，設計出可以抵抗量子攻擊的可搜索加密方案，在保證安全性的條件下，對方案的效率進行分析優(yōu)化，對其性能進行擴展，使得方案滿足一定的魯棒性、實用性.

2) 在安全搜索與隱私保護的基礎理論研究的基礎上，探索安全搜索與隱私保護的一般規(guī)律與方法，并在此基礎之上進行方案的輕量化研究，并探索在安全搜索與隱私保護的過程中一次使用有關的公鑰加密方案，以期適用于存儲、計算資源受限網絡環(huán)境.

① 探索可搜索加密輕量化方法.可搜索加密作為安全搜索的一個基礎理論與必要工具，在保證搜索語句的表達能力與可搜索加密方案達到一定安全級別的前提下，結合實際網絡環(huán)境的應用需求，對可搜索加密方案進行輕量化.由于在實際網絡中資源受到限制，而普通的可搜索加密方案要求較大的計算能力及傳輸能力，因此無法直接應用.相應地，我們需要將可搜索加密方案進行輕量化處理，降低其計算復雜度和傳輸復雜度.研究支持模糊搜索、有序搜索、區(qū)間搜索以及子集搜索等復雜性可搜索能力的輕量化處理方法，探尋滿足不同安全級別可搜索加密方案的輕量化方法，以期滿足各類網絡環(huán)境的不同需求.

② 探索屬性基加密實現(xiàn)安全搜索的輕量化和高效實現(xiàn)方法.屬性基加密作為安全搜索與隱私保護的一種基本工具與方法，無論是現(xiàn)有的屬性基加密方案還是屬性基簽名方案或屬性基安全協(xié)議，都還遠遠不夠高效，無法為實際所用.特別對于資源受限的網絡設備而言，加密系統(tǒng)的效率尤為重要.故在研究基于屬性基加密以及簽名的安全搜索與隱私保護的一般理論的基礎之上，需要對其進行優(yōu)化，以期能夠進一步提高效率，包括表達能力更加豐富、更短密文密鑰以及公開參數(shù)、加解密配對次數(shù)越少、難題假設越簡單等方面.

對于那些經過優(yōu)化還未能達到應用于資源受限的網絡設備的方案與協(xié)議，采取輕量化的方法，允許存在一次或多次輕量化方法，將原來資源與開銷較大的計算進行輕量化，以期能夠用于資源受限的網絡設備.同時，在保證高效輕量化的基礎上，探索減少輕量化屬性基加密的使用次數(shù)的途徑或方法.

3) 在研究安全搜索與隱私保護的基礎理論、探索安全搜索與隱私保護的新方法與新技術的基礎上，針對各類新興網絡環(huán)境的不同應用場景，研究安全搜索與隱私保護的具體實施方案，減少大開銷運算的使用，期待大開銷達到“少量計算，多次使用”的目的，使其更適合在資源受限的網絡中部署.主要存在網絡應用中的2個關鍵問題值得進一步研究：

① 傳感存儲服務中的動態(tài)安全搜索技術.移動網絡環(huán)境下的傳感信息呈現(xiàn)動態(tài)性、實時性、大規(guī)模等特點，我們擬從保護數(shù)據(jù)安全和用戶隱私出發(fā)，探尋在傳感存儲系統(tǒng)中的動態(tài)可搜索加密方案.

② 現(xiàn)代物流系統(tǒng)中隱私保護的動態(tài)查詢技術.現(xiàn)有的物流系統(tǒng)中，寄件人和收件人的信息都會顯示在郵寄單上，用戶的數(shù)據(jù)安全和用戶隱私受到了極大的威脅.同時，郵件單上的信息是靜態(tài)的，而物品的位置是實時變化的，因此無法直接應用于移動設備中.在移動網絡環(huán)境下的物流系統(tǒng)中，在保證傳統(tǒng)物流數(shù)據(jù)安全與隱私保護的基礎上，著重解決物流地址的實時變化以及位置隱私保護問題.同時，使用可搜索加密技術對物流傳感信息提供實時查詢追蹤等服務.

3 結束語

本文圍繞可搜索加密的新理論、新方法和新技術，針對可搜索加密的模式、安全性、表達能力和搜索效率等方面進行綜述.主要內容包括：安全搜索必不可少的新理論，包括可搜索加密、屬性基加密及其輕量化等相關理論；基于輕量化公鑰密碼算法，并在此基礎上研究減少公鑰密碼算法的使用次數(shù)實現(xiàn)資源受限網絡安全搜索新方法；針對體域網、車載網、智能電網等具體網絡應用服務，介紹新理論、新方法的應用，期望找到一些高效解決這類問題的具體方法.最后，還指出了該領域當前研究中需要解決的公開問題和未來的發(fā)展趨勢.

我們長期以來的一個觀點是：不管是安全搜索還是其他安全或隱私保護問題，如果頻繁使用開銷極大的公鑰加密，其意義最多只是提供了一個“從無到有”的思路.一個方案要付諸實踐，在不得不使用公鑰密碼算法時，必須研究減少公鑰密碼的使用次數(shù).

[1] Song Xiaodong, Wagner D, Perrig A. Practical techniques for searches on encrypted data[C] //Proc of IEEE Symp on Security and Privacy 2000. Piscataway, NJ: IEEE, 2000: 44-55

[2] Boneh D, Kushilevitz E, Ostrovsky R. Public Key encryption with keyword search[G] //LNCS 3027: Proc of Eurocrypt 2004. Berlin: Springer, 2004: 506-522

[3] Waters B, Balfanz D, Durfee G. Building an encrypted and searchable audit log[C] //Proc of NDSS 2004. Berlin: Springer, 2004: 5-6

[4] Golle P, Staddon J, Waters B. Secure conjunctive keyword search over encrypted data[C] //Proc of ACNS 2004. Berlin: Springer, 2004: 31-45

[5] Park D J, Kim K, Lee P J. Public key encryption with conjunctive field keyword search[J]. Information Security Applications, 2005, 3325: 73-86

[6] Curtmola R, Garay J A, Kamara S, et al. Searchable symmetric encryption: Improved definitions and efficient constructions[C] //Proc of ACM CCS 2006. New York: ACM, 2006: 79-88

[7] Wang Peishun, Wang Huaxiong, Pieprzyk J. Threshold privacy preserving keyword searches[G] //Proc of SOFSEM 2008. Berlin: Springer, 2008: 646-658

[8] Park D J, Cha J Y, Lee P J. Searchable keyword-based encryption, 2005/367[R/OL]. IACR ePrint Cryptography Archive, 2005[2017-06-30]. http://eprint.iacr.org/2005/367

[9] Baron J, Defrawy K. E, Minkovich K, et al. R.5pm: Secure pattern matching[C] //Proc of the 8th Int Conf on Security and Cryptography for Networks. New York: ACM, 2012: 222-240

[10] Hazay C, Toft T. Computationally secure pattern matching in the presence of malicious adversaries[C] //Proc of ASIACRYPT 2010. Berlin: Springer, 2010: 195-212

[11] Faust S, Hazay C, Venturi D. Outsourced pattern matching[C] //Proc of Int Colloquium on Automata, Languages, and Programming 2013. Berlin: Springer, 2013: 545-556

[12] Chase M, Shen E. Pattern matching encryption, 2014/638[R/OL]. IACR ePrint Cryptography Archive, 2014 [2017-06-30]. http://eprint.iacr.org/2014/638

[13] Yasuda M, Shimoyama T, Kogure J, et al. Secure pattern matching using somewhat homomorphic encryption[C] //Proc of ACM Workshop on Cloud Computing Security Workshop 2013. New York: ACM, 2013: 65-76

[14] Saha T K, Koshiba T. An enhancement of privacy-preserving wildcards pattern matching[C] //Proc of Int Symp on Foundations and Practice of Security 2016. Berlin: Springer, 2016: 145-160

[15] Chase M, Shen E. Substring-searchable symmetric encryption[J]. Proceedings on Privacy Enhancing Technologies, 2015 (2): 263-281

[16] Strizhov M, Osman Z, Ray I. Substring position search over encrypted cloud data supporting efficient multi-user setup[J]. Future Internet, 2016, 8(3): 1-26

[17] Goldreich O, Ostrovsky R. Software protection and simulation on oblivious RAMs[J]. Journal of the ACM, 1996, 43(3): 431-473

[18] Goh E-J. Secure indexes, 2003/216[R/OL]. IACR ePrint Cryptography Archive, 2003 [2017-06-30]. http://eprint.iacr.org/2003/216, 2013

[19] Chang Yancheng, Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data[C] //Proc of ACNS 2005. Berlin: Springer, 2005: 442-455

[20] Kurosawa K, Ohtaki Y. UC-secure searchable symmetric encryption[C] //Proc of Int Conf on Financial Cryptography and Data Security 2012. New York: ACM, 2012: 285-298

[21] Bost R. ∑ oφoζ: Forward secure searchable encryption[C] //Proc of ACM CCS 2016. New York: ACM, 2016: 1143-1154

[22] Bao Feng, Deng R H, Ding X, et al. Private query on encrypted data in multi-user settings[C] //Proc of Int Conf on Information Security Practice and Experience 2008. Berlin: Springer, 2008: 71-85

[23] Sun Shifeng, Liu J, Sakzad A, et al. An efficient non-interactive multi-client searchable encryption with support for boolean queries[C] //Proc of ESORICS 2016. Berlin: Springer, 2016: 154-172

[24] Rompay V, Cédric R Molva, ?nen M. A leakage-abuse attack against multi-user searchable encryption[J]. Privacy Enhancing Technologies, 2017, 3(2017): 164-174

[25] Shen E, Shi E, Waters B. Predicate privacy in encryption systems[C] //Proc of Theory of Cryptography Conference 2009. Berlin: Springer, 2009: 457-473

[26] Cash D, Jarecki S, Jutla C, et al. Highly-scalable searchable symmetric encryption with support for boolean queries[C] //Proc of CRYPTO 2013. Berlin: Springer, 2013: 353-373

[27] Popa R A, Redfield C, Zeldovich N, et al. CryptDB: Protecting confidentiality with encrypted query processing[C] //Proc of the 23rd ACM Symp on Operating Systems Principles 2011. New York: ACM, 2011: 85-100

[28] Boneh D, Waters B. Conjunctive, subset, and range queries on encrypted data[C] //Proc of Theory of Cryptography Conf 2007. Berlin: Springer, 2007: 535-554

[29] Li Hongwei, Yang Yi, Luan T H, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Trans on Dependable and Secure Computing. 2016, 13(3): 312-325

[30] Chen Rongmao, Mu Yi, Yang Guomin, et al. Dual-server public-key encryption with keyword search for secure cloud storage[J]. IEEE Trans on Information Forensics and Security, 2016, 11(4): 789-798

[31] Chen Rongmao, Mu Yi, Yang Guomin, et al. Server-aided public key encryption with keyword search[J]. IEEE Trans on Information Forensics and Security, 2016, 11(12): 2833-2842

[32] Fu Zhangjie, Ren Kui, Shu Jiangang, et al. Enabling personalized search over encrypted outsourced data with efficiency improvement[J]. IEEE Trans on Parallel and Distributed Systems, 2016, 27(9): 2546-2559

[33] Li Hongwei, Yang Yi, Luan T H, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Trans on Dependable and Secure Computing, 2016, 13(3): 312-325

[34] Fu Zhangjie, Wu Xinle, Guan Chaowen, et al. Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement[J]. IEEE Trans on Information Forensics and Security, 2016, 11(12): 2706-2716

[35] Yang Yang, Ma Maode. Conjunctive keyword search with designated tester and timing enabled proxy re-encryption function for e-health clouds[J]. IEEE Trans on Information Forensics and Security, 2016, 11(4): 746-759

[36] Zhang Wei, Lin Yaping, Xiao Sheng, et al. Privacy preserving ranked multi-keyword search for multiple data owners in cloud computing[J]. IEEE Trans on Computers, 2016, 65(5): 1566-1577

[37] Shao Feng, Zhang Shun, Zhong Hong, et al. Keyword search protocol with privacy preservation using ID-based proxy reencryption[J]. International Journal of Security and Networks, 2016, 11(4): 188-195

[38] Wan Zhiguo, Deng R H. VPSearch: Achieving verifiability for privacy-preserving multi-keyword search over encrypted cloud data[J]. IEEE Trans on Dependable and Secure Computing, 2016, DOI: 10.1109/TDSC.2016.2635128

[39] Liang Kaitai, Huang Xinyi, Guo Fuchun, et al. Privacy-preserving and regular language search over encrypted cloud data[J]. IEEE Trans on Information Forensics and Security, 2016, 11(10): 2365-2376

[40] Dong Changyu, Russello G, Dulay N. Shared and searchable encrypted data for untrusted servers[J]. Journal of Computer Security, 2011, 19(3): 367-397

[41] Tang Qiang, Chen Liqun. Public-key encryption with registered keyword search[C] //Proc of European Public Key Infrastructures Workshop 2009. Berlin: Springer, 2009: 163-178

[42] Li Jin, Wang Qian, Wang Cong, et al. Fuzzy keyword search over encrypted data in cloud computing[C] //Proc of IEEE INFOCOM 2010. Piscataway, NJ: IEEE, 2010: 441-445

[43] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption[C] //Proc of ACM CCS 2012. New York: ACM, 2012: 965-976

[44]Yang Yang, Liu Ximeng, Deng R H, et al. Flexible wildcard searchable encryption system[J]. IEEE Trans on Services Computing, 2017, DOI: 10.1109/TSC.2017.2714669

[45] Sahai A, Waters B. Fuzzy identity-based encryption[C] //Proc of EUROCRYPT 2005. Berlin: Springer, 2005: 457-473

[46] Cheung L, Newport C. Provably secure ciphertext policy ABE[C] //Proc of ACM CCS 2007. Berlin: Springer, 2007: 456-465

[47] Goyal V, Jain A, Pandey O, et al. Bounded ciphertext policy attribute based encryption[C] //Proc of Int Colloquium on Automata, Languages, and Programming 2008. Berlin: Springer, 2008: 579-591

[48] Emura K, Miyaji A, Nomura A, et al. A ciphertext-policy attribute-based encryption scheme with constant ciphertext length[C] //Proc of Int Conf on Information Security Practice and Experience 2009. New York: ACM, 2009: 13-23

[49] Herranz J, Laguillaumie F, Ràfols C. Constant size ciphertexts in threshold attribute-based encryption[C] //Proc of PKC 2010. New York: ACM, 2010: 19-34

[50] Allison B Lewko, Waters B. Unbounded HIBE and attribute-based encryption[C] //Proc of EUROCRYPT 2011. Berlin: Springer, 2011: 547-567

[51] Okamoto T, Takashima K. Fully secure unbounded inner-product and attribute-based encryption[C] //Proc of ACNS 2012. Berlin: Springer, 2012: 349-366

[52] Rouselakis Y, Waters B. Practical constructions and new proof methods for large universe attribute-based encryption[C] //Proc of ACM CCS 2013. New York: ACM, 2013: 463-474

[53] Green M, Hohenberger S, Waters B. Outsourcing the decryption of ABE ciphertexts[C] //Proc of USENIX 2011. New York: ACM, 2011: 34-49

[54] Lewko A, Waters B. New proof methods for attribute-based encryption: Achieving full security through selective techniques[C] //Proc of CRYPTO 2012. Berlin: Springer, 2012: 180-198

[55] Hohenberger S, Waters B. Attribute-based encryption with fast decryption[C] //Proc of PKC 2013. Berlin: Springer, 2013: 162-179

[56] Hohenberger S, Waters B. Online/offline attribute-based encryption[C] //Proc of PKC 2014. Berlin: Springer, 2014: 293-310

[57] Boneh D, Gentry C, Gorbunov S, et al. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[C] //Proc of EUROCRYPT 2014. Berlin: Springer, 2014: 533-556

[58] Yamada S, Attrapadung N, Hanaoka G, et al. A framework and compact constructions for non-monotonic attribute-based encryption[C] //Proc of PKC 2014. Berlin: Springer, 2014: 275-292

[59] Boneh D, Raghunathan A, Segev G. Function-private identity-based encryption: Hiding the function in functional encryption[C] //Proc of CRYPTO 2013. Berlin: Springer, 2013:461-478

[60] Zheng Qingji, Xu Shouhuai, Ateniese G. VABKS: Verifiable attribute-based keyword search over outsourced encrypted data[C] //Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 522-530

[61] Sun Wenhai, Yu Shucheng, Lou Wenjing, et al. Protecting your right: Attribute-based keyword search with fine-grained owner-enforced search authorization in the cloud[C] //Proc of IEEE INFOCOM 2014. Piscataway, NJ: IEEE, 2014: 226-234

[62] Shi Jie, Lai Junzuo, Li Yingjiu, et al. Authorized keyword search on encrypted data[C] //Proc of ESORICS 2014. Berlin: Springer, 2014: 419-435

[63] Khader D. Introduction to attribute based searchable encryption[C] //Proc of Communications and Multimedia Security 2014. Berlin: Springer, 2014: 131-135

[64] Sun Wenhai, Yu Shucheng, Lou Wenjing, et al. Protecting your right: Verifiable attribute-based keyword search with fine-grained owner-enforced search authorization in the cloud[J]. IEEE Trans on Parallel and Distributed Systems, 2016, 27(4): 1187-1198

[65] Chen Dongdong, Cao Zhenfu, Dong Xiaolei. Online/offline ciphertext-policy attribute-based searchable encryption[J]. Journal of Computer Research and Development, 2016, 53(10): 2365-2375 (in Chinese)

(陳冬冬, 曹珍富，董曉蕾. 在線/離線密文策略屬性基可搜索加密[J]. 計算機研究與發(fā)展, 2016, 53(10): 2365-2375)

[66] Hu Baishuang, Liu Qin, Liu Xuhui, et al. DABKS: Dynamic attribute-based keyword search in cloud computing[C] //Proc of IEEE Int Conf on Communications (ICC 2017). Piscataway, NJ: IEEE, 2017: 1-6

[67] Xia Zhihua, Wang Xinhui, Sun Xingming, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Trans on Parallel and Distributed Systems, 2016, 27(2): 340-352

[68] Cui Baojiang, Liu Zheli, Wang Lingyu. Key-aggregate searchable encryption (KASE) for group data sharing via cloud storage[J]. IEEE Trans on Computers, 2016, 65(8): 2374-2385

[69] Wang Qian, He Meiqi, Du Minxin, et al. Searchable encryption over feature-rich data[J]. IEEE Trans on Dependable and Secure Computing, 2016, DOI: 10.1109/TDSC.2016.2593444

[70] Wu Xinle, Fu Zhangjie, Sun Xingming. Text-based searchable encryption in cloud: A survey[J]. Journal of Internet Technology, 2017, 18(1): 207-213

[71] Pouliot D, Wright C V. The shadow nemesis: Inference attacks on efficiently deployable, efficiently searchable encryption[C] //Proc of ACM SIGSAC Conf on Computer and Communications Security 2016. New York: ACM, 2016: 1341-1352

[72] Li Jiguo, Lin Xiaonan, Zhang Yichen, et al. KSF-OABE: Outsourced attribute-based encryption with keyword search function for cloud storage[J]. IEEE Trans on Services Computing, 2016, DOI: 10.1109/TSC.2016.2542813

[73] Hahn F, Kerschbaum F. Searchable encryption with secure and efficient updates[C] //Proc of ACM CCS 2014. New York: ACM, 2014: 310-320

[74] Kamara S, Papamanthou C. Parallel and dynamic searchable symmetric encryption[C] //Proc of Int Conf on Financial Cryptography and Data Security 2013. New York: ACM, 2013: 258-274

[75] Kurosawa K, Ohtaki Y. How to update documents verifiably in searchable symmetric encryption[C] //Proc of Int Conf on Cryptology and Network Security 2013. Berlin: Springer, 2013: 309-328

[76] Chase M, Kamara S. Structured encryption and controlled disclosure[C] //Proc of ACNS 2010. Berlin: Springer, 2010: 577-594

[77] Wen Mi, Lu Rongxing, Lei Jingsheng, et al. Sesa: An efficient searchable encryption scheme for auction in emerging smart grid marketing[J]. Security and Communication Networks, 2014, 7(1): 234-244

[78] Yang Yi, Li Hongwei, Liu Wenchao, et al. Secure dynamic searchable symmetric encryption with constant document update cost[C] //Proc of GLOBECOM 2014. Piscataway, NJ: IEEE, 2014: 775-780

[79] Liu Chang, Zhu Liehuang, Wang Mingzhong, et al. Search pattern leakage in searchable encryption: Attacks and new construction[J]. Information Sciences, 2010, 265: 176-188

[80] Arriaga A, Tang Qiang, Ryan P. Trapdoor privacy in asymmetric searchable encryption schemes[C] //Proc of Int Conf on Cryptology in Africa 2014. Berlin: Springer, 2014: 31-50

[81] Naveed M, Prabhakaran M, Gunter C A. Dynamic searchable encryption via blind storage[C] //Proc of IEEE Symp on Security and Privacy 2014. Piscataway, NJ: IEEE, 2014: 639-654

[82] Emura K, Miyaji A, Rahman M S, et al. Generic constructions of secure-channel free searchable encryption with adaptive security[J]. Security and Communication Networks, 2015, 8(8): 1547-1560

[83] Hahn F, Kerschbaum F. Searchable encryption with secure and efficient updates[C] //Proc of ACM CCS. New York: ACM, 2014: 310-320

[84] B?sch C, Tang Qiang, Hartel P, et al. Selective document retrieval from encrypted database[C] //Proc of Int Conf on Information Security 2012. New York: ACM, 2012: 224-241

[85] Ibraimi L, Nikova S, Hartel P, et al. Public-key encryption with delegated search[C] //Proc of ACNS 2011. Berlin: Springer, 2011: 532-549

[86] Sedghi S, Van L P, Nikova S, et al. Searching keywords with wildcards on encrypted data[C] //Proc of Int Conf on Security and Cryptography for Networks 2010. Berlin: Springer, 2010: 138-153

[87] Dong Changyu, Russello G, Dulay N. Shared and searchable encrypted data for untrusted servers[J]. Journal of Computer Security, 2011, 19(3): 367-397

[88] Kuzu M, Islam M S, Kantarcioglu M. Efficient similarity search over encrypted data[C] //Proc of IEEE ICDE 2012. Piscataway, NJ: IEEE, 2012: 1156-1167

[89] Krishna C R, Mittal S A. Privacy preserving synonym based fuzzy multi-keyword ranked search over encrypted cloud data[C] //Proc of Computing 2016. Berlin: Springer, 2016: 1187-1194

[90] Li Dongmei, Dong Xiaolei, Cao Zhenfu. Secure and privacy-preserving pattern matching in outsourced computing[J]. Security and Communication Networks, 2016, 9(16): 3444-3451

[91] Zhou Jun, Cao Zhenfu, Dong Xiaolei, et al, PPDM: A privacy-preserving protocol for cloud-assisted e-healthcare systems[J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(7): 1332-1344

[92] Zhou Jun, Cao Zhenfu, Dong Xiaolei. PPOPM: More efficient privacy preserving outsourced pattern matching[C] //Proc of ESORICS 2016. Berlin: Springer, 2016: 135-153

ResearchAdvancesonSecureSearchableEncryption

Dong Xiaolei, Zhou Jun, and Cao Zhenfu

(DepartmentofCryptographyandNetworkSecurity,SchoolofComputerScienceandSoftwareEngineering,EastChinaNormalUniversity,Shanghai200062)

With the development of big data and cloud computing, the issue of secure search via the technique of searchable encryption has increasingly been the focus of the researchers in cryptography and network security all over the world. In the light of the new theories, new solutions and new techniques of searchable encryption, this paper presents a survey mainly from the following four aspects: the modes, the security, the expressiveness and the efficiency of secure searchable encryption. It discusses the new theories which are essential to secure search for ubiquitous network, including searchable encryption, attribute-based encryption, and applying these cryptographic mechanisms to obtain the generalized solutions to the theoretical problems of secure search in types of new emerging network services. Based on the aforementioned theoretical results, this paper studies the new approaches to construct practical secure search for these network services, comprising the light-weight public-key cryptographic algorithms, reducing the times of applying the light-weight public-key cryptographic algorithms in secure search, and exploiting any public-key cryptographic algorithm only once to obtain new approaches for secure search in the environment of resource-constrained network applications. We also focus on studying how to apply the new theories and approaches to solve the problems associated to secure search in different kinds of networks, including body area network, wireless vehicular ad hoc network, smart grid and so on. It is traditionally required to apply inefficient public-key cryptographic algorithms a number of times to construct secure search protocols. How to manipulate the public-key cryptographic algorithms and make them suitable to be used in resource-constrained networks becomes the key issue. Light-weighting public-key cryptographic algorithms is certainly a convincing way to address it. On the other hand, minimizing the number (once would be ideal) of applying the light-weighted public-key cryptographic algorithms guarantees more efficient and practical solutions and thus is the key problem to address the issue. Finally, we suggest several interesting open research issues and the trend in the future.

secure search; searchable encryption; lightweight; attribute-based encryption; efficient implementation

TP391

DongXiaolei, born in 1971. PhD, distinguished professor in East China Normal University. Her main research interests include number theory, cryptography and network security, and big data security and privacy preserving.

ZhouJun, born in 1982. PhD, associate professor in East China Normal University. His main research interests include key theories for secure outsourced computation and privacy preserving, and the applied cryptography in big data processing (jzhou@sei.ecnu.edu.cn).

CaoZhenfu, born in 1962. PhD, distinguished professor in East China Normal University. His main research interests include number theory and new theories for cryptography and network security (security and privacy preserving for cloud computing and big data processing).