軟件學(xué)報ISSN1000-9825,CODENRUXUEWJournalofSoftware,2014,25(4):880?895[doi:10.13328/ki.jos.004554]?中國科學(xué)院軟件研究所版權(quán)所有.E-mail:jos@Tel/Fax:+86-10-62562563*可搜索加密機(jī)制研究與進(jìn)展1(清華大學(xué)計算機(jī)科學(xué)與技術(shù)系,北京100084)2(信息科學(xué)與技術(shù)國家實(shí)驗(yàn)室(清華大學(xué)),北京100084)通訊作者:舒繼武,E-mail:shujw@.cn摘要:隨著云計算的迅速發(fā)展,用戶開始將數(shù)據(jù)遷移到云端服務(wù)器,以此避免繁瑣的本地數(shù)據(jù)管理并獲得更加便捷的服務(wù).為了保證數(shù)據(jù)安全和用戶隱私,數(shù)據(jù)一般是以密文存儲在云端服務(wù)器中,但是用戶將會遇到如何在密文找的難題.可搜索加密(searchableencryption,簡稱SE)是近年來發(fā)展的一種支持用戶在密文上進(jìn)行關(guān)鍵字查找的密碼學(xué)原語,它能夠?yàn)橛脩艄?jié)省大量的網(wǎng)絡(luò)和計算開銷,并充分利用云端服務(wù)器龐大的計算資源進(jìn)行密文上的關(guān)鍵字查找.介紹了SE機(jī)制的研究背景和目前的研究進(jìn)展,對比闡述了基于對稱密碼學(xué)和基于公鑰密碼學(xué)而構(gòu)SE關(guān)鍵詞:可搜索加密;數(shù)據(jù)安全;隱私;密碼學(xué);云計算;云存儲中圖法分類號:TP309文獻(xiàn)標(biāo)識碼:A中文引用格式:沈志榮,薛巍,舒繼武.可搜索加密機(jī)制研究與進(jìn)展.軟件學(xué)報,2014,25(4):880?895..cn/1000-9825/4554.htm英文引用格式英文引用格式:ShenZR,XueW,ShuJW.Surveyontheresearchanddevelopmentofsearchableencryptionschemes.RuanJianXueBao/JournalofSoftware,2014,25(4):880?895(inChinese)./1000-9825/4554.htmSurveyontheResearchandDevelopmentofSearchableEncryptionSchemesSHENZhi-Rong1,XUEWei1,2,SHUJi-Wu1,21(DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China)2(TsinghuaNationalLaboratoryforInformationScienceandTechnology(TsinghuaUniversity),Beijing100084,China)Correspondingauthor:SHUJi-Wu,E-mail:shujw@Abstract:Withtherapiddevelopmentofcloudcomputing,usersarebeginningtomovetheirdatatothecloudserversinordertoavoidtroublesomedatamanagementatlocalmachinesandenjoyconvenientservice.Toprotectdatasecurityanduserprivacy,dataareusuallystoredinencryptedforminthecloud,butitactivatestheinconveniencewhentheusertriestoretrievethefilescontainingsomeinterestedkeywords.Searchableencryption(SE)isarecentlydevelopedcryptographicprimitivethatsupportskeywordsearchoverencrypteddata,whichnotonlysaveshugenetworkbandwidthandcomputationcapacityforusers,butalsomigratesthecumbersomesearchoperationtothecloudservertoutilizeitsvastcomputationalresources.ThispaperfirstintroducestheresearchbackgroundandthecurrentdevelopmentofSEschemesandcomparesthedifferentfeaturesbetweensymmetrickeycryptographybasedSEschemesandpublickeycryptographybasedSEschemes.TheresearchstatusofthesearchquerysupportedinSEschemesisthenprovided.Thediscussionincludesthesupportofsinglekeywordsearchquery,conjunctive(andmulti-keyword)searchqueryandcomplexsearchquery,respectively.Finally,thisstudypresentsthetypicalapplicationscenarioofSEschemes,anddiscussesthepossibledevelopmenttendency.Keywords:searchableencryption;datasecurity;privacy;cryptography;cloudcomputing;cloudstorage*基金項(xiàng)目:國家自然科學(xué)基金(61232003);國家科技重大專項(xiàng)(2013ZX03002004-003);中美軟件合作研究項(xiàng)目(61361120098)收稿時間:2012-09-08;定稿時間:2013-12-05;jos在線出版時間:2014-01-14CNKI網(wǎng)絡(luò)優(yōu)先出版:2014-01-1413:02,/kcms/doi/10.13328/ki.jos.000013.html沈志榮等:可搜索加密機(jī)制研究與進(jìn)展881近年來,隨著云計算技術(shù)[1?3]的迅猛發(fā)展,一些典型的云服務(wù)產(chǎn)品也順勢發(fā)布,并得到了人們廣泛的關(guān)注,例如云網(wǎng)絡(luò)存儲工具Dropbox[4]、亞馬遜簡易儲存服務(wù)(Amazonsimplestorageservice)[5]和微軟的云計算平臺WindowsAzure[6]等.它們在云端服務(wù)器上為用戶保存數(shù)據(jù)和搭設(shè)虛擬系統(tǒng)環(huán)境,通過網(wǎng)絡(luò)向用戶傳輸對數(shù)據(jù)的操作服務(wù),并根據(jù)用戶所使用的硬件資源和服務(wù)時間進(jìn)行收費(fèi).由于其方便快捷的特性和靈活的收費(fèi)方式,越來越多的用戶選擇將本地的數(shù)據(jù)遷移到云端服務(wù)器中,以此來節(jié)省本地的數(shù)據(jù)管理開銷和系統(tǒng)維護(hù)開支.由于數(shù)據(jù)脫離了用戶的物理控制而存儲在云端,云端服務(wù)器管理員和非法用戶(如黑客等不具有訪問權(quán)限的用戶)可以嘗試通過訪問數(shù)據(jù)來試圖獲取數(shù)據(jù)所包含的信息,這將可能造成數(shù)據(jù)信息和用戶隱私的泄露.近年來,由于黑客的非法入侵和云端服務(wù)器管理員的不當(dāng)操作造成了多起云安全事故的發(fā)生,直接導(dǎo)致了大量用戶資料和私人數(shù)據(jù)的泄露.例如,Sony公司在2011年由于黑客入侵導(dǎo)致上億用戶資料外泄事故[7]和Google公司在2011年發(fā)生的Gmail大規(guī)模用戶數(shù)據(jù)泄露事件等,這些頻繁發(fā)生的云事故,讓用戶開始更加審慎考慮當(dāng)數(shù)據(jù)存放在云端時的安全性以及自己的個人隱私是否能夠得到有效保護(hù)等問題.為了保證數(shù)據(jù)的機(jī)密性,越來越多的公司和個人用戶選擇對數(shù)據(jù)進(jìn)行加密,并將數(shù)據(jù)以密文形式存儲在云端服務(wù)器,但是當(dāng)用戶需要尋找包含某個關(guān)鍵字的相關(guān)文件時,將會遇到如何在云端服務(wù)器的密文進(jìn)行搜索操作的難題.一種最簡單的方法是將所有密文數(shù)據(jù)下載到本地進(jìn)行解密,然后在明文上進(jìn)行關(guān)鍵字搜索,但是這種操作不僅因?yàn)楹芏嗖恍枰臄?shù)據(jù)浪費(fèi)了龐大的網(wǎng)絡(luò)開銷和存儲開銷,而且用戶也需要因?yàn)榻饷芎退阉鞑僮鞲冻鼍薮蟮挠嬎汩_銷.另外,這種方法也極不適用于低帶寬的網(wǎng)絡(luò)環(huán)境中.而另一種極端的方法是將密鑰和關(guān)鍵字發(fā)給云端服務(wù)器,讓云端服務(wù)器解密密文數(shù)據(jù),并進(jìn)行明文上的搜索操作.但是這種做法又將讓用戶的個人數(shù)據(jù)重新曝光于云端服務(wù)器管理員和非法用戶的視線之下,嚴(yán)重威脅到數(shù)據(jù)的安全和用戶的個人隱私.為了更好地解決這個問題,可搜索加密(searchableencryption)便應(yīng)運(yùn)而生,并在近幾年中得到了研究者的廣泛研究和發(fā)展[8?32].用戶可以首先使用SE機(jī)制對數(shù)據(jù)進(jìn)行加密,并將密文存儲在云端服務(wù)器;當(dāng)用戶需要搜索某個關(guān)鍵字時,可以將該關(guān)鍵字的搜索憑證(searchcapability)發(fā)給云端服務(wù)器;云端將接收到的搜索憑證對每個文件進(jìn)行試探匹配,如果匹配成功,則說明該文件中包含該關(guān)鍵字;最后,云端將所有匹配成功的文件發(fā)回給用戶.在收到搜索結(jié)果之后,用戶只需要對返回的文件進(jìn)行解密.在安全性上,云端服務(wù)器在整個搜索的過程中除了能夠猜測任意兩個搜索語句是否包含相同的關(guān)鍵字(即,搜索模式,searchpattern),并知道多次搜索的結(jié)果(即,訪問模式,accesspattern)、文件密文、文件密文大小和一些搜索憑證之外,不會獲得關(guān)于所請求搜索關(guān)鍵字內(nèi)容以及文件的明文信息(一些工作也嘗試使服務(wù)器端無法獲得訪問模式,例如文獻(xiàn)[31,33,34]的工作).在訪問效率上,通過以上過程可以直觀發(fā)現(xiàn)使用SE機(jī)制給用戶帶來的方便性:首先,用戶不需要為了沒有包含關(guān)鍵字的文件浪費(fèi)網(wǎng)絡(luò)開銷和存儲空間;其次,對關(guān)鍵字進(jìn)行搜索的操作交由云端來執(zhí)行,充分利用了云端強(qiáng)大的計算能力;最后,用戶不必對不符合條件的文件進(jìn)行解密操作,節(jié)省了本地的計算資源.1996年,文獻(xiàn)[31]首次提出了隱藏用戶訪問模式的密文搜索機(jī)制,但是它要求用戶和服務(wù)器端進(jìn)行多重對數(shù)輪交互,這種方法在實(shí)際中運(yùn)用的效率不高.2000年,文獻(xiàn)[8]提出了一種基于對稱算法下的SE方法的實(shí)現(xiàn)方法,開創(chuàng)了使用實(shí)用性的SE機(jī)制來實(shí)現(xiàn)在密文上進(jìn)行關(guān)鍵字搜索的先例.在此之后,許多研究者不斷推動著使用對稱加密算法支持多個關(guān)鍵字搜索的SE機(jī)制[15,22].2004年,文獻(xiàn)[16]提出了基于公鑰密碼學(xué)算法上的SE機(jī)制,為后來的研究者通過公鑰密碼學(xué)實(shí)現(xiàn)更加多樣的SE方案提供了指導(dǎo).另外,研究者不僅在理論上設(shè)計多樣的SE機(jī)制,并且也開始嘗試將它們應(yīng)用于真實(shí)應(yīng)用場景中.例如,文獻(xiàn)[9]提出了在日志數(shù)據(jù)上實(shí)現(xiàn)密文搜索的方法,微軟公司提出的CryptographicCloudStorage[35]中實(shí)現(xiàn)了基于對稱密碼學(xué)下的密文搜索的功能,以及針對云計算環(huán)境下所做的一些具有現(xiàn)實(shí)指導(dǎo)意義的工作[12,13,21]等.在此基礎(chǔ)上,本文主要分析和總結(jié)了當(dāng)前SE機(jī)制的研究現(xiàn)狀,探討了其未來的發(fā)展趨勢.從分析中可以得出:由于網(wǎng)絡(luò)技術(shù)的迅速發(fā)展導(dǎo)致現(xiàn)今的數(shù)據(jù)獲取將更加方便和快捷,在一些特殊應(yīng)用場景中,例如電子病歷存儲、個人郵件處理、財政數(shù)據(jù)審計等,用戶更加在意數(shù)據(jù)的安全性和個人隱私保護(hù).因此,SE機(jī)制在未來的一段時間內(nèi)仍然是工業(yè)界和學(xué)術(shù)界的研究熱點(diǎn).特別是在數(shù)據(jù)以密文形式存儲在云端的前提下,一種高效而又靈活的SE機(jī)制的設(shè)計和實(shí)現(xiàn),都將對云計算的普及起到推動性的作用.JournalofSoftware軟件學(xué)報Vol.25,No.4,April2014本文第1節(jié)主要從總體上介紹SE機(jī)制的主要研究內(nèi)容.第2節(jié)主要對現(xiàn)有的SE機(jī)制的算法進(jìn)行分類,分析它們的優(yōu)劣,并介紹一些公鑰密碼學(xué)簡單的術(shù)語.第3節(jié)主要介紹現(xiàn)有SE機(jī)制對搜索語句的支持情況.第4節(jié)針對SE機(jī)制的應(yīng)用場景進(jìn)行分析.最后,第5節(jié)總結(jié)當(dāng)前的研究現(xiàn)狀,并對未來的研究方向加以展望.1SE機(jī)制SE機(jī)制的正確性和安全性、支持搜索語句的效果、密鑰和密文長度以及算法的性能,是現(xiàn)今SE的主要研究內(nèi)容究內(nèi)容.現(xiàn)今SE的研究內(nèi)容主要有以下幾個方面(如圖1所示):1)靈活、高效的搜索語句的設(shè)計靈活的搜索語句不僅能夠讓用戶可以更加精確地定位到所需要的數(shù)據(jù)文件,同時也可以讓用戶能夠更加靈活地表述搜索需求.SE機(jī)制從研究初期的支持單詞搜索,到后來逐漸發(fā)展為支持連接關(guān)鍵字搜索,再到支持區(qū)間搜索和子集搜索等復(fù)雜的邏輯語句.其研究難點(diǎn)在于:如何達(dá)到支持復(fù)雜的搜索請求的效果以及如何尋找到適合的困難假設(shè)來證明其安全性,同時使得該機(jī)制又具有可以接受的性能.隨著云計算的發(fā)展,在海量用戶和海量數(shù)據(jù)的應(yīng)用場景下,提供安全、靈活、高效的SE機(jī)制將是研究者所極力追求的目標(biāo)之一.2)模糊搜索和基于相似度排序的模糊搜索由于用戶表述不精確或者輸入錯誤等各種原因,造成精確匹配搜索將有可能無法找到用戶所真正需要的文件,因此,模糊搜索的引入能夠智能地尋找與用戶所輸入的搜索詞相關(guān)的文件.由于數(shù)據(jù)存儲形式為密文且基于安全需求的考慮,目前在明文上所廣泛應(yīng)用的模糊搜索方法無法直接運(yùn)用到密文上的搜索中,因此,設(shè)計支持模糊搜索和基于相似度排序的模糊搜索的可搜索加密機(jī)制,是一個亟待研究的內(nèi)容之一.3)在不同現(xiàn)實(shí)場景中對SE機(jī)制的應(yīng)用自從SE機(jī)制提出后,針對其所能部署的應(yīng)用場景得到了研究者的關(guān)注.從SE機(jī)制提出初期的數(shù)據(jù)所有者獨(dú)享數(shù)據(jù)[8,10,15,26],到后來數(shù)據(jù)所有者將搜索的能力共享給其他用戶[12,13,21,22,28],以及云存儲環(huán)境下的一些特殊場景中用戶私密數(shù)據(jù)的管理[12,14,21]等.針對不同的應(yīng)用場景,需要相應(yīng)的SE機(jī)制來支持,因此,設(shè)計適合目的應(yīng)用場景的SE機(jī)制,是應(yīng)用密碼學(xué)領(lǐng)域的研究方向之一.RankedFuzzyKeywordssupportSearchableencryptionschemesPublickeySymmetrickeySingleowner-singlesearcherMultiowner-singlesearchertokenSingleowner,multi-searcherResearchofSEschemesSE機(jī)制的研究內(nèi)容ResearchofsearchableencryptionschemesSearchableencryptionmodelkeywordsConjunctivekeywordsFlexiblequeryRangeSubsetBilinearUsersgeneratetokenAuthoritydistributestokenkeywordMultiOwnerissuespairingRSAEncryptionSingle沈志榮等:可搜索加密機(jī)制研究與進(jìn)展8832SE機(jī)制的構(gòu)造算法現(xiàn)今眾多的SE機(jī)制的設(shè)計可以根據(jù)其構(gòu)造算法的不同而分為兩類,即:基于對稱密碼學(xué)算法(symmetrickeycryptographybased)的SE機(jī)制[8?10,12,13,15,21,22,26,32]以及基于公鑰密碼學(xué)算法(publickeycryptographybased)的SE機(jī)制[9,11,14,16,20,23,24,29,30].前者主要是使用一些偽隨機(jī)函數(shù)生成器(pseudorandomfunctiongenerator)、偽隨機(jī)數(shù)生成器(pseudorandomnumbergenerator)、哈希算法和對稱加密算法構(gòu)建而成;而后者主要是使用雙線性映射等代數(shù)工具,并將安全性建立在一些復(fù)雜性問題的難解性之上.這兩種方法的區(qū)別是:首先,由于大部分基于公鑰密碼學(xué)算法的SE機(jī)制都是基于雙線性映射之上來構(gòu)造的,在搜索的過程中需要進(jìn)行群元素之間和雙線性對的計算,因此,它們的開銷要遠(yuǎn)高于基于對稱密碼學(xué)算法的SE機(jī)制;其次,基于對稱密碼學(xué)的SE機(jī)制更加適用于單用戶創(chuàng)造數(shù)據(jù)并與多用戶共享的應(yīng)用場景,而基于公鑰密碼學(xué)的SE機(jī)制則允許除數(shù)據(jù)所有者之外的用戶使用可搜索加密機(jī)制來產(chǎn)生數(shù)據(jù)密文并生成加密后的索引表.2.1SE機(jī)制的主要算法SE的構(gòu)造方法眾多,因此其形式化描述方法各不相同.基本的SE機(jī)制主要包括4種算法[20],分別是Setup,GenToken,BuildIndex和Query:(1)Setup:該算法主要由權(quán)威機(jī)構(gòu)或者數(shù)據(jù)所有者進(jìn)行并生成密鑰.在基于公鑰密碼學(xué)的SE機(jī)制中,該算法會根據(jù)輸入的安全參數(shù)(securityparameter)來產(chǎn)生公鑰和私鑰;在基于對稱密碼學(xué)的SE機(jī)制中,運(yùn)行該算法后會產(chǎn)生一些私鑰,例如偽隨機(jī)函數(shù)的密鑰等;(2)GenToken:該算法以根據(jù)用戶需要搜索的關(guān)鍵字為輸入,產(chǎn)生相應(yīng)的搜索憑證.算法的執(zhí)行者主要由應(yīng)用場景決定,可以由數(shù)據(jù)所有者、用戶或者權(quán)威機(jī)構(gòu)來執(zhí)行(具體場景部分將在第4節(jié)中進(jìn)行討論);(3)BuildIndex:該算法由數(shù)據(jù)所有者執(zhí)行.在這種算法中,數(shù)據(jù)所有者將根據(jù)文件內(nèi)容,選出相應(yīng)的關(guān)鍵字集合,并使用可搜索加密機(jī)制建立索引表.在基于公鑰密碼學(xué)的SE機(jī)制中,數(shù)據(jù)所有者會使用公鑰對每個文件的關(guān)鍵字集進(jìn)行加密;在基于對稱密碼學(xué)的SE機(jī)制中,數(shù)據(jù)所有者會使用對稱密鑰或者使用基于密鑰的哈希算法對關(guān)鍵字集進(jìn)行加密.而文件內(nèi)容主體將會使用對稱加密算法進(jìn)行加密;(4)Query:該算法是由服務(wù)器端進(jìn)行.服務(wù)器將以接收到的搜索憑證和每個文件中的索引表為輸入,進(jìn)行協(xié)議所預(yù)設(shè)的計算,最后通過輸出結(jié)果是否與協(xié)議預(yù)設(shè)的結(jié)果相同來判斷該文件是否滿足搜索請求.服務(wù)器最后將搜索結(jié)果返回.最后,用戶在獲得返回的文件密文之后,再使用相應(yīng)的對稱密鑰對數(shù)據(jù)密文進(jìn)行解密.2.2基于對稱密碼學(xué)的SE機(jī)制對稱密碼學(xué)算法指的是:加密的密鑰和解密的密鑰都是衍生于同一個密鑰,它們或者相等或者之間需要一些簡單的轉(zhuǎn)換[36].對稱密碼學(xué)算法的優(yōu)點(diǎn)是計算開銷小,適用于大塊數(shù)據(jù)的加密,缺點(diǎn)則是加密方和解密方需要在事先實(shí)現(xiàn)密鑰的協(xié)商,而密鑰則需要通過安全信道傳輸.而基于對稱密碼學(xué)的SE機(jī)制是采用偽隨機(jī)函數(shù)、偽隨機(jī)置換以及哈希算法(或者散列算法)對關(guān)鍵字按照一些步驟進(jìn)行處理,當(dāng)需要對關(guān)鍵字進(jìn)行搜索時,首先將關(guān)鍵字隨機(jī)化處理,然后讓服務(wù)器端根據(jù)協(xié)議所預(yù)設(shè)的計算方式進(jìn)行關(guān)鍵字的匹配,如果最后的結(jié)果是某種特定的格式,則說明匹配成功.例如:在文獻(xiàn)[8]的工作中,當(dāng)服務(wù)器端將關(guān)鍵字的密文E(w)和服務(wù)器端的密文C進(jìn)行異或運(yùn)算后,需要判斷結(jié)果的前(n?m)位的哈希值是否是后m位;在文獻(xiàn)[9]的工作中,需要判斷最后的結(jié)果是否是(flag|K)格式.基于對稱密碼學(xué)的SE機(jī)制在運(yùn)算性能上較基于公鑰密碼學(xué)的SE機(jī)制更高效,但在支持搜索語句的靈活性上,現(xiàn)今的基于對稱密碼學(xué)的SE機(jī)制只能支持單個關(guān)鍵字或者是連接關(guān)鍵字的搜索,而且搜索憑證的大小需要與所搜索的關(guān)鍵字?jǐn)?shù)目呈線性關(guān)系.2.3基于公鑰密碼學(xué)的SE機(jī)制現(xiàn)今應(yīng)用比較普遍的基于公鑰密碼學(xué)的SE機(jī)制大部分構(gòu)建于雙線性對(bilinearpairing)之上,其安全性都是基于不同的安全假設(shè).下面首先給出關(guān)于雙線性對的定義以及一些應(yīng)用較為普遍的困難問題.RiRiJournalofSoftware軟件學(xué)報Vol.25,No.4,April2014(3)可計算性(computable):群G1,G2中的運(yùn)算以及雙線性映射e運(yùn)算在多項(xiàng)式時間內(nèi)可解.定義2(DDH,離散Diffie-Hellman問題)[11].假設(shè)G是一個素數(shù)階p的群,其中,g是G的生成元,隨機(jī)地從pabcggagbgcgc等于gab.基于公鑰密碼學(xué)的SE機(jī)制由于涉及到群元素之間的運(yùn)算,開銷較大.同時,正是由于雙線性對的特性和復(fù)雜性假設(shè)的存在,使得一些支持更加復(fù)雜的搜索語句的工作得以發(fā)展.另外,基于公鑰密碼學(xué)的SE機(jī)制更加適用于一些不安全的網(wǎng)絡(luò)中,它不需要加密方和解密方事先協(xié)商密鑰,用戶可以直接使用對外公開的公鑰對關(guān)鍵字集合進(jìn)行加密,而數(shù)據(jù)所有者可以使用私鑰產(chǎn)生搜索憑證進(jìn)行密文上的關(guān)鍵字搜索.3SE機(jī)制搜索效果分析3搜索語句是用戶搜索興趣的表現(xiàn),靈活的搜索語句不僅可以讓用戶能夠更加準(zhǔn)確地描述自己的搜索意愿,同時也能夠更加精確地定位到用戶需要的文件.在本節(jié)中,根據(jù)SE機(jī)制支持的搜索語句,分為單詞字搜索、連接關(guān)鍵字搜索和復(fù)雜邏輯結(jié)構(gòu)語句這3類.3.1支持單詞搜索的SE機(jī)制支持單詞搜索指的是用戶一次只能對一個關(guān)鍵字進(jìn)行搜索,云端服務(wù)器通過該憑證搜索到包含該詞的文件,然后將最后滿足條件的結(jié)果返回給用戶.早期的SE機(jī)制研究主要考慮的應(yīng)用場景是:數(shù)據(jù)所有者為了節(jié)省本地存儲空間,將數(shù)據(jù)以密文形式存儲在遠(yuǎn)端服務(wù)器,并在帶寬受限的環(huán)境下進(jìn)行關(guān)鍵字搜索操作.在該情況下所衍生出來的SE機(jī)制,主要是以基于對稱密碼學(xué)算法為主.文獻(xiàn)[8]于2000年提出了一種基于對稱密碼學(xué)算法的實(shí)用SE方案,具體如圖2所示.PlaintextWWiEEE(wi)LLiCiphertextFk(Fk(Si)SikFig.2FinalschemeinRef.[8]2文獻(xiàn)[8]中的最終機(jī)制在這個方案中,偽隨機(jī)函數(shù)F和f公開.在對數(shù)據(jù)加密時,文件內(nèi)容被分割為固定大小的文件塊,經(jīng)過加密后的文件塊E(wi)被分為兩個部分,分別是Li和Ri.同時,數(shù)據(jù)所有者利用偽隨機(jī)位(pseudorandombits)Si生成(Si,Fki(Si)),并與(Li,Ri)經(jīng)過異或運(yùn)算生成密文Ci,其中,Li和Si(或Ri和Fki(Si))的長度分別為(n?m)位(或m位),kifkLi需要搜索關(guān)鍵字wi時,數(shù)據(jù)所有者將E(wi)和ki發(fā)給服務(wù)器端.服務(wù)器端將密文Ci與E(wj)進(jìn)行異或運(yùn)算,然后判斷得到的結(jié)果是否滿足(s,Fki(s))的形式,如果滿足,則說明匹配成功,并將該文件返回.這種方法雖然能夠基本上實(shí)現(xiàn)單詞搜索,但卻存在著一些缺陷:云端服務(wù)器需要對每個文件的內(nèi)容進(jìn)行掃沈志榮等:可搜索加密機(jī)制研究與進(jìn)展885描,看密文內(nèi)容是否存在給定的關(guān)鍵字的密文形式相匹配的內(nèi)容,造成的計算開銷將與文件大小呈線性關(guān)系,在海量數(shù)據(jù)環(huán)境下,該方法效率不佳.同時,服務(wù)器端可以通過統(tǒng)計攻擊的方法獲得一些額外的用戶隱私信息,例如,通過得到的搜索憑證來判斷用戶前后搜索的關(guān)鍵字是否相同等.針對文獻(xiàn)[8]中所提SE方案搜索效率低下等缺點(diǎn),文獻(xiàn)[10]提出了使用安全索引的方法來快速實(shí)現(xiàn)對海量密文數(shù)據(jù)的搜索.這種搜索機(jī)制建立在BloomFilter[37]之上,即,每個文件都有對應(yīng)的一些獨(dú)立的哈希函數(shù)和BloomFilter數(shù)據(jù)結(jié)構(gòu).在文件加密之前,需要對文件中的關(guān)鍵字使用私鑰加密,再使用哈希函數(shù)映射到Filter之上并記錄,最后,將映射后的Filter和文件的密文上傳到服務(wù)器中.當(dāng)用戶需要進(jìn)行密文搜索時,需要將關(guān)鍵字的密文發(fā)送給云端服務(wù)器,再由云端服務(wù)器使用每個文件的哈希函數(shù)進(jìn)行關(guān)鍵字到Filter的映射.如果映射到的位置之前都有記錄的痕跡,則說明這個關(guān)鍵字有很大的概率是在該文件中,最后,云端服務(wù)器將得到的匹配文件發(fā)給用戶.這種方法的優(yōu)點(diǎn)是能夠利用哈希函數(shù)計算快速的特點(diǎn),快速地查找關(guān)鍵字所在的密文文件;但是它也繼承了BloomFilter存在錯誤率的特點(diǎn),有可能導(dǎo)致一些文件本來并不包含關(guān)鍵字,最后卻能夠通過哈希函數(shù)的檢測,而被云端作為結(jié)果返回給用戶,給用戶帶來一些額外的帶寬和計算開銷.由于之前的SE機(jī)制都是基于對稱密碼學(xué)算法,文獻(xiàn)[16]給出了基于公鑰密碼下的可搜索加密機(jī)制PEKS的構(gòu)造方法,該文的作者們主要考慮的應(yīng)用場景是:用戶Alice掌握著私鑰(privatekey),并將相對應(yīng)的公鑰(publickey)公開,為了讓電子郵件網(wǎng)關(guān)(E-mailgateway)分揀接收到的郵件,Alice會事先將一些特定關(guān)鍵字的陷門(trapdoor)Tw發(fā)送給電子郵件網(wǎng)關(guān),使得它能夠通過判斷郵件中是否包含關(guān)鍵字W來選擇接受設(shè)備.與此同時,電子郵件網(wǎng)關(guān)在判斷的過程中無法獲得關(guān)于關(guān)鍵字和郵件內(nèi)容的有效信息.在PEKS機(jī)制的加密算法中使用到了兩個哈希算法H1和H2,用戶使用哈希算法H1將每個關(guān)鍵字映射到群G1中,然后選取隨機(jī)數(shù)r和雙線性映射將關(guān)鍵字W隨機(jī)化映射到群G2中.這樣,即使是相同的關(guān)鍵字所生成的密文也將有所不同,并將r的信息以gr形式保存,最后生成密文(gr,H2(t)).當(dāng)需要生成搜索憑證時,使用H1將關(guān)鍵字映射到G1中,并選取隨機(jī)數(shù)a,將H1(W)a發(fā)給服務(wù)器端,使得即使是相同的關(guān)鍵字,由于隨機(jī)數(shù)a的作用,所產(chǎn)生的搜索憑證也將有所不同.最后,服務(wù)器端利用雙線性映射的性質(zhì)進(jìn)行關(guān)鍵字的匹配判斷.該方法的優(yōu)點(diǎn)是支持?jǐn)?shù)據(jù)接收者對多個發(fā)送者所加密的密文中進(jìn)行搜索的應(yīng)用場景,而且由于隨機(jī)數(shù)的作用,系統(tǒng)的加密效果為非確定性加密,導(dǎo)致了服務(wù)器端無法通過密文是否相同來判斷索引表(或搜索憑證)中是否具有相同的關(guān)鍵字.其缺點(diǎn)是計算開銷因?yàn)殡p線性對的引進(jìn)而加大,特別是對操作(pairingoperation)的計算開銷較大,使得該方法在海量數(shù)據(jù)處理場景中的應(yīng)用性受到一定的限制.另外,PEKS的安全性在隨機(jī)語言機(jī)模型(randomoraclemodel)下成立,并不適合現(xiàn)實(shí)應(yīng)用.文獻(xiàn)[9]分別基于對稱密碼學(xué)和基于身份加密(identitybasedencryption,簡稱IBE)給出了兩種SE機(jī)制的設(shè)計方法以實(shí)現(xiàn)在加密后的審計日志上進(jìn)行關(guān)鍵字的搜索.在基于對稱密碼學(xué)的設(shè)計中,審計日志服務(wù)器(auditlogserver)首先從數(shù)據(jù)中萃取出具有代表性的關(guān)鍵字{wi}=1,然后使用帶有密鑰的偽隨機(jī)函數(shù)和一個隨機(jī)位串r,計算得到密文.用戶需要向?qū)徲嫶?auditescrowagent)請求搜索關(guān)鍵字w操作,審計代理根據(jù)每個審計日志服務(wù)器的密鑰{Sj}=1,使用偽隨機(jī)函數(shù)生成搜索憑證(searchcapability)并發(fā)給用戶.用戶持有該搜索憑證并利用r對密文進(jìn)行XOR運(yùn)算,如果結(jié)果滿足某種特定的格式,則說明搜索成功.而在基于IBE的設(shè)計中,審計日志服務(wù)器以關(guān)鍵字wi為公鑰,對(flag|K)使用IBE的加密算法進(jìn)行加密.當(dāng)收到搜索關(guān)鍵字w的請求后,審計代理通過計算得到w的私鑰dw作為搜索憑證發(fā)給用戶.用戶使用dw對密文使用IBE中的解密算法進(jìn)行解密,若得到的結(jié)果是(flag|K)形式,則說明解密成功.與其他SE機(jī)制的應(yīng)用場景不同,該方法需要審計日志服務(wù)器對日志進(jìn)行加密,同時要求用戶訪問服務(wù)器進(jìn)行搜索,需要用戶自己承擔(dān)搜索開銷.文獻(xiàn)[15]則考慮了兩種應(yīng)用場景,分別是當(dāng)用戶擁有足夠的空間存儲生成關(guān)鍵字的字典以及當(dāng)用戶所擁有的存儲空間無法存放字典的情況.所謂的字典就是用來表示每個關(guān)鍵字的、長度為d的二元組合(i,wi),其中,i∈2d.在第1種情況中,用戶需要為每個文件j建立二進(jìn)制位串索引Ij,并使用偽隨機(jī)函數(shù)將該文件包含的每個關(guān)鍵字的id使用偽隨機(jī)置換函數(shù)進(jìn)行置換,并將置換結(jié)果所在的位置1,并使用另一個隨機(jī)位串對Ij進(jìn)行異或運(yùn)算,隱藏Ij中每一位的值.在第2種情況中,用戶將字典用偽隨機(jī)置換函數(shù)隨機(jī)化后存儲在服務(wù)器端.當(dāng)需要進(jìn)行關(guān)鍵字的搜索時,則需要與服務(wù)器端進(jìn)行兩輪的交互,第1輪是從服務(wù)器中取出想要搜索關(guān)鍵字的二進(jìn)制串表JournalofSoftware軟件學(xué)報Vol.25,No.4,April2014示,第2輪中則是計算出關(guān)鍵字的陷門并發(fā)給服務(wù)器端.針對之前的SE機(jī)制只是假設(shè)攻擊者(adversary)并不會考慮搜索的陷門(trapdoor)和以前搜索結(jié)果的特點(diǎn),文獻(xiàn)[22]提出了一種更強(qiáng)的自適應(yīng)(adaptive)攻擊者模型,在該模型中,攻擊者會將之前搜索過的陷門和搜索結(jié)果作為參照來決定下一次的查詢語句.在文獻(xiàn)[22]所做的工作中,提出了兩種設(shè)計方案:第1種設(shè)計方案是在假設(shè)攻擊者是non-adaptive的情況下保證安全,并使用了連接表(linkedlist)、數(shù)組和查找表等數(shù)據(jù)結(jié)構(gòu)將不同文件中的相同關(guān)鍵字連接起來,提高了搜索的性能;而在第2種方案中,則保證了自適應(yīng)的語義安全(adaptivesemanticsecurity).同時,針對以前基于公鑰密碼學(xué)算法中只有掌握私鑰的用戶才能對用公鑰加密的數(shù)據(jù)進(jìn)行搜索的限制,文獻(xiàn)[22]采用了廣播加密(broadcastencryption)的方法,在共享用戶群中共享密鑰r,使得該共享用戶群也能夠?qū)@些密文數(shù)據(jù)進(jìn)行搜索.之前的SE機(jī)制只是簡單地將滿足關(guān)鍵字的搜索結(jié)果返回但卻缺乏對搜索結(jié)果的整理,而用戶需要在本地對結(jié)果進(jìn)行整理并找出最相關(guān)的結(jié)果.文獻(xiàn)[12]針對搜索結(jié)果進(jìn)行了一些優(yōu)化,提出了一種在云數(shù)據(jù)中實(shí)現(xiàn)安全排序的方法,這種方法不僅能夠使云端服務(wù)器進(jìn)行關(guān)鍵字的密文搜索,同時還能夠?qū)λ阉鞯慕Y(jié)果對于關(guān)鍵字的相關(guān)性程度進(jìn)行排序,最后,將前k個最相關(guān)的文件返回給用戶.這種操作更加有利于用戶更快地找出自己所感興趣的數(shù)據(jù),節(jié)省了用戶的開銷.為了實(shí)現(xiàn)排序的效果,首先需要文件所有者在上傳文件之前,針對每個關(guān)鍵字在文件中出現(xiàn)的次數(shù),根據(jù)相關(guān)性分?jǐn)?shù)模型計算該文件對于每個關(guān)鍵字的相關(guān)性得分,然后在本地構(gòu)建一個關(guān)鍵字和文件的倒排索引表,每個表格的數(shù)據(jù)則是該關(guān)鍵字和文件的相關(guān)性分?jǐn)?shù),然后再將索引表加密.同時,使用保序加密(order-preservingencryption[38])對相關(guān)性分?jǐn)?shù)加密,當(dāng)用戶需要搜索密文關(guān)鍵字時,云端服務(wù)器再根據(jù)每個文件對該關(guān)鍵字相關(guān)性分?jǐn)?shù)的密文結(jié)果進(jìn)行排序,并將經(jīng)過排序后的前k個文件返回給用戶.這種方法的優(yōu)點(diǎn)是,在每次搜索的過程中,用戶可以得到在相關(guān)性分?jǐn)?shù)模型下對該關(guān)鍵字最為相關(guān)的文件,提高了用戶體驗(yàn),并節(jié)省了一定的帶寬和因?yàn)榻饷軒淼挠嬎汩_銷,但是云端服務(wù)器也掌握了每個文件對于某個關(guān)鍵字相關(guān)性程度的信息.針對有可能發(fā)生的印刷錯誤以及用戶由于疏忽導(dǎo)致精確匹配無法發(fā)生作用的情景,文獻(xiàn)[13]則考慮了在云計算中實(shí)現(xiàn)密文上的模糊關(guān)鍵字搜索的應(yīng)用場景.在文獻(xiàn)[13]的設(shè)計中,主要考慮了3種情況下的模糊搜索,分別是插入、刪除和替換操作.該文作者使用了編輯距離(editdistance)的概念,對于某個單詞,他們將在某個編輯距離之內(nèi)的所有單詞都加密,然后上傳到云端服務(wù)器.當(dāng)用戶需要搜索某個單詞時,可以定位到與該單詞具有某個編輯距離的所有單詞,然后將包含這些單詞的文件返回給用戶.該方法雖然可以實(shí)現(xiàn)對于關(guān)鍵字的模糊搜索,但是帶來的代價是需要存儲的可能數(shù)據(jù)量過于龐大;而且用戶雖然可以得到近似的結(jié)果,但是結(jié)果的不精確性也將給用戶帶來極大的網(wǎng)絡(luò)和計算開銷.3.2支持連接關(guān)鍵字搜索(conjunctivekeywordsearch)3.2由于支持單詞的SE機(jī)制只允許用戶一次只能發(fā)送一個單詞的搜索憑證,這極不符合現(xiàn)實(shí)生活中多詞搜索的應(yīng)用需求,特別是當(dāng)單詞無法精確定位到用戶所想要的文件時,單詞搜索的限制可能需要用戶使用不同關(guān)鍵字多輪搜索,或者是經(jīng)過一輪密文搜索后,對返回結(jié)果解密,通過在明文上進(jìn)行搜索來尋找目標(biāo)文件,而這樣的結(jié)果將給用戶帶來極差的操作體驗(yàn).針對這些不足,支持連接關(guān)鍵字搜索的可搜索加密機(jī)制開始得到研究者廣泛的關(guān)注和研究.文獻(xiàn)[11]針對之前的搜索機(jī)制中只能使用單詞搜索的不足,提出了兩種支持連接關(guān)鍵字搜索的SE機(jī)制.在這一方案中,每個文件都有固定數(shù)量的關(guān)鍵字域,每個域中都有特定的關(guān)鍵字來表征這些文件的特性.例如:在郵件中具有關(guān)鍵字域“主題、發(fā)送方、接收方”,而在“主題”域中可能具有關(guān)鍵值“會議”等.第1種機(jī)制能夠達(dá)到固定的在線網(wǎng)絡(luò)開銷,所謂固定指的是用戶數(shù)據(jù)所有者進(jìn)行在線交互的網(wǎng)絡(luò)開銷是依賴于每個文件中的關(guān)鍵字域數(shù)量,在這個方案中,用戶需要發(fā)送兩個部分的搜索憑證:第1個部分可以在高速網(wǎng)絡(luò)中離線發(fā)送到服務(wù)器端,稱為“原型憑證(proto-capability)”,其大小與存儲在服務(wù)器端的文件數(shù)量線性相關(guān);第2個部分稱為“查詢部分(querypart)”,需要用戶與數(shù)據(jù)所有者進(jìn)行在線交互而得到.當(dāng)用戶將查詢部分發(fā)給服務(wù)器端時,服務(wù)器端會將其與原型憑證整合成完整的搜索憑證,并進(jìn)行搜索.該機(jī)制的安全性建立在DDH(decisionalDiffie-Hellman)問題沈志榮等:可搜索加密機(jī)制研究與進(jìn)展887的復(fù)雜性之上.針對第1種機(jī)制可能導(dǎo)致網(wǎng)絡(luò)開銷過大的情況,在第2種機(jī)制中使用了固定網(wǎng)絡(luò)開銷的搜索憑證,即,搜索憑證對于文件數(shù)量而言是固定的,但是依然與關(guān)鍵字域數(shù)量線性相關(guān).文獻(xiàn)[26]分別基于對稱密碼學(xué)和公鑰密碼學(xué)提出了兩種實(shí)現(xiàn)連接關(guān)鍵字搜索的高效SE機(jī)制,但是需要保證沒有重復(fù)的關(guān)鍵字.在基于對稱密碼學(xué)的SE機(jī)制中,首先對關(guān)鍵字采用偽隨機(jī)函數(shù)進(jìn)行加密,當(dāng)用戶需要搜索m個關(guān)鍵字時,就使用秘密共享(secretsharing)中的recover算法,將這m個關(guān)鍵字的密文作為輸入,并將結(jié)果作為陷門發(fā)給服務(wù)器端.服務(wù)器端也調(diào)用secretsharing中的recover算法,對于每個文件進(jìn)行判斷,如果結(jié)果等于陷門,則說明該文件包含了所有的關(guān)鍵詞.但是該方案要求陷門的大小和文件數(shù)量呈線性關(guān)系.針對這個問題,文獻(xiàn)[26]提出了基于公鑰密碼學(xué)的SE機(jī)制,通過使用雙線性映射使得陷門的大小固定,但其的安全性則是建立在DDH,XDH和MXDH的復(fù)雜性之上.之前的基于公鑰密碼學(xué)機(jī)制要么只能支持“多個發(fā)送者-單個接受者”的應(yīng)用場景,要么會出現(xiàn)密文過于龐大的情況,文獻(xiàn)[24]針對這種情況提出了一種基于公鑰密碼學(xué)的SE機(jī)制,其核心思想是:通過使用多接受者公鑰加密方法(multi-receiverpublickeyencryption)將所有接受者的公鑰對關(guān)鍵字集合進(jìn)行加密,通過支持連接關(guān)鍵字的公鑰加密方法,實(shí)現(xiàn)了支持每個接受者只需使用自己的私鑰就能對連接關(guān)鍵字進(jìn)行搜索以及在“單個發(fā)送者-多個接受者”場景下支持密文搜索的效果.作為文獻(xiàn)[12]工作的拓展,文獻(xiàn)[21]的工作能夠讓服務(wù)器對用戶所請求搜索的多個關(guān)鍵字,根據(jù)每個文件對于所請求關(guān)鍵字的得分排序,并將排名最高的k個文件返回給用戶,服務(wù)器端將無法獲得用戶搜索的關(guān)鍵字信息、文件是否包含某個關(guān)鍵字信息以及最后每個文件的得分信息.其核心思想是:采用kNN[39]的思想,首先生成兩個二進(jìn)制位串,分別稱為文件的數(shù)據(jù)向量(datavector)和用戶的查詢向量(queryvector).這兩個向量中的每個位都分別與關(guān)鍵字進(jìn)行一一對應(yīng),并以該位的值來表示該文件以及用戶的查詢請求是否包含某個關(guān)鍵字,然后使用兩個互逆的矩陣分別對這兩個位串加密,保證文件包含關(guān)鍵字的信息和用戶查詢語句對云端服務(wù)器不可見.在計算得分的時候,還需要對兩個位串的乘積通過加入隨機(jī)數(shù)來進(jìn)行隨機(jī)化處理.這種方法與前面的連接關(guān)鍵字搜索的不同之處在于:普通的連接關(guān)鍵字搜索是返回的文件需要保證包含每個域上的關(guān)鍵字;而在這里的多詞搜索中,即使某個文件沒有全部包含所請求的關(guān)鍵字,但只要其得分位列于前k中,依然可以被返回.另外,隨機(jī)數(shù)的引入也導(dǎo)致了最終得分的不精確性,根據(jù)文獻(xiàn)[21]中的描述,當(dāng)引入隨機(jī)變量的正態(tài)分布標(biāo)準(zhǔn)差σ=1時,最后結(jié)果的不準(zhǔn)確度最高可達(dá)到20%.該機(jī)制的安全性建立在文獻(xiàn)[39]之上,能夠抵御已知明文攻擊(known-plaintextattack).除了在普通數(shù)據(jù)上進(jìn)行搜索之外,文獻(xiàn)[32]也嘗試著在對加密后的圖結(jié)構(gòu)數(shù)據(jù)(graph-structuredata)上進(jìn)行搜索的機(jī)制,該機(jī)制遵循“過濾和確認(rèn)(filtering-and-verification)”原則,即:在過濾步驟里,預(yù)先為每個圖建立一個基于特征的索引(feature-basedindex),其中,特征(feature)是原圖的子圖;而在確認(rèn)階段,則需要判斷每個圖像的特征是否與請求同構(gòu).由于特征集合的大小和整個圖像集合相比更小,因此這種操作減輕了比較的工作量.與文獻(xiàn)[21]不同,為了讓云端服務(wù)器無法通過相關(guān)性得分來判斷在一次搜索中所匹配的關(guān)鍵字?jǐn)?shù)量這一信息,該文放棄了在每個圖形索引中使用二進(jìn)制位串中的每一位的值來表征是否包含特征的方法,而是分別從一個隨機(jī)數(shù)串S和一個隨機(jī)數(shù)矩陣M中取值來表征,其中,M[i][j]<S[j].如果圖形Gi包含特征Fj,則相應(yīng)的索引表取值為S[j];否則,取值為M[i][j].為了保證索引表對云端服務(wù)器不可見,使用了一對互逆的矩陣分別對圖形索引表和查詢語句中的數(shù)據(jù)向量和查詢向量進(jìn)行隱藏.最后,在搜索時,數(shù)據(jù)所有者會將搜索預(yù)期值作為搜索憑證的一部分發(fā)給用戶,而云端服務(wù)器在計算相關(guān)性得分時,如果某個圖形的相關(guān)性得分等于該預(yù)期值,則說明該圖形包含所有的特征;反之,如果得分小于預(yù)期值,則說明該圖不滿足所有的特征,但是云端服務(wù)器無法在不滿足的圖形中獲取它們包含特征數(shù)量多少的信息.該機(jī)制能夠抵御已知明文攻擊.3.3支持復(fù)雜邏輯結(jié)構(gòu)的可搜索加密機(jī)制另外,近年來逐漸發(fā)展的謂詞加密(predicateencryption)是一種涵蓋面比較廣的密碼學(xué)原語(cryptographicprimitive),它涵蓋了基于屬性的加密機(jī)制(attribute-basedencryptionscheme[40,41])和基于身份的加密機(jī)制(identity-basedencryptionscheme[42]).在謂詞加密中,每個密文和刻畫其性質(zhì)的屬性I∈Σ相聯(lián)系(其中,Σ是所有屬JournalofSoftware軟件學(xué)報Vol.25,No.4,April2014性的集合),而對應(yīng)著謂詞f∈F的私鑰(secretkey)記作SKf.如果SKf和I滿足f(I)=1,則SKf能夠解密與I相聯(lián)系的密文.謂詞加密可以被運(yùn)用于密文搜索中,其中每個密文的屬性可以用該文件含有的典型關(guān)鍵字來刻畫,謂詞可被認(rèn)為是用戶的查詢語句,私鑰可看作是根據(jù)用戶查詢語句生成的搜索憑證,而f(I)=1可認(rèn)為密文的關(guān)鍵字滿足用戶的查詢語句.文獻(xiàn)[30]提出了支持析取子句、多項(xiàng)式方程和內(nèi)積形式的謂詞加密構(gòu)造方法.通過在復(fù)合階群(compositeordergroup)上構(gòu)建向量(vector)來表示析取范式、合取范式和多項(xiàng)式方程等復(fù)雜邏輯結(jié)構(gòu).雖然該方法支持多種邏輯結(jié)構(gòu),但是由于建立在復(fù)合階群之上的雙線性對的計算開銷大約是素數(shù)階群的50倍[43,44],因此該方法的性能不是很理想.在該方法的實(shí)現(xiàn)中,雖然可以使用一些預(yù)處理來加速雙線性對計算[45],但是總的效率依然遠(yuǎn)低于其他建立在素數(shù)階群之上的SE機(jī)制.另外,支持內(nèi)積的謂詞加密也可以適用于子集和區(qū)間的關(guān)鍵字搜索,可以將判斷是否屬于子集和區(qū)間的關(guān)系式轉(zhuǎn)換為以“或”關(guān)系連接的子句.例如,對于判斷語句“x∈[1,3]”,可以將其轉(zhuǎn)換為“(x=1)∨(x=2)∨(x=3)”,然后再將該子句轉(zhuǎn)換為內(nèi)積形式.針對謂詞加密的代理,文獻(xiàn)[12]考慮了文獻(xiàn)[20]中的代理問題,并提出了實(shí)現(xiàn)的方案.另外,文獻(xiàn)[25]還考慮了謂詞的隱私性問題,構(gòu)造了一個實(shí)現(xiàn)謂詞隱私保護(hù)的密碼學(xué)原語,該構(gòu)造建立在一個復(fù)合群之上,其中,該復(fù)合群可以表示成4個子群的直積.該方法能夠達(dá)到更高強(qiáng)度的屬性隱藏安全(attribute-hidingsecurity),意味著除了用戶通過密鑰獲得的額外信息之外,每個密文所關(guān)聯(lián)的屬性信息都將被隱藏.文獻(xiàn)[29]構(gòu)造出了基于DPVS(dualpairingvectorspace)的分級謂詞加密方案(hierarchicalpredicateencryption,簡稱HPE),其中,DPVS是n個素數(shù)階群的直積所展成的空間,并且DPVS上的雙線性運(yùn)算相當(dāng)于在n個素數(shù)階群上進(jìn)行雙線性運(yùn)算.通過在DPVS上構(gòu)造出單位正交向量(b,b*),將向量b用于構(gòu)造密文,將向量b*用于生成密鑰,使得用戶可以根據(jù)自己的私鑰將部分權(quán)限代理給其他用戶.假設(shè)用戶Alice能夠解密的文件集合為FAAliceBobBobFBFBFARDSP和IDSP假設(shè)下,對選擇性明文攻擊(chosenplaintextattack)達(dá)到選擇性屬性隱藏(selectiveattribute-hiding)安全.文獻(xiàn)[17]考慮到網(wǎng)絡(luò)入侵檢測的問題而提出了MRQED機(jī)制,在不可信的遠(yuǎn)端服務(wù)器中存放網(wǎng)絡(luò)審計日志的密文形式并進(jìn)行搜索,當(dāng)網(wǎng)絡(luò)入侵發(fā)生時,審計者(auditor)可以通過被授權(quán)的key來查找在某個特定區(qū)間中的網(wǎng)絡(luò)流信息.在他們的工作中,提出多維區(qū)間查詢(multi-dimensionalrangequery)機(jī)制,其中,在每個維度上支持區(qū)間查詢,并定義了兩種安全模型,分別是匹配保護(hù)安全(match-concealingsecurity)和匹配泄露安全(match-revealingsecurity),最后證明了所提出的方案在這兩種安全模型下能夠達(dá)到選擇性安全(selectivesecure).另外,他們的工作可以防止串謀攻擊(collusionattack).文獻(xiàn)[14]考慮了在加密后的個人健康記錄(personalhealthrecord,簡稱PHR)上進(jìn)行授權(quán)搜索的應(yīng)用場景,并利用分級的謂詞加密(hierarchicalpredicateencryption,簡稱HPE)支持靈活的搜索語句.在他們的設(shè)計中,用戶首先在本地產(chǎn)生合取范式形式(conjunctivenormalform,簡稱CNF)的查詢語句,需要先向本地的LTA申請,本地的LTA認(rèn)證用戶的請求并將合取范式的查詢語句轉(zhuǎn)換為謂詞向量(predicatevector)和屬性向量(attributevector)來表示,最后,LTA將轉(zhuǎn)換成的謂詞向量作為輸入,使用分級謂詞加密方法中的代理算法(delegationalgorithm)產(chǎn)生相應(yīng)的搜索憑證(searchcapability)并頒發(fā)給用戶.為了保證查詢語句的隱私,文獻(xiàn)[14]引入了一個代理服務(wù)器(proxyserver)對密文進(jìn)行再處理,使得云端服務(wù)器無法達(dá)到通過公鑰遍歷生成密文來試探搜索語句的內(nèi)容的效果.由于該機(jī)制建立在文獻(xiàn)[29]之上,因此其安全性能夠達(dá)到文獻(xiàn)[29]中所提方案的安全性.3.4小3.4從以上的分析可以看出:隨著研究者們對SE機(jī)制的研究和發(fā)展以及為了滿足一些特定的應(yīng)用需求,SE機(jī)制在搜索效果上得到迅速的發(fā)展:首先,從對搜索語句的支持上,SE機(jī)制的搜索效果從簡單的單詞搜索,逐步發(fā)展成靈活、復(fù)雜的查詢語句,不僅支持合取范式和析取范式等查詢語句,而且在每個維度上支持相同匹配(equality)、子集(subset)和區(qū)間(range)查詢,這將更有利于用戶描述自己的搜索意愿;其次,從對搜索結(jié)果的優(yōu)化處理上看,SE機(jī)制的搜索結(jié)果從只滿足用戶搜索請求,逐步發(fā)展成支持返回與用戶搜索關(guān)鍵字相關(guān)的前k個文件,以及支持容錯的密文搜索等,這將更有利于用戶能夠更快地找到自己所需要的文件.表1對一些SE機(jī)制在所沈志榮等:可搜索加密機(jī)制研究與進(jìn)展889基于的算法、查詢語句支持等方面進(jìn)行總結(jié),其中,對于一些基于公鑰密碼學(xué)的SE機(jī)制,還歸納了它們所基于的安全性假設(shè).Table1ComparisonofSEschemesEAlgorithmbasedQuerysupportSchemesAssumptionsSymmetrickeycryptographybasedSEschemesSinglekeywordSWP00[8]WBDS04[9]G03[10]CGKO06[22]WCLRL10[12]LWWCRL10[13]CM05[15]\\\\\\\Multi-KeywordCWLRL11[21]\ConjunctiveeywordqueryCYWRL11[32]BKM05[26]\\PublickeycryptographybasedSEschemesSinglekeywordWBDS04[9]BCOP04[16]DRD10[23]BDHBDHRSAassumptionsConjunctivekeywordsHL07[24]GSW04[11]BKM05[26]DLDHDDH,BDDHDDH,XDH,MXDHComplexsearchqueryOT09[29]KSW08[30]LYCL11[14]SBCSP07[17]BW07[20]RDSP,IDSPLargenumberfactorizationRDSP,IDSPDBDH,DLABDH,C3DH另外,針對一些具有典型意義的基于公鑰密碼學(xué)的SE機(jī)制,我們給出了它們在公鑰長度、索引密文長度、搜索憑證大小、索引表的加密以及每次匹配搜索時間開銷的比較,具體見表2.從表1中可以看出:基于公鑰密碼學(xué)的SE機(jī)制大部分都使用了雙線性對工具,然后使用了一些安全假設(shè)來證明該機(jī)制的安全性.同時,從表2中可以看出:在一些支持連接關(guān)鍵字的SE機(jī)制中,搜索憑證的大小和關(guān)鍵字?jǐn)?shù)目呈線性關(guān)系,例如DRD10[23],BKM05[26];有的則和文件的數(shù)量呈線性關(guān)系,例如GSW04[11].而對于支持內(nèi)積的謂詞加密機(jī)制而言,所需要的公鑰大小通常與向量長度n有關(guān),例如在OT09[29]中,公鑰大小是O(n2),這是由于其所需要的公鑰為O(n)個長度為n的向量.另外,對于支持“單個發(fā)送者-多個接受者”的情況,公鑰大小還與接受者的數(shù)量有關(guān),例如HL07[24].對于支持子集和區(qū)間查找的SE機(jī)制,密文和搜索憑證的長度都與維度的數(shù)目以及每個維度中關(guān)鍵字的數(shù)量有關(guān),.BW.Table2Comparisonofsomepublic-keycryptographybasedSEschemes表2一些基于公鑰密碼學(xué)的SE機(jī)制的對比SchemePKsizeCTsizeSearchcapsizeEncryptiontimeSearchtimeGSW04BCOP04O)O)OWOWO(F)&O(KW)O)OWGO(W)G+O(W)H1O(KW)G&O(KW)PO(1)P+O(1)H2LYCL11[14]O(n2)OnOnSBCSP07[17]BW07[20]DRD10[23]HL07[24]BKM05[26]O(DlogT)O(DlogT)O(DlogT)O(logTD)P+O(logTD)G′O(DT)O(DT)O(D)O(W)GO(KW)PO)O(W)O(KW)OWGO(1)G)+O(1)HO)O(W+U)O(KW+U)O(KW)G+O(1)G+O(1)PO)O(W)O(KW)O(KW)G+O(1)G+O(1)POT09[29]O(n2)OnOnKSW08[30]OnOnOnO(n)GO(n)PKW:Thenumberofkeywords,W:Thenumberofwords,F:Thenumberofdocuments,D:Thenumberofdimensions,T:Thenumberofkeywordsovereachdimension,U:Thenumberofusers,n:Thelengthofthevector,P:Thepairingoperation,G/G′/G1/GT:OperationsingroupG/G′/G1/G2,H1/H2:ThehashoperationearchcapEncryptedfilesearchcapEncryptedfilesJournalofSoftware軟件學(xué)報Vol.25,No.4,April20144SE機(jī)制的應(yīng)用模型近年來,SE機(jī)制已被廣泛地應(yīng)用于實(shí)際場景中.根據(jù)應(yīng)用場景,SE機(jī)制可以分為3類:第1類是數(shù)據(jù)所有者并不將數(shù)據(jù)共享給其他用戶,而是獨(dú)自擁有對數(shù)據(jù)的搜索的權(quán)利;第2類是數(shù)據(jù)所有者允許其他經(jīng)過認(rèn)證后的用戶對其數(shù)據(jù)進(jìn)行搜索;第3類是多個數(shù)據(jù)所有者允許某個特定的用戶對數(shù)據(jù)進(jìn)行搜索,例如郵件處理場景.4.1數(shù)據(jù)獨(dú)享場景在早期的SE機(jī)制中,數(shù)據(jù)所有者獨(dú)享搜索權(quán)限是主要考慮的應(yīng)用場景,如圖3所示.用戶將數(shù)據(jù)上傳到服務(wù)器端,并不是出于與其他用戶共享的目的,而是為了節(jié)省本地存儲空間和管理開銷,同時希望能夠在低帶寬的網(wǎng)絡(luò)環(huán)境下對數(shù)據(jù)進(jìn)行訪問.由用戶獨(dú)享搜索權(quán)限的數(shù)據(jù)可以是用戶的私密數(shù)據(jù),例如電子病歷、郵件等涉及到個人隱私和公司內(nèi)部事務(wù)等的數(shù)據(jù).在文獻(xiàn)[8,10,26]的工作中,主要考慮了當(dāng)用戶Alice在保留搜索能力的前提下,將個人數(shù)據(jù)的密文存放在不可信的服務(wù)器上,在帶寬受限的環(huán)境中,需要對其數(shù)據(jù)進(jìn)行搜索的應(yīng)用場景.在文獻(xiàn)[15]的工作中,主要考慮兩種應(yīng)用場景:第1種是當(dāng)用戶在使用家中的電腦存儲的字典產(chǎn)生搜索憑證,并發(fā)給遠(yuǎn)端服務(wù)器的密文搜索;第2種應(yīng)用場景是當(dāng)用戶使用存儲空間較小的手機(jī)時,需要將字典存放在遠(yuǎn)端服務(wù)器,然后經(jīng)過與服務(wù)器端進(jìn)行兩輪交互,對服務(wù)器端的密文數(shù)據(jù)進(jìn)行搜索.EncryptedfilesDataownerFig.3Scenariothatdataaresearchedbytheowneronly圖3數(shù)據(jù)只由數(shù)據(jù)所有者獨(dú)享4.2數(shù)據(jù)共享場景數(shù)據(jù)共享場景主要適用于數(shù)據(jù)所有者將自己的一些數(shù)據(jù)與其他用戶共享的場景.當(dāng)數(shù)據(jù)所有者允許經(jīng)過認(rèn)證后的用戶對其數(shù)據(jù)進(jìn)行搜索時,則有3種方式使得其他用戶能夠根據(jù)自己感興趣的關(guān)鍵字獲取到搜索憑證,分別是:由數(shù)據(jù)所有者生成搜索憑證;或者數(shù)據(jù)所有者將一部分密鑰信息發(fā)布給授權(quán)的用戶,由授權(quán)用戶在本地產(chǎn)生搜索憑證;或者將分發(fā)搜索憑證的責(zé)任交由信任的第三方權(quán)威機(jī)構(gòu)來執(zhí)行.這3種方法各有所適用的應(yīng)用場景.4.2.1由數(shù)據(jù)所有者生成搜索憑證由數(shù)據(jù)所有者生成搜索憑證可以保證數(shù)據(jù)實(shí)時地由數(shù)據(jù)所有者控制,使得非法用戶在沒有獲得搜索憑證的情況下無法對數(shù)據(jù)進(jìn)行搜索操作,具體情況如圖4(a)所示.但是這種方法也要求數(shù)據(jù)所有者必須時刻在線處理用戶的搜索請求,并在本地為每個請求計算生成搜索憑證,這極有可能導(dǎo)致數(shù)據(jù)所有者的計算能力成為整個系統(tǒng)的瓶頸,從而降低了系統(tǒng)的可擴(kuò)展性.在文獻(xiàn)[21]的工作中,用戶需要將所請求的關(guān)鍵字集合W~以及一個二元向量Q發(fā)給數(shù)據(jù)所有者,其中,Q[j]的作用是表征Wj是否在W~中.根據(jù)用戶的請求,數(shù)據(jù)所有者使用密鑰矩陣計算得到{M1′,M1′′},并將其返回.由于是矩陣之間的乘積,因此對數(shù)據(jù)所有者而言,開銷不是很大.rchcapcapServerEncryptedfilesrEncryptedfilesEncryptedfilesEncryptedfilesEncryptedfilesEncryptedfiles沈志榮等:可搜索加密機(jī)制研究與進(jìn)展891rchcapcapServerEncryptedfilesrEncryptedfilesEncryptedfilesEncryptedfilesEncryptedfilesEncryptedfilesrchrequestDataownerApplyrchrequestDataownerUsersResponsewithcapUsersUsersUsersDataownerDataownerAUsersUsersDataownerDataownerAuthority(a)數(shù)據(jù)所有者產(chǎn)生搜索憑證并發(fā)給用戶(b)用戶在本地產(chǎn)生搜索憑證(c)可信審計機(jī)構(gòu)處理用戶請求并分發(fā)搜索憑證Fig.4Scenariothatdataaresharedbetweenmultipleusers圖4數(shù)據(jù)在多用戶之間共享的場景4.2.2由用戶在本地自己生成搜索憑證由用戶自己生成搜索憑證不僅可以有效地減輕數(shù)據(jù)所有者的計算負(fù)擔(dān),還避免了與數(shù)據(jù)所有者進(jìn)行交互操作所帶來的網(wǎng)絡(luò)開銷和時間延遲,增強(qiáng)了系統(tǒng)的可擴(kuò)展性.但是數(shù)據(jù)所有者喪失了對用戶搜索關(guān)鍵字的認(rèn)證,同時,共享給用戶密鑰也加大了數(shù)據(jù)泄露的可能性.該應(yīng)用場景如圖4(b)所示.在文獻(xiàn)[12,22]的工作中,數(shù)據(jù)所有者需要將密鑰x,y共享給認(rèn)證用戶,用戶可以根據(jù)自己感興趣的關(guān)鍵字w生成陷門T=(πx(w),fy(w)),其中,f和π分別是偽隨機(jī)函數(shù)(pseudo-randomfunction)和哈希函數(shù).在文獻(xiàn)[13]的工作中,數(shù)據(jù)所有者需要和認(rèn)證用戶(theauthorizeduser)共享一個密鑰sk,當(dāng)認(rèn)證用戶需要對某個關(guān)鍵字w進(jìn)行搜索時,則利用單向函數(shù)f產(chǎn)生憑證f(sk,w)并發(fā)給云端服務(wù)器.文獻(xiàn)[28]考慮了一種比較新穎的系統(tǒng)模型,每個用戶都擁有自己單獨(dú)的私鑰,并且都可以自己向中立的數(shù)據(jù)庫服務(wù)器端上傳密文.與此同時,每個用戶都有權(quán)利針對某個關(guān)鍵字使用自己的私鑰來生成搜索憑證,并對整個數(shù)據(jù)庫進(jìn)行搜索.4.2.3由可信審計機(jī)構(gòu)生成搜索憑證在多數(shù)據(jù)所有者和多用戶的環(huán)境中,由于服務(wù)器端的數(shù)據(jù)歸屬復(fù)雜,數(shù)據(jù)所有者可以將分發(fā)搜索憑證的責(zé)任交由可信審計機(jī)構(gòu)執(zhí)行,具體情況如圖4(c)所示.由可信審計機(jī)構(gòu)生成搜索憑證可以不要求數(shù)據(jù)所有者時刻在線,并利用可信審計機(jī)構(gòu)強(qiáng)大的計算能力來承擔(dān)產(chǎn)生搜索憑證的計算負(fù)擔(dān),同時達(dá)到對用戶的搜索請求進(jìn)行授權(quán)的目的.但是這也要求數(shù)據(jù)所有者對其完全信任,并將數(shù)據(jù)的控制權(quán)限交給該機(jī)構(gòu).其中,基于公鑰密碼學(xué)的SE機(jī)制較為適用于這種應(yīng)用場景.文獻(xiàn)[14]考慮了用戶在加密的電子病歷上進(jìn)行搜索的應(yīng)用場景,其中,電子病歷由可信的第三方機(jī)構(gòu)TA進(jìn)行保存管理.該文提出了使用TA/LTA對用戶的搜索權(quán)限進(jìn)行認(rèn)證并頒發(fā)搜索憑證的系統(tǒng)框架,每個LTA都被賦予了一些屬性密鑰,這些屬性密鑰決定了該LTA對數(shù)據(jù)的訪問權(quán)限.當(dāng)認(rèn)證用戶的搜索請求時,LTA使用自己的屬性密鑰對用戶的請求進(jìn)行代理操作(delegationoperation),即,經(jīng)過認(rèn)證后的用戶請求能夠檢索到的文件不能超過該LTA的權(quán)限.這種方法能夠緩解TA成為整個系統(tǒng)性能瓶頸的情況,并提高了系統(tǒng)的可擴(kuò)展性.但在該系統(tǒng)框架中,由于TA擁有了最高的權(quán)限,造成數(shù)據(jù)的明文信息將完全曝光在TA的視線之中,而數(shù)據(jù)所有者喪失了對數(shù)據(jù)的完全控制能力.在文獻(xiàn)[9]的工作中構(gòu)造了兩種機(jī)制:在第1種機(jī)制中,每個調(diào)查者(investigator)在搜索之前都需要將所要搜索的詞w發(fā)給審計代理機(jī)構(gòu),以此獲取搜索憑證(searchcapability)dw:=〈HS1(w),...,HSt(w)?,其中,HSi(w)是以Si為密鑰的哈希函數(shù);在第2種機(jī)制中,審計代理使用IBE中的哈希函數(shù)以及隨機(jī)數(shù),調(diào)用IBE中密鑰生成算法在文獻(xiàn)[17]的工作中,主要考慮審計者在網(wǎng)絡(luò)入侵發(fā)生后,對網(wǎng)絡(luò)流量進(jìn)行審計并找出入侵者的應(yīng)用場景.審計者需要向權(quán)威機(jī)構(gòu)進(jìn)行申請,并獲得搜索憑證.892JournalofSoftware軟件學(xué)報Vol.25,No.4,April20144.3郵件處理場景這種情況主要使用于基于公鑰密碼學(xué)的SE機(jī)制.郵件發(fā)送者使用公鑰對郵件進(jìn)行加密,郵件接收者利用私鑰對一些感興趣的關(guān)鍵字生成搜索憑證并發(fā)給網(wǎng)關(guān),讓網(wǎng)關(guān)根據(jù)感興趣的關(guān)鍵字對郵件進(jìn)行分揀.在文獻(xiàn)[16]的工作中,主要考慮郵件接收者對其他用戶利用其公鑰加密的郵件進(jìn)行判斷的場景.郵件接受者針對感興趣的關(guān)鍵字使用私鑰生成搜索憑證并發(fā)給網(wǎng)關(guān),網(wǎng)關(guān)根據(jù)搜索憑證來判斷郵件中是否有接受者所制定的關(guān)鍵字,并以此來判斷郵件的緊急程度,從而選擇其最終的接受設(shè)備.在文獻(xiàn)[20]的另一項(xiàng)工作中,主要考慮的是郵件接受者根據(jù)感興趣的謂詞條件生成搜索憑證P并發(fā)給網(wǎng)關(guān),使其根據(jù)搜索憑證來判斷郵件是否滿足謂詞條件P,以此來決定接受的設(shè)備.該謂詞條件包括某個關(guān)鍵字是否屬于某個區(qū)間,以及判斷該關(guān)鍵字集合是否是某個集合的子集等.針對文獻(xiàn)[16,20]所考慮的應(yīng)用場景是多個用戶發(fā)送給某個郵件接收者的情況,文獻(xiàn)[24]考慮了其對偶問題,即,一個用戶需要將一封郵件發(fā)送給多個接受者的情況.他們考慮的是使用多接受者的公鑰加密方法對郵件進(jìn)行處理,從而避免因?yàn)榉謩e使用每個接受者的公鑰對郵件加密而帶來的重復(fù)加密開銷,以及支持郵件接受者單獨(dú)使用私鑰生成搜索憑證對郵件進(jìn)行搜索.4.4小結(jié)4.4本節(jié)主要對SE機(jī)制的應(yīng)用場景和系統(tǒng)模型進(jìn)行了介紹,分析了每種應(yīng)用場景的特點(diǎn).從以上的分析可以得出以下幾個結(jié)論:?首先,SE機(jī)制的研究與現(xiàn)實(shí)的需求緊密相關(guān),具體體現(xiàn)在各個SE機(jī)制都能在一些特定的現(xiàn)實(shí)場景中為用戶節(jié)省大量的開銷和繁瑣的操作.另外,對于每個應(yīng)用的場景都有各自的威脅模型和系統(tǒng)模型的定義,而它們所關(guān)注和改善的目標(biāo)都極為不同,而這些不同之處也產(chǎn)生了額外的問題,進(jìn)而帶來新的設(shè)計,例如,如果需要減輕數(shù)據(jù)所有者的負(fù)擔(dān)而給予用戶生成搜索憑證的能力,則需要將相關(guān)的密鑰分發(fā)給用戶,同時保證授權(quán)用戶不會將該密鑰泄露;?其次,現(xiàn)實(shí)中的一些特定的應(yīng)用需求,也極大地凸顯出其與現(xiàn)有SE機(jī)制的不合之處,從而讓研究者們開始分析和設(shè)計適應(yīng)該需求下的SE機(jī)制,進(jìn)而達(dá)到提高安全性的同時又在極大程度上保證其效率的效果.5總結(jié)與展望本文針對可搜索加密機(jī)制的研究現(xiàn)狀進(jìn)行了較為全面的介紹和討論:首先,針對SE機(jī)制的研究內(nèi)容進(jìn)行介紹;其次,對SE機(jī)制的構(gòu)造算法、對搜索語句的支持程度以及其被考慮的應(yīng)用場景進(jìn)行了分析和討論.從以上介紹中可以看出:SE機(jī)制的研究逐漸成熟化,將逐漸成為云計算環(huán)境下用戶對數(shù)據(jù)密文進(jìn)行操作的有利工具.未來的一段時間,SE機(jī)制依然將被視為解決云計算中的安全問題的研究熱點(diǎn)之一.隨著越來越多的數(shù)據(jù)存儲在云端服務(wù)器中,以及用戶對數(shù)據(jù)安全和個人隱私的敏感程度越來越強(qiáng),如何高效、精確且安全地對存儲在云端服務(wù)器中的密文進(jìn)行搜索,將是研究者不斷研究的方向.我們認(rèn)為,進(jìn)一步的研究應(yīng)重點(diǎn)解決以下問題:第一,高效率且支持靈活查詢語句的SE機(jī)制是未來重點(diǎn)的研究方向之一.隨著越來越多的用戶接受云的概念,同時在云端服務(wù)器存儲的數(shù)據(jù)逐漸向海量級別發(fā)展,在這種條件下,如何給用戶良好的搜索體驗(yàn),對SE機(jī)制的性能將是極大的考驗(yàn).基于對稱密碼學(xué)的SE機(jī)制在性能上較為優(yōu)越,而一些基于公鑰密碼學(xué)的SE機(jī)制雖然能夠支持靈活的查詢語句,但是由于其要么構(gòu)造于復(fù)合群之上(例如文獻(xiàn)[20,30]的工作),要么是構(gòu)建于多個素數(shù)群的直積之上(例如文獻(xiàn)[29]的工作),由于公鑰密碼學(xué)的計算開銷約是對稱密碼學(xué)算法的1000倍[46],導(dǎo)致了它們的性能效果將難以適用于海量用戶和海量數(shù)據(jù)的應(yīng)用場景中.雖然一些能夠提高群元素間運(yùn)算速度的硬件[47]已經(jīng)推出,以及一些并行化技術(shù)也能夠在一定程度上減輕搜索時所帶來的時間等待,但是只有設(shè)計出高效的SE機(jī)制,才是在算法角度上根本性地成為加快現(xiàn)今搜索效率的有效方法.第二,支持模糊搜索(fuzzysearch)和支持按相關(guān)性排序的可搜索加密機(jī)制依然是未來需要解決的問題.沈志榮等:可搜索加密機(jī)制研究與進(jìn)展893由于現(xiàn)今的大部分可搜索加密機(jī)制都是基于匹配搜索(equalitysearch),因此在密文上實(shí)現(xiàn)快速、高效的支持按相關(guān)性排序搜索和模糊搜索之上的工作依然處于初始研究階段.一些工作[13,21,48,49]雖然在一定程度上實(shí)現(xiàn)了基于相關(guān)性排序和模糊搜索,但是依然存在著一些不足,例如,文獻(xiàn)[13]中的方法其存儲開銷較大且僅支持單詞搜索等.第三,支持關(guān)系運(yùn)算(>,<,==等)的可搜索加密機(jī)制依然是未來需要研究的內(nèi)容.現(xiàn)有的一些工作雖然能夠?qū)崿F(xiàn)區(qū)間查詢(rangequery)和子集查詢(subsetquery),但在支持關(guān)系運(yùn)算的效果上依然不夠理想.在未來的一段時間里,支持關(guān)系運(yùn)算的可搜索加密機(jī)制的研究依然是研究的一個熱點(diǎn),它的研究也將為加密數(shù)據(jù)庫上的查詢提供一些借鑒.第四,保留語義的SE機(jī)制依然是研究難點(diǎn).加密雖然能夠?qū)⒚魑男畔㈦[藏,但同時也破壞了明文中的語義關(guān)系,使得用戶無法像在明文上通過機(jī)器學(xué)習(xí)等方法使得返回的密文能夠越來越符合用戶的需求.未來的SE機(jī)制研究成果或許