多數據所有者場景下具有訪問模式和搜索模式隱私的對稱可搜索加密方案*

侯欣怡, 劉晉璐, 張 茜, 秦 靜

山東大學 數學學院, 濟南250100

1 引言

隨著云計算的發展[1]和對個人數據便捷存儲需求的激增, 越來越多的組織和個人傾向于將數據外包到云服務器.為了保證外包數據的安全性, 數據所有者需要對外包數據加密.但是一般的加密方案不具有搜索功能, 如果數據用戶不能有選擇地檢索他們需要的數據片段, 那么就喪失了云數據存儲的優勢.可搜索加密技術允許數據用戶在密文數據庫上執行搜索操作.數據所有者首先將加密文件和搜索索引上傳到服務器存儲, 之后數據用戶向服務器發送對關鍵詞的加密問詢, 服務器在索引上安全地執行搜索操作, 并將與問詢匹配的加密文件返回給客戶端, 由客戶端執行解密.Song 等人[2]首先給出能夠在密文上搜索的SSE 方案.Goh 等人[3]給出一個基于布隆過濾器(Bloom filter, BF) 的SSE 方案.之后, Curtmola 等人[4]給出一個改進的安全性定義并構造了滿足新定義的SSE 方案.后續工作[5–8]對SSE 方案的安全性、效率和功能性進行了進一步研究.

現有的SSE 方案[3–8]以一些泄漏為代價獲得了效率, SSE 中的泄露包括訪問模式和搜索模式.訪問模式泄露了搜索陷門和被匹配文件之間的關系, 搜索模式泄露了搜索陷門中是否包含相同的關鍵詞.近年來的研究表明, 半誠實的服務器利用暴露的訪問和搜索模式能夠恢復加密的搜索關鍵詞[9–13].Liu 等人[9]的研究表明, 通過利用搜索模式, 云服務器能夠從用戶的搜索習慣中推斷出搜索的關鍵詞.研究表明[10–12], 通過利用訪問和搜索模式, 云服務器能夠使用關于文件的一些先驗知識來導出文件中的關鍵詞.Zhang 等人[12]給出了一個文件注入攻擊,使用20%的文件先驗知識能夠實現70%的關鍵字恢復準確率.Oya 等人[13]提出了一種利用訪問和搜索模式泄漏以及一些背景和查詢分布信息的攻擊, 能夠恢復數據用戶搜索的關鍵字.動態對稱可搜索加密(dynamic symmetric searchable encryption, DSSE) 方案[14–16]允許對外包的加密數據進行階段性更新, 但是一個半誠實的云服務器可以通過觀察特定用戶對數據庫的更新操作來推斷更敏感的信息, 另外, 關鍵詞的更新頻率也可以用于推導訪問模式.

一個解決訪問和搜索模式泄露問題的方法是不經意隨機訪問機制(oblivious random access mechanism, ORAM)[17], ORAM 通過在訪問數據時不斷洗牌和重新加密數據來隱藏訪問模式.直接將ORAM與SSE 結合構造的隱藏訪問模式的SSE 方案需要巨大的通信和計算開銷.兩輪不經意隨機訪問機制(two rounds oblivious random access mechanism, TWORAM)[18]是一種基于ORAM 的SSE 方案, 需要至少四輪通信.另外一種解決訪問和搜索模式泄露問題的方法是基于隱私信息檢索(privacy information retrieval, PIR)[19]技術的方案, 在從一個數據庫中讀取一個文件時也能夠完全隱藏訪問模式, 但是同樣需要巨大的通信和計算開銷.

Chen 等人[20]給出了一個與任意SSE 方案兼容的差分隱私混淆架構, 應用該架構的SSE 方案能夠隱藏訪問模式, 結果是服務器只會得到一個混淆的訪問模式.但是, 由于混淆訪問模式是固定的, 因此問詢相同的關鍵詞時總會產生相同的混淆訪問模式, 服務器通過檢查混淆訪問模式是否相同就能夠判斷加密問詢的潛在關鍵詞是否相同, 這就向服務器泄露了搜索模式.

Shang 等人[21]給出了一個能夠同時隱藏訪問和搜索模式的對稱可搜索加密方案, 稱為混淆SSE(obfuscated symmetric searchable encryption, OSSE).OSSE 通過為每一次關鍵詞問詢提供一個全新的混淆訪問模式來隱藏搜索模式.OSSE 在每一次關鍵詞問詢中, 會為每一個要搜索的文件生成一個專門的搜索陷門, 因此發送給服務器的搜索陷門數量與搜索的文件數量呈線性關系.另外, 由于OSSE 中加密索引和生成關鍵詞搜索陷門時使用的是相同的密鑰, 因此如果想要在不同密鑰生成的文件索引上搜索, 需要使用與加密索引對應的密鑰分別生成搜索陷門(且每一個密鑰生成的搜索陷門數量與使用該密鑰生成的文件索引數量呈線性關系), 因此OSSE 不適用于多數據所有者場景.

上述SSE 方案都是在一個單一的數據所有者上傳的加密文件上進行搜索的場景, 一個更實際的場景是, 數據用戶能夠搜索不同數據所有者上傳的加密文件.對此, 有兩種直接的關鍵詞問詢方式: (1) 數據用戶為每一個索引產生一個搜索陷門, 這使得發送給服務器的搜索陷門數量與云服務器上存儲的文件總數呈線性關系, 這會造成巨大的通信開銷; (2) 所有數據所有者使用同一個密鑰加密文件索引, 這一方法顯然缺乏安全保證.因此, 需要專門為多數據所有者場景設計可搜索加密方案, 即只需要一個單一的搜索陷門, 就能夠在不同密鑰加密的索引上搜索.Popa 等人[22]給出了一個多密鑰可搜索加密方案, 解決了多數據所有者場景下可搜索加密問題, 數據用戶只需要向服務器發送一個單一的關鍵詞搜索陷門, 就能夠在不同密鑰加密的索引上搜索.Zhang 等人[23]給出了多數據所有者模型下的隱私保護的多關鍵詞排序搜索系統.Sun 等人[24]針對Zhang 等人[23]方案中存在的關鍵詞猜測攻擊和等價測試攻擊的問題進行了改進, 給出了一個能夠抵抗上述兩種攻擊的多數據所有者場景下的多關鍵詞排序搜索方案.He 等人[25]給出了一個基于屬性的可搜索加密方案, 能夠在多數據所有者系統中實現布爾關鍵詞搜索.Miao 等人[26]提出了一種新的共享多數據所有者場景, 在共享多數據所有者系統中, 多個數據所有者能夠共同維護一個文件, 他們給出了一個共享多數據所有者場景下訪問策略隱藏的密文策略基于屬性的關鍵詞搜索系統.Ge等人[27]給出了一個多數據所有者系統中密文策略基于屬性的關鍵詞搜索和數據共享方案, 在數據共享過程中支持密文中的關鍵詞和訪問策略的更新.

