復(fù)雜語(yǔ)義可搜索加密研究*

劉晉璐, 秦 靜,2, 汪 青, 趙 博, 張 茜, 蘇 燁

1. 山東大學(xué) 數(shù)學(xué)學(xué)院, 濟(jì)南 250100

2. 中國(guó)科學(xué)院 信息工程研究所 信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室, 北京 100093

1 引言

隨著信息時(shí)代的高速發(fā)展, 互聯(lián)網(wǎng)技術(shù)已成為支撐社會(huì)發(fā)展的“基建”, 以互聯(lián)網(wǎng)為基礎(chǔ)的先進(jìn)技術(shù)方興未艾, 深刻地影響著社會(huì)生產(chǎn)方式的改變, 加快了人類文明的發(fā)展進(jìn)程. 例如, 云醫(yī)療系統(tǒng)[1]革新了醫(yī)生診斷病情的方式, 有利于實(shí)現(xiàn)精準(zhǔn)醫(yī)療; 物聯(lián)網(wǎng)技術(shù)[2–4]可以增加系統(tǒng)內(nèi)設(shè)備之間的協(xié)調(diào)性和靈活性,有利于發(fā)展高精尖生產(chǎn)工藝等等. 這些新興技術(shù)在運(yùn)行和使用過(guò)程中會(huì)產(chǎn)生大量的數(shù)據(jù), 如果將這些數(shù)據(jù)存儲(chǔ)在本地, 不斷累積的數(shù)據(jù)會(huì)對(duì)系統(tǒng)造成巨大的存儲(chǔ)負(fù)擔(dān), 并且所需要的存儲(chǔ)設(shè)備也會(huì)影響部署系統(tǒng)時(shí)的靈活性. 此時(shí), 云計(jì)算服務(wù)為解決數(shù)據(jù)存儲(chǔ)問(wèn)題提供了重要的技術(shù)選擇[5,6]. 借助互聯(lián)網(wǎng)技術(shù)尤其是5G通訊技術(shù)可以快速地將這些數(shù)據(jù)存儲(chǔ)到具有強(qiáng)大數(shù)據(jù)存儲(chǔ)和處理能力的云服務(wù)器上, 并且可以根據(jù)實(shí)際需求在云服務(wù)器端對(duì)數(shù)據(jù)進(jìn)行處理[7–11]. 因此, 云計(jì)算服務(wù)在這些新興技術(shù)中扮演著重要的角色, 不僅可以減輕本地的存儲(chǔ)負(fù)擔(dān), 還可以幫助系統(tǒng)執(zhí)行復(fù)雜的計(jì)算.

盡管云計(jì)算服務(wù)在數(shù)據(jù)存儲(chǔ)和計(jì)算處理方面具有巨大的優(yōu)勢(shì), 為信息社會(huì)的發(fā)展提供了有力支撐, 但是用戶數(shù)據(jù)泄漏事件時(shí)有發(fā)生, 如何安全地使用云計(jì)算服務(wù)就成為了一個(gè)重要的課題, 其中滿足存儲(chǔ)在云服務(wù)器中數(shù)據(jù)的隱私性是安全使用云計(jì)算服務(wù)的最基本要求. 密碼學(xué)作為保障信息安全的重要方法, 在云計(jì)算安全中發(fā)揮著不可替代的作用. 為保護(hù)云數(shù)據(jù)安全, 用戶可首先使用加密算法對(duì)數(shù)據(jù)進(jìn)行加密處理然后再上傳到云服務(wù)器中存儲(chǔ), 例如可以使用AES、RSA 或者ElGamal 等傳統(tǒng)加密算法將明文數(shù)據(jù)轉(zhuǎn)化為沒(méi)有實(shí)際意義的密文. 為了使用這些加密數(shù)據(jù), 可以采用文獻(xiàn)[12,13] 中提出的“下載-解密-使用” 模式,用戶首先將所需的數(shù)據(jù)下載并存儲(chǔ)到本地, 對(duì)這些數(shù)據(jù)解密得到相應(yīng)的明文數(shù)據(jù)后才可以進(jìn)行后續(xù)的使用和處理. 在該模式下, 對(duì)云服務(wù)器中的加密數(shù)據(jù)進(jìn)行搜索并定位目標(biāo)數(shù)據(jù)是整個(gè)過(guò)程的基礎(chǔ). 但是, 加密數(shù)據(jù)的“無(wú)意義性” 在保證隱私性的同時(shí), 也對(duì)搜索和定位目標(biāo)數(shù)據(jù)帶來(lái)了困難. 數(shù)據(jù)的隱私性與可使用性一直是一對(duì)主要矛盾, 而可搜索加密技術(shù)[14–16]賦予了密文被實(shí)施關(guān)鍵詞搜索的能力, 不僅可以保證數(shù)據(jù)的隱私性, 還突破了傳統(tǒng)加密方案不可對(duì)加密數(shù)據(jù)進(jìn)行搜索的瓶頸.

可搜索加密于2000 年由Song 等人[14]首次提出, 主要分為對(duì)稱可搜索加密(searchable symmetric encryption, SSE)[14]和公鑰可搜索加密(public key encryption with keyword search, PEKS)[15]. 由于SSE 使用的是偽隨機(jī)函數(shù)等對(duì)稱密碼技術(shù), 在運(yùn)行效率方面表現(xiàn)出色, 但由于在生成索引和陷門時(shí)使用同一個(gè)密鑰, 數(shù)據(jù)擁有者和數(shù)據(jù)使用者需要共享密鑰才能實(shí)現(xiàn)對(duì)密文的搜索, 而PEKS 使用的是基于身份的加密等公鑰密碼技術(shù), 因此可以實(shí)現(xiàn)豐富的性質(zhì)和更高的安全性, 但運(yùn)行效率比SSE 低. 如圖1 所示, 可搜索加密有以下四個(gè)步驟:

(1) 加密: 數(shù)據(jù)擁有者在本地使用密鑰對(duì)明文文件加密處理得到密文數(shù)據(jù), 并將其上傳到云服務(wù)器.

(2) 陷門生成: 具有搜索能力的用戶根據(jù)搜索關(guān)鍵詞生成陷門, 并將其上傳到云服務(wù)器.

(3) 搜索: 云服務(wù)器依據(jù)用戶上傳的陷門, 對(duì)密文數(shù)據(jù)進(jìn)行搜索得到匹配的密文文件并返回給用戶.

(4) 解密: 用戶對(duì)服務(wù)器返回的密文文件解密得到對(duì)應(yīng)的明文文件.

早期的大多數(shù)可搜索加密只能實(shí)現(xiàn)完整的、精確的單關(guān)鍵詞搜索, 且將包含搜索關(guān)鍵詞的文件全部返回給用戶. 但在實(shí)際執(zhí)行搜索時(shí), 一方面用戶經(jīng)常會(huì)出現(xiàn)對(duì)要搜索的關(guān)鍵詞記憶不準(zhǔn)確, 拼寫錯(cuò)誤的情形或以兩個(gè)及以上關(guān)鍵詞作為搜索條件; 另一方面, 將包含搜索關(guān)鍵詞的文件全部返回給用戶, 而不考慮文件與搜索關(guān)鍵詞之間相關(guān)性的搜索不僅會(huì)導(dǎo)致不必要的網(wǎng)絡(luò)流量, 而且使得用戶必須對(duì)搜索到的所有文件進(jìn)行處理, 以找到符合他們興趣的文件, 這在當(dāng)今“按需付費(fèi)” 云范例中是不希望出現(xiàn)的. 因此, 為了使得可搜索加密更符合實(shí)際需求, 各種功能多樣化的可搜索加密方案被提出, 例如: 通配符可搜索加密、模糊關(guān)鍵詞可搜索加密、多關(guān)鍵詞可搜索加密等. 為了減少不必要的網(wǎng)絡(luò)流量, 對(duì)于加密云數(shù)據(jù)進(jìn)行有效而安全的排序關(guān)鍵詞搜索方案被提出, 即根據(jù)搜索結(jié)果和排序標(biāo)準(zhǔn)返回與搜索關(guān)鍵詞相關(guān)性最強(qiáng)的前k個(gè)文件, 也被稱為返回top-k結(jié)果的可搜索加密. 我們把符合搜索條件的所有文件全部返回給用戶且只能實(shí)現(xiàn)完整的、精確的單關(guān)鍵詞可搜索加密稱為傳統(tǒng)可搜索加密, 而將通配符、模糊等這種功能多樣化的可搜索加密統(tǒng)稱為復(fù)雜語(yǔ)義可搜索加密.

本文主要對(duì)復(fù)雜語(yǔ)義SSE 進(jìn)行研究, 關(guān)注近年來(lái)通配符、模糊關(guān)鍵詞、多關(guān)鍵詞這三類復(fù)雜語(yǔ)義SSE的研究進(jìn)展, 并對(duì)三者之間的關(guān)系進(jìn)行分析, 最后提出現(xiàn)階段這三類復(fù)雜語(yǔ)義加密搜索需要解決的問(wèn)題和未來(lái)研究思路.

2 復(fù)雜語(yǔ)義對(duì)稱可搜索加密

2.1 通配符對(duì)稱可搜索加密

雖然利用傳統(tǒng)的可搜索加密方案可以實(shí)現(xiàn)在密文中搜索目標(biāo)數(shù)據(jù), 但這些方案都只支持完整的關(guān)鍵詞搜索. 而在實(shí)際搜索時(shí), 用戶經(jīng)常會(huì)出現(xiàn): (1) 對(duì)要搜索的關(guān)鍵詞記憶不準(zhǔn)確或不完整, 例如: 用戶想要搜索2020 年8 月某一天保存的一份文件, 但記不清具體哪天; (2) 不需要準(zhǔn)確搜索, 只需要滿足一個(gè)或多個(gè)屬性, 例如: 在員工信息管理系統(tǒng)里面, 管理員想要搜索居住地為山東省的員工名單.

對(duì)于上述兩種情形, 如果利用傳統(tǒng)的可搜索加密, 則用戶無(wú)法根據(jù)搜索目標(biāo)直接輸入完整的關(guān)鍵詞進(jìn)行搜索, 只能通過(guò)搜索目標(biāo)枚舉所有可能的關(guān)鍵詞, 即對(duì)于情形(1): 用戶對(duì)31 個(gè)關(guān)鍵詞“2020/08/01”、“2020/08/02”、···、“2020/08/31” 分別生成陷門進(jìn)行搜索得到2020 年8 月保存的所有文件然后進(jìn)行篩選得到目標(biāo)文件; 對(duì)于情形(2): 管理員分別對(duì)關(guān)鍵詞“山東省濟(jì)南市”、“山東省臨沂市”、“山東省青島市” 等生成陷門進(jìn)行搜索得到居住地為山東省的員工名單.

顯然, 這種通過(guò)枚舉所有可能的陷門進(jìn)行搜索的方法是不高效的. 因此, 通配符可搜索加密被提出. 通配符主要有“?” 和“*” 兩種, “?” 代表一個(gè)字符, 稱其為單字符通配符; “*” 可以代表任意多個(gè)字符, 稱其為多字符通配符. 對(duì)于上述兩種情形, 用戶可對(duì)關(guān)鍵詞“2020/08/??” 生成陷門, 管理員可對(duì)關(guān)鍵詞“山東省*” 生成陷門進(jìn)行搜索. 因此, 相對(duì)于目標(biāo)為完整關(guān)鍵詞的傳統(tǒng)可搜索加密, 通配符可搜索加密可以支持關(guān)鍵詞的部分匹配而不只限于關(guān)鍵詞的完整匹配, 應(yīng)用更加廣泛.

現(xiàn)有的大多數(shù)通配符SSE 都基于布隆過(guò)濾器(Bloom filter, BF)[17]構(gòu)造索引.

布隆過(guò)濾器于1970 年由布隆提出[17], 是一種可以進(jìn)行集合成員判定的數(shù)據(jù)結(jié)構(gòu). BF 使用一個(gè)m比特的數(shù)組代表一個(gè)集合, 該數(shù)組的所有位置被初始化為0. 對(duì)于一個(gè)給定的集合S={s1,s2,··· ,sn},使用l個(gè)獨(dú)立的哈希函數(shù)hi:{0,1}*→[1,m],1≤i ≤l計(jì)算集合中每個(gè)元素對(duì)應(yīng)的l個(gè)哈希值, 然后將BF 中哈希值對(duì)應(yīng)的位置設(shè)置為1, 這樣就把集合S中的每個(gè)元素插入到了BF 中. 為了判斷一個(gè)元素q是否屬于一個(gè)集合S, 計(jì)算q對(duì)應(yīng)的l個(gè)哈希值h1(q),h2(q),··· ,hl(q), 檢測(cè)集合S對(duì)應(yīng)的BF 中這l個(gè)位置是否全為1, 若有一個(gè)不為1, 則q一定不屬于集合S; 若l個(gè)位置全為1, 則有很大概率認(rèn)為q ∈S,即有一定的概率會(huì)出現(xiàn)假陽(yáng)性, 這是由于這l個(gè)位置可能是由其它元素設(shè)置為1 而不是q. 如圖2 所示為BF 生成的一個(gè)簡(jiǎn)單例子, 其中S={s1,s2},l= 3,h1(s1) = 2,h2(s1) = 7,h3(s1) = 8,h1(s2) = 5,h2(s2)=2,h3(s2)=1:

根據(jù)索引和陷門生成時(shí)對(duì)關(guān)鍵詞的處理方式可將基于BF 的通配符SSE 分為以下兩類:

2.1.1 枚舉

2011 年, B¨osch 等人[18]利用布隆過(guò)濾器與偽隨機(jī)函數(shù)構(gòu)造聯(lián)合通配符對(duì)稱可搜索加密方案. 該方案基于Goh 等人[19]的Z-IDX 索引, 將r個(gè)哈希函數(shù)作用在文件的每個(gè)關(guān)鍵詞上, 映射到布隆過(guò)濾器中, 對(duì)每個(gè)文件生成一個(gè)布隆過(guò)濾器, 把過(guò)濾器作為矩陣的一行, 構(gòu)成一個(gè)n×b階矩陣, 作為所有文件的索引, 其中n是文件的個(gè)數(shù),b是布隆過(guò)濾器的大小. 但由于不同文件中的相同關(guān)鍵詞在布隆過(guò)濾器中的位置是相同的, 敵手可以根據(jù)兩個(gè)文件的布隆過(guò)濾器了解他們的相似性, 因此該方案不能抵抗相關(guān)性攻擊.B¨osch 等人提出隱藏索引的方法以抵抗相關(guān)性攻擊, 即對(duì)布隆過(guò)濾器的每一比特生成一個(gè)掩碼, 與該比特進(jìn)行異或, 得到加密的布隆過(guò)濾器, 將其作為索引上傳到服務(wù)器. 在搜索時(shí), 服務(wù)器基于陷門返回加密過(guò)濾器對(duì)應(yīng)的列, 用戶在本地解密得到搜索結(jié)果. 為了支持通配符搜索, 在構(gòu)造索引時(shí), 根據(jù)通配符在關(guān)鍵詞中的個(gè)數(shù)、位置、代表的字符數(shù)枚舉關(guān)鍵詞通配符形式的變體, 然后將關(guān)鍵詞及其所有的變體映射到過(guò)濾器中. 雖然該方案的效率比文獻(xiàn)[20] 中支持通配符的非對(duì)稱搜索方案有所提高且一個(gè)通配符可以代表多個(gè)字符, 但該方案在進(jìn)行通配符搜索時(shí), 對(duì)關(guān)鍵詞含通配符的形式進(jìn)行枚舉, 并將這些關(guān)鍵詞映射到過(guò)濾器上, 導(dǎo)致預(yù)處理成本大且服務(wù)器端索引存儲(chǔ)量大.

2016 年, Hu 等人[21]提出了一個(gè)多功能對(duì)稱可搜索加密方案, 能夠支持通配符搜索、相似搜索(編輯距離和漢明距離) 和模糊搜索, 并且支持分離關(guān)鍵詞搜索和對(duì)文件的更新. 該方案的索引為倒排索引, 為文件集中每個(gè)不同的關(guān)鍵詞建立一個(gè)布隆過(guò)濾器, 但索引生成方式與文獻(xiàn)[18,19] 有些不同. 為了減少存儲(chǔ)量, 該方案將矩陣型的索引壓縮為數(shù)組形式, 即索引為一個(gè)含有t個(gè)單元的數(shù)組T, 數(shù)組的每個(gè)單元記錄矩陣型索引中每一列為1 的位置對(duì)應(yīng)的關(guān)鍵詞. 對(duì)搜索關(guān)鍵詞生成陷門時(shí), 需要枚舉出所有可能的關(guān)鍵詞, 然后用r個(gè)hash 函數(shù)作用在每個(gè)關(guān)鍵詞上建立一個(gè)BF; 在進(jìn)行相似搜索時(shí), 需要用戶提取出與搜索關(guān)鍵詞的(編輯或漢明) 距離滿足閾值條件的所有關(guān)鍵詞, 然后用r個(gè)hash 函數(shù)作用在每個(gè)關(guān)鍵詞上建立一個(gè)BF 從而得到陷門; 在進(jìn)行模糊搜索時(shí), 需要生成兩個(gè)陷門, 一個(gè)是精確搜索的陷門, 另一個(gè)是相似搜索的陷門. 搜索過(guò)程也與之前方案中的方法不同, 對(duì)于給定的陷門BF 和索引T, 對(duì)BF 的每個(gè)為0 的位置i, 在索引中提取出T[i] 中的所有關(guān)鍵詞, 得到關(guān)鍵詞集S, 計(jì)算S在文件集的所有關(guān)鍵詞中的補(bǔ)集ˉS, 返回給用戶與ˉS中關(guān)鍵詞對(duì)應(yīng)的所有I′, 索引建立與搜索過(guò)程如圖3 所示. 該方案雖然支持多種類型的搜索, 且能夠?qū)崿F(xiàn)多字符通配符搜索, 但在生成陷門時(shí), 需要提取出所有可能的關(guān)鍵詞, 預(yù)處理成本大且搜索時(shí)通信復(fù)雜度大.

2.1.2 提取特征

B¨osch 等人[18]與Hu 等人[21]的方案基于關(guān)鍵詞整體建立索引, 所以需要將關(guān)鍵詞通配符所有可能的形式進(jìn)行枚舉, 效率低, 存儲(chǔ)量大. 為了解決上述問(wèn)題, 文獻(xiàn)[22–25] 提出對(duì)關(guān)鍵詞提取特征實(shí)現(xiàn)通配符搜索的方法.

2012 年, Suga 等人[22]通過(guò)提取關(guān)鍵詞中所有單個(gè)字符對(duì)應(yīng)位置級(jí)聯(lián)字符的特征, 為每個(gè)關(guān)鍵詞構(gòu)造一個(gè)布隆過(guò)濾器, 建立倒排索引, 提出了一個(gè)支持多種類型搜索的可搜索加密方案. 如圖4 所示, 在生成索引時(shí), 首先按字符位置級(jí)聯(lián)字符的方式提取每個(gè)關(guān)鍵詞的特征集合(如cloud 對(duì)應(yīng)的特征集合為{1||c,2||l,3||o,4||u,5||d}), 然后將特征集合中的每個(gè)元素通過(guò)哈希函數(shù)映射到過(guò)濾器中, 生成該關(guān)鍵詞對(duì)應(yīng)的過(guò)濾器索引. 在生成搜索關(guān)鍵詞陷門時(shí), 按相同的方式提取非通配符的字符特征(如*lou* 對(duì)應(yīng)的特征集合為{2||l,3||o,4||u}) 生成過(guò)濾器. 當(dāng)搜索關(guān)鍵詞與索引關(guān)鍵詞匹配時(shí), 搜索關(guān)鍵詞的特征集為索引關(guān)鍵詞特征集的子集, 故在陷門過(guò)濾器為1 的位置, 在索引過(guò)濾器中也必為1. 雖然該方案不需要通過(guò)枚舉的方式來(lái)實(shí)現(xiàn)通配符搜索, 但由于提取特征方式的局限性, 不適用于多字符通配符搜索, 不具有實(shí)用性.

2016 年, Hu 等人[23]為了解決文獻(xiàn)[22] 中一個(gè)通配符只能代表一個(gè)字符的局限性, 提出了一種新的關(guān)鍵詞特征提取方法, 使得一個(gè)通配符可以代表任意多個(gè)字符, 具體操作如下: 對(duì)于陷門中的關(guān)鍵詞, 第一個(gè)通配符前面的字符按正序記錄, 最后一個(gè)通配符后面的字符按倒序記錄, 除此之外, 記錄除通配符外所有字符的存在性(如c*o*d 對(duì)應(yīng)的特征集合為{c||1,d||-1,c||0,o||0,d||0}). 最后, 將這些記錄對(duì)應(yīng)的哈希值添加到過(guò)濾器中. 對(duì)于索引中的關(guān)鍵詞, 分別記錄每個(gè)字符的正序、倒序、存在性, 如cloud 對(duì)應(yīng)的特征集合為:{c||1,l||2,o||3,u||4,d||5,d||-1,u||-2,o||-3,l||-4,c||-5,c||0,l||0,o||0,o||0,u||0,d||0}, 然后將這些記錄的哈希值添加到過(guò)濾器中. 圖5 為上述通配符搜索的一個(gè)具體示例. 由于上述通配符搜索技術(shù)存在一定的的錯(cuò)誤概率, 如關(guān)鍵詞cloud 能夠匹配陷門關(guān)鍵詞c*uo*d 與c*od*, 但cloud 并不滿足這兩個(gè)通配符形式. 因此Hu 等人提出通過(guò)記錄關(guān)鍵詞的n-gram(關(guān)鍵詞中出現(xiàn)的連續(xù)n個(gè)字符)代替上述方法中關(guān)鍵詞字符的存在性來(lái)避免這種錯(cuò)誤. 在上述通配符搜索技術(shù)的基礎(chǔ)上, Hu 等人利用與文獻(xiàn)[22]相同的方法提出了一個(gè)支持通配符搜索的對(duì)稱可搜索加密方案, 并證明該方案達(dá)到了IND-CKA 安全. 但2021 年Chatterjee 等人[26]給出了一個(gè)具體的攻擊, 指出該方案并不能達(dá)到IND-CKA 安全. 該攻擊利用方案在索引和陷門生成時(shí)直接將字符級(jí)聯(lián)位置的哈希值對(duì)應(yīng)的布隆過(guò)濾器的位置設(shè)置為1(即相同的字符在不同的關(guān)鍵詞索引、陷門中對(duì)應(yīng)的哈希值相同), 通過(guò)兩個(gè)關(guān)鍵詞的過(guò)濾器的交集得到兩個(gè)關(guān)鍵詞中公共字符對(duì)應(yīng)的陷門, 進(jìn)而選擇合適的挑戰(zhàn)關(guān)鍵詞集, 使得兩個(gè)關(guān)鍵詞集的索引可區(qū)分.

圖5 通配符搜索Figure 5 Wildcard search

2016 年, Zhao 等人[24]通過(guò)對(duì)文獻(xiàn)[22] 中關(guān)鍵詞特征提取方式的改進(jìn), 使文獻(xiàn)[24] 方案中的通配符搜索能夠同時(shí)支持單字符通配符“?” 與多字符通配符“*”. 但與文獻(xiàn)[22] 的倒排索引不同, Zhao 等人通過(guò)為每個(gè)文件的每個(gè)關(guān)鍵詞建立一個(gè)布隆過(guò)濾器索引, 每個(gè)文件的索引都可以看作一個(gè)m×b的二進(jìn)制矩陣, 其中m表示一個(gè)文件中關(guān)鍵詞的個(gè)數(shù),b表示單個(gè)布隆過(guò)濾器的大小. 與文獻(xiàn)[18] 類似, Zhao 等人首先提出一個(gè)基礎(chǔ)方案, 但該方案不能抵抗相關(guān)性攻擊, 因此在該方案的基礎(chǔ)上, Zhao 等人提出了一個(gè)與文獻(xiàn)[18] 隱藏索引的方式不同的隱藏索引的方案, 首先區(qū)分不同的關(guān)鍵詞在不同文件中的身份, 即為每一個(gè)關(guān)鍵詞對(duì)應(yīng)的過(guò)濾器生成一個(gè)ID, 然后為每個(gè)布隆過(guò)濾器的每個(gè)比特生成一個(gè)掩碼, 并將該掩碼與原過(guò)濾器對(duì)應(yīng)比特進(jìn)行異或, 得到隱藏索引. 搜索時(shí), 在服務(wù)器端進(jìn)行解密得到搜索結(jié)果, 如圖6 所示. 與文獻(xiàn)[18]中2-round 的隱藏索引方案相比, 該隱藏索引方案為1-round, 效率更高. 但因?yàn)槭钦蛩饕? 每個(gè)文件的索引均為一個(gè)m×b的二進(jìn)制矩陣且關(guān)鍵詞的特征提取較為繁瑣, 導(dǎo)致存儲(chǔ)量較大, 搜索速率較低.

圖6 隱藏索引構(gòu)建Figure 6 Building of hidden index

2019 年, 于文[25]在文獻(xiàn)[23] 的基礎(chǔ)上, 利用Lai 等人[27]提出的一種輕量級(jí)對(duì)稱密鑰隱藏向量加密技術(shù), 將文獻(xiàn)[23] 中索引過(guò)濾器和陷門過(guò)濾器分別看作索引向量和查詢向量, 然后對(duì)布隆過(guò)濾器加密(如圖7 所示), 提出了一個(gè)更加安全的通配符搜索方案. 該方案的數(shù)據(jù)保密性更強(qiáng), 而且在搜索時(shí)避免了陷門和索引的兩個(gè)布隆過(guò)濾器之間比特值的一一匹配, 提高了搜索效率. 但在該方案中, 過(guò)濾器的每一比特都要通過(guò)一個(gè)偽隨機(jī)函數(shù)進(jìn)行加密(用帶密鑰的hash 函數(shù), 例如HMAC-SHA256 作為偽隨機(jī)函數(shù)), 生成256 比特的密文, 因此索引的存儲(chǔ)量擴(kuò)大為原來(lái)的256 倍.

