無假陽性的可驗證通配符可搜索加密

趙 博, 劉晉璐, 秦 靜,2

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

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

1 引言

計算機網(wǎng)絡的迅速發(fā)展和信息化進程的加速, 使得各領域中的數(shù)據(jù)飛速增長, 用戶本地的存儲空間已經(jīng)無法滿足這種需求. 此時, 云計算[1–4]服務為解決數(shù)據(jù)存儲問題提供了重要的技術支撐. 借助互聯(lián)網(wǎng)技術尤其是5G 通訊技術可以快速地將這些數(shù)據(jù)存儲到具有強大數(shù)據(jù)存儲和處理能力的云服務器上. 然而用戶將數(shù)據(jù)外包給云服務器使數(shù)據(jù)脫離了物理控制, 存儲在云服務器上的數(shù)據(jù)可能會遭受來自云存儲服務器供應商的內部攻擊或來自黑客的外部攻擊, 導致用戶隱私數(shù)據(jù)泄露. 為了保護云數(shù)據(jù)安全, 通常在數(shù)據(jù)外包之前對數(shù)據(jù)進行加密, 然后再上傳到云服務器. 但是傳統(tǒng)的加密算法使得密文不可區(qū)分, 因此搜索和定位密文數(shù)據(jù)變得困難.

為了解決上述問題, Song 等人[5]首次提出基于密文線性掃描的對稱可搜索加密方案. 對稱可搜索加密[6–8]是一種支持用戶在密文上進行關鍵詞檢索的密碼學原語, 用戶使用可搜索加密技術加密明文數(shù)據(jù),其他用戶(包括加密者) 通過該協(xié)議可以實現(xiàn)對密文的關鍵詞檢索. 2004 年Goh[9]提出安全索引概念,并利用偽隨機函數(shù)和布隆過濾器構建了索引形式為文件-關鍵詞(稱為正向索引) 的對稱可搜索加密協(xié)議,在搜索某個關鍵字時利用BF 可以快速判斷某元素是否在某個集合中的性質判定密文文件是否包含某個關鍵詞, 搜索復雜度與文件總數(shù)相關. 與Goh 方案類似, Chang 等[10]在2005 年通過預先建立字典生成加密索引構建了可搜索加密方案.

上述方案只支持完整關鍵詞的搜索. 然而, 在實際應用中, 用戶可能不能或不需要輸入完整的關鍵詞,通配符可搜索加密[11–13]技術的提出解決了該問題. 在通配符可搜索加密中, 用戶可以使用通配符表示詢問關鍵詞中不能具體表達的字符, 從而實現(xiàn)關鍵詞的部分匹配而不局限于完整匹配. 通配符主要有“?” 和“*” 兩種, “?” 代表一個字符, 稱其為單字符通配符, “*” 可以代表任意多個字符, 稱其為多字符通配符. 例如, Alice 想要搜索存儲在云端的所有pdf 文件, 則可以使用“*” 表示文件名稱, 從而利用“*.pdf” 搜索到所有的pdf 類型文件. 又如, Alice 想要搜索在2021 年10 月的某一天存儲的一份文件, 但忘記了具體的存儲日期, 這時Alice 不需要分別搜索10 月份每一天存儲的文件, 而可以使用“*102021” 搜索到10 月份所有的文件, 從而篩選得到目標文件. 2011 年, B?sch 等人[14]利用布隆過濾器(bloom filter, BF) 與偽隨機函數(shù)構造聯(lián)合通配符對稱可搜索加密方案, 該方案的索引為正向索引, 為了實現(xiàn)通配符搜索, 在索引生成階段, 需將每個文件包含的所有關鍵詞及每個關鍵詞通配符形式的所有變體插入到文件對應的BF中. 2016 年, Hu 等人[15]提出一種多功能可搜索加密方案, 同時支持通配符搜索、近似搜索、模糊搜索、分離關鍵詞搜索和對文件的更新. 該方案的索引為關鍵詞-文件形式(稱為倒排索引), 為了實現(xiàn)通配符搜索, 在陷門生成時, 需要對關鍵詞通配符所有可能形式進行枚舉. 上述兩個方案通過在索引或陷門生成時枚舉關鍵詞通配符形式的所有變體實現(xiàn)通配符搜索, 效率低且存儲或通訊負擔大. 2012 年, Suga 等人[16]對關鍵詞中每個字符提取位置特征構造了一個支持多種類型搜索的可搜索加密方案. 該方案的索引為倒排索引, 在索引生成階段, 按照字符位置級聯(lián)字符的方式提取特征集合, 然后將特征集合中每一個元素映射到BF 中. 由于提取特征方式的局限性, 該方案只能支持單字符通配符搜索. 2016 年, Hu 等人[17]改進文獻[16] 中的特征提取方式, 利用關鍵詞每個字符的正序、倒序以及存在性, 提出了一個多字符通配符搜索方案. 同年, Zhao 等人[18]提取單字符絕對位置, 兩字符相對位置特征也解決了多字符通配符搜索問題. 2019 年, 于文等人[19]基于Hu 的方案利用隱藏向量加密技術, 將索引過濾器和陷門過濾器分別看作索引向量和查詢向量, 然后對BF 加密提出了一個更加安全的通配符搜索方案. 該方案的數(shù)據(jù)保密性更強,而且在搜索時避免了陷門和索引的兩個BF 之間比特值的一一匹配, 提高了搜索效率. 但在該方案中, 過濾器的每一比特都要通過一個偽隨機函數(shù)進行加密, 增大了索引存儲.