本文給出一個多數據所有者場景下能夠同時隱藏訪問和搜索模式的SSE 方案.本文方案中, 數據所有者生成文件索引時, 將誤報(返回文件中不包含問詢的關鍵詞) 和假陰性(包含問詢關鍵詞的文件沒有被返回) 植入到每一個文件索引中.在關鍵詞問詢過程中, 數據用戶發送給服務器的關鍵詞加密問詢能夠以一種對服務器保密的方式概率地觸發文件索引中的誤報和假陰性, 這就為每一次關鍵詞問詢產生了一個全新的混淆訪問模式, 從而同時隱藏了訪問和搜索模式.另外, 本文方案適用于多數據所有者場景, 即問詢者只需要向服務器發送一個單一的搜索陷門, 就能夠在不同密鑰加密的索引上搜索.

本文方案的主要貢獻如下:

? 借助內積謂詞加密和近似同態加密構造一個新的對稱可搜索加密方案, 其主要特征為: (1) 能夠同時隱藏訪問和搜索模式; (2) 適用于多數據所有者場景, 即數據用戶只需要向服務器發送一個單一的關鍵詞搜索陷門, 就能夠在不同密鑰加密的索引上進行搜索.

? 證明本文給出的對稱可搜索加密方案具有自適應的不可區分安全性, 并且方案具有訪問和搜索模式的差分隱私性.

? 在具有代表性的真實世界數據集上對方案進行實驗, 說明了本文方案的實用性.

本文結構如下: 第2 節介紹相關預備知識; 第3 節介紹本文方案的系統模型以及安全定義; 第4 節給出具體方案; 第5 節對本文方案的安全性進行分析; 第6 節對本文方案的復雜度進行分析并在一個真實數據集上進行實驗.

表1 比較了本文方案與一些其他SSE 方案.

表1 現有工作對比Table 1 Comparison of existing works

2 預備知識

2.1 對稱可搜索加密

設一個數據所有者持有的文件集合為D={D1,D2,···,Dn},D[i] 表示D中第i個文件, indi表示D[i] 的標識符, 這里假設文件標識符(identity, id) 與文件內容獨立.設D[i] 的關鍵詞列表為Wi, 設關鍵詞域為Δ={w1,w2,···,w|Δ|},|Δ| 為關鍵詞域的大小, 則有Wi ?Δ,1≤i ≤n.設D(w) 表示所有包含關鍵詞w的文件按照id 的順序組成的文件列表.

下面給出SSE 方案的定義.

定義1 一個SSE 方案是以下4 個多項式時間算法的集合:

下面借用Curtmola 等人[4]給出的SSE 方案的安全定義, 其中為了定義SSE 的安全性給出歷史記錄、訪問模式、搜索模式和軌跡的概念.

數據用戶和服務器之間的交互由一個文件集合和一個數據用戶想要搜索的關鍵詞序列決定, 文件集合和問詢的關鍵詞序列都需要向敵手隱藏.上述這一交互的實例化稱為歷史記錄.正式地, 一個文件集合D上的q-問詢歷史記錄是一個二元組H={D,w}, 包括文件集合D和一個包含q個關鍵詞的向量w=(w1,w2,···,wq).

訪問模式是指一個歷史記錄中的每一個關鍵詞對應的文件id.

定義2 (訪問模式) 文件集合D上的訪問模式α(H) 由一個q-問詢歷史記錄H={D,w}誘導得出, 是一個元組(D(w1),D(w2),···,D(wq)), 也可以表示成一個大小為q×n的二元矩陣α(H), 使得

即如果第i行對應的關鍵詞wi包含在第j列對應的文件D[j] 中, 則矩陣α(H) 位置[i,j] 處的值為1,否則為0.

搜索模式反映了哪些搜索陷門對應歷史記錄中相同的關鍵詞.

定義3 (搜索模式) 文件集合D上的搜索模式σ(H) 由一個q-問詢歷史記錄H={D,w}誘導得出, 是一個大小為q×q的二元矩陣α(H), 使得

wi=wj表示第i行對應的關鍵詞wi與第j列對應的關鍵詞wj相同, 反之,wi ?=wj表示不同.

一個歷史記錄的軌跡包括能夠泄露的關于歷史記錄的信息, 具體來說包括訪問和搜索模式、文件大小和標識符, 除此以外不包含其它任何信息.

定義4 (軌跡) 文件集合D上的軌跡τ(H) 由一個q-問詢歷史記錄H={D,w}誘導得出, 是一個序列

2.2 差分隱私

差分隱私(differential privacy, DP)[28]是一個重要的隱私性的理論概念, 已經被廣泛地應用于數據庫隱私中[20,29].差分隱私以一個隱私參數ε為特征, 它保證了隱私保護算法的相鄰輸入產生任意給定輸出的概率是相近的, 因此通過觀察算法的輸出很難獲得關于秘密輸入的信息.借用Shang 等人[21]定義的SSE 中訪問模式泄露和搜索模式泄露的差分隱私性.用函數SE表示一個SSE 方案, 其輸入為一個文件集合D和一個關鍵詞問詢向量w, 輸出為一個軌跡τ(H), 其中H表示一個歷史記錄H={D,w}.

