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

李穎，馬春光

?

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

李穎，馬春光

（哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150000）

隨著云計(jì)算的迅速發(fā)展，為保護(hù)用戶外包數(shù)據(jù)的安全和用戶隱私，越來(lái)越多的企業(yè)和用戶選擇將數(shù)據(jù)加密后上傳。因此，對(duì)云服務(wù)器上加密數(shù)據(jù)的有效搜索成為用戶關(guān)注的重點(diǎn)?？伤阉骷用芗夹g(shù)是允許用戶對(duì)密文數(shù)據(jù)進(jìn)行檢索的密碼原語(yǔ)，利用云服務(wù)器的強(qiáng)大計(jì)算資源進(jìn)行關(guān)鍵詞檢索。根據(jù)使用密碼體制的不同，介紹了可搜索加密的分類，將其分為對(duì)稱可搜索加密和非對(duì)稱可搜索加密?；谶@種分類，首先介紹了典型方案，之后從可搜索加密的語(yǔ)句表達(dá)能力和安全性2方面進(jìn)行介紹，并指出了該領(lǐng)域當(dāng)前研究中急需解決的問(wèn)題及未來(lái)研究方向。

云計(jì)算；可搜索加密；對(duì)稱可搜索加密；非對(duì)稱可搜索加密

1 引言

近年來(lái)，隨著網(wǎng)絡(luò)的快速發(fā)展，大數(shù)據(jù)時(shí)代已然到來(lái)，由于人們?nèi)粘．a(chǎn)生的數(shù)據(jù)越來(lái)越多，云存儲(chǔ)技術(shù)也隨之興起，如亞馬遜簡(jiǎn)易存儲(chǔ)服務(wù)以及國(guó)內(nèi)的百度云盤等。但是，隨著該技術(shù)的發(fā)展，人們發(fā)現(xiàn)，當(dāng)把數(shù)據(jù)外包到云服務(wù)器時(shí)，用戶也就無(wú)法對(duì)數(shù)據(jù)進(jìn)行控制，使用戶的隱私安全面臨巨大的挑戰(zhàn)。普遍的解決辦法是數(shù)據(jù)加密后上傳，但是又會(huì)遇到如何在密文上進(jìn)行查詢的難題，最簡(jiǎn)單的方法是將文件下載解密后查詢。這種操作由于下載了不需要的文件而浪費(fèi)了大量網(wǎng)絡(luò)開銷，且進(jìn)行解密和查詢也浪費(fèi)了大量計(jì)算開銷，這種方法并不適用。由于云服務(wù)器具有強(qiáng)大的計(jì)算能力，人們希望由服務(wù)器進(jìn)行檢索功能，可以把密鑰發(fā)送給云服務(wù)器，之后由服務(wù)器解密并查詢，但云服務(wù)器通常是“誠(chéng)實(shí)且半可信”的，用戶的隱私暴露在云服務(wù)器面前，仍然有泄露的風(fēng)險(xiǎn)。

為了解決這類問(wèn)題，可搜索加密（SE，searchable encryption）技術(shù)應(yīng)運(yùn)而生。本文對(duì)可搜索加密的基本概念進(jìn)行研究[1]，關(guān)注近年來(lái)可搜索加密的研究進(jìn)展，針對(duì)現(xiàn)有方法進(jìn)行分類并對(duì)可搜索加密的未來(lái)發(fā)展進(jìn)行展望。

2 基本概念

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

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

圖1 可搜索加密過(guò)程

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

2) 陷門生成：經(jīng)過(guò)數(shù)據(jù)擁有者授權(quán)的數(shù)據(jù)使用者使用密鑰對(duì)待查詢的關(guān)鍵詞生成陷門，發(fā)送給云服務(wù)器。

3) 查詢檢索：云服務(wù)器對(duì)數(shù)據(jù)使用者提交的陷門和每個(gè)上傳文件的索引表進(jìn)行檢索，返回包含陷門關(guān)鍵詞的密文文件。

