可搜索加密研究進展綜述

李穎，馬春光

?

可搜索加密研究進展綜述

李穎，馬春光

（哈爾濱工程大學計算機科學與技術學院，黑龍江 哈爾濱 150000）

隨著云計算的迅速發展，為保護用戶外包數據的安全和用戶隱私，越來越多的企業和用戶選擇將數據加密后上傳。因此，對云服務器上加密數據的有效搜索成為用戶關注的重點。可搜索加密技術是允許用戶對密文數據進行檢索的密碼原語，利用云服務器的強大計算資源進行關鍵詞檢索。根據使用密碼體制的不同，介紹了可搜索加密的分類，將其分為對稱可搜索加密和非對稱可搜索加密?；谶@種分類，首先介紹了典型方案，之后從可搜索加密的語句表達能力和安全性2方面進行介紹，并指出了該領域當前研究中急需解決的問題及未來研究方向。

云計算；可搜索加密；對稱可搜索加密；非對稱可搜索加密

1 引言

近年來，隨著網絡的快速發展，大數據時代已然到來，由于人們日常產生的數據越來越多，云存儲技術也隨之興起，如亞馬遜簡易存儲服務以及國內的百度云盤等。但是，隨著該技術的發展，人們發現，當把數據外包到云服務器時，用戶也就無法對數據進行控制，使用戶的隱私安全面臨巨大的挑戰。普遍的解決辦法是數據加密后上傳，但是又會遇到如何在密文上進行查詢的難題，最簡單的方法是將文件下載解密后查詢。這種操作由于下載了不需要的文件而浪費了大量網絡開銷，且進行解密和查詢也浪費了大量計算開銷，這種方法并不適用。由于云服務器具有強大的計算能力，人們希望由服務器進行檢索功能，可以把密鑰發送給云服務器，之后由服務器解密并查詢，但云服務器通常是“誠實且半可信”的，用戶的隱私暴露在云服務器面前，仍然有泄露的風險。

為了解決這類問題，可搜索加密（SE，searchable encryption）技術應運而生。本文對可搜索加密的基本概念進行研究[1]，關注近年來可搜索加密的研究進展，針對現有方法進行分類并對可搜索加密的未來發展進行展望。

2 基本概念

2000年，Song等[1]首次提出了可搜索加密的概念。作為一種新型的密碼原語，可搜索加密技術使用戶具有在密文域上進行關鍵詞搜索的能力。數據以密文方式存儲在云服務器上時，利用云服務器的強大計算能力進行關鍵詞的檢索，而不會向服務器泄露任何用戶的隱私。這不僅僅使用戶的隱私得到了有效保護，而且檢索效率也在服務器的幫助下得到了大幅度提升。

可搜索加密技術的一般過程如圖1所示，主要分為4步。

圖1 可搜索加密過程

1) 文件加密：數據擁有者在本地使用加密密鑰對將要上傳的文件進行加密，并將密文上傳服務器。

2) 陷門生成：經過數據擁有者授權的數據使用者使用密鑰對待查詢的關鍵詞生成陷門，發送給云服務器。

3) 查詢檢索：云服務器對數據使用者提交的陷門和每個上傳文件的索引表進行檢索，返回包含陷門關鍵詞的密文文件。

4) 文件解密：數據使用者使用解密密鑰對云服務器返回的密文文件進行解密。

可搜索加密主要包含對稱可搜索加密（SSE，symmetric searchable encryption）和非對稱可搜索加密（ASE，asymmetric searchable encryption）2種類型，這2種類型來源于不同的現實問題，之后用來解決不同的需求問題。下面對這2類可搜索加密進行詳細講解。

3 對稱可搜索加密

3.1 定義

對于可搜索加密技術的來源，要追溯到不可信賴的服務器存儲問題[2]，即假設用戶Alice希望將文件上傳至云服務器，但是面臨著數據泄露的風險，為了保護用戶的個人隱私，可以選擇將文件加密后上傳。采用傳統的加密算法，當Alice需要查詢云服務器上的某個文件時，需要將所有文件全部下載，解密后檢索，因為只有用戶Alice自己擁有解密的能力，而在密文上是無法進行檢索的。此類問題就需要新型的加密方案：加密后的文件可以執行檢索功能，并在這個過程中不會泄露有關數據的任何明文信息。