可以看出, 現(xiàn)有的通配符可搜索加密方案基本都基于布隆過濾器構造索引, 但是布隆過濾器一個顯著的弊端就是存在假陽性, 即搜索時會返回多余的文件給用戶, 這不僅帶來不必要的網(wǎng)絡通訊量, 而且增加了用戶對密文文件處理的負擔. 另外, 現(xiàn)有的通配符可搜索加密方案只考慮了半誠實的服務器[20], 但是在商業(yè)云計算服務中, 云服務器可能是自私的, 為了節(jié)省計算量或者下載帶寬, 服務器可能會返回錯誤的搜索結果或者部分搜索結果. 針對上述問題, 本文設計了一個無假陽性的可驗證通配符可搜索加密方案. 主要工作如下:

(1) 無假陽性. 本文將一種特殊的通配符搜索類型—前綴類型, 轉化為范圍搜索. 具體地, 對關鍵詞字典進行編碼, 使得每一個關鍵詞對應一個二十六進制數(shù)字. 這種編碼方式保證了編碼數(shù)值大小順序等價于原始關鍵詞的字典順序. 然后將所有的關鍵詞編碼存儲在一個數(shù)組中, 搜索時將詢問的單字符通配符分別替換為a 與z, 并對替換后的兩個關鍵詞進行編碼, 索引數(shù)組中的編碼值介于這兩者數(shù)值之間的關鍵詞即為搜索結果.

(2) 有序二叉位圖樹(ordered binary bitmap tree, OBBT) 索引結構. 當關鍵詞字典包含的關鍵詞較多, 使用數(shù)組索引進行線性查找的搜索效率較低, 為此我們提出有序二叉位圖樹索引. OBBT 通過提取關鍵詞字符每一位特征, 將其存儲在樹的各層結構中, 樹的第i層表示關鍵詞第i個字符的存在性, 每個節(jié)點用位圖表示該層包含的所有字符, 葉子節(jié)點存儲該路徑包含的所有可能關鍵詞編碼值, 使得數(shù)組的大范圍搜索轉化為其子范圍搜索. 進一步地, 為了提高在每個葉子節(jié)點內的搜索效率及保證索引關鍵詞的隱私性, 令每個葉子節(jié)點數(shù)組的元素按照數(shù)值大小進行排序并利用保序加密對編碼值進行加密, 匹配出介于兩個編碼密文值區(qū)間的所有關鍵詞即為搜索結果.