4) 文件解密：數(shù)據(jù)使用者使用解密密鑰對(duì)云服務(wù)器返回的密文文件進(jìn)行解密。

可搜索加密主要包含對(duì)稱可搜索加密（SSE，symmetric searchable encryption）和非對(duì)稱可搜索加密（ASE，asymmetric searchable encryption）2種類型，這2種類型來(lái)源于不同的現(xiàn)實(shí)問(wèn)題，之后用來(lái)解決不同的需求問(wèn)題。下面對(duì)這2類可搜索加密進(jìn)行詳細(xì)講解。

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

3.1 定義

對(duì)于可搜索加密技術(shù)的來(lái)源，要追溯到不可信賴的服務(wù)器存儲(chǔ)問(wèn)題[2]，即假設(shè)用戶Alice希望將文件上傳至云服務(wù)器，但是面臨著數(shù)據(jù)泄露的風(fēng)險(xiǎn)，為了保護(hù)用戶的個(gè)人隱私，可以選擇將文件加密后上傳。采用傳統(tǒng)的加密算法，當(dāng)Alice需要查詢?cè)品?wù)器上的某個(gè)文件時(shí)，需要將所有文件全部下載，解密后檢索，因?yàn)橹挥杏脩鬉lice自己擁有解密的能力，而在密文上是無(wú)法進(jìn)行檢索的。此類問(wèn)題就需要新型的加密方案：加密后的文件可以執(zhí)行檢索功能，并在這個(gè)過(guò)程中不會(huì)泄露有關(guān)數(shù)據(jù)的任何明文信息。

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

=(,,,,)

其中

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

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

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

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

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

對(duì)稱可搜索加密通常對(duì)關(guān)鍵詞首先進(jìn)行處理，大多數(shù)采用偽隨機(jī)函數(shù)或者散列算法等方法，模糊關(guān)鍵詞語(yǔ)義進(jìn)行隨機(jī)化的處理。當(dāng)用戶進(jìn)行關(guān)鍵詞檢索時(shí)，將查詢關(guān)鍵詞進(jìn)行相同處理，與文件的關(guān)鍵詞進(jìn)行相似度匹配，結(jié)果滿足某種格式，則說(shuō)明匹配成功，返回相應(yīng)的文件。

3.2 SWP方案

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

圖2 SWP可搜索加密機(jī)制

具體構(gòu)造如下。

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

4)()：服務(wù)器進(jìn)行如下計(jì)算

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

3.3 對(duì)稱可搜索加密語(yǔ)句的表達(dá)能力

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

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

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

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

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

3.4 對(duì)稱可搜索加密的安全性

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

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

對(duì)于對(duì)稱可搜索加密的安全性的研究，之前一直集中在適應(yīng)性安全與非適應(yīng)性安全2方面，利用可信硬件降低安全假設(shè)也是未來(lái)的研究方向之一。

3.5 小結(jié)

根據(jù)上文的介紹，可以發(fā)現(xiàn)，至今為止對(duì)于對(duì)稱可搜索加密的研究主要在搜索語(yǔ)句的表達(dá)能力和安全性2方面，表1對(duì)一些對(duì)稱可搜索加密機(jī)制的安全性進(jìn)行了總結(jié)。

其中，“外”表示方案抵抗外部攻擊，“內(nèi)”表示抵抗服務(wù)器的內(nèi)部攻擊。從表1中可以看出，現(xiàn)有的對(duì)稱可搜索加密方案雖然搜索語(yǔ)句的表達(dá)能力和效率方面存在差異，但基本滿足日常所需的安全要求，對(duì)于特定環(huán)境下的加密方案，還需要人們針對(duì)不同的應(yīng)用場(chǎng)景進(jìn)行研究。

4 非對(duì)稱可搜索加密

4.1 定義

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

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

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

=(,,,)

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

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

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

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

