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

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

2. 中國科學院 信息工程研究所 信息安全國家重點實驗室, 北京 100093

1 引言

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

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

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

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

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

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

(4) 解密: 用戶對服務器返回的密文文件解密得到對應的明文文件.

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

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

2 復雜語義對稱可搜索加密

2.1 通配符對稱可搜索加密

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

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

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

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

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

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

2.1.1 枚舉

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

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

2.1.2 提取特征

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

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

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

圖5 通配符搜索Figure 5 Wildcard search

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

圖6 隱藏索引構建Figure 6 Building of hidden index

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

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

2.2 模糊關鍵詞對稱可搜索加密

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

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

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

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

2.2.1 編輯距離

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

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

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

2.2.2 局部敏感哈希

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

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

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

(1) 英文關鍵詞

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

圖8 LSH 索引Figure 8 LSH 索引

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

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

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

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

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

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

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

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

(2) 中文關鍵詞

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

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

圖11 基礎方案關鍵詞向量Figure 11 Keyword vector in BCMS

圖12 增強方案關鍵詞向量Figure 12 Keyword vector in ECMS

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

雖然上述提到的方案[31–37]基于LSH 實現(xiàn)了模糊關鍵詞搜索, 但由于用戶上傳到云服務器的文件不只有文本文件, 故設計能夠對于各種類型的加密文件, 例如: 圖像、音頻、視頻文件的模糊可搜索方案是很有必要的.

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

圖13 基礎索引結構Figure 13 Structure of basic index

2.3 多關鍵詞對稱可搜索加密

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

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

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

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

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

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

(3) 布爾搜索(Boolean search). 布爾搜索是指多個關鍵詞之間的邏輯關系為布爾運算的搜索.

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

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

2.3.1 一般多關鍵詞可搜索加密

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.2 多關鍵詞排序可搜索加密

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

(1) 保序加密

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

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

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

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

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

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

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

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

由于在構建KBB-Tree 時, 葉子節(jié)點的放置是隨機的, 而葉子節(jié)點的位置顯然會影響搜索效率, 故可以通過選取有效的葉子節(jié)點放置方法提高DMRS 的搜索效率.

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

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

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

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

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

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

3 復雜語義對稱可搜索加密之間的關系

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

3.1 通配符與模糊關鍵詞對稱可搜索加密的關系

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

圖16 通配符與模糊關鍵詞搜索對比Figure 16 Comparison between wildcard and fuzzy search

3.2 通配符與多關鍵詞對稱可搜索加密的關系

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

3.2.1 通過枚舉構造的通配符SSE 可轉化為分離關鍵詞SSE

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

3.2.2 通過提取特征構造的通配符SSE 可轉化為聯(lián)合關鍵詞SSE

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

3.2.3 通配符SSE 可轉化為一般多關鍵詞SSE

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

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

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

3.3 模糊與多關鍵詞對稱可搜索加密的關系

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

圖17 總結了我們上述提到的這三者之間的關系.

圖17 三者之間的關系Figure 17 Relationship among three SSEs

4 存在問題及研究思路

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

4.1 通配符對稱可搜索加密

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

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

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

4.1.2 實現(xiàn)無假陽性通配符可搜索加密有效工具的探索

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

4.2 模糊關鍵詞對稱可搜索加密

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

4.2.1 關鍵詞向量轉化方式

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

4.2.2 搜索相似關鍵詞的有效工具

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

4.3 多關鍵詞對稱可搜索加密

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

4.3.1 有效的布爾可搜索加密方案的設計

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

4.3.2 用戶端排序的多關鍵詞可搜索加密方案

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

5 總結

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