定義1 （對稱可搜索加密）[3]定義在字典Δ={W1,W2,…,W}上的對稱可搜索加密算法可描述為五元組。

=(,,,,)

其中

1)=(λ)：λ是安全參數，該算法根據安全參數生成加密密鑰。

2) (,)=(,)：是明文文件集合，=(1,2,…,D),D∈2，該算法生成文件索引密文文件集=(1,2,…,C)，部分方案不需要生成索引。

3)T=(,)：其中，是用戶輸入需要查詢的關鍵詞，該算法生成關鍵詞對應的陷門T。

4)()=(,T)：該算法根據用戶輸入生成的陷門T以及文件的索引進行查找，輸出與輸入關鍵詞匹配的文件集合()。

5)D=(,C)：用生成的密鑰解密返回的密文文件C，生成明文文件D。

對稱可搜索加密通常對關鍵詞首先進行處理，大多數采用偽隨機函數或者散列算法等方法，模糊關鍵詞語義進行隨機化的處理。當用戶進行關鍵詞檢索時，將查詢關鍵詞進行相同處理，與文件的關鍵詞進行相似度匹配，結果滿足某種格式，則說明匹配成功，返回相應的文件。

3.2 SWP方案

2000年，Song等[2]第一次提出了在密文上進行搜索的方案SWP，具體方法如圖2所示。

圖2 SWP可搜索加密機制

具體構造如下。

1)()：數據擁有者生成加密密鑰和以及偽隨機流1,2,…,S（為文件中的單詞塊數目）。

4)()：服務器進行如下計算

雖然該算法可以使服務器不能獲得任何明文信息，但是由于需要掃描全文，使算法效率較低，并且該算法容易收到統計攻擊的威脅。

3.3 對稱可搜索加密語句的表達能力

對于可搜索加密，用戶希望在查詢時可以快速而準確地找到所需的文件，而且能夠清晰準確地描述用戶的搜索條件，這就需要可搜索加密在語句表達能力方面進行深入研究。近幾年，搜索語句表達能力方面的研究主要分為單關鍵詞搜索、多關鍵詞搜索、連接關鍵詞搜索和模糊關鍵詞搜索。

在可搜索加密提出時，單關鍵詞檢索也隨之提出。2000年，Song等[2]提出了SWP方案，但是他們并沒有進行安全性的定義，2006年，Curtmola等[4]則給出了安全性的定義，并給出了2個SSE方案（SSE-1和SSE-2）。2010年，Wang等[5]提出了一個排序對稱可搜索加密的定義，并給出了一個基于現有密碼原語對稱密鑰保序加密技術的有效設計。2012年，Premasathian[6]提出了使用乘法和同時同余的快速搜索加密方案。在這些方案中，任何用戶都可以確定加密文檔中是否存在特定關鍵字。該消息可以通過任何技術加密。在某些方案中可以確定關鍵字的出現次數。

單關鍵詞檢索雖然可以快速檢索，但是準確度不高，不能精確定位文件，多關鍵詞檢索隨之提出。2013年，Premasathian[7]首次提出了多關鍵詞檢索方案，該方案利用連接與門將關鍵詞進行連接，并且該方案對用戶數據和搜索令牌進行隱藏，保證了安全性。2014年，Fu等[8]提出了一種智能語義搜索方案，該方案不僅返回基于關鍵字的精確匹配的結果，而且還返回基于關鍵字的語義匹配的結果。同時，該方案支持搜索結果的可驗證性。2014年，Fu等[9]又提出了一種有效的解決加密云數據支持同義詞查詢的多關鍵詞排序搜索問題。2016年，Xia等[10]提出了一個可以動態進行文件的增刪改查的多關鍵詞檢索方案。2017年，楊旸等[11]首次在可搜索加密技術中引入加權平均分的概念，對文件中不同區域的關鍵詞設置不同的權重表示重要程度，針對MRSE（multi-keyword ranked search over encrypted cloud data）方案的不足，提出了更加高效的多關鍵詞排序檢索方案。