對(duì)于現(xiàn)有的非對(duì)稱可搜索加密技術(shù)，構(gòu)建方法大多基于不同的困難假設(shè)，其中大部分基于雙線性對(duì)（bilinear pairing），下面進(jìn)行詳細(xì)介紹。

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

3)可計(jì)算性（computable）：群1，2中的運(yùn)算以及雙線性映射運(yùn)算在多項(xiàng)式時(shí)間內(nèi)可解。

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

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

由于雙線性對(duì)涉及群元素的運(yùn)算，使非對(duì)稱可搜索加密技術(shù)的開銷變大，但也正是由于這個(gè)特性，使非對(duì)稱可搜索加密可以實(shí)現(xiàn)復(fù)雜的加密技術(shù)。而且，在一些相對(duì)不安全的網(wǎng)絡(luò)中，非對(duì)稱可搜索加密技術(shù)因?yàn)椴恍枰獏f(xié)商密鑰而更加適用，因?yàn)閿?shù)據(jù)擁有者可以使用公鑰對(duì)文件進(jìn)行加密，而數(shù)據(jù)使用者可以使用私鑰進(jìn)行搜索和解密。

4.2 BDOP-PEKS方案

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

該方案基于BDH困難假設(shè)，使方案的效率極低，并且不能抵抗關(guān)鍵詞猜測(cè)攻擊。

4.3 非對(duì)稱可搜索加密語(yǔ)句的表達(dá)能力

對(duì)于非對(duì)稱可搜索加密語(yǔ)句表達(dá)能力的研究，起初只支持精確關(guān)鍵詞檢索，之后進(jìn)行了擴(kuò)展研究，包括多關(guān)鍵詞搜索和模糊關(guān)鍵詞搜索。

表1 SSE機(jī)制總結(jié)

2004年，Boneh等[29]最早提出PEKS概念，并基于BF-IBE構(gòu)造了第一個(gè)PEKS方案BDOP-PEKS，安全性可歸結(jié)為BDH數(shù)學(xué)假設(shè)。2005年，Abdalla等[32]提供了一個(gè)匿名IBE方案到安全的PEKS方案的變換，給出了一個(gè)統(tǒng)計(jì)一致的方案。

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

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

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

4.4 非對(duì)稱可搜索加密的安全性

對(duì)于早期提出的公鑰可搜索加密技術(shù)，之后的研究發(fā)現(xiàn)很多存在不同的漏洞，這也使對(duì)非對(duì)稱可搜索加密安全性的研究成為重點(diǎn)。

文獻(xiàn)[41]首次提出Boneh等[29]的PEKS方案存在嚴(yán)重的安全漏洞，這是因?yàn)殛P(guān)鍵字的選擇范圍比密碼小得多，用戶通常使用知名關(guān)鍵字搜索文檔，這個(gè)事實(shí)足以引起離線的關(guān)鍵字猜測(cè)攻擊。通過(guò)進(jìn)一步的研究，Jeong等[42]展示了一個(gè)關(guān)于構(gòu)建安全PEKS方案以防止關(guān)鍵字猜測(cè)攻擊公開問(wèn)題的負(fù)面結(jié)果。結(jié)果表明，一致性意味著PEKS中的關(guān)鍵字猜測(cè)攻擊不安全。這意味著，當(dāng)可能的關(guān)鍵字的數(shù)量受到某個(gè)多項(xiàng)式的限制時(shí)，構(gòu)建安全且一致的PEKS方案來(lái)防范關(guān)鍵字猜測(cè)攻擊是不可能的。

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

根據(jù)以上的研究發(fā)現(xiàn)，關(guān)于公鑰可搜索加密機(jī)制安全性的研究主要集中在對(duì)關(guān)鍵詞猜測(cè)攻擊的各種抵御方案，之后的研究將主要集中在研究高效的可抵御關(guān)鍵詞猜測(cè)攻擊的加密方案。

4.5 小結(jié)