定義5 (訪問模式的差分隱私性) 一個由函數SE刻畫的SSE 方案的訪問模式具有ε-差分隱私性(ε-DP), 當且僅當對任意一個長度為q的關鍵詞問詢向量w ∈Δq, 對任意一對相鄰文件集合D,D′?22Δ(只在第i個文件中的關鍵詞w處不同, 其余位置處的關鍵詞相同, 即w要么在D[i] 中, 要么在D′[i] 中,但不會同時在兩者之中, 而D[i] 和D′[i] 其余位置的關鍵詞以及D和D′中的其余文件完全相同), 以及對任意的軌跡τ(H), 成立

上述定義保證了給定軌跡(允許泄露的信息) 不能決定一個文件是否包含一個關鍵詞, 這意味著具有ε-差分隱私性的文件也具有訪問模式隱私.

定義6 (搜索模式的差分隱私性) 一個由函數SE刻畫的SSE 方案的搜索模式具有ε-差分隱私性, 當且僅當對于任意一個數據集合D ?22Δ, 任意一對相鄰的關鍵詞問詢向量w,w′∈Δ|w|(w和w′只有一個元素不同, 即w[i]?=w′[i]), 以及對任意的軌跡τ(H), 成立

d表示D(w[i]) 和D(w′[i]) 中不同文件的數量.

上述定義保證了通過觀察軌跡(允許泄露的信息) 不能確定客戶端搜索的是哪一個關鍵詞列表.這意味著搜索模式的隱私性, 即服務器不能猜測自己執行的兩個問詢是否包含相同的關鍵詞.

2.3 對稱加密

一個對稱加密方案SE=(Gen,Enc,Dec) 由三個算法組成.密鑰生成算法Gen 能夠概率地輸出一個密鑰k ∈K,K是密鑰空間; 加密算法Enc 輸入一個密鑰k ∈K和一條消息m ∈M, 能夠輸出一個密文c ←?Enck(m), 其中M是明文空間; 解密算法Dec 輸入一個密鑰k ∈K和一條密文c ∈C, 能夠輸出一條明文m ←?Deck(c), 其中C是密文空間.

是可忽略的.

2.4 隱私謂詞加密

內積隱私謂詞加密(inner product predicate encryption,IPE)方案涉及一個謂詞函數P:A×B?→{0,1}, 其中A = B = Zlt,t是一個大質數, A 和B 分別稱為屬性向量空間和謂詞向量空間.對于所有的x,y ∈Zlt, 如果〈x,y〉=0, 則P(x,y)=1,〈·,·〉 表示計算兩個向量之間的內積.

一個IPE 方案由四個算法組成: (pp,SK)←?IPE.Setup(1λ) 中給定安全參數λ, 算法輸出系統參數pp 和私鑰SK; ctx ←?IPE.Encrypt(pp,SK,x,M) 中給定系統參數pp、私鑰SK、屬性向量x ∈A 和一條消息M, 輸出x的密文ctx; sky ←?IPE.KeyGen(pp,SK,y) 中給定系統參數pp、私鑰SK、謂詞向量y ∈B, 輸出對y的加密sky;M/⊥←?IPE.Decrypt(pp,ctx,sky) 中給定系統參數pp、屬性向量和謂詞向量的密文ctx和sky, 輸出消息M或者錯誤符號⊥.

稱IPE 方案是正確的, 如果對所有的λ ∈N,x ∈A,y ∈B, 對于(pp,SK)←?IPE.Setup(1λ),ctx ←?IPE.Encrypt(pp,SK,x,M) 和sky ←?IPE.KeyGen(pp,SK,y), 下式成立

IPE 中涉及三種安全性需求: 負載隱藏、屬性隱藏和謂詞隱藏.下面分別使用負載隱藏游戲、屬性隱藏游戲和謂詞隱藏游戲定義這三種安全性[31].

謂詞函數P: A×B?→{0,1}的負載隱藏安全性由一個挑戰者C和一個敵手A之間的游戲來定義.負載隱藏安全性保證了密文不會暴露關于被加密的消息的任何信息.

(1) 負載隱藏游戲

? 建立階段: 挑戰者C運行IPE.Setup(1λ) 產生系統參數pp 和私鑰SK.將pp 發送給敵手A, 并秘密保管私鑰SK.

? 問詢階段1:A能夠對下列預言機進行多項式次數的問詢:

– KeyGenOKey(y) :A發送一個關于y ∈B 的問詢, 返回一個私鑰sky ←?IPE.KeyGen(pp,SK,y).

– EncryptOEnc(x) :A發送一個關于x ∈A 和消息M的問詢, 返回一個密文ctx ←?IPE.Encrypt(pp,SK,x,M).

? 挑戰階段: 敵手A向挑戰者C提交一個x?∈A 和兩個長度相同的消息M0,M1.要求對所有在問詢階段1 中問詢過預言機OKey的y ∈B 滿足P(x?,y)=0.C隨機選擇b ∈{0,1}, 返回一個挑戰密文ctx?←?IPE.Encrypt(pp,SK,x?,Mb).

? 問詢階段2: 這一階段與問詢階段1 相同, 但A只被允許向預言機OKey問詢滿足P(x?,y) = 0的y ∈B.

? 猜測: 敵手A輸出一個比特b′, 如果b′=b則贏得游戲.

敵手贏得上述負載隱藏游戲的優勢被定義為

定義7 (IPE 的負載隱藏) 稱IPE 是負載隱藏的, 如果不存在概率多項式時間的敵手A能夠以一個不可忽略的優勢贏得上述負載隱藏游戲.

下面通過一個挑戰者C和一個敵手A之間的游戲來定義IPE 屬性隱藏安全性.屬性隱藏安全性保證了敵手不能通過密文ctx獲得關于屬性x ∈A 的任何信息.

(2) 屬性隱藏游戲

? 建立階段、問詢階段1、問詢階段2 和猜測與負載隱藏游戲相同.

? 挑戰階段: 敵手A向挑戰者C提交兩個屬性x(0),x(1)∈A 和一個消息M.要求對所有在問詢階段1 中問詢過預言機OKey的y ∈B 有P(x(0),y) =P(x(1),y).C隨機選擇b ∈{0,1}, 返回一個挑戰密文ctxb ←?IPE.Encrypt(pp,SK,x(b),M).

