云環境下加密圖上top-k 最近模糊關鍵詞查詢

潘瑛穎

(福建師范大學 計算機與網絡空間安全學院,福建 福州 350117)

0 引言

圖數據在許多領域得到廣泛應用,如社交網絡、知識圖譜等。 隨著云計算的快速發展,數據擁有者傾向于將大規模圖數據外包給云服務器以降低存儲和管理成本,但數據隱私泄露的風險也由此增加。 為保護數據隱私,數據擁有者需要在外包前對圖數據進行加密,同時保留一定的隱私查詢能力。

2010 年,Chase 等[1]引入結構化加密的概念并提出支持圖的鄰居查詢、鄰接查詢和標記圖上聚集子圖查詢的結構化加密方案。 此后,一系列支持近似或精確最短距離查詢[2-3]、約束最短距離查詢[4]、最短路徑查詢等功能的圖加密方案先后提出[5]。 Liu 等[6]提出了支持top-k 最近關鍵字查詢的圖加密方案,查詢距離給定節點最近的k 個具有給定關鍵詞的節點,是一類重要的圖查詢應用。 但是,該方案針對精確關鍵字的提出,缺乏對細微的文字拼寫錯誤的容忍,在一些場景下不能滿足應用的需要。 在此基礎上,本文提出支持在加密圖上進行top-k 最近模糊關鍵詞查詢的圖加密方案,該方案基于2-Hop 標簽技術構造加密的2-Hop 標簽索引,使用基于通配符的方法為關鍵詞生成模糊集,構造模糊關鍵詞索引,可以在出現細微拼寫錯誤的情況下,返回距離給定節點最近的k 個可能被想要的關鍵詞標記的節點。

1 符號定義和系統模型

1.1 符號定義

本文的符號定義如表1 所示。 SKE=(Gen,Enc,Dec)是一個對稱加密方案,包括密鑰生成算法SKE.Gen、加密算法SKE. Enc 和解密算法SKE. Dec,在選擇明文攻擊下具有偽隨機的密文,滿足CPA 安全。無向標記圖G=(V,E,W)由頂點集V、邊集E 和關鍵詞字典W 組成,對于關鍵詞w,W[w]存儲被w 標記的頂點的集合。

表1 符號定義

1.2 系統模型

本文方案支持在加密的標記圖上進行top-k 最近模糊關鍵詞查詢,標記圖的各個節點被若干關鍵詞標記。 方案的系統模型包括兩個實體:用戶和云服務器。 用戶將原始圖數據轉換成加密索引外包給云服務器;用戶將查詢令牌T 發送給云服務器;云服務器執行查詢算法獲得加密結果R 并返回給用戶。 R 由k個節點密文組成,用戶解密R 得到明文結果。 具體如圖1 所示。

圖1 系統模型

本文提出的支持top-k 最近模糊關鍵詞查詢的圖加密方案包括5 個算法,形式化定義如下。

定義1. 一個支持top-k 最近模糊關鍵詞查詢的圖加密方案Π 是一個包括5 個算法的元組Π =(KeyGen, Encrypt, Token, Query, Decrypt)。

(1)K←KeyGen(1λ):密鑰生成算法,輸入安全參數λ,輸出密鑰集K。

(2)I←Encrypt(K,G):加密算法,輸入密鑰集K和圖G,輸出加密索引I。

(3)T←Token(K,k,v,w):令牌生成算法,輸入密鑰集K,整數k,節點v 和關鍵詞w,輸出令牌T。

(4)R←Query(I,T):查詢算法,輸入加密索引I和令牌T,輸出加密結果R。

(5)m←Decrypt(K,R):解密算法,輸入密鑰K 和加密結果R,解密得到明文結果m。

1.3 安全模型

圖加密是結構化加密的一種,因此本文修改使用Chase 等[1]提出的自適應選擇查詢攻擊安全性定義,即CQA2-安全性定義。 云服務器是誠實但好奇的,本文中被認為是敵手A。 泄露函數Λ1和Λ2分別表示存儲在云服務器的加密數據泄露的信息和云服務器接收令牌查詢的過程的泄露。

定義2. (CQA2-安全性)方案Π = (KeyGen,Encrypt, Token, Query, Decrypt)是一個圖加密查詢方案,Λ1和Λ2是方案的兩個泄露函數。 給定安全參數λ,半誠實敵手A 和模擬器Σ 執行的兩個概率性實驗Real 和Ideal,定義如下。