(3) 搜索結果可驗證. 為了驗證搜索結果的正確性, 在每個編碼值的后面級聯(lián)一個驗證標簽(驗證標簽是對關鍵詞信息、密文hash 校驗值、密文標志符進行加密). 用戶與服務器第一輪交互之后,云服務器返回一個驗證標簽集. 用戶解密驗證標簽集中的每一個標簽, 得到關鍵詞及包含每個關鍵詞的文件標識符與密文hash 校驗值. 然后用戶對比詢問關鍵詞和解密得到的關鍵詞判定返回密文標識符的正確性. 第二輪交互云服務器返回密文, 用戶利用hash 值校驗返回密文的正確性和完整性.

2 預備知識

2.1 符號說明

首先給出本文中用到的符號說明.

2.2 偽隨機置換

定義1 (偽隨機置換[21])F:{0,1}k×{0,1}l →{0,1}l是一個函數(shù)族, 若F滿足以下兩個條件則稱F是(t,ε,q) 偽隨機置換.

(1) 任意給定x ∈{0,1}1和密鑰k ∈{0,1}k都能有效的計算F(k,x).

(2) 對于任意t時間多項式時間算法A做至多q次自適應詢問都有

2.3 保序加密

定義2 (保序加密) 對于群R中的子集A,B, 滿足關系|A|≤|B|. 函數(shù)f:A →B為一個保序函數(shù),即對于?i,j ∈A有f(i)＜f(j) 當且僅當i ＜j. 對于一個加密算法Π=(Gen,Enc,Dec), 明文空間和密文空間分別為M,C. 如果Enc(k,·) 是一個滿足上述條件的保序映射函數(shù), 那么Π = (Gen,Enc,Dec) 就是一個保序加密算法.

定義3 (random order preserving function, ROPF[22]) 保序加密方案Π = (Gen,Enc,Dec), 明文空間M, 密文空間C, 滿足|D|≤|R|. 方案Π 被認為是ROPF 安全的, 如果對于任意概率多項式敵手A, 存在一個可忽略函數(shù)negl 使得,

2.4 PCPA 安全

定義4(pseudo-randomness against chosen plaintext attacks,PCPA[6]) 令SKE=(Gen,Enc,Dec)表示為一個對稱加密方案,A表示一個敵手, 考慮如下概率實驗PCPASKE,A(λ):

(1) Gen(λ) 產生一個密鑰K.

(2) 敵手A允許訪問隨機預言機EncK(·).

(3)A輸出一個信息m.

(4) 兩個密文文本c0,c1按照如下方式產生,c0←EncK(m),c1從SKE 的密文空間中隨機選取. 隨機選擇一個比特b, 將cb發(fā)送給敵手A.

(5)A允許訪問加密隨機預言機, 經(jīng)過多項式次詢問之后輸出一個比特b′.

(6) 如果b′=b, 實驗輸出1, 否則輸出0.

我們說SKE 是PCPA 安全的, 如果對于任意概率多項式(probabilistic polynomial-time, PPT) 敵手A, 存在一個可忽略函數(shù)negl 使得,

2.5 系統(tǒng)模型

如圖1 所示, 系統(tǒng)模型包括三個實體, 數(shù)據(jù)擁有者、云服務器和數(shù)據(jù)使用者. 假定數(shù)據(jù)擁有者和數(shù)據(jù)使用者是誠實可信的, 會忠實執(zhí)行協(xié)議. 云服務器是半可信且好奇的[23], 即其可能為了節(jié)省其計算量或者下載帶寬而返回錯誤的搜索結果或者部分搜索結果.

圖1 系統(tǒng)模型Figure 1 System model

數(shù)據(jù)擁有者擁有一個文檔集D, 想要外包給云服務器. 首先, 為了確保數(shù)據(jù)的安全性, 將文檔集加密得到密文文檔C. 其次, 為了對密文文檔進行高效的檢索及驗證搜索結果, 從文檔集中提取關鍵詞字典, 并利用關鍵詞字典構建一個可驗證的安全索引I, 最后將索引I和密文C上傳到云服務器. 數(shù)據(jù)使用者經(jīng)過數(shù)據(jù)擁有者授權, 利用數(shù)據(jù)擁有者提供的密鑰生成搜索陷門TQ并發(fā)送給云服務器. 云服務器利用陷門在索引上搜索并返回搜索結果Tagsecond, 數(shù)據(jù)使用者利用Tagsecond與服務器交互驗證搜索結果的正確性和完整性.