敵手贏得上述屬性隱藏游戲的優勢被定義為

定義8 (IPE 的屬性隱藏) 稱IPE 是屬性隱藏的, 如果不存在概率多項式時間的敵手A能夠以一個不可忽略的優勢贏得上述屬性隱藏游戲.

下面通過一個挑戰者C和一個敵手A之間的游戲來定義IPE 謂詞隱藏安全性.謂詞隱藏安全性保證了敵手不能通過私鑰sky獲得關于謂詞y ∈B 的任何信息.

(3) 謂詞隱藏游戲

? 建立階段、問詢階段1、問詢階段2 和猜測與負載隱藏游戲相同.

? 挑戰階段: 敵手A向挑戰者C提交兩個屬性y(0),y(1)∈B, 要求對所有在問詢階段1 中問詢過預言機OEnc的x ∈A 有P(x,y(0)) =P(x,y(1)).C隨機選擇b ∈{0,1}, 返回一個挑戰私鑰sky(b)←?IPE.KeyGen(pp,SK,y(b)).

敵手贏得上述屬性隱藏游戲的優勢被定義為

定義9 (IPE 的謂詞隱藏) 稱IPE 是謂詞隱藏的, 如果不存在概率多項式時間的敵手A能夠以一個不可忽略的優勢贏得上述謂詞隱藏游戲.

2.5 基于近似同態加密的打包加密

近似同態加密(somewhat homomorphic encryption, SHE) 是一種支持在密文上進行有限次加法和乘法運算的公鑰加密方案.Yasuda 等人[34]給出了一個基于SHE 的打包加密方式, 他們給出的打包方式能夠高效計算向量內積.本文方案借助文獻[34] 中的打包加密產生關鍵詞的加密問詢.

SHE 方案涉及一個基本環R=Z[x]/(f(x)), 其中f(x)=xn+1 是n階的分圓多項式,n是2 的冪次.SHE 的密文空間是基本環Rq=R/qR=Fq[x]/(f(x)), 其中q是一個質數, 有q ≡1(mod 2n).SHE 的明文空空間為Rt=Ft[x]/(f(x)),t ＜q是一個整數.SHE 還涉及一個標準差為σ的離散高斯錯誤分布χ=DZn,σ.

s選自噪聲分布χ,ai是Rq中的一個均勻隨機元素, “錯誤多項式”ei選自錯誤分布χ,ui是Rq中一個均勻隨機的環元素.c≈表示計算不可區分.

定義10 (兩種打包加密PackEncrypt)[34]對于一個長度為n的向量A=(A0,A1,···,An?1)∈Znt,定義兩種類型的打包密文:

(1) 設pm1(A) = ∑n?1i=0Aixi, 對于足夠大的t, 可以將多項式pm1(A) 認為是Rt中的元素.然后,定義ctpack(1)(pm1(A))←?SHE.Encrypt(pm1(A),pk) 為第一種類型的打包密文.

(2) 設pm2(A) =?∑n?1i=0Aixn?i, 定義ctpack(2)(pm2(A))←?SHE.Encrypt(pm2(A),pk) 為第二種類型的打包密文.

定理 1 (打包密文上的安全內積計算)[34]對于兩個長度為n的向量A,B, 設密文 ct 為ctpack(1)(pm1(A)) 和ctpack(2)(pm2(B)) 之間的同態乘積.定義m0為解密結果SHE.Decrypt(ct,sk)∈Rt中的常數項, 則m0=〈A,B〉modt, 即解密結果中的常數項是向量A,B的內積.

注意到, 對于兩個向量A= (A0,A1,···,An?1) 和B= (B0,B1,···,Bn?1).計算A的第一種類型的打包密文ctpack(1)(pm1(A)) = (c0,c1), 并計算B按照第二種類型打包后得到的多項式pm2(B)·ctpack(1)(pm1(A)) = pm2(B)·(c0,c1) = (pm2(B)·c0,pm2(B)·c1), 調用SHE.Decrypt 對其解密后得到的多項式的常數項也為〈A,B〉.

2.6 偽隨機函數和偽隨機生成器

定義11 (偽隨機函數(pseudorandom functions, PRF))[36]一個PRFF:K×X ?→Y是一個定義在密鑰空間K、一個域X和一個范圍Y上的帶密鑰的函數(這些集合被安全參數λ參數化),F的輸出與一個真正的隨機值不可區分.一個PRF 的安全性由兩個與敵手A的實驗EXP(0) 和EXP(1) 定義.首先從密鑰空間K中均勻隨機選擇一個密鑰k, 給定對PRF 的描述, 敵手被允許對以下預言機進行問詢:

?Evaluate:A輸入x ∈X, 返回F(k,x).

?Challenge:A輸入x ∈X,要求x沒有在Evaluate 預言機中被問詢過.如果b=1,返回F(k,x);如果b=0, 預言機返回一個隨機值y ∈Y.

敵手完成對上述預言機的問詢后, 輸出一個比特b′∈{0,1}.定義Wb為敵手在實驗EXP(b) 中輸出b′=1 的事件.敵手A的優勢定義為

稱一個PRF 是安全的, 如果對于所有PPT 敵手A, AdvPRFA(1λ) 是可忽略的.

定義12 (密鑰同態的PRF (key-homomorphic PRF))[37]設(K,?) 和(Y,?) 是群.稱一個帶密鑰的函數F:K×X ?→Y是一個密鑰同態的PRF, 如果

(1)F是一個安全的PRF;

(2) 對于任意的k1,k2∈K和x ∈X, 有

定義13 (偽隨機生成器(pseudorandom generators, PRG))[37]一個PRG 是一個高效的可計算的函數G:X ?→Y, 其中(X,?) 和(Y,?) 是群.稱一個PRG 是安全的, 如果對于任意的PPT 算法A

是可忽略的.

3 模式隱藏的對稱可搜索加密方案

3.1 符號說明