起初對于可搜索加密技術的研究，并未考慮關鍵詞之間布爾組合的情況，這也成為之后阻礙可搜索加密技術發展的一大難題。2013年，Cash等[12]介紹了第一個可搜索的對稱加密（SSE）協議的設計和分析，該協議支持外包對稱加密數據的聯合搜索和一般布爾查詢，并可擴展到超大型數據庫和任意結構化數據，包括自由文本搜索。2016年，Li等[13-18]實現了“AND、OR、NOT”等布爾運算的關鍵字可搜索加密方案。

以上對于關鍵詞檢索的研究全部是基于精確查詢的條件，但當用戶輸入的關鍵詞與文件的關鍵詞存在誤差時，便不能準確查找，降低了搜索準確度。模糊關鍵詞檢索則有效地解決了這個問題。2009年，Bringer等[19]描述了一個用于容錯可搜索加密的新原語及其安全模型。這種通用的方案只允許使用某個關鍵字的近似值對加密數據進行搜索。它能夠有效地查詢安全數據庫，以便通過對其進行精確估計來獲取確切的數據。2010年，Li等[20]利用編輯距離來量化關鍵字相似度并開發構建模糊關鍵字集的高級技術，這大大減少了存儲和表示的開銷。2011年，Chuah等[21]提出了一種基于隱私感知的基于樹的方法來支持模糊多關鍵字特征。2017年，楊旸等[22]提出了基于雙因子排序算法的關鍵詞模糊搜索方案，以漢明距離和相似度分數為依據。2017年，王愷璇等[23]采用敏感散列函數對關鍵詞建立索引，并采用布隆過濾器，實現了多關鍵詞的模糊檢索。

3.4 對稱可搜索加密的安全性

在進行可搜索加密方案的研究時，除了要考慮方案的準確性和效率，還要考慮方案是否安全，為了證明方案的安全性，通常是采用與攻擊模型結合的方法證明。

2000年Song等[2]首次提出可搜索加密時只是要求檢索時不會泄露明文信息，但是文章給出的定義不能抵抗攻擊者的簡單攻擊。2003年，Goh等[24]正式定義了一個安全索引并為針對自適應選擇關鍵字攻擊（IND-CKA, semantic security against adaptive chose keyword attack）的稱為語義安全性的索引制定了安全模型。但是由于方案中使用了布隆過濾器，使查詢結果并不準確。2004年，Chang等[25]描述了可搜索加密技術的基于模擬的安全性定義，考慮了攻擊者可以多次試探服務器的情況，限制了服務器無法獲得除查詢結果之外的任何信息。2006年，Curtmola等[4]提出了“適應性安全性”（adaptive security）和“非適應性安全性”（non-adaptive security）2個新的安全模型，之后的大部分關于安全性的研究大多基于此展開，并提出了目前唯一一個符合adaptive security模型的對稱可搜索加密方案。2012年，Chai等[26]采用可驗證的SSE（VSSE）方案，以提供除數據隱私之外的可驗證的可搜索性，給出了滿足安全性的可搜索加密方案。2015年，柳祚鵬[27]首次提出了同義詞搜索問題，采用同義詞集合，給出了一個可以進行同義詞檢索的方案，滿足non-adaptive安全。2017年，陸海寧[28]提出了一種可以對搜索模式進行隱藏的方案，將關鍵詞進行分組，組內關鍵詞具有相同的搜索陷門，使服務器和敵手無法區分。

對于對稱可搜索加密的安全性的研究，之前一直集中在適應性安全與非適應性安全2方面，利用可信硬件降低安全假設也是未來的研究方向之一。

3.5 小結

根據上文的介紹，可以發現，至今為止對于對稱可搜索加密的研究主要在搜索語句的表達能力和安全性2方面，表1對一些對稱可搜索加密機制的安全性進行了總結。

其中，“外”表示方案抵抗外部攻擊，“內”表示抵抗服務器的內部攻擊。從表1中可以看出，現有的對稱可搜索加密方案雖然搜索語句的表達能力和效率方面存在差異，但基本滿足日常所需的安全要求，對于特定環境下的加密方案，還需要人們針對不同的應用場景進行研究。

4 非對稱可搜索加密

4.1 定義