(1)RealA(λ):敵手A 選擇一個圖G 發送給挑戰者。 挑戰者生成密鑰K←KeyGen(1λ),計算加密索引I←Encrypt(K,G)返回給A。 A 生成多項式數量的自適應查詢發送給挑戰者。 對于每個查詢(k,v,w),挑戰者生成令牌T←Token(K,k,v,w)發送給A,A 運行Query(I,T)獲得R。 最后,A 返回b∈{0,1}作為Real實驗的輸出。

(2)IdealA,∑(λ):A 選擇圖G。 給定泄露函數Λ1(G),Σ 模擬得到加密索引I?發送給A。 A 生成多項式數量的自適應查詢。 給定泄露函數Λ2,對于每個查詢q,Σ 獲得Λ2(I,Q),根據Λ2(I,Q)模擬令牌T?返回給A,A 運行Query(I?,T?)獲得模擬查詢結果R?。 最后,A 返回b∈{0,1}作為Ideal 實驗的輸出。

如果對所有概率多項式時間(Probabilistic Polynomial Time,PPT)敵手A,存在PPT 模擬器Σ滿足:

| Pr[RealA(λ) = 1] - Pr[IdealA,S(λ) = 1] |≤negl(λ)

negl(λ)是一個可忽略函數,則方案Π 對于自適應選擇查詢攻擊是(L1,L2)-安全的。

2 相關技術

2.1 2-Hop 標簽

2-Hop 標簽是一種預生成的快速計算兩節點間最短距離的索引結構[7]。 給定無向圖G=(V,E),L是圖G 的2-Hop 標簽,則L 為每個節點v 分配標簽集L(v)。 L(v)是(u,d)對的集合,u 表示共享節點,d 表示u 和v 之間的最短距離。

對于任意兩個可達頂點s 和t,存在至少一個節點u,使2-Hop 標簽滿足:(1)(u,d1)∈L(s),(u,d2)∈L(t);(2)u 在s 和t 之間的最短路徑上。 因此,對于任意兩個可達節點s 和t,可使用以下公式在L 上回答s 和t 之間的最短距離查詢distQ(s,t,L)。

distQ(s,t,L)=min{d1+d2| (u,d1)∈L(s),(u,d2) ∈L(t)}

如果L(s)和L(t)沒有共享節點,則distQ(s,t,L)=∞。 如果對任意s 和t,最短距離dst=distQ(s,t,L)成立,則L 是G 的一個2-Hop Cover。

本文使用Akiba 等[8]提出的剪枝地標標簽(Pruned Landmark Labeling,PLL)算法生成2-Hop 標簽。 PLL 算法對每個節點使用剪枝的BFS 構造2-Hop 標簽索引。 如圖2 所示展示了一個無向圖的2-Hop 標簽。

圖2 2-Hop 標簽示例

2.2 改進的保序編碼

在2-Hop 標簽索引上計算兩節點間最短距離,需要再進行一次加法運算后進行值的比較。 Liu 等[6]改進的保序編碼算法OPE 滿足這一要求。 輸入正整數密鑰K3和整數d,OPE 將d 編碼為D←K3·d+r,其中r 是(0,K3/2)內的隨機數。

對于任意4 個整數值d1,d2,d3和d4,保序編碼分別為Ddi←OPE(K3,di),i=1,2,3,4。 如果(d1+d2)>(d3+d4),那么(Dd1+Dd2)>(Dd3+Dd4)成立。

2.3 基于通配符構造模糊集

Li 等[9]利用編輯距離衡量兩個關鍵詞的相似性,并在此基礎上提出一種基于通配符的方法構造模糊集。 編輯距離是指將一個單詞轉換為另一個進行替換、刪除或插入一個字符3 種操作所需的次數。 基于通配符的方法使用通配符“?”表示同一位置的一次編輯操作。 給定關鍵詞w,Sw,ed是關鍵詞w 的編輯距離≤ed 的模糊集,Sw,ed第一個元素是w 本身。 例如,令ed=1,art 的模糊集為Sart,1={act,?art,?rt,a?rt,a?t,ar?t,ar?,art?}。

3 方案設計

本節對提出的標記圖上top-k 最近模糊關鍵詞搜索的圖加密方案Π=(KeyGen, Encrypt, Token,Query, Decrypt)的各個算法進行詳細介紹。

(1)K←KeyGen(1λ):密鑰生成算法由用戶執行,輸入安全參數λ,生成λ-bit 隨機字符串K1和K2作為偽隨機函數P 的密鑰,生成OPE 的密鑰K3←Ζ2