設Δ 表示所有可能的關鍵詞組成的關鍵詞域,|Δ| =s.設N個數據所有者DO ={DO1,DO2,···,DON}, 考慮一個數據所有者DO∈DO, 設其文件集合為D={D1,D2,···,Dn},D中的第i個文件D[i] 的關鍵詞列表為Wi,1≤i ≤n,Wi中的元素滿足如下條件: 對于關鍵詞列表Δ 中的第j個關鍵詞w=Δ[j]:

(1) 如果w ∈Wi, 則令Wi[j]=w,1≤j ≤s;

(2) 如果w/∈Wi,Wi[j]=w?1,w?1是不屬于Δ 的隨機元素.

這樣, 對于所有的1≤i ≤n, 有|Wi|=s.另外, 小寫加粗字母表示向量, 大寫加粗字母表示集合, 其它符號首次出現時會進行說明.表2 概括了方案中用到的符號.

表2 方案的符號表示Table 2 Symbolic representation of scheme

表3 概率分析Table 3 Probabilistic analysis

表4 通信開銷Table 4 Communication Overhead

3.2 參數說明

本文方案中, 每一次關鍵詞問詢都會產生一個混淆訪問模式, 即返回的文件中有的包含問詢的關鍵詞,有的不包含問詢的關鍵詞(誤報), 還有一些文件雖然包含了問詢的關鍵詞但是沒有被返回(假陰性).誤報和假陰性的存在會產生一些效用損失, 效用損失可以用真陽性率(true positive rate, TPR) 和誤報率(false positive rate, FPR) 來刻畫:

? 真陽性率(TPR) 指返回文件中包含問詢關鍵詞的概率.? 誤報率(FPR) 指返回文件中不包含問詢關鍵詞的概率.

大多數情況中, 數據用戶會要求盡量高的真陽性率(TPR).另外, 為了減少通信開銷以及對精確度的要求, 需要盡量低的誤報率(FPR).本文方案中, 文件索引中的誤報和假陰性由數據用戶發送的關鍵詞搜索陷門觸發, 因此數據用戶能夠在產生關鍵詞搜索陷門時對TPR 和FPR 進行調節.

3.3 方案的系統框架

本文方案分為建立階段和搜索階段, 由三個實體組成: 誠實的數據所有者DO、數據用戶U以及一個誠實且好奇的服務器S.

3.3.1 建立階段

建立階段由數據所有者DO 完成.這一階段中, 不同數據所有者會使用各自的密鑰生成文件索引和文件的搜索令牌列表, 對文件加密, 并將文件索引、搜索令牌列表以及加密文件上傳到服務器.

在索引生成算法BuildIndex 中, 將關鍵詞列表Wi中的元素和文件標識符indi作為多項式的根.DO 調用多項式生成函數GenPoly(Wi,indi) 生成多項式的系數向量x= (x1,x2,···,xs+2)∈Zs+2t(因為有s+ 1 個根(s個Wi中的元素和1 個文件id 作為根), 所以多項式有s+ 2 個系數), 將其作為文件的屬性向量.然后使用隱私謂詞加密對x和文件標識符indi ∈{0,1}m加密, 得到加密索引Ii=ctx=(c0,c1,···,cs+2)∈{0,1}m×Zs+2t.在令牌列表生成算法TokenList 中, 對于Wi中的每一個元素, DO 調用謂詞生成函數GenPred(w) 生成元素w ∈Wi的謂詞向量y=(y1,y2,···,ys+2)∈Zs+2t,其中yi=wi?1,1≤i ≤s+2.使用隱私謂詞加密對y加密, 得到sky ∈Zt.另外, 調用GenPred 分別生成文件標識符indi和一個隨機元素w?1/∈Δ 的謂詞向量, 并使用隱私謂詞加密對這兩個謂詞向量加密.上述得到的所有謂詞向量的密文能夠組成一個s+2 維的列表TKi ∈Zs+2t, 將其作為文件D[i] 的搜索令牌列表.

3.3.2 搜索階段

這一階段由數據用戶U和服務器S共同完成.數據用戶U使用自己的用戶密鑰KU生成關鍵詞搜索陷門并發送至服務器進行關鍵詞問詢, 服務器S使用接收到的搜索陷門能夠在不同數據所有者上傳的文件索引上執行搜索操作并將與陷門匹配的文件返回給數據用戶U.

圖1 給出了本文方案的系統模型圖.

圖1 系統模型圖Figure 1 System model diagram

3.4 方案的安全定義

根據Curtmola 等人[4]給出的安全性定義, 考慮一個挑戰者C和一個敵手A=(A0,A1,···,Av+1)之間的游戲IndSSE,A(λ), 其中λ ∈N 是安全參數.

(1) 挑戰者C運行(pp,KI,KDO)←?Setup(1λ,1s) 產生對稱加密密鑰KDO、索引密鑰KI和系統參數pp; 運行KU ←?KeyGen(1λ) 產生用戶密鑰KU;C將pp 發送給A并公開, 保持KDO、KI和KU的隱私性, 選擇一個隨機比特b ←?{0,1}.

(2) 運行(stA,D0,D1)←?A0(1λ), 將兩個文件集合(D0,D1) 發送給C.stA是一個字符串, 用于捕捉A的狀態.

(3) 對于文件集合Db中的每一個文件,C分別運行BuildIndex 和TokenList, 產生文件索引集合Ib和令牌列表集合TKbi;C運行Cb ←?Encrypt(KDO,Db)產生密文集合Cb;C將(Ib,{TKbi},Cb)返回給A.

(4) 運行(stA,w0,1,w1,1)←?A1(stA,Ib,{TKbi},Cb) 將關鍵詞對(w0,1,w1,1) 發送給C.

(5)C運行tb,1←?Trapdoor(KU,wb,1), 將tb,1返回給A.

(6) 對2≤i ≤v, 運行(stA,w0,i,w1,i)←?Ai(stA,Ib,{TKbi},Cb,tb,1,tb,2,···,tb,i?1), 將關鍵詞對(w0,i,w1,i) 發送給C.

(7)C產生關鍵詞wb,i的搜索陷門tb,i ←?Trapdoor(KU,wb,i), 將tb,1返回給A.

(8) 令tb=(tb,1,tb,2,···,tb,v), 運行b′←?Av+1(stA,Ib,{TKbi},Cb,tb).