圖7 隱藏向量加密示例Figure 7 Example of hidden vector encryption

2.2 模糊關(guān)鍵詞對(duì)稱可搜索加密

傳統(tǒng)的可搜索加密只能實(shí)現(xiàn)精確關(guān)鍵詞的搜索, 而缺乏對(duì)微小的拼寫及格式錯(cuò)誤的容忍, 但這正是在現(xiàn)實(shí)的搜索中經(jīng)常出現(xiàn)的. 例如: 用戶由于粗心在搜索包含關(guān)鍵詞“word” 的文檔時(shí)將搜索關(guān)鍵詞輸入為“woed” 或數(shù)據(jù)擁有者將密文文檔上傳到云服務(wù)器時(shí), 預(yù)設(shè)的關(guān)鍵詞為“PO Box”, 但由于用戶缺乏對(duì)服務(wù)器端數(shù)據(jù)的確切認(rèn)識(shí), 輸入的搜索關(guān)鍵詞為“P.O. Box”.

在上述兩種情形下, 由于關(guān)鍵詞“woed” 與“P.O. Box” 都不是索引關(guān)鍵詞, 故傳統(tǒng)的精確關(guān)鍵詞搜索將無(wú)法返回用戶感興趣的文件.

與精確關(guān)鍵詞相比, 模糊關(guān)鍵詞搜索允許用戶輸入中有微小的拼寫錯(cuò)誤或形式不一致問(wèn)題. 對(duì)于上述兩種情形, 模糊關(guān)鍵詞搜索可以根據(jù)查詢關(guān)鍵詞“woed” 找到包含索引關(guān)鍵詞“word” 的文檔, 可以根據(jù)查詢關(guān)鍵詞“P.O. Box” 找到包含索引關(guān)鍵詞“PO Box” 的文檔. 因此, 模糊關(guān)鍵詞搜索極大地提高了系統(tǒng)可用性和用戶的搜索體驗(yàn).

基于使用的工具, 可將現(xiàn)有的模糊關(guān)鍵詞SSE 分為以下兩類:

2.2.1 編輯距離

編輯距離(edit distance), 又稱萊文斯坦(Levenshtein) 距離, 是指兩個(gè)字符串之間, 由一個(gè)轉(zhuǎn)變?yōu)榱硪粋€(gè)所需要用到的最少編輯操作. 編輯操作包括: (1) 插入(insert), 即在一個(gè)字符串中插入一個(gè)字符; (2)刪除(delete), 即從一個(gè)字符串中刪除一個(gè)字符; (3) 替換(substitute), 即在一個(gè)字符串中將一個(gè)字符改變?yōu)榱硪粋€(gè)字符.

2011 年, Liu 等人[29]指出文獻(xiàn)[28] 中基于通配符的模糊關(guān)鍵詞集構(gòu)造技術(shù)使得方案需要較大的索引存儲(chǔ)空間, 為了減少索引存儲(chǔ)量, 他們提出基于字典的模糊關(guān)鍵詞集構(gòu)造方法, 即模糊關(guān)鍵詞集中的關(guān)鍵詞必須是字典中有意義的詞匯, 從而減少無(wú)意義的候選關(guān)鍵詞, 進(jìn)而減少了文檔索引所需的存儲(chǔ)空間,同時(shí)減少了搜索時(shí)陷門與索引的匹配時(shí)間, 提高了搜索效率.

雖然基于字典的模糊關(guān)鍵詞集構(gòu)造方法較基于通配符的模糊關(guān)鍵詞集構(gòu)造極大的減少了存儲(chǔ)空間, 提高了效率, 但這兩個(gè)方案都是通過(guò)構(gòu)造模糊關(guān)鍵詞集實(shí)現(xiàn)模糊搜索的功能, 索引大小都與關(guān)鍵詞數(shù)量成線性關(guān)系.

2.2.2 局部敏感哈希

局部敏感哈希(locality sensitive hashing, LSH)[30]是一種針對(duì)海量高維數(shù)據(jù)的快速最近鄰查找算法, 其基本思想是: 給定一個(gè)度量距離, 原始高維數(shù)據(jù)空間中的兩個(gè)相鄰的數(shù)據(jù)點(diǎn)通過(guò)相同的映射或投影變換后會(huì)有很大概率被映射到新的低維空間的同一位置, 而不相鄰的兩個(gè)數(shù)據(jù)點(diǎn)被映射到低維空間相同位置的概率很小. 一個(gè)哈希函數(shù)簇H是(r1,r2,p1,p2)-敏感的如果對(duì)于任意兩點(diǎn)s,t和h ∈H滿足:

其中d(s,t) 為點(diǎn)s和點(diǎn)t之間的距離.

依據(jù)搜索的數(shù)據(jù)類型, 可將基于LSH 的模糊關(guān)鍵詞SSE 分為以下三類:

(1) 英文關(guān)鍵詞

2012 年, Kuzu 等人[31]基于局部敏感哈希設(shè)計(jì)了一個(gè)支持模糊搜索的密文搜索方案, 該方案利用LSH 將相似的關(guān)鍵詞以較高的概率映到相同的桶中, 而不相似的關(guān)鍵詞映到相同桶中的概率較低的特點(diǎn)來(lái)篩選搜索結(jié)果, 而不需要構(gòu)造模糊關(guān)鍵詞集. 具體地, 如圖8 所示, 在構(gòu)造索引時(shí), 首先提取每個(gè)文件的特征(關(guān)鍵詞); 其次, 將特征轉(zhuǎn)化為其對(duì)應(yīng)的向量; 然后利用min-hash 將特征向量映到對(duì)應(yīng)的桶中, 桶中存儲(chǔ)特征對(duì)應(yīng)的比特向量, 即向量的每個(gè)分量對(duì)應(yīng)文件集的一個(gè)文件, 若文件包含該特征, 則對(duì)應(yīng)分量為1, 否則為0; 最后, 分別利用偽隨機(jī)置換和選擇明文攻擊偽隨機(jī)性(pseudo-randomness against chosen plaintext attacks, PCPA) 安全的加密方案加密桶的標(biāo)識(shí)符和桶中的比特向量. 搜索時(shí), 需要兩輪交互才能搜索到匹配的密文文檔. 具體地, 用戶按照與索引構(gòu)造時(shí)相同的方式生成詢問(wèn)特征對(duì)應(yīng)的桶標(biāo)識(shí)符, 并利用偽隨機(jī)置換生成陷門, 服務(wù)器返回陷門對(duì)應(yīng)桶中加密的比特向量并將其發(fā)送給用戶, 用戶利用密鑰解密, 得到最終需要的文件標(biāo)識(shí)符, 并向服務(wù)器請(qǐng)求返回對(duì)應(yīng)密文文件.

圖8 LSH 索引Figure 8 LSH 索引

為了防止訪問(wèn)模式的泄露, 基于上述基礎(chǔ)的搜索方案, 文獻(xiàn)[31] 又提出了一個(gè)雙服務(wù)器的搜索方案.在該雙服務(wù)器方案中, 假設(shè)兩個(gè)服務(wù)器都是誠(chéng)實(shí)但好奇的, 且服務(wù)器之間不會(huì)共謀, 數(shù)據(jù)擁有者將索引和密文文件分別發(fā)送給兩個(gè)服務(wù)器, 在搜索時(shí)兩個(gè)服務(wù)器各執(zhí)行基礎(chǔ)搜索方案兩輪交互中的一輪. 進(jìn)一步地,在雙服務(wù)器搜索方案的基礎(chǔ)上, 為了減輕用戶端的計(jì)算負(fù)擔(dān), 文獻(xiàn)[31] 使用Paillier 加密實(shí)現(xiàn)了雙服務(wù)器下的一輪交互搜索方案.

雖然文獻(xiàn)[31] 利用LSH 生成索引, 使得不需要構(gòu)造模糊關(guān)鍵詞集也實(shí)現(xiàn)了模糊搜索功能, 但該方案需要兩輪交互且僅支持單關(guān)鍵詞搜索.

2014 年, Wang 等人[32]利用局部敏感哈希技術(shù)提出了一個(gè)在已知密文模型下安全的多關(guān)鍵詞模糊搜索方案. 與文獻(xiàn)[31] 不同的是, 在將關(guān)鍵詞轉(zhuǎn)化為具有LSH 的度量空間對(duì)應(yīng)的向量時(shí), 文獻(xiàn)[31]利用bigram (關(guān)鍵詞中出現(xiàn)的連續(xù)兩個(gè)字符) 的哈希值生成關(guān)鍵詞對(duì)應(yīng)向量, 而該方案直接利用關(guān)鍵詞的bigram 生成對(duì)應(yīng)的bigram 向量, 從而避免了生成向量時(shí)哈希碰撞的情形; 其次在文獻(xiàn)[31] 中通過(guò)Jaccard 距離度量相似性, 進(jìn)而利用min-hash 生成索引, 而該方案通過(guò)歐幾里得距離度量相似性, 利用p-stable hash 生成索引. 具體地, 如圖9 所示, 一個(gè)關(guān)鍵詞首先被轉(zhuǎn)化為一個(gè)bigram 集, 然后使用一個(gè)262維的比特向量來(lái)表示一個(gè)bigram 集, 向量中的每個(gè)分量代表所有262個(gè)bigram 中的其中一個(gè). 對(duì)于一個(gè)給定關(guān)鍵詞的bigram 集, 將出現(xiàn)在bigram 集中的bigram 對(duì)應(yīng)分量設(shè)置為1; 其次, 為每個(gè)文件構(gòu)造一個(gè)BF 索引, 將文件集中包含的所有關(guān)鍵詞對(duì)應(yīng)的bigram 向量通過(guò)p-stable hash 映到過(guò)濾器中,即將bigram 向量對(duì)應(yīng)的p-stable hash 值對(duì)應(yīng)的BF 位置設(shè)置為1. 按照同樣的方式可生成搜索關(guān)鍵詞(集) 對(duì)應(yīng)的向量. 為了保護(hù)關(guān)鍵詞的隱私, 利用安全KNN 加密文件向量與詢問(wèn)向量生成安全索引與陷門. 搜索時(shí), 計(jì)算陷門與每個(gè)文件的安全索引的內(nèi)積即可得到搜索關(guān)鍵詞(集) 與文件的相關(guān)性得分, 內(nèi)積越大, 則有越大的概率說(shuō)明文件包含越多的搜索關(guān)鍵詞. 為了進(jìn)一步地提高安全性, 基于基礎(chǔ)方案, Wang等人通過(guò)將原本的LSH 替換為一個(gè)偽隨機(jī)函數(shù)與p-stable hash 函數(shù)的復(fù)合得到了一個(gè)在已知背景模型下安全的模糊搜索方案.

2017 年, Fu 等人[33]指出在文獻(xiàn)[32] 中將關(guān)鍵詞轉(zhuǎn)化為bigram 會(huì)增大歐幾里得距離, 對(duì)除一個(gè)字母拼寫錯(cuò)誤以外的其它拼寫錯(cuò)誤不是有效的, 并且該方案不支持相同詞根的關(guān)鍵詞搜索, 也沒(méi)有考慮關(guān)鍵詞和文件之間的相關(guān)性. 基于上述弊端, 如圖10 所示, Fu 等人進(jìn)行了以下幾點(diǎn)改進(jìn): 引入詞根提取算法(stemming algorithm) 使得可以實(shí)現(xiàn)相同詞根的關(guān)鍵詞搜索; 將關(guān)鍵詞轉(zhuǎn)化為uni-gram (關(guān)鍵詞中出現(xiàn)的單個(gè)字符), 可以有效減小歐幾里得距離; 將文件與關(guān)鍵詞的相關(guān)性考慮在內(nèi), 即將關(guān)鍵詞向量通過(guò)哈希映到過(guò)濾器時(shí), 將對(duì)應(yīng)的哈希值位置設(shè)置為關(guān)鍵詞對(duì)應(yīng)的相關(guān)性分?jǐn)?shù)而不是1, 體現(xiàn)了關(guān)鍵詞和文件之間的相關(guān)性. 基于以上改進(jìn), 文獻(xiàn)[33] 實(shí)現(xiàn)了更有效、準(zhǔn)確的多關(guān)鍵詞模糊搜索.

圖10 有效的多關(guān)鍵詞模糊搜索Figure 10 Efficient multi-keyword fuzzy search