非對稱可搜索加密（即基于公鑰的可搜索加密）技術的來源可以追溯到不可信賴的服務器路由問題[3]，即Bob希望向Alice發送郵件，需經由郵件服務器，為了保證郵件的隱私性，需要在郵件服務器不知道郵件內容的前提下，可以正確地按照郵件的內容將郵件發送給Alice。

Boneh等[29]首次將可搜索加密技術應用到非對稱密碼學中，提出PEKS（public key encryption with keyword search）概念，算法描述如下。

定義2 （PEKS）[3]非對稱密碼體制下可搜索加密算法可描述為

=(,,,)

1) (,)=()：是安全參數，該算法根據安全參數生成公鑰和私鑰。

2)C=(,)：利用生成的公鑰和加密文件的關鍵詞，生成關鍵詞密文C。

3)T=(,)：利用生成的私鑰和用戶輸入的關鍵詞，生成關鍵詞的陷門T。

4)=(,C,T)：根據生成的公鑰、關鍵詞的陷門T和關鍵詞密文C，計算匹配相似度，輸出判定值∈{0,1}。

對于現有的非對稱可搜索加密技術，構建方法大多基于不同的困難假設，其中大部分基于雙線性對（bilinear pairing），下面進行詳細介紹。

定義3 （雙線性對）[29]對于雙線性映射:1×1→2，需要滿足以下條件。

3)可計算性（computable）：群1，2中的運算以及雙線性映射運算在多項式時間內可解。

定義4 離散Diffie-Hellman問題（DDH）[30]：假設是一個素數階的群，其中，是的生成元，隨機地從{0,…,?1}中選擇元素,,，給定元組(,g,g,g)，判斷g是否等于g。

定義5 雙線性Diffie-Hellman問題（BDH）[31]：對于群及其生成元，給定g,g,g，計算(,)。

由于雙線性對涉及群元素的運算，使非對稱可搜索加密技術的開銷變大，但也正是由于這個特性，使非對稱可搜索加密可以實現復雜的加密技術。而且，在一些相對不安全的網絡中，非對稱可搜索加密技術因為不需要協商密鑰而更加適用，因為數據擁有者可以使用公鑰對文件進行加密，而數據使用者可以使用私鑰進行搜索和解密。

4.2 BDOP-PEKS方案

2004年，Boneh等[29]最早提出PEKS概念，并基于BF-IBE構造了第一個PEKS方案BDOP-PEKS，安全性可歸結為BDH數學假設。具體構造如下。

該方案基于BDH困難假設，使方案的效率極低，并且不能抵抗關鍵詞猜測攻擊。

4.3 非對稱可搜索加密語句的表達能力

對于非對稱可搜索加密語句表達能力的研究，起初只支持精確關鍵詞檢索，之后進行了擴展研究，包括多關鍵詞搜索和模糊關鍵詞搜索。

表1 SSE機制總結

2004年，Boneh等[29]最早提出PEKS概念，并基于BF-IBE構造了第一個PEKS方案BDOP-PEKS，安全性可歸結為BDH數學假設。2005年，Abdalla等[32]提供了一個匿名IBE方案到安全的PEKS方案的變換，給出了一個統計一致的方案。

關于布爾關鍵詞檢索，公鑰可搜索加密也進行了研究。2004年，Golle等[30]提出了一個連接關鍵詞的方案，該方案在文檔數量上是線性的，并且依賴于安全性的決策性Diffie-Hellman（DDH）假設，并且通信成本與關鍵字數量級相關。2005年，Park等[33]給出了一種連接關鍵詞的PECK方案，并提出了基于DBDH假設的方案Park-1和基于DBDHI假設的Park-2方案。2007年，Boneh等[31]提出了允許用戶進行連接關鍵詞檢索、區間檢索以及子集檢索的可搜索加密方案。

針對非對稱可搜索加密單關鍵詞檢索的不足，2005年，Dong等[34]給出了一種可以實現連接關鍵詞搜索的公鑰加密問題的解決方案。2007年，Yong等[35]構造了一個高效的PECK方案，其安全性在隨機預言模型中經過決策線性Diffie-Hellman假設證明。引入了一種稱為多用戶PECK方案的新概念，它可以實現高效的計算和通信開銷，并有效管理服務器中多個用戶的存儲。在2013年，Hu等[36]提出了PEKS擴展的定義，稱為公鑰加密排序多關鍵字搜索（PERMKS），這意味著接收者可以查詢關鍵字的任何子集和數據中出現的查詢關鍵字的數量來評估數據與搜索查詢的相似性排名。在2016年，Miao等[37]設計了一個高效的加密原語，稱為可驗證的多關鍵字搜索，通過加密的云數據獲取動態數據擁有者方案，以保護數據的機密性和完整性。2017年，張楠等[38]提出了一種多關鍵詞公鑰可搜索加密方案，并實現了密文全文檢索系統Bluce。