(9) 如果b′=b, 則輸出1; 否則輸出0.其中限制τ(D0,w0,1,w0,2,···,w0,v) =τ(D1,w1,1,w1,2,···,w1,v).稱SSE 在自適應不可區分性的意義上是安全的, 如果對于所有多項式大小的敵手A= (A0,A1,···,Av+1),v= poly(λ),贏得上述游戲的優勢

是可忽略的.概率來自于對b的選擇以及算法中用到的概率.

4 具體方案

4.1 建立階段

這一階段由數據所有者DO∈DO 運行, 受到Tseng 等人[33]利用密鑰同態的PRF 構造的具有屬性和謂詞隱藏性的IPE 方案(下面簡記為KIPE) 的啟發, 建立文件D[i]∈D的搜索索引Ii, 搜索令牌列表TKi, 并對文件加密, 將Ii、TKi和加密文件上傳到服務器.

設文件D[i] 的關鍵詞列表為Wi,1≤i ≤n,Wi中元素的性質如前文所述.

4.2 搜索階段

這一階段由數據用戶U和服務器S共同完成.利用Yasuda 等人[34]給出基于SHE 的打包加密方案生成數據用戶的搜索面門.

考慮問詢關鍵詞Δ[k],1≤k ≤s.注意到, 如果Δ[k]∈D[i], 則有Wi[k]=Δ[k].

其中yid是indi的謂詞向量.服務器S將ct1,ct2,ct3返回給數據用戶U.

數據用戶U接收到來自服務器的ct1,ct2,ct3后, 首先調用SHE.Decrypt 對ct1,ct2,ct3解密, 分別得到m1= TK[j] (j可能的取值為k,s+1,s+2),m2=〈c,y〉, 令m3= ct3.數據用戶U按如下步驟計算:

在搜索階段中, 由于搜索陷門是通過近似同態加密中的打包加密算法SHE.PackEncrypt 生成的,因此根據SHE.PackEncrypt 算法的性質, 搜索陷門能夠與存儲在服務器上的密文索引中的c和搜索令牌列表TKi的打包形式pm2(c) 和pm2(TKi) 直接進行同態乘操作, 從而得到計算結果(ct1,ct2,ct3), 數據用戶可以通過服務器返回的(ct1,ct2,ct3) 得到搜索結果.由于在服務器的搜索過程中只在搜索陷門和密文索引之間進行了同態乘操作, 所以數據用戶的搜索陷門可以在不同密鑰加密的文件索引上搜索, 同時生成的陷門大小只與要求的真陽性率和誤報率有關, 而與要搜索的文件數量獨立.

5 安全性分析

5.1 參數分析

本文方案中, 數據用戶產生的加密問詢能夠概率地觸發文件索引中的誤報和假陰性, 因此每一次關鍵詞問詢都會產生一個全新的混淆訪問模式, 這樣就同時隱藏了訪問模式和搜索模式.

在文件索引的建立過程中, 需要向索引中添加誤報和假陰性, 因此, 一個文件的索引中一共存在四種狀態: 真陽性、假陽性(即誤報)、真陰性和假陰性.在一次問詢的過程中, 文件中的哪一種狀態被觸發完全由關鍵詞搜索陷門決定.下面對一個文件索引中的4 種狀態被觸發的概率進行分析.

要求:

(1) TPR＞FPR, 即v(PTP+PFP)＞(1?v)PFP;

(2) FNR＞FPR, 即vPFN＞(1?v)PFP(為了減少帶寬開銷要求盡量低的誤報率).

5.2 方案的自適應的不可區分安全性

定理2 如果方案底層的密鑰同態的PRF 和PRG 是安全的, SHE 在PLWE 假設下是安全的, 對稱加密方案SE 是CPA 安全的, 則本文給出的SSE 方案具有自適應的不可區分安全性.

引理1 如果方案中底層的密鑰同態的PRFF是安全的, 則對于k= 1,2,···,s+2, Gamek?1與Gamek之間是不可區分的, 并且對于k′=1,2,···,s+2, Games+3+k′?1與Games+3+k′之間是不可區分的.

證明: 首先證明, 對于k=1,2,···,s+2, Gamek?1與Gamek之間是不可區分的.

假設存在一個敵手A能夠以一個不可忽略的優勢區分Gamek?1與Gamek,k=1,2,···,s+2.則能夠構建一個挑戰者C1區分定義11 中的實驗EXP(0) 和EXP(1).在調用實驗EXP(b) 并接收到對PRFF的描述后, 挑戰者C1模擬與敵手A的游戲.

? 建立階段: 挑戰者首先從Zt中隨機選擇a1,···,ak?1,ak+1,···,as+2, 從X中隨機選擇h, 并選擇一個PRGG, 將pp = (F,G) 發送給敵手A.挑戰者使用h對底層實驗進行挑戰查詢, 并獲得f作為響應.

? 問詢階段1: 在這一階段中, 敵手被允許對以下預言機進行多項式次數的問詢:

– KeyGenOKey(y): 輸入一個向量y=(y1,y2,···,ys+2)∈Zs+2t, 挑戰者計算

并將sky返回給敵手.通過將ak設置為底層實驗選擇的密鑰, 可知sky是一個y的有效的私鑰.

– EncryptOEnc(x): 輸入一個向量x=(x1,x2,···,xs+2)∈Zs+2t和一個消息M.挑戰者執行以下操作:

(1) 從Zt中隨機選擇δ,σ.

(2) 計算ck=F(δxk,h)+f+σ.

(3) 對于i=1,···,k ?1,k+1,···,s+2, 計算ci=F(δxi+ai,h)+σ.

(4) 計算c0=M ⊕G(σ).

(5) 返回ctx=(c0,c1,···,cs+2).

? 挑戰階段: 敵手提交兩個具有相同長度的消息M0,M1, 和一個向量x?=(x?1,x?2,···,x?s+2), 要求對于所有問詢過預言機OKey的y有〈x?,y〉?= 0.在接收到x?,M0,M1之后, 挑戰者隨機選擇β ∈{0,1}, 然后按照如下方式計算挑戰密文ct?:

(1) 從Zt中隨機選擇δ,σ.

因此預言機的回應都是形式正確的.

下面分析挑戰者C1攻破底層PRF 的優勢.首先, 如果挑戰者與實驗EXP(0) 交互, 則f是Zt中的一個隨機元素, 因此挑戰密文中的c1,c2,···,ck是隨機元素, 此時是在Gamek中, 則有

如果挑戰者與實驗EXP(1) 交互, 則f是輸入為h的PRF 的輸出.將ak設置為底層實驗的密鑰,則有f=F(ak,h), 此時預言機的回應顯然是形式正確的.挑戰密文

因此, 如果底層的PRF 是安全的, 則對于k=1,2,···,s+2, Gamek?1和Gamek是不可區分的.

以上從負載隱藏模型下證明了Gamek?1和Gamek是不可區分的,k= 1,2,···,s+2, 下面證明在屬性隱藏模型下Gamek?1和Gamek是不可區分的,k=1,2,···,s+2.

假設存在一個敵手A能夠以一個不可忽略的優勢區分Gamek?1與Gamek,k= 1,2,···,s+2.則能夠構建一個挑戰者C′1區分定義11 中的實驗EXP(0) 和EXP(1).在調用實驗EXP(b) 并接收到對PRFF的描述后, 挑戰者C′1模擬與敵手A的游戲.

所以, 如果底層的PRF 是安全的, 則對于k=1,2,···,s+2, Gamek?1和Gamek是不可區分的.

因此無論是在負載隱藏模型下還是在屬性隱藏模型下Gamek?1和Gamek都是不可區分的,k=1,2,···,s+2.

下面在謂詞隱藏模型下, 證明對于k′= 1,2,···,s+2, Games+3+k′?1與Games+3+k′之間是不可區分的.′

Gamek′?1,s+2和Gamek′,s+2顯然是一致的.下面證明如果底層的PRFF是安全的, 則對于i=1,2,···,s+2, Gamek′?1,i?1和Gamek′?1,i是不可區分的.

設存在一個敵手A能夠以一個不可忽略的優勢區分Gamek′?1,i?1和Gamek′?1,i, 則能夠構建一個挑戰者C2區分定義11 中的實驗EXP(0) 和EXP(1).在調用實驗EXP(b) 并接收到關于PRFF的描述后, 挑戰者C2按如下方式模擬與敵手A的游戲:

將sk?返回給敵手A.

如果挑戰者與實驗EXP(1) 交互, 則f是PRF 輸入h后的輸出.將ai設置為底層實驗選擇的密鑰,則有f=F(ai,h), 因此有

引理2 如果方案中底層的PRGG是安全的, 則Games+2與Games+3之間是不可區分的.

證明: 挑戰者C3接收到關于PRGG的描述和ψ ∈{0,1}m之后, 模擬下述與敵手A的游戲:

建立階段: 挑戰者首先選擇一個密鑰同態偽隨機函數F: Zt×X ?→Zt, 從Zt中隨機選擇a1,a2,···,as+2, 從X中隨機選擇h, 然后將(F,G) 發送給敵手.

問詢階段1: 按照引理1 中的預言機OKey,OEnc回應問詢.

挑戰階段: 敵手提交兩個長度相同的消息M0,M1和一個向量x?, 要求對于所有在問詢階段1 中問詢過OKey的y滿足〈x?,y〉?=0.在接收到M0,M1,x?之后, 挑戰者隨機選擇β ∈{0,1}并計算挑戰密文ct?: 隨機選擇R1,R2,···,Rs+2∈Zt, 對于i= 1,2,···,s+2, 設ci=Ri, 計算c0=Mβ ⊕ψ.返回挑戰密文ct?=(c0,c1,···,cs+2).

問詢階段2: 與問詢階段1 相同, 但要求敵手不能向預言機OKey問詢滿足〈x?,y〉=0 的y.

猜測: 敵手輸出一個比特β′.如果β′=β則敵手輸出1.設Ss+2表示敵手在Games+2中正確輸出這一事件.如果ψ=G(σ) 是由PRGG輸入σ后生成的, 則此時是在Games+2中, 并且有

因此有

是可忽略的.

引理3 如果底層的SHE 在PLWE 假設下是安全的, 則對于l= 1,2,···,v, Game2s+5+l?1與Game2s+5+l之間是不可區分的.

證明: 假設存在一個敵手A能夠區分Game2s+5+l?1和Game2s+5+l, 1≤l ≤v.下面構造一個挑戰者C4:

(1)C4選擇s ←?χ作為私鑰sk=s, 另外選擇a1←?Rq和e ←?χ.

(2) 對于來自A的關鍵詞對(w0,l,w1,l),C4選擇一個比特β.C4選擇u,f,g ←?χ, 計算wβ,l的陷門tβ,l= (c0,l,c1,l),c0,l=a0u+tg+pm1(x),c1,l=a1u+tf x是wβ,l的謂詞向量.其中a0∈{?a1s,?(a1s+te)}, 將事件a0=?a1s記做～W0, 將事件a0=?(a1s+te) 記做～W1.C4將tβ,l返回給A.

(3)A接收到tβ=(tβ,1,tβ,2,···,tβ,v) 后, 輸出一個比特b′.如果b=b′,C4輸出1, 否則輸出0.首先說明C4計算出的挑戰密文是符合規范的.如果a0=?a1s,則c0,k=?a1su+tg+pm1(x),計算[c0,k+c1,ks]qmodt可解密得到pm1(x).如果a0=?(a1s+te), 則(c0,k,c1,k) 顯然為合法密文.設Si表示敵手A攻破Gamei這一事件.當a0=?a1s, 即事件W0發生時,a0為一隨機元素,所以(c0,k,c1,k) 是(Rq)2中的一個隨機元素, 則此時是在Gamek中, 因而有

是可忽略的.

注意到, Pr[S0]=Pr[IndSSE,A(λ)=1], 所以有

是可忽略的.

5.3 方案的差分隱私性

本文方案通過隨機地添加誤報和假陰性同時隱藏了訪問和搜索模式.下面刻畫泄露的訪問模式, 即混淆訪問模式, 利用混淆的訪問模式定義本文方案的泄露(即混淆軌跡), 并使用混淆軌跡概念進行方案的差分隱私性證明.