λ,生成對稱密鑰K4←SKE. Gen(1λ),密鑰集K=(K1,K2,K3,K4)。

(2)I←Encrypt(K,G):加密算法用戶執行,輸入密鑰K,給定無向圖G=(V,E,W),生成加密的圖索引I=(DX1,DX2),包括一個加密的2-Hop 標簽索引DX1和加密的模糊關鍵詞索引DX2。 加密算法包括兩個子算法HopIndex 和KeywordIndex,HopIndex 算法生成加密的2-Hop 標簽索引,KeywordIndex 算法生成加密的模糊關鍵詞索引。 如圖3 所示,展示了一個加密索引示例,圖3(a)是一個包含6 個節點、8 條邊和3 個關鍵詞的標記圖,圖3(b)和圖3(c)分別是加密的2-Hop 標簽索引和模糊關鍵詞索引。

圖3 加密索引示例

HopIndex 算法如算法1 所示,輸入密鑰集K=(K1,K2,K3,K4)和圖G=(V,E,W),初始化DX1。 首先,使用Akiba 等[8]提出的PLL 算法計算圖G 的2-Hop 標簽L;然后,對L 加密,過程如下:先對圖中的每個節點v,計算labv←P(K1,v‖′lab′)作為檢索陷門,再對(u,d)∈L(v),計算Nu←P(K1,u‖′link′)隱藏真實的共享節點,并使用改進的OPE 算法加密距離d得到保序編碼值Dd,將數據對? Nu,Dd? 插入Lv,Lv是L(v)的加密形式;最后,將鍵值對(labv,Lv)插入DX1。

算法1.DX1←HopIndex(K,G)

輸入:密鑰集K,圖G=(V,E,W)

輸出:加密的2-Hop 標簽索引DX1

解析K 為(K1,K2,K3,K4),初始化DX1;

生成G 的2-Hop 標簽索引L;

FOR v∈V DO

labv←P(K1,v‖′lab′);

初始化空集Lv;

FOR (u,d)∈L(v) DO

Nu←P(K1,u‖′link′),Dd←OPE(K3,d);

將插入Lv;

END FOR

將(labv,Lv)插入DX1;

END FOR

RETURN DX1.

KeywordIndex 算法如算法2 所示,輸入密鑰集K和圖G=(V,E,W),生成加密的模糊關鍵詞索引DX2。對于圖G=(V,E,W)中出現的每一個關鍵詞w∈W,首先,使用基于通配符的方法為其構造模糊集Sw,ed;然后,對于wt∈Sw,ed,計算保密值labwt←P(K2,wt‖′lab′)插入Labw,Labw是w 的加密模糊集;接著,對每個節點v∈W[w],使用SKE 加密v 得到密文encv,計算偽隨機函數值labv←P(K1,v‖′lab′),并將插入Lw,獲得加密節點集Lw,labv將兩個加密索引關聯起來,可在DX1上進行檢索;最后,將一對加密的模糊集-節點集對(Labw,Lw)插入DX2。 最終返回DX2。 在加密算法中,用戶運行兩個子算法DX1←HopIndex(K,G)和DX2←KeywordIndex(K,G)獲得加密索引I=(DX1,DX2)發送給云服務器。

算法2. DX2←KeywordIndex(K,G)

輸入:密鑰集K,圖G=(V,E,W)

輸出:加密的模糊關鍵詞索引DX2

解析K 為(K1,K2,K3,K4),初始化索引表DX2;

FOR w∈W DO

構造模糊集Sw,ed,初始化空集Labw和Lw;

FOR wt∈Sw,edDO

labwt←P(K2,wt‖′lab′),將labwt插入Labw;

END FOR

FOR v∈W[w] DO

encv←SKE. Enc(K4,v),labv←P (K1,v‖′lab′);

將插入Lw;

END FOR

將(Labw,Lw)插入DX2;END FOR

RETURN DX2.

(3)T←Token(K,k,v,w):令牌生成算法由用戶運行,輸入密鑰集K=(K1,K2,K3,K4),整數k,節點v和關鍵詞w。 首先,計算labv←P(K1,v‖′lab′);然后,為輸入的關鍵詞w 構造模糊集Sw,ed,并初始化一個空集Labw,對模糊集Sw,ed中的每個元素wi,計算labwi←P(K2,wi‖′lab′)并插入Labw,獲得w 的加密模糊集;最后,算法輸出查詢令牌T=(k,labv,Labw)。