2017 年, Yang 等人[34]通過(guò)對(duì)關(guān)鍵詞提取n-gram 特征, 將傳統(tǒng)的針對(duì)文檔的sim-hash 算法改進(jìn)使其能夠?qū)﹃P(guān)鍵詞生成指紋, 從而對(duì)文件集建立倒排索引, 搜索時(shí)計(jì)算搜索關(guān)鍵詞對(duì)應(yīng)的sim-hash 指紋,并計(jì)算索引關(guān)鍵詞和搜索關(guān)鍵詞sim-hash 指紋之間的漢明距離, 然后依據(jù)漢明距離從小到大的順序?qū)op-k的密文文件返回給用戶. 但由于包含一個(gè)關(guān)鍵詞的文檔往往不只一篇, 因此僅僅基于漢明距離只能實(shí)現(xiàn)較粗糙的排序結(jié)果. 為了實(shí)現(xiàn)更細(xì)粒度的排序, 利用TF-IDF 原則計(jì)算關(guān)鍵詞的相關(guān)度分?jǐn)?shù), 并對(duì)其進(jìn)行保序加密操作, 實(shí)現(xiàn)了相關(guān)度分?jǐn)?shù)的隱私保護(hù), 最后按照漢明距離優(yōu)先, 相關(guān)度分?jǐn)?shù)次之的雙因子排序規(guī)則實(shí)現(xiàn)了更精確的排序. 更進(jìn)一步地, 為了使得方案更適用于海量數(shù)據(jù)集, 通過(guò)構(gòu)造指紋索引樹來(lái)提高搜索效率, 同時(shí)為了達(dá)到在不需要遍歷整棵樹的情況下能夠比較漢明距離, 設(shè)計(jì)了一種新型的遍歷方法.

2019 年, Cao 等人[35]指出為了實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的模糊關(guān)鍵詞搜索, 在對(duì)關(guān)鍵詞預(yù)處理時(shí), Wang 等人[32]提出的“2-gram” 方法只對(duì)拼寫錯(cuò)誤的模糊搜索有效, 而不能有效的處理字母順序顛倒, 增加或刪除字母的情況, Fu 等人[33]提出的“uni-gram” 方法雖然在處理字母順序顛倒, 增加或刪除字母的情況時(shí)比“2-gram” 更有效, 但由于其缺少字母順序的信息, 因此文獻(xiàn)[33] 無(wú)法識(shí)別“相同字母異序詞”, 例如:“devil” 與“l(fā)ived”. 因此, 為了提高搜索準(zhǔn)確性, Cao 等人提出一種新穎的方法將關(guān)鍵詞轉(zhuǎn)化為“orderpreserved uni-gram(OPU)” 向量. 具體地, 每個(gè)關(guān)鍵詞被轉(zhuǎn)化為一個(gè)u×26+30 維的向量, 其中u為關(guān)鍵詞中的字母數(shù), 可以將該向量看作u個(gè)字母塊和一個(gè)數(shù)字與符號(hào)塊, 一個(gè)字母塊對(duì)應(yīng)26 比特, 代表26個(gè)英文字母‘a(chǎn)’ 到‘z’, 關(guān)鍵詞中出現(xiàn)的字母對(duì)應(yīng)分量為1, 其余為0. 數(shù)字與符號(hào)塊共對(duì)應(yīng)30 比特, 其中10 比特對(duì)應(yīng)數(shù)字‘0’ 到‘9’, 剩余20 比特對(duì)應(yīng)關(guān)鍵詞中廣泛出現(xiàn)的符號(hào). 進(jìn)一步地, 為了減弱字母順序的混亂對(duì)搜索準(zhǔn)確性的影響, Cao 等人引入一個(gè)“傳感” 機(jī)制, 將原本的二進(jìn)制向量轉(zhuǎn)化為浮點(diǎn)數(shù)向量. 每個(gè)關(guān)鍵詞轉(zhuǎn)化為向量后, 利用LSH 得到BF, 然后將每個(gè)文件包含的關(guān)鍵詞對(duì)應(yīng)的BF 合并得到每個(gè)文件對(duì)應(yīng)的BF. 為了提高搜索效率, Cao 等人基于k-means 聚類算法將相似的文件劃分到一個(gè)類中進(jìn)而得到一個(gè)等級(jí)索引樹(hierarchical index tree, HIT), 最后利用安全KNN 加密HIT 的每個(gè)結(jié)點(diǎn)保證安全性和隱私性.

2020 年, Zhong 等人[36]指出雖然文獻(xiàn)[33] 比文獻(xiàn)[32] 有更準(zhǔn)確的搜索結(jié)果, 但其搜索時(shí)間與文件數(shù)量n成正比, 即為O(n), 搜索效率低. 因此基于文獻(xiàn)[33], Zhong 等人引入平衡二叉樹將所有的BF 索引聚合到一起, 使得搜索時(shí)間減少為O(rlogn).

(2) 中文關(guān)鍵詞

雖然上述方案[31–36]在無(wú)需構(gòu)造模糊關(guān)鍵詞集的情況下可以實(shí)現(xiàn)模糊關(guān)鍵詞搜索, 但這些方案都旨在實(shí)現(xiàn)英文關(guān)鍵詞的模糊搜索, 而漢字是典型的非字母語(yǔ)言, 詞語(yǔ)是靈活多樣的, 因此上述方案不適用于中文關(guān)鍵詞的模糊關(guān)鍵詞搜索.

2019 年, Yang 等人[37]在設(shè)計(jì)了兩個(gè)中文關(guān)鍵字向量生成算法的基礎(chǔ)上, 利用文獻(xiàn)[32] 的思想, 通過(guò)LSH 和BF 提出了兩個(gè)可以用于中文字符的模糊多關(guān)鍵詞排序可搜索加密. 具體地, 在第一個(gè)基礎(chǔ)中文多關(guān)鍵詞模糊排序搜索方案(basic Chinese multi-keyword fuzzy rank search scheme, BCMS) 中, 中文關(guān)鍵詞向量生成算法將一個(gè)中文關(guān)鍵詞轉(zhuǎn)換為一個(gè)拼音串, 該拼音串又被分為聲母、韻母和聲調(diào)三部分.關(guān)鍵詞向量的結(jié)構(gòu)如圖11 所示, 方案使用一個(gè)63 比特的向量代表一個(gè)關(guān)鍵詞, 前23 比特代表中文的23個(gè)聲母, 中間的24 比特代表24 個(gè)韻母, 最后的16 比特代表關(guān)鍵詞中詞的位置和聲調(diào)(為“ab” 這樣的形式, 其中“a” 代表在關(guān)鍵詞中的第1–4 個(gè)詞, “b” 代表漢語(yǔ)拼音的四個(gè)聲調(diào)). 如果該元素存在于拼音字符串中, 則對(duì)應(yīng)位置被設(shè)置為1, 否則設(shè)置為0. 例如, 關(guān)鍵詞“實(shí)驗(yàn)” 的音節(jié)分割集為{sh,i,12,y,an,24},其中“12” 表示在關(guān)鍵詞“實(shí)驗(yàn)” 中第一個(gè)詞“實(shí)” 為二聲, “24” 表示第二個(gè)詞“驗(yàn)” 為四聲. 由于在基礎(chǔ)方案中, 關(guān)鍵詞向量生成算法沒(méi)有考慮不同方式拼寫錯(cuò)誤的差異, 也沒(méi)有考慮關(guān)鍵詞術(shù)語(yǔ)的權(quán)重, 導(dǎo)致搜索結(jié)果不夠準(zhǔn)確. 因此為了提高搜索準(zhǔn)確性, 基于BCMS, 提出了一個(gè)增強(qiáng)的中文多關(guān)鍵詞模糊排序搜索方案(enhanced Chinese multi-keyword fuzzy rank search scheme, ECMS), 該方案基于uni-gram 將一個(gè)拼音串轉(zhuǎn)換為一個(gè)關(guān)鍵詞向量, 擴(kuò)大了拼音字符串中不同方式拼寫錯(cuò)誤的差異, 從而使排序結(jié)果更加準(zhǔn)確. 具體地, 該關(guān)鍵詞向量生成算法將中文關(guān)鍵詞轉(zhuǎn)換為一個(gè)拼音串, 然后使用uni-gram 方法分離拼音串. 關(guān)鍵詞向量的結(jié)構(gòu)如圖12 所示, 方案使用一個(gè)120 比特的向量代表一個(gè)關(guān)鍵詞, 第一個(gè)26 比特代表關(guān)鍵詞中第一個(gè)詞的英文26 個(gè)字符, 同理第二個(gè)、第三個(gè)、第四個(gè)26 比特分別代表第二、三、四個(gè)詞的英文26 個(gè)字符, 最后16 比特代表詞的位置和聲調(diào)(BCMS). 如果該元素存在于拼音字符串中, 則對(duì)應(yīng)位置被設(shè)置為1, 否則設(shè)置為0, 例如, 關(guān)鍵詞“故事” 的音節(jié)分割集為{g1,u1,14,s2,h2,i2,24}, 其中“g1”表示英文字符“g” 來(lái)自第一個(gè)詞“故”. 此外, 增強(qiáng)的方案通過(guò)結(jié)合關(guān)鍵詞向量的歐幾里得距離, 關(guān)鍵詞頻率和加權(quán)區(qū)域得分提出了一個(gè)三因子排序算法, 進(jìn)一步提高了搜索準(zhǔn)確性.

圖11 基礎(chǔ)方案關(guān)鍵詞向量Figure 11 Keyword vector in BCMS

圖12 增強(qiáng)方案關(guān)鍵詞向量Figure 12 Keyword vector in ECMS

(3) 功能多樣的數(shù)據(jù)

雖然上述提到的方案[31–37]基于LSH 實(shí)現(xiàn)了模糊關(guān)鍵詞搜索, 但由于用戶上傳到云服務(wù)器的文件不只有文本文件, 故設(shè)計(jì)能夠?qū)τ诟鞣N類型的加密文件, 例如: 圖像、音頻、視頻文件的模糊可搜索方案是很有必要的.

2016 年, Wang 等人[38]通過(guò)將搜索標(biāo)準(zhǔn)視為高維特征向量而不是關(guān)鍵詞, 解決了在加密的功能豐富的多媒體數(shù)據(jù)上支持大規(guī)模相似性搜索的挑戰(zhàn). Wang 等人利用特征提取算法, 對(duì)文件提取特征進(jìn)而得到每個(gè)文件fi對(duì)應(yīng)的特征向量pi, 然后計(jì)算每個(gè)特征向量對(duì)應(yīng)的LSH 值的方式構(gòu)造索引. 具體地, 如圖13 所示,M個(gè)LSH 哈希函數(shù)被用來(lái)生成M個(gè)哈希表, 每個(gè)哈希表對(duì)應(yīng)有m個(gè)桶, 故共有Mm個(gè)桶,依次計(jì)算每個(gè)文件特征向量對(duì)應(yīng)的M個(gè)桶, 然后將其對(duì)應(yīng)的倒排文件向量(inverter file identifier, IFV)存儲(chǔ)于桶中, IFV 的每個(gè)分量對(duì)應(yīng)一個(gè)文件, 分量為1 則代表該文件的特征向量被LSH 映到桶中. 計(jì)算每個(gè)桶中存儲(chǔ)的所有的IFV 的或得到該桶對(duì)應(yīng)的IFV, 為了減小搜索結(jié)果假陽(yáng)性的概率, 桶中最終存儲(chǔ)的IFV 為其左右相鄰的桶對(duì)應(yīng)的IFV 與自身的IFV 的或, 另外, 通過(guò)相同的方式構(gòu)造所要添加文件的子索引或?qū)FV 中所要?jiǎng)h除文件對(duì)應(yīng)分量設(shè)置為0 的方式可以實(shí)現(xiàn)文件動(dòng)態(tài)的增加或刪除. 搜索時(shí), 利用相同的方式, 得到搜索文件對(duì)應(yīng)的M個(gè)桶的位置, 對(duì)M個(gè)桶中IFV 求交得到一個(gè)新的向量, 將該向量為1 的分量對(duì)應(yīng)的密文文件返回給用戶. 在上述沒(méi)有保護(hù)索引隱私的基礎(chǔ)構(gòu)造的基礎(chǔ)上, Wang 等人分別利用Paillier 同態(tài)加密和偽隨機(jī)置換加密IFV 設(shè)計(jì)了兩個(gè)適應(yīng)性選擇詢問(wèn)攻擊安全和前向安全的相似搜索方案.

圖13 基礎(chǔ)索引結(jié)構(gòu)Figure 13 Structure of basic index

2.3 多關(guān)鍵詞對(duì)稱可搜索加密

在傳統(tǒng)的可搜索加密方案中, 用戶只能通過(guò)對(duì)單個(gè)關(guān)鍵詞生成陷門的方式進(jìn)行搜索. 但在實(shí)際執(zhí)行搜索操作時(shí), 僅使用一個(gè)關(guān)鍵詞往往無(wú)法準(zhǔn)確描述需要搜索的目標(biāo)數(shù)據(jù), 例如: 管理員需要在學(xué)生信息管理系統(tǒng)搜索“碩士二年級(jí)” 或“碩士三年級(jí)” 的學(xué)生名單.