定義5 (無假陽性的可驗證通配符可搜索加密系統(tǒng)) 無假陽性的可驗證通配符可搜索加密系統(tǒng)Π 由以下算法組成:

(1) KeyGen(λ)→(sk,k): 輸入安全參數(shù)λ, 數(shù)據(jù)擁有者調用密鑰生成算法, 輸出密鑰k和密鑰集sk.

(2) Enc(k,D)→C: 輸入密鑰k和文檔集D, 數(shù)據(jù)擁有者調用加密算法, 輸出密文文檔C.

(3) BuildIndex(sk,D)→I: 輸入密鑰集sk 和文檔集D, 數(shù)據(jù)擁有者調用索引建立算法, 輸出索引I.

(4) Trapdoor(sk,Q)→TQ: 輸入密鑰集sk 和詢問關鍵詞Q, 數(shù)據(jù)使用者調用陷門生成算法, 輸出陷門TQ.

(5) Search(TQ,I)→Tag: 輸入陷門TQ和索引I, 云服務器調用搜索算法, 輸出驗證標簽集Tagsecond.

(6) Verify(sk,Tag)→0/1: 輸入驗證標簽集Tagsecond和密鑰集sk 數(shù)據(jù)使用者調用驗證算法與服務器進行交互驗證, 驗證搜索結果.

2.6 安全模型

首先介紹一些輔助性概念.

定義6 (查詢歷史) 一個方案的查詢歷史包括: 文檔集合D= (D1,D2,··· ,Dm) 以及詢問列表Qk=(q1,q2,··· ,qk), 將查詢歷史表示為H=(D,Qk).

定義7 (視圖) 查詢歷史的視圖包括: 加密文件Encsk(D), 安全索引Encsk(Ikw) 和陷門Tr(Qk), 將視圖表示為V(H)={Encsk(D),Encsk(Ikw),Tr(Qk)}.

定義8 (訪問模式) 一個查詢歷史的訪問模式指的是詢問Qk的搜索結果AP ={D(q1),D(q2),···,D(qk)}.

定義9 (軌跡) 一個查詢歷史的軌跡指的是云服務器能捕捉到的信息, 將查詢的軌跡表示為T(H) ={AP,|·|},|·| 表示索引結構本身的特性.

定義10 (非適應性語義安全) 令Π = (KeyGen,Enc,BuildIndex,Trapdoor,Search,Verify) 表示一個無假陽性的可驗證通配符可搜索加密方案,S表示一個模擬器, 非適應性語義安全描述如下:

·RealΠ,A(λ) 的具體過程如下:

(1) 挑戰(zhàn)者運行KeyGen(λ)→K.

(2) 敵手選擇文檔集合D.

(3) 挑戰(zhàn)者運行Enc(k,D) 和BuildIndex(sk,D) 算法得到Encsk(D) 和索引Encsk(Ikw). 同時運行Trapdoor(sk,Q) 算法為敵手的詢問列表Qk生成陷門Tr=(Tr1,Tr2,··· ,Trk).

(4) 輸出視圖V=(Encsk(D),Encsk(Ikw),Tr(Qk)).

·SimΠ,A,S(λ) 是如下一個模擬過程:

(1) 敵手輸入查詢歷史H.

(2) 模擬器S根據(jù)T(H) 模擬Encsk(D),Encsk(Ikw),Tr(Qk).

(3) 輸出視圖V′= (Encsk(D),Encsk(Ikw),Tr(Qk)),. 我們稱方案是Π 是非適應性語義安全的, 如果對于任意多項式時間的敵手A, 均存在一個多項式時間模擬器S, 使得Real 與Sim 的視圖V和V′是計算不可區(qū)分的.

3 無假陽性的可驗證通配符可搜索加密方案

為了設計一個在加密數(shù)據(jù)上安全有效的搜索方案, 需要做三個重要的設計:

(1) 建立安全的索引和陷門數(shù)據(jù)結構.

(2) 一個高效的匹配詢問和索引中關鍵詞的搜索算法.