(4)R←Query(I,T):云服務器執行查詢算法進行查詢,過程如算法3 所示,解析令牌T 獲得k,labv和加密模糊集Labw。 首先,借助labv從DX1獲取給定節點v 的加密2-Hop 標簽集。 初始化兩個空集L′w和Temp 作為候選集。 比較Labw和DX2各條目中的加密模糊集Labwi,若兩者交集不為空,則對應的加密節點集Lwi可能被用戶想要的關鍵詞標記。 從DX2中找出所有可能被關鍵詞標記的保密數據項添加到候選集L′w;對每一對

算法3. R←Query(I,T)

輸入:加密的圖索引I,令牌T

輸出:加密結果R

解析I 為(DX1,DX2),解析T 為(k,labv,Labw);

Lv←DX2[labv];

初始化空集L′w和Temp;

FOR (Labwi,Lwi)∈DX2and Labw∩LabwiDO

檢查每對∈Lwi,如果labu不在L′w中,則將插入L′w;

END FOR

FOR∈L′wDO

Lu←DX2[labu];

Dvu←∞;

FOR∈Lv, ∈LuDO

IF Ni= Njand Dvu> Di+ DjTHEN

Dvu= Di+ Dj;

END IF

END FOR

將(encu, Dvu)插入Temp;

END FOR

選取Temp 中距離編碼值Dvu最小的k 個加密節點作為R;

RETURN R.

如圖4 所示,是一個查詢過程示例。 查詢距離節點e 最近的被art 標記的2 個節點,但在輸入關鍵詞時誤拼寫為artt。 圖中生成的查詢令牌T=(2,labe,{labartt,lab?artt…labart?,labartt?})。 云服務器使用令牌T 在加密索引上進行查詢。 第1 步,使用labe獲取DX1中節點e 的加密標簽集;第2 步,根據artt 的加密模糊集{labartt,lab?artt…labart?,labartt?}檢索可能包含想要關鍵詞的加密節點項{(enca,laba),(encd,labd),(ence,labe),(encf,labf)};第3 步,在DX1中使用陷門獲得a,d,e 和f 的加密標簽集,分別計算e 到a,d,e和f 的最短距離編碼;第4 步將加密節點-最短距離編碼對插入Temp,選擇最短距離編碼最小的2 個節點密文ence和encf作為結果R。

圖4 查詢過程示例

(5)m←Decrypt(K,R):用戶輸入密鑰K4和加密結果集R,依次對R 中保存的密文項使用SKE.Dec 解密,得到明文結果m。

4 安全性分析和性能評估

4.1 安全性分析

本節簡要分析兩個泄露函數Λ1和Λ2,并證明提出的支持top-k 最近模糊關鍵詞查詢的圖加密方案Π 滿足CQA2-安全,即方案Π 對于自適應選擇查詢攻擊是(Λ1,Λ2)-安全的。

泄露函數Λ1。 Λ1表示由存儲在云服務器中的加密圖索引I 存在的泄漏,定義Λ1(G)= {|V|,|W|,len1,len2,info},|V|和|W|分別是圖的節點數和關鍵詞數,len1和len2記錄DX1和DX2中每個索引條目大小,info 泄露OPE 泄露的距離值順序信息。 由于云服務器保存加密的2-Hop 標簽索引,不泄露原始圖的真實結構。

泄露函數Λ2。 Λ2表示查詢過程引起泄露的信息。 設Q={q1,q2…qn}是一個非空查詢序列,Λ2(I,Q)= {ΛQP(Q),ΛIP(I,Q)},包括查詢模式泄露ΛQP(Q)和索引模式泄露ΛIP(I,Q)。 ΛQP(Q)揭示當前查詢是否與已執行的查詢存在重復,即查詢的節點、關鍵詞和整數參數k 的重復情況,由于使用偽隨機函數對節點和關鍵詞進行了混淆,不泄露真實的節點和關鍵詞。 ΛIP(I,Q)揭示在查詢過程中出現的泄露,包括兩部分:(1)查詢結果和查詢過程訪問了哪些索引條目;(2)查詢過程中獲取的索引內部關聯情況,包括相同元素及部分距離順序。

定理1. 如果P,OPE,SKE 是安全的,則方案Π即滿足CQA2-安全。

證明:證明的主要思路是構造模擬器Σ,利用泄露函數Λ1和Λ2模擬索引I?和查詢序列Q?。 如果敵手A 不能區分Real 實驗和Ideal 實驗,則認為方案滿足CQA2-安全。 Σ 首先生成虛擬密鑰集K?←KeyGen(1λ),假定節點標識符和關鍵詞。