對(duì)于上述情形, 如果利用傳統(tǒng)的可搜索加密, 通常有兩種方法可以采用: (1) 為每個(gè)關(guān)鍵詞分別生成陷門, 對(duì)每個(gè)關(guān)鍵詞單獨(dú)進(jìn)行搜索, 再根據(jù)搜索關(guān)鍵詞之間的邏輯關(guān)系對(duì)搜索結(jié)果進(jìn)行交并集運(yùn)算(由服務(wù)器或用戶執(zhí)行) 確定最終的文檔集, 例如: 用戶分別對(duì)關(guān)鍵詞“碩士”、“二年級(jí)” 與“三年級(jí)” 生成陷門, 記作T1,T2,T3, 然后將T1,T2,T3上傳到云服務(wù)器. 云服務(wù)器在接收到陷門后, 根據(jù)安全索引進(jìn)行搜索得到分別包含關(guān)鍵詞“碩士”、“二年級(jí)”與“三年級(jí)”的文件標(biāo)識(shí)符,記作id1,id2,id3,然后將id1,id2,id3返回給用戶, 用戶端計(jì)算(id1∩id2)∪(id1∩id3), 得到最終的搜索結(jié)果id 集并向服務(wù)器請(qǐng)求返回密文文件. 或者用戶也可以在上傳陷門的同時(shí), 將搜索關(guān)鍵詞對(duì)應(yīng)的邏輯關(guān)系上傳到云服務(wù)器, 即(T1∩T2)∪(T1∩T3),這時(shí)服務(wù)器在搜索得到單關(guān)鍵詞對(duì)應(yīng)的文件id 后, 可以直接進(jìn)行交并運(yùn)算, 最后返回對(duì)應(yīng)密文文檔; (2)對(duì)所有可能要搜索的關(guān)鍵詞組合建立索引存儲(chǔ)在服務(wù)器端, 以方便進(jìn)行此類搜索, 例如: 用戶除對(duì)所有的單關(guān)鍵詞建立索引之外, 對(duì)“(碩士∩二年級(jí))∪(碩士∩三年級(jí))” 也生成相應(yīng)的索引. 搜索時(shí), 生成(碩士∩二年級(jí))∪(碩士∩三年級(jí)) 對(duì)應(yīng)陷門發(fā)送給服務(wù)器, 服務(wù)器根據(jù)安全索引進(jìn)行搜索得到對(duì)應(yīng)密文文件返回給用戶.

顯然, 上述兩種利用傳統(tǒng)可搜索加密搜索的方法都是不可取的. 方法(1) 會(huì)使服務(wù)器獲知與每個(gè)單關(guān)鍵詞匹配的文檔, 泄露過(guò)多的信息; 方法(2) 會(huì)使索引存儲(chǔ)以指數(shù)形式增長(zhǎng). 因此, 設(shè)計(jì)專門針對(duì)多關(guān)鍵詞搜索的可搜索加密方案是很有實(shí)際意義和價(jià)值的.

根據(jù)搜索的多個(gè)關(guān)鍵詞之間的邏輯關(guān)系, 可將多關(guān)鍵詞可搜索加密分為以下三類:

(1) 聯(lián)合關(guān)鍵詞搜索(conjunctive-keyword search). 聯(lián)合關(guān)鍵詞搜索為多個(gè)關(guān)鍵詞之間的邏輯關(guān)系為交的搜索, 即搜索同時(shí)包含搜索關(guān)鍵詞集中所有關(guān)鍵詞的文件.

(2) 分離關(guān)鍵詞搜索(disjunctive-keyword search). 分離關(guān)鍵詞搜索為多個(gè)關(guān)鍵詞的邏輯關(guān)系為并的搜索, 即搜索包含搜索關(guān)鍵詞集中關(guān)鍵詞的文件.

(3) 布爾搜索(Boolean search). 布爾搜索是指多個(gè)關(guān)鍵詞之間的邏輯關(guān)系為布爾運(yùn)算的搜索.

上述三種類型的搜索統(tǒng)稱為一般多關(guān)鍵詞可搜索加密. 在實(shí)際搜索中, 為了提高搜索準(zhǔn)確性, 減少帶寬開銷, 用戶往往需要服務(wù)器根據(jù)搜索結(jié)果和排序標(biāo)準(zhǔn)返回與搜索條件相關(guān)性最強(qiáng)的前k個(gè)文件, 這種搜索稱為多關(guān)鍵詞排序可搜索加密.

因此, 基于是否對(duì)搜索結(jié)果排序, 可將現(xiàn)有的多關(guān)鍵詞SSE 方案分為以下兩類:

2.3.1 一般多關(guān)鍵詞可搜索加密

2004 年, Golle 等人[39]最早對(duì)多關(guān)鍵詞可搜索加密進(jìn)行研究. 首先針對(duì)聯(lián)合關(guān)鍵詞形式的搜索定義了一個(gè)新的安全模型: 選擇關(guān)鍵詞攻擊索引不可區(qū)分(indistinguishability of ciphertext from ciphertext,ICC), 與IND-CKA 本質(zhì)上相同, 但由于該安全模型是針對(duì)聯(lián)合關(guān)鍵詞搜索提出的, 故在詢問(wèn)階段ICC 允許詢問(wèn)聯(lián)合關(guān)鍵詞的陷門, 而在IND-CKA 中只允許詢問(wèn)單關(guān)鍵詞的陷門. 其次提出了兩個(gè)滿足ICC 安全的支持聯(lián)合關(guān)鍵詞搜索的可搜索加密方案, 第一個(gè)方案無(wú)需雙線性對(duì)運(yùn)算, 只通過(guò)簡(jiǎn)單的指數(shù)運(yùn)算和偽隨機(jī)函數(shù)作用即可完成多關(guān)鍵詞搜索, 安全性依賴于Decisional Diffie-Hellman (DDH) 假設(shè), 每次查詢的通信復(fù)雜度成本與文件集的大小n成線性關(guān)系, 然而, 該成本的線性部分可以被預(yù)先發(fā)送, 當(dāng)用戶確定感興趣的查詢關(guān)鍵詞時(shí), 用戶發(fā)送常數(shù)大小的查詢部分. 第二個(gè)方案的通信復(fù)雜度為常數(shù), 但因基于雙線性映射, 在搜索時(shí)需要雙線性對(duì)計(jì)算, 效率較低, 該方案的安全性依賴于Bilinear Decisional Diffie-Hellman(BDDH) 假設(shè).

文獻(xiàn)[39] 實(shí)現(xiàn)了對(duì)于加密數(shù)據(jù)的聯(lián)合關(guān)鍵詞搜索功能, 雖然達(dá)到了ICC 安全, 但I(xiàn)CC 安全模型并沒(méi)有考慮陷門的安全性, 在這兩個(gè)方案中服務(wù)器都會(huì)知道用戶搜索的關(guān)鍵詞字段. 另外這兩個(gè)方案都是通過(guò)構(gòu)造正向索引, 依次遍歷文件索引進(jìn)行搜索, 即搜索時(shí)間復(fù)雜度與文件數(shù)量成線性關(guān)系, 因此該方法只適用于小型數(shù)據(jù)庫(kù).

2005 年, Ballard 等人[40]提出了兩個(gè)聯(lián)合關(guān)鍵詞對(duì)稱可搜索加密方案. 第一個(gè)方案基于Shamir 秘密共享, 雖然在效率方面較文獻(xiàn)[39] 有所提升, 但通訊復(fù)雜度仍與文件數(shù)量成線性關(guān)系. 為了解決該問(wèn)題,提出了第二個(gè)方案, 該方案基于雙線性對(duì), 以服務(wù)器端大量的計(jì)算量為代價(jià)使得通訊復(fù)雜度為常數(shù), 比文獻(xiàn)[39] 提出的通訊復(fù)雜度為常數(shù)的方案更為有效. 兩個(gè)方案都在標(biāo)準(zhǔn)模型下是可證安全的.

雖然文獻(xiàn)[40] 比文獻(xiàn)[39] 更為有效, 但與文獻(xiàn)[39] 有相同的缺陷, 在搜索時(shí)仍會(huì)泄露搜索關(guān)鍵詞對(duì)應(yīng)的字段, 索引也為正向索引, 即只適用于小型數(shù)據(jù)庫(kù).

對(duì)稱可搜索加密中存在一個(gè)特定的安全問(wèn)題, 當(dāng)執(zhí)行聯(lián)合關(guān)鍵詞搜索時(shí), 陷門和搜索結(jié)果會(huì)揭示搜索關(guān)鍵詞之間的關(guān)系. 例如, 如果關(guān)鍵詞集A 的搜索結(jié)果是關(guān)鍵詞集B 的超集, 則有很大概率說(shuō)明A 是B的子集. 而大多數(shù)支持聯(lián)合關(guān)鍵詞搜索的方案[39,40]都不能抵抗這種包含關(guān)系(inclusion-relation, IR) 的攻擊.

2013 年, Cai 等人[41]首次給出了針對(duì)IR 攻擊正式的安全性定義IR-secure, 并提出了一個(gè)基于BF的安全聯(lián)合關(guān)鍵詞搜索方案CKS-SE. CKS-SE 通過(guò)在生成陷門時(shí)在搜索關(guān)鍵詞集對(duì)應(yīng)的偽隨機(jī)函數(shù)值集合中隨機(jī)選取t個(gè)值, 而不是全部的偽隨機(jī)函數(shù)值作為陷門, 使得搜索關(guān)鍵詞集與陷門之間生成多對(duì)多映射, 從而達(dá)到IR-secure.

2013 年, Cash 等人[42]指出通過(guò)對(duì)搜索關(guān)鍵詞集中每個(gè)關(guān)鍵詞進(jìn)行單關(guān)鍵詞搜索然后對(duì)搜索結(jié)果求交實(shí)現(xiàn)聯(lián)合關(guān)鍵詞搜索的方法復(fù)雜度高且泄露信息較多. 另外在現(xiàn)有的可以實(shí)現(xiàn)聯(lián)合關(guān)鍵詞搜索的方案[39,40] 中搜索效率與文件數(shù)量d成線性關(guān)系, 要么需要O(d) 的通信復(fù)雜度, 要么需要復(fù)雜度為O(d)的雙線性對(duì)運(yùn)算, 且都不能擴(kuò)展到一般的布爾搜索. 因此, Cash 等人提出了第一個(gè)搜索效率為亞線性, 可以實(shí)現(xiàn)聯(lián)合關(guān)鍵詞搜索, 且可以擴(kuò)展到一般布爾搜索的可搜索加密方案OXT(oblivious cross-tags) 協(xié)議.在提出OXT 之前提出了一個(gè)基礎(chǔ)協(xié)議BXT, BXT 利用了兩個(gè)數(shù)據(jù)結(jié)構(gòu)T-set 和X-set, T-set 和X-set存儲(chǔ)的都為包含對(duì)應(yīng)關(guān)鍵詞的文件標(biāo)識(shí)符(identifier, ind) 向量, 但形式不同. T-set 中存儲(chǔ)包含對(duì)應(yīng)關(guān)鍵詞ind 的密文(稱為stag), 與倒排索引類似; X-set 存儲(chǔ)(w,ind) 形式的密文(稱為xtag). 搜索時(shí), 用戶首先選取搜索關(guān)鍵詞集中詞頻最低的關(guān)鍵詞(稱為s-term), 生成對(duì)應(yīng)的stag, 并生成其余搜索關(guān)鍵詞(稱為x-term) 對(duì)應(yīng)的xtrap, 然后將所有的stag, xtrap 及最低詞頻關(guān)鍵詞加密ind 的密鑰上傳到服務(wù)器. 服務(wù)器首先依據(jù)stag 對(duì)T-set 進(jìn)行搜索得到包含最低詞頻關(guān)鍵詞的密文ind, 并利用密鑰解密得到明文ind集, 然后利用xtrap 對(duì)X-set 檢測(cè)ind 集中每個(gè)文件是否包含其余關(guān)鍵詞. BXT 使得聯(lián)合關(guān)鍵詞的搜索復(fù)雜度降為O(min{DB(wi)}), DB(wi) 為包含wi的文件數(shù), 泄露的信息集中在min{DB(wi)}中ind與其他關(guān)鍵詞的關(guān)系, 安全性有所提升. 但由于在生成陷門時(shí)xtag 與stag 是獨(dú)立的, 故服務(wù)器可以通過(guò)在一次搜索中得到的xtrap 對(duì)另一次搜索中包含s-term 的ind 進(jìn)行檢測(cè), 例如: 通過(guò)搜索歷史(w1,w2)與(w′1,w′2), 服務(wù)器可以知道(w1,w′2) 與(w′1,w2) 的搜索結(jié)果.

為了解決上述問(wèn)題, Cash 等人最終提出OXT 協(xié)議, 更改主要體現(xiàn)在生成陷門時(shí), 使得x-term 的陷門與s-term 的陷門不是獨(dú)立的, 進(jìn)而服務(wù)器不能由用戶生成過(guò)的搜索陷門生成新的搜索陷門, 進(jìn)一步提高了安全性.