(3) 可以將安全索引和搜索算法整合的在一起的隱私保護機制.

3.1 節(jié)闡述設計(1)(2) 的主要步驟, 為了便于理解先介紹在明文數(shù)據(jù)下的索引結構和搜索算法. 3.2 節(jié)展示帶有安全機制和隱私保護的通配符搜索方案.

3.1 明文OBBT 索引

我們將一種特殊的通配搜索類型—前綴搜索, 轉化為范圍搜索. 具體來講, 對于給定的關鍵詞字典WD={kw1,kw2,··· ,kwn}, 首先使用二十六進制對每個關鍵詞kw 進行編碼, 即將英文字符a—z 與0—25 分別一一對應, 并將所有的數(shù)字級聯(lián)為一個整數(shù)codekw. 例如, searchable 對應的二十六進制編碼為codesearch= 18×269+4×268+···+4×260. 關鍵詞按照該規(guī)則得到的編碼值順序與關鍵詞按照字典排序結果是一致的. 將所有的關鍵詞編碼值存儲在一個數(shù)組中, 對于任意的帶“?” 通配符的搜索關鍵詞Q, 將關鍵詞中的“?” 替換為a, 對應的關鍵詞編碼記為codemin; 將關鍵詞中“?” 替換為z, 對應的關鍵詞編碼記為codemax. 依據(jù)編碼規(guī)則, 與Q匹配的關鍵詞編碼數(shù)值一定介于codemin與codemax之間.

當關鍵詞字典的空間較大時, 使用數(shù)組存儲所有的關鍵詞編碼進行線性查找, 搜索效率較低, 為此我們設計了一個OBBT 索引將數(shù)組分隔并劃分到不同的葉子節(jié)點中, 使得大范圍的數(shù)組搜索轉化為其子范圍搜索. OBBT 是利用逐字符對比判斷每個字符是否相同, 進而判定關鍵詞是否存在. 也就是說, OBBT提取出關鍵詞的每一字符特征, 將其存儲在二叉樹的各層中. 二叉樹的第i層表示關鍵詞第i個字符的存在性, 每個節(jié)點用位圖表示該層包含的所有字符. 其中根節(jié)點為26 位的位圖表示首字符的存在性, 第二層開始每個節(jié)點為13 位的位圖(左節(jié)點代表a—m, 右節(jié)點代表n—z). 葉子節(jié)點存儲該路徑包含的所有可能關鍵詞編碼值-關鍵詞對. 搜索時, 對比每一層的位圖是否包含詢問關鍵詞的特征, 定位到與詢問關鍵詞匹配的葉子結點, 從而進入葉子節(jié)點的子范圍搜索. 進一步, 為了提高每個葉子節(jié)點內部搜索效率, 令每個葉子節(jié)點數(shù)組的元素按照編碼值數(shù)值大小進行排序, 匹配出介于codemin, codemax區(qū)間的關鍵詞即為搜索關鍵詞. 下面具體介紹OBBT 的構建.

(a) OBBT 預置

給定關鍵詞字典WD={kw1,kw2,··· ,kwn}, 假設關鍵詞長度都為l, 則二叉樹的高度為l. 二叉樹根節(jié)點為26 位的位圖(bit map, bm), 其余節(jié)點結構為13 位的位圖, 葉子結點級聯(lián)一個數(shù)組. 初始化階段將所有bm 全置為0, 得到二叉位圖樹.

(b) 字符映射

建立字符與數(shù)字之間一個1-1 映射關系, 將英文字母a—z 分別映射到1—26, 通配符“?” 映射到“?”.利用1-1 映射規(guī)則將關鍵詞kwi轉化對應的特征數(shù)組Tkwi.

(c) 特征填充