模擬I?:給定Λ1(G)= { | V|,| W|,len1,len2,info},Σ 在虛擬的密鑰集、節點標識符和關鍵詞上模擬構建加密索引I?=(DX1

?,DX2

?)。 DX1?包含|V|個條目,根據len1確定每個條目需包含的加密節點距離對的數量;DX2

?包含|W|個條目,根據len2確定模糊集中元素個數和對應節點集包含的節點密文數。

模擬Q?:給定Λ2(I,Q)={ΛQP(Q),ΛIP(I,Q)},Σ 模擬查詢令牌如下。 Σ 首先根據ΛQP(Q)檢查待查詢的節點和關鍵詞和k 是否在之前的查詢中出現過,如果是,使用先前的值;否則,Σ 根據ΛIP(I,Q)泄露的查詢過程信息,選擇模擬索引I?中未使用過的對應項構造模擬令牌T?。

由于偽隨機函數P 具有偽隨機的密文,OPE 只泄露順序信息,SKE 是CPA 安全的,模擬的I?和Q?和真實情況不可區分, | Pr[RealA(λ) = 1] -Pr[IdealA,S(λ)= 1] |≤negl(λ) ,negl(λ)是一個可忽略函數,因此,方案Π 滿足CQA2-安全。

4.2 性能評估

本節對提出的方案進行實驗評估。 實驗在Intel(R) Core(TM) i7 CPU 2.30 GHz,16 GB 內存的PC上進行,利用Vmware 搭載開源項目OpenStack,使用Python 編程,選用斯坦福網絡分析平臺的ego -facebook 數據集進行測試,從中選取不同節點數的子圖,選擇500 個單詞隨機分配給各節點。 設安全參數λ=256,利用pycroptodome 庫實現P 和SKE。

4.2.1 評估方案各階段算法的存儲開銷

用戶先生成4 個密鑰,所需存儲共128 B;構造加密的圖索引I=(DX1,DX2)是一次性計算。 如圖5 所示,展示在具有不同節點數的子圖上,DX1存儲開銷和模糊集Sw,ed的參數ed=1,2,3 時,DX2存儲開銷變化。 DX1是加密的2-Hop 標簽索引,存儲和圖的大小正相關;DX2存儲在受圖的大小影響的同時,ed 越大,關鍵詞模糊集越大,所需存儲空間越大。

圖5 加密索引存儲開銷

4.2.2 測試方案各階段的時間開銷

KeyGen 算法生成4 個密鑰,時間開銷固定,在測試中低于0.1 ms。 令牌生成算法生成模糊集并計算若干偽隨機函數,時間開銷受模糊集大小影響,當關鍵詞包含8 個字符且模糊集參數ed = 1 時,約為0.12 ms。

運行HopIndex 算法生成DX1、運行KeywordIndex算法生成DX2以及運行Query 算法進行查詢所需時間如圖6 所示。 HopIndex 算法生成2-Hop 標簽并加密,所需時間與圖的大小正相關; ed = 1 時,KeywordIndex 算法所需時間開銷隨圖的規模增大而增大;在4 000 節點的子圖上運行HopIndex 和KeywordIndex 算法,所需時間約為8.5 s 和0.64 s。查詢所需時間主要受加密索引的大小影響,當節點數為4 000 時,查詢所需時間為0.01 s,在實際應用中是可接受的。

圖6 各階段時間開銷

4.2.3 分析方案的通信開銷

用戶完成對圖數據的加密后,將加密的圖索引發送給云服務器,這一過程是一次性操作,通信開銷與加密圖數據的存儲開銷一致。 在查詢過程中,用戶和云服務器之間的通信包括用戶發送令牌給云服務器和云服務器返回加密結果給用戶兩部分。 本方案的令牌包括一個整數k 和若干λ 位偽隨機函數值,在僅考慮ed=1 時,若關鍵詞長為8,通信開銷約為1.19 KB。 在云服務器將加密結果發送給用戶的過程中,通信開銷與k 有關,返回k 個SKE 加密的密文所需通信開銷為16 KB。

5 結語

本文提出一個在加密圖上進行top-k 最近模糊關鍵詞查詢方案。 結合基于通配符的方法和2-Hop標簽技術構造圖索引并對標記圖數據加密,利用OPE的性質對距離值進行比較,找出距離給定節點最近的可能具有所需關鍵詞k 個節點。 安全性和實驗評估表明本文方案是安全高效的。 然而,現實中各種網絡往往是動態變化的,未來將進一步研究動態圖的加密搜索,并將繼續豐富本文方案的設計,使其支持更復雜的功能。