與對稱可搜索加密技術的研究方向類似，公鑰可搜索加密技術的模糊搜索也已成為研究的重點。2012年，Bringer等[39]利用編輯距離到海明距離的經典嵌入，在查找關鍵關鍵字他和保留查詢機密性的同時，在容許的編輯距離上提供了一些靈活性。在2013年，Dong等[40]提出了一種新的基于模糊關鍵字搜索（IPEFKS）的交互式公鑰加密原語，它支持在公鑰設置中對加密數據進行高效的模糊關鍵字搜索。

4.4 非對稱可搜索加密的安全性

對于早期提出的公鑰可搜索加密技術，之后的研究發現很多存在不同的漏洞，這也使對非對稱可搜索加密安全性的研究成為重點。

文獻[41]首次提出Boneh等[29]的PEKS方案存在嚴重的安全漏洞，這是因為關鍵字的選擇范圍比密碼小得多，用戶通常使用知名關鍵字搜索文檔，這個事實足以引起離線的關鍵字猜測攻擊。通過進一步的研究，Jeong等[42]展示了一個關于構建安全PEKS方案以防止關鍵字猜測攻擊公開問題的負面結果。結果表明，一致性意味著PEKS中的關鍵字猜測攻擊不安全。這意味著，當可能的關鍵字的數量受到某個多項式的限制時，構建安全且一致的PEKS方案來防范關鍵字猜測攻擊是不可能的。

2010年，Tang等[43]提出了一個新的概念，即使用注冊關鍵字搜索（PERKS）的公鑰加密，它需要發件人在發件人為該關鍵字生成標簽之前向接收方注冊關鍵字。證明提出的PERKS語義安全定義不受離線關鍵詞猜測攻擊的影響。2011年，方黎明[44]給出了一個可以抵抗關鍵詞猜測攻擊的公鑰可搜索加密的安全模型。2013年，Xu等[45]使用PEKS的關鍵字隱私增強變體（稱為使用模糊關鍵字搜索（PEFKS）的公鑰加密）來解決關鍵字猜測攻擊問題。在PEFKS中，每個關鍵字對應一個確切的關鍵字搜索陷門和一個模糊關鍵字搜索陷門。2016年，Chen等[46]提出了一個名為雙服務器PEKS（DS-PEKS）的新PEKS框架，又提供了一個基于決策Diffie-Hellman的LH-SPHF一般框架的高效實例，并表明它可以實現對KGA內部的強大安全性。

根據以上的研究發現，關于公鑰可搜索加密機制安全性的研究主要集中在對關鍵詞猜測攻擊的各種抵御方案，之后的研究將主要集中在研究高效的可抵御關鍵詞猜測攻擊的加密方案。

4.5 小結

根據上文的介紹，非對稱可搜索加密方案的區別大多體現在基于的困難假設不同，達到的安全性也不同。對一些基本的公鑰可搜索加密機制的安全性等方面進行總結，具體如表2所示。

其中，IND-CKA表示自適應性選擇關鍵詞攻擊，ROM表示隨機預言機模型，DBDH代表決策雙線性Diffie-Hellman問題，DBDHI代表決策雙線性Diffie-Hellman反演假設。對于非對稱可搜索加密技術，雖然使用的困難假設不同，但其對于安全性的研究主演集中在是否能夠抵抗關鍵詞猜測攻擊和是否需要安全通道兩方面?？沈炞C的公鑰可搜索加密方案仍是待解決的問題，需要人們的深入研究。

5 結束語