根據(jù)上文的介紹，非對(duì)稱可搜索加密方案的區(qū)別大多體現(xiàn)在基于的困難假設(shè)不同，達(dá)到的安全性也不同。對(duì)一些基本的公鑰可搜索加密機(jī)制的安全性等方面進(jìn)行總結(jié)，具體如表2所示。

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

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

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

1) 靈活高效的查詢語(yǔ)句是可搜索加密技術(shù)的未來(lái)研究方向之一。現(xiàn)有的可搜索加密方案中，當(dāng)用戶進(jìn)行關(guān)鍵詞檢索時(shí)，仍然需要用戶進(jìn)行二次檢索，使搜索效率大大降低。現(xiàn)階段的研究側(cè)重多有不同，或側(cè)重模糊檢索，或側(cè)重條件檢索，不夠完善，包括模糊關(guān)鍵詞檢索、關(guān)鍵詞排序檢索、多關(guān)鍵詞檢索、關(guān)鍵詞檢索結(jié)果的可驗(yàn)證性等。

表2 PEKS機(jī)制總結(jié)

2) 保留語(yǔ)義的可搜索加密技術(shù)是未來(lái)的研究難點(diǎn)。采用加密技術(shù)可以保護(hù)用戶的數(shù)據(jù)安全，但同時(shí)也失去了詞語(yǔ)的語(yǔ)義關(guān)系，無(wú)法在密文上進(jìn)行關(guān)鍵詞檢索。未來(lái)需要研究的加密方案是使關(guān)鍵詞在加密后仍然具有服務(wù)器無(wú)法獲得的語(yǔ)義關(guān)系，不僅可以實(shí)現(xiàn)精確查詢，還可以準(zhǔn)確找到用戶所需的文件。

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

[1] 項(xiàng)菲, 劉川意, 方濱興,等. 云計(jì)算環(huán)境下密文搜索算法的研究[J].通信學(xué)報(bào), 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īng)緯, 賈春福, 劉哲理, 等. 可搜索加密技術(shù)研究綜述[J]. 軟件學(xué)報(bào), 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] 楊旸, 楊書略, 蔡圣暐, 等. 排序可驗(yàn)證的語(yǔ)義模糊可搜索加密方案[J]. 四川大學(xué)學(xué)報(bào)(工程科學(xué)版), 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] 宋衍, 韓臻, 陳棟, 等. 支持關(guān)鍵詞任意連接搜索的屬性加密方案[J]. 通信學(xué)報(bào), 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] 楊旸, 楊書略, 柯閩. 加密云數(shù)據(jù)下基于Simhash的模糊排序搜索方案[J]. 計(jì)算機(jī)學(xué)報(bào), 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] 王愷璇, 李宇溪, 周福才,等. 面向多關(guān)鍵字的模糊密文搜索方法[J]. 計(jì)算機(jī)研究與發(fā)展, 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] 柳祚鵬. 支持同義詞搜索和抗信息泄漏的對(duì)稱可搜索加密技術(shù)研究[D]. 上海: 上海交通大學(xué),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] 陸海寧. 可隱藏搜索模式的對(duì)稱可搜索加密方案[J].信息網(wǎng)絡(luò)安全, 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] 張楠, 陳蘭香. 一種高效的支持排序的關(guān)鍵詞可搜索加密系統(tǒng)研究[J]. 信息網(wǎng)絡(luò)安全, 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] 方黎明. 帶關(guān)鍵字搜索公鑰加密的研究[D]. 南京航空航天大學(xué), 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-），女，黑龍江黑河人，哈爾濱工程大學(xué)碩士生，主要研究方向?yàn)槊艽a學(xué)可搜索加密技術(shù)。

馬春光（1974-），男，黑龍江雙城人，哈爾濱工程大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)榉植际矫艽a算法與協(xié)議、云計(jì)算安全與隱私、格密碼。

2018-06-10；

2018-07-05

李穎，2472796566@qq.com

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61472097）

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