雖然文獻(xiàn)[42]可以實(shí)現(xiàn)一般的布爾搜索, 但只有在搜索表達(dá)式形式為w1∩φ(w2,··· ,wn)且DB(w1)較小時(shí)才是高效的. 而對(duì)于一般分離關(guān)鍵詞形式的搜索, 需要找到一個(gè)所有文件包含的關(guān)鍵詞w, 將搜索表達(dá)式轉(zhuǎn)化為w ∩φ(w1,··· ,wn) 形式進(jìn)行搜索, 而此時(shí)搜索復(fù)雜度仍為O(d). 另外在實(shí)際搜索場(chǎng)景中,搜索關(guān)鍵詞集中每個(gè)關(guān)鍵詞頻次都很高的情形也是很常見的, 這時(shí)OXT 將不再是高效的.

2017 年, Kamara 等人[43]提出了非交互式高效的SSE 方案IEX, 解決了文獻(xiàn)[42] 中OXT 只能對(duì)常規(guī)搜索形式的詢問(wèn)執(zhí)行亞線性搜索的問(wèn)題, 該方案能夠?qū)θ我夥蛛x和布爾詢問(wèn)執(zhí)行亞線性搜索, 實(shí)現(xiàn)最佳的通信復(fù)雜度, 即服務(wù)器返回沒(méi)有重復(fù)的文件標(biāo)識(shí)符的標(biāo)簽, 并且可以動(dòng)態(tài)的增加和刪除文件. Kamara等人首先針對(duì)詢問(wèn)w1∨w2∨···∨wq構(gòu)造了最壞情況的亞線性分離關(guān)鍵詞可搜索加密方案IEX, 由于每個(gè)布爾詢問(wèn)都可以表示成Δ1∧Δ2∧···∧Δl, Δi=wi,1∨wi,2∨···∨wi,q, 可以用IEX 方案實(shí)現(xiàn)布爾搜索. IEX 方案的索引EDB 由加密的字典EDX 和加密的全局多映射EMM 結(jié)構(gòu)組成. IEX 只是一個(gè)抽象的結(jié)構(gòu), 需要對(duì)字典和多映射的結(jié)構(gòu)加密方案具體實(shí)例化, Kamara 等人提出兩種加密多映射的方案,分別是基于文獻(xiàn)[44] 的2Lev 和文獻(xiàn)[19] 的Z-IDX 構(gòu)造, 前者提供了最優(yōu)的通信復(fù)雜度, 但存儲(chǔ)量巨大,后者平衡了效率和存儲(chǔ)的關(guān)系, 使得存儲(chǔ)量縮小近100 倍.

2018 年, Du 等人[45]對(duì)加密云存儲(chǔ)的搜索提出了一個(gè)新的索引設(shè)計(jì), 稱為概率倒排索引編碼結(jié)構(gòu).如圖14 所示, 首先從文件集d={d1,d2,··· ,d#d}中提取關(guān)鍵詞集w={w1,w2,··· ,w#w}, 為關(guān)鍵詞集中的每個(gè)關(guān)鍵詞生成一個(gè)數(shù)據(jù)標(biāo)識(shí)符向量(data identifier vector, DIV), 如果文件dj包含關(guān)鍵詞w, 則w對(duì)應(yīng)div 的第j個(gè)分量為1, 否則為0. 其次初始化一個(gè)由m個(gè)桶組成的數(shù)組γ, 對(duì)于?wj ∈w, 計(jì)算r個(gè)哈希桶的位置x1=h1(wj,sk1),··· ,xr=hr(wj,sk1), 對(duì)于每一個(gè)位置xi, 如果γ[xi] 為空, 則將divj直接存放在桶中, 否則將divj與桶中現(xiàn)存的向量做逐比特異或, 然后存放在桶中. 該索引結(jié)構(gòu)支持聯(lián)合和分離的多關(guān)鍵詞搜索, 文件的動(dòng)態(tài)更新, 但是沒(méi)有保護(hù)div 的隱私. 因此, 在基礎(chǔ)的倒排索引編碼結(jié)構(gòu)的基礎(chǔ)上, Du 等人分別利用隨機(jī)生成器(偽隨機(jī)函數(shù)) 和同態(tài)生成器(同態(tài)加密) 提出了兩個(gè)桶加密索引結(jié)構(gòu)BEIS-I 與BEIS-II. BEIS-I 與BEIS-II 均支持聯(lián)合和分離邏輯的多關(guān)鍵詞搜索、文件的動(dòng)態(tài)更新, 并滿足CKA2 安全和前向隱私.

圖14 概率倒排索引Figure 14 Probabilistic inverted index coding structure

2018 年, Lai 等人[27]明確指出OXT 方案[42]泄漏了單關(guān)鍵詞結(jié)果模式(single keyword result pattern, SP), 關(guān)鍵詞對(duì)結(jié)果模式(keyword pair result pattern, KPRP) 以及多重關(guān)鍵詞跨查詢交叉結(jié)果模式(intersection result pattern, IP) 泄漏. 為了解決OXT 中KPRP 的泄漏, Lai 等人提出HXT 方案,HXT 以O(shè)XT 為原型, 利用輕量級(jí)的對(duì)稱隱藏向量加密判斷在對(duì)稱加密下搜索的關(guān)鍵詞集是否為文件提取的關(guān)鍵詞集. 在此過(guò)程中, 相較于OXT 多了一輪交互, 用于傳輸隱藏向量加密中的判斷密文, 只有當(dāng)服務(wù)器調(diào)用隱藏向量加密的query 算法返回true 時(shí), 才表明此結(jié)果包含所有的關(guān)鍵詞. 否則, 服務(wù)器只知道該文檔不含有所有的關(guān)鍵詞, 而不知道具體不含有哪些關(guān)鍵詞, 因此關(guān)鍵詞沒(méi)有KPRP 的泄漏.

2020 年,Ma 等人[46]指出不管是OXT[42]還是HXT[27],都需要進(jìn)行指數(shù)運(yùn)算. 為了提高計(jì)算效率,Ma 等人提出了一個(gè)新的對(duì)稱原語(yǔ)Hashed-based subset mmbership check (HSMC), 該原語(yǔ)通過(guò)sender和tester 之間的交互協(xié)議判斷加密集合之間的子集關(guān)系, 執(zhí)行完協(xié)議之后, 除集合之間的子集關(guān)系外, 不會(huì)泄漏其他信息, 并且該原語(yǔ)基于hash 運(yùn)算, 效率較高. Ma 等人基于HSMC 提出兩個(gè)方案PHXT 和FHXT, 與HXT 相比, PHXT 用HSMC 替換了HXT 中的隱藏向量; FHXT 把TSet 中的t向量而不是|t| 發(fā)送給用戶, 因此在執(zhí)行完HSMC 算法后, 用戶可以直接解密獲得對(duì)應(yīng)的id, 因此少一輪交互.

2.3.2 多關(guān)鍵詞排序可搜索加密

基于使用的工具, 多關(guān)鍵詞排序可搜索加密可分為以下三類:

(1) 保序加密

2007 年, Swaminathan 等人[47]通過(guò)簡(jiǎn)單地將搜索關(guān)鍵詞集中所有關(guān)鍵詞的相關(guān)性分?jǐn)?shù)相加, 將基于保序加密(order-preserving encryption, OPE) 的單關(guān)鍵詞排序可搜索加密方案擴(kuò)展到多關(guān)鍵詞場(chǎng)景.如圖15 所示, 左圖為未加密的索引, 表中數(shù)據(jù)代表文件與關(guān)鍵詞兩兩之間的明文相關(guān)性分?jǐn)?shù); 右圖為密文索引, 表中數(shù)據(jù)為利用OPE 加密的文件與關(guān)鍵詞兩兩之間的密文相關(guān)性分?jǐn)?shù). 搜索時(shí), 直接將關(guān)鍵詞集包含的關(guān)鍵詞的密文相關(guān)性分?jǐn)?shù)相加作為最終的相關(guān)性分?jǐn)?shù), 如搜索包含w1和w2的文件時(shí),F1與搜索條件的相關(guān)性得分為15(12+3),F2與搜索條件的相關(guān)性得分為19(3+16). 由于OPE 會(huì)將原始數(shù)據(jù)擴(kuò)展為范圍更大的密文數(shù)據(jù), 會(huì)使加密總分?jǐn)?shù)不能完全保留排序, 例如未加密之前對(duì)于搜索條件w1∩w2,F3的相關(guān)性得分為1.6,F4的相關(guān)性得分為2.7, 即F4的相關(guān)性強(qiáng)于F3, 而利用OPE 加密后F4的相關(guān)性(21) 弱于F3(22), 因此排序結(jié)果不準(zhǔn)確.

圖15 基于OPE 的多關(guān)鍵詞排序搜索Figure 15 Multi-keyword ranked search based on OPE

2012 年, Xu 等人[48]基于文獻(xiàn)[47] 提出一個(gè)兩步排序策略來(lái)實(shí)現(xiàn)更準(zhǔn)確的排序結(jié)果. 第一步以“坐標(biāo)匹配” 的方式對(duì)文檔進(jìn)行粗略排序, 即根據(jù)每個(gè)文檔包含的搜索關(guān)鍵詞的數(shù)量對(duì)文檔進(jìn)行分類, 在第二步中, 對(duì)于在第一步中得到的每個(gè)分類利用與文獻(xiàn)[47] 相同的方法進(jìn)行進(jìn)一步地排序. 雖然Xu 等人的方案比文獻(xiàn)[47] 排序準(zhǔn)確性有所提高, 但由于在每個(gè)分類中仍采用與文獻(xiàn)[47] 相同的方法, 故仍然存在相同的排序準(zhǔn)確性問(wèn)題, 且由于OPE 自身的加密特性, 會(huì)不可避免地泄露一些數(shù)據(jù)隱私.

(2) 向量空間模型——安全KNN

2011 年, Cao 等人[49]通過(guò)將每個(gè)文件和搜索關(guān)鍵詞集表示為維數(shù)為關(guān)鍵詞字典大小的0/1 向量, 結(jié)合安全的KNN 加密, 提出了多關(guān)鍵詞密文排序搜索方案MRSE. 具體地, 向量的每個(gè)分量代表關(guān)鍵詞字典中的一個(gè)關(guān)鍵詞, 在生成文件對(duì)應(yīng)的向量時(shí), 若文件包含某個(gè)關(guān)鍵詞, 則該關(guān)鍵詞對(duì)應(yīng)分量為1, 否則為0; 在生成搜索關(guān)鍵詞集對(duì)應(yīng)的向量時(shí), 若搜索關(guān)鍵詞集包含某關(guān)鍵詞, 則該關(guān)鍵詞對(duì)應(yīng)分量為1, 否則為0. 通過(guò)安全的KNN 對(duì)文件向量和搜索向量加密, 計(jì)算加密的文件向量與加密的搜索向量之間的內(nèi)積, 利用“坐標(biāo)匹配” 度量文件與搜索多關(guān)鍵詞之間的相關(guān)性, 內(nèi)積越大, 說(shuō)明對(duì)應(yīng)文件包含的搜索關(guān)鍵詞數(shù)越多, 相關(guān)性越強(qiáng).

關(guān)鍵詞詞頻在一定程度上反映了關(guān)鍵詞對(duì)文件的重要程度, 對(duì)文件進(jìn)行排序時(shí)應(yīng)考慮關(guān)鍵詞的重要程度. 而在MRSE 中將文件和搜索關(guān)鍵詞集表示為0/1 向量只考慮了文件包含搜索關(guān)鍵詞的數(shù)量, 并未考慮關(guān)鍵詞對(duì)文件的重要程度.

由于文獻(xiàn)[49,50] 在搜索時(shí)都需要通過(guò)計(jì)算每個(gè)文件向量與搜索向量的內(nèi)積得到相關(guān)性分?jǐn)?shù)然后排序, 因此搜索效率與文件數(shù)量是成線性關(guān)系的. 為了提高搜索效率, 后續(xù)研究者提出了許多新穎的索引樹結(jié)構(gòu)實(shí)現(xiàn)了優(yōu)于線性搜索的搜索效率:

2015 年, Xia 等人[51]通過(guò)構(gòu)建關(guān)鍵詞平衡二叉樹(keyword balanced binary tree, KBB-Tree) 索引提出一個(gè)動(dòng)態(tài)的多關(guān)鍵詞密文排序搜索方案DMRS. KBB-Tree 自下而上構(gòu)建, 每個(gè)葉子節(jié)點(diǎn)代表一個(gè)文件, 存儲(chǔ)該文件代表的文件向量, 中間結(jié)點(diǎn)存儲(chǔ)篩選向量, 篩選向量的每個(gè)分量為其子節(jié)點(diǎn)對(duì)應(yīng)分量的最大值. 利用安全KNN 加密每個(gè)節(jié)點(diǎn)存儲(chǔ)的向量. 搜索時(shí), 可通過(guò)篩選向量排除不包含搜索關(guān)鍵詞文件的子樹, 有效的縮小搜索范圍, 并利用“深度優(yōu)先搜索” 算法提高搜索效率.