本文針對可搜索加密技術的研究現狀進行了介紹，首先對可搜索加密的研究機制進行了介紹，其次從對稱可搜索加密和非對稱可搜索加密2個方面對研究進展進行分析。從上文的討論中可以看出，可搜索加密技術的研究已經逐漸成熟，并在未來的一段時間內，依然被認為是解決云計算安全的研究熱點之一。筆者認為，可搜索加密機制中仍然存在值得深入研究的問題，主要包括如下內容。

1) 靈活高效的查詢語句是可搜索加密技術的未來研究方向之一。現有的可搜索加密方案中，當用戶進行關鍵詞檢索時，仍然需要用戶進行二次檢索，使搜索效率大大降低?，F階段的研究側重多有不同，或側重模糊檢索，或側重條件檢索，不夠完善，包括模糊關鍵詞檢索、關鍵詞排序檢索、多關鍵詞檢索、關鍵詞檢索結果的可驗證性等。

表2 PEKS機制總結

2) 保留語義的可搜索加密技術是未來的研究難點。采用加密技術可以保護用戶的數據安全，但同時也失去了詞語的語義關系，無法在密文上進行關鍵詞檢索。未來需要研究的加密方案是使關鍵詞在加密后仍然具有服務器無法獲得的語義關系，不僅可以實現精確查詢，還可以準確找到用戶所需的文件。

3) 可搜索加密技術的安全性是研究的重點之一。如今，基本的可搜索加密技術已經初具規模，具有廣闊的應用空間，其安全性問題是阻礙可搜索加密技術應用的重要原因，至今仍然有許多可搜索加密技術受到猜測關鍵詞攻擊的潛在威脅。因此，設計一種安全、高效的可搜索加密技術，也是未來的研究方向之一。

[1] 項菲, 劉川意, 方濱興,等. 云計算環境下密文搜索算法的研究[J].通信學報, 2013(7):143-153. XIANG F, LIU C Y, FANG B X, et al. Research on ciphertext search for the cloud environment[J]. Journal on Communications, 2013, 34(7):143-153.

[2] SONG D X, WAGNER D, PERRIG A. Practical techniques for searches on encrypted data[C]// IEEE Computer Society. 2000: 44.

[3] 李經緯, 賈春福, 劉哲理, 等. 可搜索加密技術研究綜述[J]. 軟件學報, 2015, 26(1): 109-128. LI J W, JIA C F, LIU Z L, et al. Survey on the searchable encryption[J]. Journal of Software, 2015,26(1):109-128.

[4] CURTMOLA R, GARAY J, KAMARA S, et al. Searchable symmetric encryption: improved definitions and efficient constructions[C]//ACM Conference on Computer and Communications Security. ACM, 2006:79-88.

[5] WANG C, CAO N, LI J, et al. Secure ranked keyword search over encrypted cloud data[C]//IEEE International Conference on Distributed Computing Systems. 2010:253-262.

[6] PREMASATHIAN N, CHOTO S. Searchable encryption schemes: with multiplication and simultaneous congruences[C]//IEEE International ISC Conference on Information Security and Cryptology. 2013:147-150.

[7] PREMASATHIAN N, CHOTO S. Searchable encryption schemes: with multiplication and simultaneous congruences[C]//International ISC Conference on Information Security and Cryptology. 2013: 147-150.

[8] FU Z, SHU J, SUN X, et al. Smart cloud search services: verifiable keyword-based semantic search over encrypted cloud data[J]. IEEE Transactions on Consumer Electronics, 2014, 60(4):762-770.

[9] FU Z, SUN X, LINGE N, et al. Achieving effective cloud search services: multi-keyword ranked search over encrypted cloud data supporting synonym query[J]. IEEE Transactions on Consumer Electronics, 2014, 60(1):164-172.

[10] XIA Z, WANG X, SUN X, et al. A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(2): 340-352.

[11] 楊旸, 楊書略, 蔡圣暐, 等. 排序可驗證的語義模糊可搜索加密方案[J]. 四川大學學報(工程科學版), 2017, 49(4):119-128. YANG Y, YANG S L, CAI S. Semantically searchable encryption scheme supporting ranking verification[J].Journal of Sichuan University(Engineering Science Edition),2017, 49(4):119-128.

[12] 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: Springer. 2013: 353-373.