其中Bern() 函數表示Bernoulli 分布.

下面給出混淆訪問模式的定義.

定義14 (混淆訪問模式) 一個歷史記錄H上的混淆訪問模式?α(H) 是一個大小為q×n的二元矩陣, 其中第i行用式(1)來刻畫.

混淆軌跡概括了本文方案的泄露.

定義15 (混淆軌跡) 本文方案中, 在對q個關鍵詞搜索時, 一個歷史記錄的軌跡稱為混淆軌跡, 定義為?T, 有

最后, 如果考慮q個問詢的序列, 最壞的情況是, 這q個問詢都是對w?或者都是對w′?的問詢, 則根據訪問模式的差分隱私定義, 可以得到

(2) 搜索模式的差分隱私性證明

所以

6 方案的性能分析

6.1 理論分析

6.1.1 通信開銷

設數據用戶U授權訪問的文件數量為ndoc.對關鍵詞w= Δ[k],1≤k ≤s進行問詢時的通信開銷依賴于:

(1) 客戶端發送給服務器的搜索陷門大小;

(2) 服務器返回給客戶端的在文件索引上計算出的密文總數ndoc(為授權訪問的文件總數);

(3) 客戶端發送給服務器的id 總數(≤ndoc);

(4) 服務器返回給客戶端的所有文件.

所以本文方案的全部通信開銷為

所以本文方案的通信開銷是一個標準SSE 方案的通信開銷的cost_over 倍, 其值取決于Ew, 即取決于問詢內容和關鍵詞的分布.

6.1.2 計算開銷

本文方案除了相關參數和密鑰以外不需要額外的客戶端存儲.另外, 由于建立階段只需要進行一次,因此忽略建立階段的計算復雜度和通信開銷的分析.

考慮對一個關鍵詞問詢時的計算復雜度.首先考慮服務器的計算復雜度, 這里將其衡量為服務器需要執行的搜索陷門和文件索引之間的計算次數, 即為數據用戶U能夠訪問的所有文件的數量ndoc.對于客戶端的計算復雜度, 將其衡量為客戶端需要執行的計算次數, 由于服務器將每一個文件索引上計算得到的密文返回給問詢用戶, 因此客戶端計算文件id 時需要執行的計算次數也為ndoc.

6.2 實驗分析

這一節將對本文方案的效率進行實驗分析.

使用Enron 電子郵件數據集[39]中的數據,在設備Intel(R)Core(TM)i7-6700HQ CPU@2.60 GHz上使用java 對本文方案進行測試.

根據不同的應用環境, 為了保證SHE 方案的安全性和正確性, 需要設置合適的密鑰參數(n,q,t,σ).這里主要基于文獻[29] 中的工作設置參數.

根據文獻[40] 中的結論, 如果滿足

就能夠保證SHE 方案的正確性.具體來說, 取σ=8,t=2048 作為明文空間的參數, 另外, 取n ≥2048,根據上述不等式可以得到q ＞260, 所以

將本文方案與Shang 等人[21]給出的能夠同時隱藏訪問和搜索模式的OSSE 方案進行對比.

圖2 展示了在真陽性率TPR=0.99 時, 客戶端生成一個關鍵詞的搜索陷門的時間與授權搜索的文件數量ndoc之間的關系.本文方案生成一個關鍵詞的搜索陷門的時間大約為11 s, 受文件數量的影響非常微小.另外, 一個打包密文的大小為2n·lg(q)≈31 KB, 所以在一次關鍵詞問詢時客戶端發送給服務器的搜索陷門的大小為(#tw·31) KB, 與授權搜索的文件數量是獨立的, 因此本文方案適用于多數據所有者場景.OSSE 方案中, 一次關鍵詞問詢所生成的搜索陷門數量等于要搜索的文件數量, 所以生成搜索陷門的時間與文件數量呈線性關系, 故OSSE 方案顯然不適用于多數據所有者場景.

圖2 生成搜索陷門時間與文件數量的關系Figure 2 Relationship between trapdoor generation time and number of files

圖3 展示了本文方案與OSSE 方案在不同真陽性率(TPR)下客戶端生成搜索陷門的時間.結果顯示,本文方案中, 生成關鍵詞搜索陷門所需的時間隨著TPR 的變大而增長, 而OSSE 方案陷門生成時間不受TPR 的影響.由于本文方案中的TPR 完全由問詢用戶決定, 因此數據用戶可以根據自身需求選擇合適的TPR 以平衡效率和安全性.

圖3 不同TPR 下搜素陷門生成時間Figure 3 Trapdoor generation time under different TPRs

圖4 展示了一次關鍵詞問詢中本文方案的搜索時間與ndoc之間的關系.結果顯示, 搜索時間會隨著文件數量的增長有明顯增長.

圖4 搜索時間與文件數量的關系Figure 4 Relationship between search time and number of files

圖5 展示了一次關鍵詞問詢中本文方案中客戶端計算文件id 的時間與ndoc之間的關系.結果顯示,客戶端的計算時間會隨著文件數量的增長有明顯增長.

圖5 客戶端計算時間與文件數量的關系Figure 5 Relationship between client computing time and number of files

7 總結

針對現有大多數可搜索加密方案中普遍存在的訪問和搜索模式泄露問題, 本文給出了一個多數據所有者場景下能夠同時隱藏訪問和搜索模式的對稱可搜索加密方案, 滿足自適應的不可區分安全性, 并且能夠證明方案具有訪問和搜索模式的差分隱私安全性.本文方案借助內積謂詞加密生成文件索引, 使用近似同態加密生成關鍵詞搜索陷門, 最終實現了只需要一個單一的關鍵詞搜索陷門, 就能夠在不同密鑰加密的文件索引上進行搜索, 并且每一次關鍵詞問詢都會產生一個全新的混淆訪問模式, 從而同時隱藏了訪問模式和搜索模式.本文考慮的是靜態數據庫中隱藏訪問和搜索模式, 未來將進一步研究動態數據庫中隱藏訪問和搜索模式.