通過步驟(b) 將關鍵詞字典轉化為對應的特征數(shù)組集T={Tkw1,Tkw2,··· ,Tkwn}, 并按照如下規(guī)則將T中元素逐個填充到OBBT 中. 對于T中任意的數(shù)組Tkwi= [θ1,θ2,··· ,θl], 首先填充根節(jié)點, 將根節(jié)點位圖的θ1位置置為1. 接下來填充其他層的節(jié)點, 判斷數(shù)組Tkwi的第j位值θj, 若θj ≤13, 則將第j層的左節(jié)點θj位置置為1; 若θj ＞13, 則將第j層的右節(jié)點θj-13 位置置為1. 逐層填充直到完成最后一層, 將關鍵詞kwi填充到葉子節(jié)點的數(shù)組中. 按照上述流程將特征數(shù)組集T全部填充到OBBT 中,如圖2 所示. 下面以searchable 為例, 描述如何構建OBBT 以及填充關鍵詞.

圖2 OBBT 索引Figure 2 OBBT index

首先, 根據(jù)關鍵詞長度確定 OBBT 的高度為 10, 按照 (a) 所述構建一個 10 層的全 0 二叉位圖樹. 其次, 根據(jù) (b) 所述的 1-1 對應規(guī)則將字符轉化為對應的特征數(shù)組: searchable→[19,5,1,18,3,8,1,2,12,5]. 接下來, 將數(shù)組填充至OBBT 中, 數(shù)組的第一位為19, 將根節(jié)點的第19位置為1; 數(shù)組的第二位是5, 將第二層的左節(jié)點第5 個位置置為1. 依次類推直至填充到最后一層. 最后將關鍵詞searchable 級聯(lián)在葉子節(jié)點.

(d) 編碼與排序

按照上述規(guī)則將所有的關鍵詞填充到OBBT 中, 每個葉子節(jié)點級聯(lián)該分支所有可能的關鍵詞. 接下來, 將葉子節(jié)點所有關鍵詞進行編碼和排序. 我們利用二十六進制規(guī)則對關鍵詞的每一個字符進行編碼,也就是將英文字符a—z 與0—25 分別一一對應, 并將編碼后的數(shù)字級聯(lián)得到一個對應的整數(shù). 將每個葉子節(jié)點的級聯(lián)的所有關鍵詞按照如上規(guī)則得到編碼值-關鍵詞對組, 將其級聯(lián)在OBBT 葉子節(jié)點. 最后, 將每個組的元素按照編碼值大小進行排序, 得到有序二叉排序樹.

(e) 逐層匹配算法

給一個詢問關鍵詞Q, 我們利用逐層匹配算法進行查詢. 不妨設Q的第i位為“?”, 將關鍵詞Q按照步驟(b) 通過1-1 對應關系轉化為特征數(shù)組TQ={θ1,θ2,··· ,?,··· ,θl}; 將Q的第i位替換為a 和z,并利用算法(d) 計算出其對應的編碼值, 記為codemin,codemax. 首先將特征數(shù)組與根節(jié)點進行匹配, 判斷位圖θ1位的值, 如果該位置為1, 繼續(xù)搜索; 否則停止搜索, 表示關鍵詞不存在. 接下來判斷θ2的值, 如果θ2≤13, 那么搜索第二層的左節(jié)點, 并判斷θ2位置是否為1, 如果為1 繼續(xù)搜索, 否則停止搜索; 如果θ2＞13, 則搜索右節(jié)點, 判斷θ2-13 位置是否為1, 如果為1 繼續(xù)搜索, 否則停止搜索. 依據(jù)上述規(guī)則,直到遇見通配符, 跳過第i層, 直接進入第i+1 層, 如果θi+1≤13, 則同時搜索i+1 層的兩個左節(jié)點;如果θi+1＞13, 同時搜索兩個右節(jié)點; 直到最后一層匹配結束, 返回葉子節(jié)點數(shù)組中codemin,codemax區(qū)間的所有關鍵詞.

3.2 通配符搜索加密方案

本節(jié)展示帶有安全機制和隱私保護的通配符方案. 本文方案包括六個多項式時間算法:

- KeyGen(λ): 輸入一個安全參數(shù)λ, 輸出密鑰k, 密鑰集sk ={skop,skver,skf}, 其中skop是保序加密密鑰, sktag是加密標簽密鑰, skf是偽隨機置換密鑰.