[13] LI H, YANG Y, LUAN T, et al. Enabling fine-grained multi-keyword search supporting classified sub-dictionaries over encrypted cloud data[J]. IEEE Transactions on Dependable & Secure Computing, 2016, 13(3):312-325.

[14] 宋衍, 韓臻, 陳棟, 等. 支持關鍵詞任意連接搜索的屬性加密方案[J]. 通信學報, 2016, 37(8):77-85. SONG Y, HAN Z, CHEN D. Attribute-based encryption supporting arbitrary conjunctive key word search[J]. Journal on Communications, 2016, 37(8):77-85.

[15] CHEN R, MU Y, YANG G, et al. Dual-server public-key encryption with keyword search for secure cloud storage[J]. IEEE Transactions on Information Forensics & Security, 2017, 11(4): 789-798.

[16] CHEN R, MU Y, YANG G, et al. Server-aided public key encryption with keyword search[J]. IEEE Transactions on Information Forensics & Security, 2016, 11(12):2833-2842.

[17] FU Z, REN K, SHU J, et al. Enabling personalized search over encrypted outsourced data with efficiency improvement[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(9): 2546-2559.

[18] FU Z, SUN X, JI S, et al. Towards efficient content-aware search over encrypted outsourced data in cloud[C]//IEEE International Conference on Computer Communications, 2016:1-9.

[19] BRINGER J, CHABANNE H, KINDARJI B. Error-tolerant searchable encryption[C]//IEEE International Conference on Communications. 2009:1-6.

[20] LI J, WANG Q, WANG C, et al. Fuzzy keyword search over encrypted data in cloud computing[C]//INFOCOM. 2010. 1-5.

[21] CHUAH M, HU W. Privacy-aware bedtree based solution for fuzzy multi-keyword search over encrypted data[C]// International Conference on Distributed Computing Systems Workshops. IEEE, 2011. 273-281.

[22] 楊旸, 楊書略, 柯閩. 加密云數據下基于Simhash的模糊排序搜索方案[J]. 計算機學報, 2017, 40(2):431-444. YANG Y,YANG S L,KE M. Ranked fuzzy keyword search based on simhash over encrypted cloud data[J]. Chinese Journal of Computers, 2017, 40(2):431-444.

[23] 王愷璇, 李宇溪, 周福才,等. 面向多關鍵字的模糊密文搜索方法[J]. 計算機研究與發展, 2017, 54(2):348-360. WANG K X, LI Y X, ZHOU F C, et al. Multi-keyword fuzzy search over encrypted data[J]. Journal of Computer Research and Development, 2017, 54(2): 348-360.

[24] GOH E J. Secure Indexes[J]. Submission, 2003.

[25] CHANG Y C, MITZENMACHER M. Privacy preserving keyword searches on remote encrypted data[C]//International Conference on Applied Cryptography and Network Security. 2005:442-455.

[26] CHAI Q, GONG G. Verifiable symmetric searchable encryption for semi-honest-but-curious cloud servers[C]//IEEE International Conference on Communications. 2012. 917-922.

[27] 柳祚鵬. 支持同義詞搜索和抗信息泄漏的對稱可搜索加密技術研究[D]. 上海: 上海交通大學,2015. LIU Z P. Research on symmetric searchable encryption technology supporting synonym search and anti-information leak-age[D]. Shanghai: Shanghai Jiaotong University.2015.

[28] 陸海寧. 可隱藏搜索模式的對稱可搜索加密方案[J].信息網絡安全, 2017(01): 38-42. LU H N. Searchable symmetric encryption with hidden search pattern[J]. Netinfo Security,2017(1):38-42.

[29] BONECH D, CRESCENZO G D, OSTROVSKY R, et al. Public key encryption with keyword search[C]// International Conference on the Theory and Applications of Cryptographic Techniques. 2004: 506-522.

[30] GOLLE P, STADDON J, WATERS B. Secure conjunctive keyword search over encrypted data[J]. Lecture Notes in Computer Science, 2004, 3089:31-45.

[31] BONEH D, WATERS B. Conjunctive, subset, and range queries on encrypted data[J]. TCC 2007, 2007, 4392:535--554.

[32] ABDALLA M, BELLARE M, CATALANO D, et al. Searchable encryption revisited: consistency properties, relation to anonymous ibe, and extensions[M]//Advances in Cryptology–CRYPTO 2005. 2005. 205-222.

[33] PARK D, KIM K, LEE P. Public key encryption with conjunctive field keyword search in information security applications[C]//The 5th International Workshop (WISA’04). 2004. 23-25.

[34] DONG J P, KIM K, LEE P J. Public key encryption with conjunctive field keyword search[M]//Information Security Applications. Berlin: Springer. 2004. 73-86.

[35] YONG H H, LEE P J. Public key encryption with conjunctive keyword search and its extension to a multi-user system[C]// International Conference on Pairing-Based Cryptography. 2007. 2-22.

[36] HU C, LIU P. Public key encryption with ranked multi-keyword search[C]//International Conference on Intelligent Networking and Collaborative Systems. 2013. 109-113.

[37] MIAO Y, MA J, LIU X, et al. VMKDO: verifiable multi-keyword search over encrypted cloud data for dynamic data-owner[J]. Peer-to-Peer Networking and Applications, 2016(1):1-11.

[38] 張楠, 陳蘭香. 一種高效的支持排序的關鍵詞可搜索加密系統研究[J]. 信息網絡安全, 2017(2):43-50. ZHANG N, CHEN L X. Research on an efficient ranked keywords searchable encryption system[J].Netinfo Security,2017(2):43-50.

[39] BRINGER J, CHABANNE H. Embedding edit distance to enable private keyword search[J]. Human-centric Computing and Information Sciences, 2012, 2(1):1-12.

[40] DONG Q, GUAN Z, WU L, et al. Fuzzy keyword search over encrypted data in the public key setting[C]// International Conference on Web-Age Information Management. Springer Berlin Heidelberg, 2013, 729-740.

[41] JIN W B, RHEE H S, PARK H A, et al. Off-line keyword guessing attacks on recent keyword search schemes over encrypted data[C]// The Workshop on Secure Data Management. Springer Berlin Heidelberg, 2006:75-83.

[42] JEONG I R, KWON J O, HONG D, et al. Constructing PEKS schemes secure against keyword guessing attacks is possible?[J]. Computer Communications, 2009, 32(2):394-396.

[43] TANG Q, CHEN L. Public-key encryption with registered keyword search[C]//European Conference on Public Key Infrastructures, Services and Applications. Springer-Verlag, 2009. 163-178.

[44] 方黎明. 帶關鍵字搜索公鑰加密的研究[D]. 南京航空航天大學, 2012. FANG L M. Research on keyword encryption with keyword search[D]. Naijing: Nanjing Aerospace University,2012.

[45] 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.

[46] CHEN R, MU Y, YANG G, et al. dual-server public-key encryption with keyword search for secure cloud storage[J]. IEEE Transactions on Information Forensics & Security, 2017, 11(4):789-798.

Overview of searchable encryption research

LI Ying，MA Chunguang

School of Computer Science and Technology, Harbin Engineering University, Harbin 150000, China

With the development of cloud computing, there is an increasing number of companies and individuals outsourcing their data to cloud server in the encrypted form to protect data security and user privacy. As a result, efficient retrieval of encrypted data stored on cloud server has become the issue that users may pay attention to. Searchable encryption (SE) is a cryptographic primitive that supports keyword search over encrypted data, and migrates the cumbersome search operation to the cloud server to utilize its vast computational resources. Reviews previous research according to the different cryptosystems used, and divides SE into two groups, that is symmetric searchable encryption and asymmetric searchable encryption. Based on this classification, first introduces a typical program, and then introduces from the two aspects of the expression of searchable encryption and security.Finally, the need-to-be-solved problems and main research directions are discussed.

cloud computing, searchable encryption, symmetric searchable encryption, asymmetric searchable encryption

TP393

A

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

李穎（1993-），女，黑龍江黑河人，哈爾濱工程大學碩士生，主要研究方向為密碼學可搜索加密技術。

馬春光（1974-），男，黑龍江雙城人，哈爾濱工程大學教授、博士生導師，主要研究方向為分布式密碼算法與協議、云計算安全與隱私、格密碼。

2018-06-10；

2018-07-05

李穎，2472796566@qq.com

國家自然科學基金資助項目（No.61472097）

The National Natural Science Foundation of China(No.61472097)