由于在構(gòu)建KBB-Tree 時(shí), 葉子節(jié)點(diǎn)的放置是隨機(jī)的, 而葉子節(jié)點(diǎn)的位置顯然會(huì)影響搜索效率, 故可以通過(guò)選取有效的葉子節(jié)點(diǎn)放置方法提高DMRS 的搜索效率.

2015 年, Chen 等人[52]考慮文件之間的相關(guān)性, 在MRSE[50]的基礎(chǔ)上提出了一個(gè)基于層次聚類的多關(guān)鍵詞排序可搜索加密方案(MRSE-HCI).MRSE-HCI 通過(guò)引入二分k-means 的層次聚類方法自頂向下構(gòu)建層次聚類索引樹, 初始時(shí)整個(gè)文件集合為一個(gè)簇, 利用二分k-means 劃分簇, 直至劃分得到的子簇中包含的文件數(shù)量不超過(guò)給定的閾值. 劃分簇的過(guò)程即為層次聚類索引樹(hierarchical clustering index tree, HCI-Tree) 的構(gòu)建過(guò)程. HCI-Tree 中每一個(gè)節(jié)點(diǎn)代表一個(gè)簇, 存儲(chǔ)簇中所包含文件的數(shù)量和這些文件對(duì)應(yīng)的中心向量, 葉子節(jié)點(diǎn)與其包含的文件直接關(guān)聯(lián). 文件向量同MRSE 仍利用TF-IDF 和向量空間模型生成, 并利用安全KNN 加密各個(gè)節(jié)點(diǎn)中的向量. 搜索時(shí), 從HCI-Tree 第一層開始計(jì)算簇中心向量與搜索向量的內(nèi)積, 然后選取內(nèi)積小的結(jié)點(diǎn)繼續(xù)進(jìn)行該過(guò)程直到找到最小聚類簇, 計(jì)算最小聚類簇中文件向量與搜索向量的內(nèi)積得到相關(guān)性得分, 若該最小聚類簇中的文件數(shù)量小于用戶提前選定的所要搜索的文件數(shù)k, 則服務(wù)器追溯到該結(jié)點(diǎn)的父節(jié)點(diǎn)搜索得到該節(jié)點(diǎn)的兄弟節(jié)點(diǎn), 重復(fù)此過(guò)程直到搜索到k個(gè)文件.

2019 年, Guo 等人[53]基于MRSE, 引入BF 構(gòu)建平衡二叉索引樹, 提高搜索效率. 索引樹自下而上進(jìn)行構(gòu)建, 每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)一個(gè)文件, 存儲(chǔ)文件id, 文件向量和文件的BF, 非葉子節(jié)點(diǎn)存儲(chǔ)其子節(jié)點(diǎn)對(duì)應(yīng)BF 的或, 利用安全KNN 加密葉子節(jié)點(diǎn)的文件向量. 根據(jù)搜索關(guān)鍵詞生成其對(duì)應(yīng)的搜索向量和BF. 搜索時(shí), 首先利用BF 自上向下進(jìn)行搜索, 排除掉不可能匹配的子樹, 最后利用搜索向量與文件向量計(jì)算相關(guān)性分?jǐn)?shù)得到top-k文件.

雖然通過(guò)樹形索引的建立實(shí)現(xiàn)了優(yōu)于線性搜索的搜索效率, 但由于原本通過(guò)將每個(gè)文件表示為空間向量模型中的點(diǎn), 然后利用安全KNN 加密每個(gè)向量實(shí)現(xiàn)多關(guān)鍵詞排序搜索的方法時(shí)空開銷大, 而樹形索引建立的同時(shí)會(huì)產(chǎn)生大量的中間節(jié)點(diǎn), 進(jìn)一步增加了時(shí)空開銷.

(3) 向量空間模型——同態(tài)加密

2013 年, Yu 等人[54]通過(guò)引入相似相關(guān)性和方案穩(wěn)健性的概念說(shuō)明基于OPE 且在服務(wù)器端進(jìn)行排序操作的多關(guān)鍵詞密文排序可搜索加密技術(shù)會(huì)不可避免的泄露數(shù)據(jù)隱私, 并利用向量空間模型和同態(tài)加密(homomorphic encryption, HE) 設(shè)計(jì)了一個(gè)在用戶端排序的搜索時(shí)需要兩輪交互的多關(guān)鍵詞密文排序搜索方案TRSE. 生成索引時(shí), 首先為文件集中每個(gè)文件生成對(duì)應(yīng)的文件向量, 向量的每個(gè)分量為對(duì)應(yīng)關(guān)鍵詞與文件的相關(guān)性分?jǐn)?shù), 然后利用HE 加密每個(gè)分量, 生成文件對(duì)應(yīng)的索引; 陷門生成時(shí), 根據(jù)搜索關(guān)鍵詞集, 生成搜索向量, 若搜索關(guān)鍵詞集包含某關(guān)鍵詞, 則對(duì)應(yīng)分量為1, 否則為0, 然后利用HE 加密每個(gè)分量. 搜索時(shí)服務(wù)器計(jì)算每個(gè)加密的文件向量與加密的搜索向量的內(nèi)積, 得到密文相關(guān)性分?jǐn)?shù), 并將其發(fā)送給用戶, 用戶端進(jìn)行解密得到明文相關(guān)性分?jǐn)?shù)并進(jìn)行排序, 最后向服務(wù)器請(qǐng)求返回相應(yīng)的top-k密文文件.

雖然文獻(xiàn)[54]在用戶端完成排序操作, 在一定程度上保護(hù)了數(shù)據(jù)隱私, 但由于是基于同態(tài)加密實(shí)現(xiàn)的,效率較低且用戶端計(jì)算量大.

3 復(fù)雜語(yǔ)義對(duì)稱可搜索加密之間的關(guān)系

目前關(guān)于通配符、模糊關(guān)鍵詞、多關(guān)鍵詞這三種類型的復(fù)雜語(yǔ)義SSE 已有了一系列的研究成果. 但據(jù)我們所知, 目前還沒(méi)有學(xué)者對(duì)這三者之間的關(guān)系進(jìn)行過(guò)研究. 而探索這三者之間的關(guān)系, 一方面可以激發(fā)我們從多角度的思維設(shè)計(jì)這三種類型的復(fù)雜語(yǔ)義SSE 方案; 另一方面可以激發(fā)設(shè)計(jì)多種復(fù)雜語(yǔ)義結(jié)合的SSE 方案的思路. 因此, 本節(jié)不僅對(duì)已有的研究成果中這三類復(fù)雜語(yǔ)義SSE 之間的關(guān)系進(jìn)行研究, 同時(shí)提出一種新的通配符SSE 關(guān)鍵詞特征提取方式, 進(jìn)而引入了一種將通配符SSE 轉(zhuǎn)化為一般多關(guān)鍵詞SSE 的方法.

3.1 通配符與模糊關(guān)鍵詞對(duì)稱可搜索加密的關(guān)系

通配符與模糊關(guān)鍵詞搜索雖然是分別為解決不能進(jìn)行完整關(guān)鍵詞和精確關(guān)鍵詞搜索而提出的兩種不同的復(fù)雜語(yǔ)義可搜索加密, 但現(xiàn)有的關(guān)于這兩種復(fù)雜語(yǔ)義搜索的研究成果又有緊密的聯(lián)系. 如圖16 所示,通過(guò)提取特征構(gòu)造的通配符SSE 與基于LSH 的模糊關(guān)鍵詞SSE 都是首先通過(guò)對(duì)索引關(guān)鍵詞與搜索關(guān)鍵詞提取特征得到特征集, 再利用哈希函數(shù)將特征集插入到過(guò)濾器中, 生成關(guān)鍵詞對(duì)應(yīng)的索引和陷門. 不同的是, 在通配符可搜索加密中, 只要索引關(guān)鍵詞符合通配符關(guān)鍵詞形式則表明匹配成功, 即索引關(guān)鍵詞的特征集應(yīng)包含陷門關(guān)鍵詞的特征集, 故在搜索時(shí)直接比對(duì)陷門過(guò)濾器與索引過(guò)濾器即可; 而在模糊關(guān)鍵詞搜索中我們想要搜索的是包含與搜索關(guān)鍵詞盡可能相似的關(guān)鍵詞的文件, 故需進(jìn)一步計(jì)算索引過(guò)濾器和陷門過(guò)濾器的LSH 值, 利用LSH 的性質(zhì)刻畫兩者的相似性.

圖16 通配符與模糊關(guān)鍵詞搜索對(duì)比Figure 16 Comparison between wildcard and fuzzy search

3.2 通配符與多關(guān)鍵詞對(duì)稱可搜索加密的關(guān)系

現(xiàn)有解決通配符可搜索加密的技術(shù)主要有枚舉與提取特征兩種, 雖然這兩種技術(shù)是針對(duì)通配符搜索提出的, 但這兩種通配符搜索技術(shù)本質(zhì)上可分別轉(zhuǎn)化分離關(guān)鍵詞與聯(lián)合關(guān)鍵詞這兩種形式的多關(guān)鍵詞可搜索加密. 另外, 我們提出了一種新的關(guān)鍵詞特征提取方式, 使得通配符可搜索加密可轉(zhuǎn)化為一般的多關(guān)鍵詞可搜索加密.

3.2.1 通過(guò)枚舉構(gòu)造的通配符SSE 可轉(zhuǎn)化為分離關(guān)鍵詞SSE

文獻(xiàn)[21] 通過(guò)為文件集中每個(gè)關(guān)鍵詞建立一個(gè)布隆過(guò)濾器, 然后將矩陣型的索引壓縮為數(shù)組形式生成最終的索引. 為了實(shí)現(xiàn)通配符搜索, 對(duì)搜索關(guān)鍵詞生成陷門時(shí), 枚舉所有可能的關(guān)鍵詞, 然后用r個(gè)hash 函數(shù)作用在每個(gè)關(guān)鍵詞上建立一個(gè)BF, 本質(zhì)即為搜索語(yǔ)句為所有可能的關(guān)鍵詞求并的分離關(guān)鍵詞搜索.

3.2.2 通過(guò)提取特征構(gòu)造的通配符SSE 可轉(zhuǎn)化為聯(lián)合關(guān)鍵詞SSE

文獻(xiàn)[22–24] 通過(guò)對(duì)索引關(guān)鍵詞與搜索關(guān)鍵詞提取特征, 然后將特征集通過(guò)哈希函數(shù)映到過(guò)濾器, 生成陷門過(guò)濾器和索引過(guò)濾器, 最后通過(guò)將陷門過(guò)濾器與每個(gè)關(guān)鍵詞對(duì)應(yīng)的索引過(guò)濾器比對(duì)進(jìn)行搜索, 若陷門過(guò)濾器為1 的位置在索引過(guò)濾器對(duì)應(yīng)位置也都為1, 則說(shuō)明匹配成功, 即為對(duì)特征集同時(shí)包含搜索關(guān)鍵詞特征集中所有特征的關(guān)鍵詞的搜索, 例如在文獻(xiàn)[23] 對(duì)含通配符的關(guān)鍵詞c*o*d 提取得特征得到特征集{c||1,d||-1,c||0,o||0,d||0}, 本質(zhì)即為搜索語(yǔ)句為(c||1)∩(d||-1)∩(c||0)∩(o||0)∩(d||0) 的聯(lián)合關(guān)鍵詞搜索.

3.2.3 通配符SSE 可轉(zhuǎn)化為一般多關(guān)鍵詞SSE

通過(guò)上述說(shuō)明現(xiàn)有的一些通配符可搜索加密方案可轉(zhuǎn)化為分離關(guān)鍵詞搜索或聯(lián)合關(guān)鍵詞搜索. 現(xiàn)在我們提出一種新的關(guān)鍵詞特征提取方式, 使得通配符SSE 可轉(zhuǎn)化為一般的多關(guān)鍵詞SSE. 我們根據(jù)關(guān)鍵詞包含的通配符類型分情況說(shuō)明: 當(dāng)關(guān)鍵詞包含單字符通配符“?” 時(shí), 通過(guò)枚舉通配符“?” 可能代表的字符然后提取關(guān)鍵詞中所有的2-gram 字符串; 當(dāng)關(guān)鍵詞包含多字符通配符“*” 時(shí), 提取關(guān)鍵詞中除“*” 之外的2-gram 字符串. 下面我們通過(guò)具體的例子具體解釋特征提取方式及如何將通配符搜索轉(zhuǎn)化為一般多關(guān)鍵詞搜索.

(1) 關(guān)鍵詞key?ord 的特征集為{ke,ey,{ya,yb,··· ,yz},or,rd}, 可轉(zhuǎn)化為搜索表達(dá)式為“ke∩ey∩(ya∪yb∪···∪yz)∩or∩rd” 的布爾關(guān)鍵詞搜索;