- Index_Enc(sk,OBBT): 輸入OBBT 和密鑰sk. 對每層節(jié)點進行加密, 若節(jié)點位于第i層, 則令該節(jié)點的位圖作偽隨機置換F(ski,bm), 其中ski= skf ⊕i. 對于葉子結點層級聯(lián)的數(shù)組中每個元素編碼-關鍵詞, 將其加密生成一個tag ={tagfirst,tagsecond}: tagfirst= Encop(codekw) 其中Enc 為保序加密算法. tagsecond= Encver(kw||id1||id2||···||idk||hash(C1,C2,··· ,Ck)) 其中Enc為語義安全的對稱加密算法, idi為包含kw 的文檔標識符,Ci為idi對應Di密文. 輸出加密后的OBBT 索引.

- Enc(D,k): 輸入密鑰k, 明文文檔集D={D1,D2,··· ,Dm}, 加密每個文檔Di得到密文文檔集C={C1,C2,··· ,Cm}, 其中Ci=Enck(Di), Enc 為語義安全的對稱加密算法.

- BuildIndex(sk,D): 輸入密鑰sk, 文檔集D={D1,D2,··· ,Dm}以及密文文檔對應的ID ={id1,id2,··· ,idm}.

(1) 從文檔集D中提取出關鍵詞字典WD={kw1,kw2,··· ,kwn}.

(2) 利用關鍵詞字典WD按照3.1 節(jié)步驟(a),(b), (c), (d) 構建OBBT.

(3) 使用Index_Enc(sk,OBBT) 加密, 輸出加密的OBBT 索引I.

- Trapdoor(sk,Q): 輸入一個詢問關鍵詞Q和密鑰sk. 首先, 按照步驟(b) 得到特征數(shù)組T′Q=[θ1′,··· ,?,··· ,θl′], 并對數(shù)組中每個數(shù)字進行如下置換θi=F(ski,θ′i) 其中ski= sk⊕i得到數(shù)組TQ= [θ1,··· ,?,···θl], 其中“?” 代表單字符通配符. 其次, 將通配符“?” 替換為a 和z, 利用編碼算法分別計算出codemin,codemax, 并對編碼值進行如下加密trcode= Encop(code) 其中code={codemin,codemax}, 輸出陷門TQ,trcode.

- Search(TQ,I): 輸入陷門TQ和索引I, 根據(jù)逐層匹配算法, 返回葉子節(jié)點所有的驗證標簽Tagsecond.

- Verify(sk,Tag): 輸入密鑰sk 和驗證標簽集Tagsecond.

(1) 利用skver解密tag(second,i)得到對應的kw,ids={id1||id2||···||idk},hash(C1,C2,··· ,Ck)

(2) 判斷kw 與關鍵詞Q是否匹配. 如果匹配, 將所有的ids 發(fā)送給云服務器; 如果不匹配, 結束此次驗證.

(3) 云服務器返回所有的id-密文對(id1,Cid1),(id2,Cid2),··· ,(idk,Cidk).

(4) 把返回的密文進行hash 值校驗, 驗證hash(C1,C2,··· ,Ck)?=hash(Cid1,Cid2,··· ,Cidk) 如果相等輸出1, 否則輸出0.

注1 在驗證階段, 第一輪交互過程中, 驗證kw 與關鍵詞Q是否匹配, 如果匹配, 則說明服務器搜索結果是正確的, 否則認為搜索結果是錯誤的. 在第二輪交互過程中, 驗證hash(C1,C2,··· ,Ck)?=hash(Cid1,Cid2,··· ,Cidk). 如果hash(C1,C2,··· ,Ck)/= hash(Cid1,Cid2,··· ,Cidk), 則說明至少有一個返回密文不正確的或返回結果不完整. 由此驗證了服務器返回密文的正確性和完整性.

4 安全性分析

定理1 如果使用的對稱密鑰加密SKE 是PCPA 安全的,置換函數(shù)是偽隨機置換,保序加密是ROPF安全的, 則無假陽性的可驗證通配符可搜索加密方案是非適應性語義安全的.

證明: 如果對于PPT 敵手, 均存在一個多項式時間模擬算法Sim, 使得云服務器無法區(qū)分Real 的視圖V和Sim 的視圖V′, 那么云服務器就無法獲得索引和數(shù)據(jù)集的其他任何信息.

給定一個查詢歷史的軌跡為T(H) ={AP,|·|},|·| 表示樹的結構特性, 如樹的高度和葉子結點的分布等. 模擬Real 的視圖V=Encsk(D),Encsk(Ikw),Tr(Wk), 假設模擬器為Sim, Sim 具體工作步驟如下:

(4) 對于編碼值對應的關鍵詞密文, Sim 選擇與關鍵詞密文等長的隨機串級聯(lián)在數(shù)組中.由于密文是由語義安全的對稱加密生成, 任意PPT 敵手無法區(qū)分Encsk(D) 與D′. 各層結構是由偽隨機函數(shù)加密的, 葉子結點是由ROPF 保序加密函數(shù)和PCPA 安全的對稱加密, 任意PPT 敵手無法區(qū)分I′與I. 陷門是由偽隨機函數(shù)加密的, 因此Tr(Wk) 與Tr(W′k) 在多項式時間無法區(qū)分. 因此, 視圖V(Encsk(D),I,Tr(Wk)) 與V′(D′,I′,Tr(W′k)) 在PPT 敵手下是計算不可區(qū)分的, 本文方案是非適應語義安全的.

5 功能與性能分析

本節(jié)將本文方案與Hu[17]的方案進行功能和性能對比, 通過仿真實驗分別模擬用戶和云服務器索引生成時間和搜索時間. 仿真實驗是采用C++ 語言對方案性能進行測試, 運行環(huán)境是在AMD Ryzen 5 4600H CPU 3.00 GHz 和4 GB 內存的linux 系統(tǒng)上, 基于Boldyreva 的保序加密python 庫.

由圖3 可以看出, 本文方案相較于Hu 等人的方案, 存儲復雜度幾乎是不變的, 這是因為本文方案是預先建立的樹形結構, 然后可以在樹形結構中填充任意數(shù)量的關鍵詞, 而Hu 的方案是倒排索引, 隨關鍵詞數(shù)量呈線性增長. 由圖4 可以看出, 本文方案相較于Hu 等人的方案, 搜索效率極大提升, 且關鍵詞數(shù)量的變化對本文方案搜索時間基本沒有影響, 而Hu 等人方案的搜索時間隨關鍵詞數(shù)量線性增加, 這是由于我們構造了OBBT 索引, 而Hu 等人的方案為倒排索引. 由圖5 可以看出, 本文方案相較于Hu 的方案, 需要更多的時間建立索引, 這是因為本文方案采用保序加密構造索引, 而保序加密本身效率較低且我們在實驗時索引生成依賴于保序加密python 庫, 但保序加密的使用使得本文方案實現(xiàn)了無假陽性, 且在加密數(shù)據(jù)庫中索引建立的頻率一般是遠小于用戶搜索頻率的, 故這樣的開銷是可以接受的. 同時, 在表1 列出了與文獻[14,16,17] 的功能對比, 相較于文獻[14,16,17], 本文方案同時實現(xiàn)了通配符搜索、搜索結果無假陽性和搜索結果的可驗證. 因此, 本方案能夠很好地應用在云環(huán)境下.

表1 功能性對比Table 1 Functional comparison

圖3 存儲開銷Figure 3 Storage cost

圖4 搜索時間Figure 4 Search time

圖5 索引構造時間Figure 5 Index construction time

6 結論

通配符可搜索加密的提出增加了用戶的搜索體驗. 針對現(xiàn)有通配符可搜索加密方案搜索結果存在假陽性且只考慮半誠實服務器模型的局限性, 本文提出了一個無假陽性的可驗證單字符通配符搜索方案. 該方案將通配符搜索轉化為范圍搜索, 使用保序加密保證明文順序與密文順序的一致性, 并提出OBBT 索引提高其搜索效率. 所提出的方案搜索結果不存在假陽性, 支持對搜索結果正確性和完整性的驗證, 且方案是非適應性語義安全的. 最后, 性能分析表明本文方案是高效的. 因此, 本文所提出的無假陽性的可驗證通配符可搜索加密能夠在實際中實現(xiàn)更好的應用.