(2) 關(guān)鍵詞key*rd 的特征集為{ke,ey,rd}, 可轉(zhuǎn)化為搜索表達(dá)式為“ke∩ey∩rd” 的聯(lián)合關(guān)鍵詞搜索.

3.3 模糊與多關(guān)鍵詞對(duì)稱可搜索加密的關(guān)系

利用編輯距離構(gòu)造的模糊關(guān)鍵詞SSE 可轉(zhuǎn)化為分離關(guān)鍵詞SSE. 具體地, 文獻(xiàn)[28] 利用編輯距離刻畫關(guān)鍵詞之間的相似度, 通過(guò)通配符和克(gram) 兩種技術(shù)來(lái)構(gòu)造模糊關(guān)鍵詞集合進(jìn)而實(shí)現(xiàn)模糊關(guān)鍵詞搜索. 搜索時(shí), 只要索引關(guān)鍵詞對(duì)應(yīng)的模糊關(guān)鍵詞集包含搜索關(guān)鍵詞對(duì)應(yīng)的模糊關(guān)鍵詞集中的其中一個(gè)關(guān)鍵詞, 則說(shuō)明匹配成功, 即本質(zhì)為搜索關(guān)鍵詞對(duì)應(yīng)的模糊關(guān)鍵詞集中所有關(guān)鍵詞的分離關(guān)鍵詞搜索. 例如搜索關(guān)鍵詞為CASTLE, 則編輯距離為1 的基于通配符的模糊關(guān)鍵詞集合為SCASTLE,1={CASTLE,*CASTLE,*ASTLE,C*ASTLE,C*STLE,··· ,CASTL*E,CASTL*,CASTLE*}, 可以看做搜索語(yǔ)句為CASTLE∪*CASTLE∪*ASTLE∪C*ASTLE∪C*STLE∪···∪CASTL*E∪CASTL*∪CASTLE* 的分離關(guān)鍵詞搜索.

圖17 總結(jié)了我們上述提到的這三者之間的關(guān)系.

圖17 三者之間的關(guān)系Figure 17 Relationship among three SSEs

4 存在問(wèn)題及研究思路

從復(fù)雜語(yǔ)義可搜索加密提出的背景介紹中可以看出, 與只能實(shí)現(xiàn)完整的、精確的單關(guān)鍵詞搜索的傳統(tǒng)可搜索加密相比, 這些功能多樣化的復(fù)雜語(yǔ)義可搜索加密更符合實(shí)際搜索場(chǎng)景. 但現(xiàn)階段關(guān)于復(fù)雜語(yǔ)義可搜索加密的研究還尚未成熟, 仍存在一些待解決的問(wèn)題.

4.1 通配符對(duì)稱可搜索加密

通配符可搜索加密是為了解決用戶在對(duì)密文數(shù)據(jù)搜索時(shí)不能提供完整關(guān)鍵詞的情形而提出的, 在現(xiàn)有針對(duì)通配符搜索的兩種主流技術(shù)中, 雖然提取特征技術(shù)比枚舉技術(shù)在效率與存儲(chǔ)方面都有所優(yōu)化, 但由于其使用的工具BF 存在不可避免的弊端及提取特征的方式還尚未成熟, 使得基于提取特征技術(shù)的通配符可搜索加密還不足以應(yīng)用于實(shí)踐. 因此, 通配符對(duì)稱可搜索加密未來(lái)的研究工作可圍繞以下幾點(diǎn)展開:

4.1.1 關(guān)鍵詞特征提取方式的優(yōu)化

基于布隆過(guò)濾器的通配符SSE 方案中, 通過(guò)對(duì)關(guān)鍵詞提取特征構(gòu)造索引和陷門的方案在效率和存儲(chǔ)量方面與枚舉法相比顯然都是更為有效的. 在這些方案中, 文獻(xiàn)[22] 提取特征的方式最為簡(jiǎn)單, 且服務(wù)器端存儲(chǔ)量小, 但這種簡(jiǎn)便的提取方式使得方案只能實(shí)現(xiàn)單字符通配符關(guān)鍵詞搜索. 文獻(xiàn)[23,24] 通過(guò)對(duì)提取特征的方式進(jìn)一步細(xì)化, 實(shí)現(xiàn)了多字符通配符關(guān)鍵詞搜索, 但同時(shí)也導(dǎo)致效率降低、存儲(chǔ)量增大. 由此可見, 關(guān)鍵詞的特征提取方式對(duì)方案的搜索功能、效率和存儲(chǔ)量都有重要的影響. 因此, 構(gòu)造能夠同時(shí)實(shí)現(xiàn)單字符和多字符通配符搜索且效率和存儲(chǔ)量都較為有效的特征提取方式將是一項(xiàng)有意義的工作.

4.1.2 實(shí)現(xiàn)無(wú)假陽(yáng)性通配符可搜索加密有效工具的探索

現(xiàn)有的大多數(shù)通配符SSE 都是基于布隆過(guò)濾器構(gòu)造索引, 但如文獻(xiàn)[55] 所指出, 布隆過(guò)濾器一個(gè)顯著的弊端就是假陽(yáng)性不可避免, 即會(huì)返回多余的密文文件給用戶, 這不僅增加了通訊復(fù)雜度, 還增加了用戶對(duì)密文文件的處理負(fù)擔(dān). 因此探索能夠?qū)崿F(xiàn)無(wú)假陽(yáng)性搜索結(jié)果的通配符可搜索加密的有效工具將是一個(gè)有意義的研究.

4.2 模糊關(guān)鍵詞對(duì)稱可搜索加密

模糊關(guān)鍵詞可搜索加密允許用戶在對(duì)密文數(shù)據(jù)搜索時(shí)輸入中存在微小的拼寫錯(cuò)誤或形式不一致問(wèn)題.已有的模糊關(guān)鍵詞對(duì)稱可搜索加密方案大多數(shù)都是首先將關(guān)鍵詞轉(zhuǎn)化為向量, 然后利用LSH 刻畫關(guān)鍵詞的相似性. 但關(guān)鍵詞向量轉(zhuǎn)化方式還不夠完善, 使得其不能有效地兼容搜索時(shí)的關(guān)鍵詞拼寫錯(cuò)誤或形式不一致的問(wèn)題, 且LSH 有其不可避免的弊端, 對(duì)搜索準(zhǔn)確性和通訊復(fù)雜度有一定的影響. 因此, 我們對(duì)模糊關(guān)鍵詞對(duì)稱可搜索加密的研究應(yīng)特別關(guān)注:

4.2.1 關(guān)鍵詞向量轉(zhuǎn)化方式

在現(xiàn)有的利用局部敏感哈希實(shí)現(xiàn)對(duì)密文數(shù)據(jù)的模糊關(guān)鍵詞搜索方案中, 都需要首先將關(guān)鍵詞轉(zhuǎn)化為具有LSH 的度量空間對(duì)應(yīng)的向量, 再利用LSH 度量關(guān)鍵詞對(duì)應(yīng)向量間的相似性. 文獻(xiàn)[31,32] 通過(guò)提取關(guān)鍵詞的“bigram” 特征生成關(guān)鍵詞對(duì)應(yīng)向量; 文獻(xiàn)[33] 指出將關(guān)鍵詞轉(zhuǎn)化為“bigram” 會(huì)增大歐幾里得距離, 對(duì)除一個(gè)字母拼寫錯(cuò)誤以外的其他拼寫錯(cuò)誤不是有效的, 且不支持相同詞根的關(guān)鍵詞搜索, 文獻(xiàn)[33]通過(guò)引入“詞根提取算法”, 且將關(guān)鍵詞轉(zhuǎn)化為“uni-gram” 實(shí)現(xiàn)了更為準(zhǔn)確的搜索結(jié)果; 文獻(xiàn)[35] 指出文獻(xiàn)[33] 提出的將關(guān)鍵詞轉(zhuǎn)化為“uni-gram” 缺少了字母的順序消息, 無(wú)法識(shí)別“相同字母異序詞”. 為了提高搜索準(zhǔn)確性, 文獻(xiàn)[35] 提出將關(guān)鍵詞轉(zhuǎn)化為“order-preserving uni-gram” 向量. 由此可見關(guān)鍵詞的向量轉(zhuǎn)化方式, 對(duì)關(guān)鍵詞之間相似性的刻畫有重要的影響, 從而影響搜索準(zhǔn)確性.

4.2.2 搜索相似關(guān)鍵詞的有效工具

局部敏感哈希是一種針對(duì)海量高維數(shù)據(jù)的快速最鄰近查找方法, 因此被用來(lái)搜索與陷門關(guān)鍵詞相似的索引關(guān)鍵詞, 但其不可避免的會(huì)同時(shí)存在假陽(yáng)性與假陰性. 雖然我們可以通過(guò)已知的LSH 構(gòu)造新的LSH從而減小假陽(yáng)性與假陰性的概率, 但其概率始終會(huì)大于0, 搜索相似關(guān)鍵詞的有效工具對(duì)搜索準(zhǔn)確性、通訊復(fù)雜度都有重要影響.

4.3 多關(guān)鍵詞對(duì)稱可搜索加密

多關(guān)鍵詞可搜索加密使得用戶在對(duì)密文數(shù)據(jù)搜索時(shí)可以使用多個(gè)關(guān)鍵詞刻畫目標(biāo)數(shù)據(jù), 提高了用戶的搜索體驗(yàn). 但目前對(duì)多關(guān)鍵詞加密搜索的研究, 多數(shù)只能實(shí)現(xiàn)聯(lián)合關(guān)鍵詞的有效搜索, 而對(duì)于更一般的布爾搜索還沒(méi)有有效的解決方案. 除此之外, 為了減少通訊復(fù)雜度而提出的大多數(shù)多關(guān)鍵詞排序搜索方案安全性較弱. 因此, 對(duì)多關(guān)鍵詞對(duì)稱可搜索加密的研究應(yīng)特別關(guān)注:

4.3.1 有效的布爾可搜索加密方案的設(shè)計(jì)

在目前現(xiàn)有的多關(guān)鍵詞可搜索加密方案中, 文獻(xiàn)[27,42,46] 中使用的兩級(jí)索引能夠?qū)崿F(xiàn)亞線性的聯(lián)合關(guān)鍵詞搜索, 在效率方面是較有優(yōu)勢(shì)的, 但時(shí)間復(fù)雜度隨著搜索關(guān)鍵詞數(shù)量的增加而增加, 且性能主要卻決于s-term 中關(guān)鍵詞的選擇. 在實(shí)際搜索場(chǎng)景中, 搜索關(guān)鍵詞集中每個(gè)關(guān)鍵詞頻次都很高的情形也是很常見的, 這時(shí)這些方案將不再是高效的. 另外, 這些方案只能對(duì)常規(guī)的搜索形式為w1∩φ(w2,··· ,wn)的詢問(wèn)實(shí)現(xiàn)亞線性的搜索, 而對(duì)于分離關(guān)鍵詞形式的搜索, 搜索復(fù)雜度仍與文件數(shù)量成線性關(guān)系. 雖然文獻(xiàn)[43] 提出了能夠?qū)θ我夥蛛x和布爾詢問(wèn)執(zhí)行亞線性搜索的方案IEX, 但對(duì)IEX 的兩個(gè)具體實(shí)例化方案要么效率低, 要么存儲(chǔ)量大. 因此, 設(shè)計(jì)有效的布爾可搜索加密方案是一個(gè)亟待解決的問(wèn)題.

4.3.2 用戶端排序的多關(guān)鍵詞可搜索加密方案

現(xiàn)有的關(guān)于多關(guān)鍵詞排序可搜索加密的研究工作中, 大多數(shù)排序操作在服務(wù)器端執(zhí)行, 但在服務(wù)器端排序會(huì)不可避免的泄露一些統(tǒng)計(jì)信息, 這對(duì)有一定背景知識(shí)的敵手很容易造成一定的隱私泄露. 因此排序操作在用戶端實(shí)現(xiàn)是更為安全的, 但現(xiàn)有的能在用戶端排序的方案效率較低. 因此, 設(shè)計(jì)用戶端排序的多關(guān)鍵詞可搜索加密方案有重要意義.

5 總結(jié)

復(fù)雜語(yǔ)義可搜索加密雖然是依據(jù)用戶在實(shí)際搜索時(shí)可能會(huì)出現(xiàn)的不同搜索情形提出的, 但現(xiàn)有的一些通配符、模糊關(guān)鍵詞可搜索加密方案本質(zhì)上可看作多關(guān)鍵詞可搜索加密, 而且這些搜索情形往往也不是單獨(dú)出現(xiàn)的, 因此, 各種類型的復(fù)雜語(yǔ)義可搜索加密并不是相互獨(dú)立的, 設(shè)計(jì)多種復(fù)雜語(yǔ)義關(guān)鍵詞搜索相結(jié)合的可搜索加密方案是很重要的.