潘瑛穎

(福建師范大學(xué) 計(jì)算機(jī)與網(wǎng)絡(luò)空間安全學(xué)院,福建 福州 350117)

0 引言

圖數(shù)據(jù)在許多領(lǐng)域得到廣泛應(yīng)用,如社交網(wǎng)絡(luò)、知識(shí)圖譜等。 隨著云計(jì)算的快速發(fā)展,數(shù)據(jù)擁有者傾向于將大規(guī)模圖數(shù)據(jù)外包給云服務(wù)器以降低存儲(chǔ)和管理成本,但數(shù)據(jù)隱私泄露的風(fēng)險(xiǎn)也由此增加。 為保護(hù)數(shù)據(jù)隱私,數(shù)據(jù)擁有者需要在外包前對(duì)圖數(shù)據(jù)進(jìn)行加密,同時(shí)保留一定的隱私查詢能力。

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

1 符號(hào)定義和系統(tǒng)模型

1.1 符號(hào)定義

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

表1 符號(hào)定義

1.2 系統(tǒng)模型

本文方案支持在加密的標(biāo)記圖上進(jìn)行top-k 最近模糊關(guān)鍵詞查詢,標(biāo)記圖的各個(gè)節(jié)點(diǎn)被若干關(guān)鍵詞標(biāo)記。 方案的系統(tǒng)模型包括兩個(gè)實(shí)體:用戶和云服務(wù)器。 用戶將原始圖數(shù)據(jù)轉(zhuǎn)換成加密索引外包給云服務(wù)器;用戶將查詢令牌T 發(fā)送給云服務(wù)器;云服務(wù)器執(zhí)行查詢算法獲得加密結(jié)果R 并返回給用戶。 R 由k個(gè)節(jié)點(diǎn)密文組成,用戶解密R 得到明文結(jié)果。 具體如圖1 所示。

圖1 系統(tǒng)模型

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

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

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

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

(3)T←Token(K,k,v,w):令牌生成算法,輸入密鑰集K,整數(shù)k,節(jié)點(diǎn)v 和關(guān)鍵詞w,輸出令牌T。

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

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

1.3 安全模型

圖加密是結(jié)構(gòu)化加密的一種,因此本文修改使用Chase 等[1]提出的自適應(yīng)選擇查詢攻擊安全性定義,即CQA2-安全性定義。 云服務(wù)器是誠(chéng)實(shí)但好奇的,本文中被認(rèn)為是敵手A。 泄露函數(shù)Λ1和Λ2分別表示存儲(chǔ)在云服務(wù)器的加密數(shù)據(jù)泄露的信息和云服務(wù)器接收令牌查詢的過(guò)程的泄露。

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

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

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

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

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

negl(λ)是一個(gè)可忽略函數(shù),則方案Π 對(duì)于自適應(yīng)選擇查詢攻擊是(L1,L2)-安全的。

2 相關(guān)技術(shù)

2.1 2-Hop 標(biāo)簽

2-Hop 標(biāo)簽是一種預(yù)生成的快速計(jì)算兩節(jié)點(diǎn)間最短距離的索引結(jié)構(gòu)[7]。 給定無(wú)向圖G=(V,E),L是圖G 的2-Hop 標(biāo)簽,則L 為每個(gè)節(jié)點(diǎn)v 分配標(biāo)簽集L(v)。 L(v)是(u,d)對(duì)的集合,u 表示共享節(jié)點(diǎn),d 表示u 和v 之間的最短距離。

對(duì)于任意兩個(gè)可達(dá)頂點(diǎn)s 和t,存在至少一個(gè)節(jié)點(diǎn)u,使2-Hop 標(biāo)簽滿足:(1)(u,d1)∈L(s),(u,d2)∈L(t);(2)u 在s 和t 之間的最短路徑上。 因此,對(duì)于任意兩個(gè)可達(dá)節(jié)點(diǎn)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)沒(méi)有共享節(jié)點(diǎn),則distQ(s,t,L)=∞。 如果對(duì)任意s 和t,最短距離dst=distQ(s,t,L)成立,則L 是G 的一個(gè)2-Hop Cover。

本文使用Akiba 等[8]提出的剪枝地標(biāo)標(biāo)簽(Pruned Landmark Labeling,PLL)算法生成2-Hop 標(biāo)簽。 PLL 算法對(duì)每個(gè)節(jié)點(diǎn)使用剪枝的BFS 構(gòu)造2-Hop 標(biāo)簽索引。 如圖2 所示展示了一個(gè)無(wú)向圖的2-Hop 標(biāo)簽。

圖2 2-Hop 標(biāo)簽示例

2.2 改進(jìn)的保序編碼

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

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

2.3 基于通配符構(gòu)造模糊集

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

3 方案設(shè)計(jì)

本節(jié)對(duì)提出的標(biāo)記圖上top-k 最近模糊關(guān)鍵詞搜索的圖加密方案Π=(KeyGen, Encrypt, Token,Query, Decrypt)的各個(gè)算法進(jìn)行詳細(xì)介紹。

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

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

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

圖3 加密索引示例

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

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

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

輸出:加密的2-Hop 標(biāo)簽索引DX1

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

生成G 的2-Hop 標(biāo)簽索引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),生成加密的模糊關(guān)鍵詞索引DX2。對(duì)于圖G=(V,E,W)中出現(xiàn)的每一個(gè)關(guān)鍵詞w∈W,首先,使用基于通配符的方法為其構(gòu)造模糊集Sw,ed;然后,對(duì)于wt∈Sw,ed,計(jì)算保密值labwt←P(K2,wt‖′lab′)插入Labw,Labw是w 的加密模糊集;接著,對(duì)每個(gè)節(jié)點(diǎn)v∈W[w],使用SKE 加密v 得到密文encv,計(jì)算偽隨機(jī)函數(shù)值labv←P(K1,v‖′lab′),并將插入Lw,獲得加密節(jié)點(diǎn)集Lw,labv將兩個(gè)加密索引關(guān)聯(lián)起來(lái),可在DX1上進(jìn)行檢索;最后,將一對(duì)加密的模糊集-節(jié)點(diǎn)集對(duì)(Labw,Lw)插入DX2。 最終返回DX2。 在加密算法中,用戶運(yùn)行兩個(gè)子算法DX1←HopIndex(K,G)和DX2←KeywordIndex(K,G)獲得加密索引I=(DX1,DX2)發(fā)送給云服務(wù)器。

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

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

輸出:加密的模糊關(guān)鍵詞索引DX2

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

FOR w∈W DO

構(gòu)造模糊集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):令牌生成算法由用戶運(yùn)行,輸入密鑰集K=(K1,K2,K3,K4),整數(shù)k,節(jié)點(diǎn)v和關(guān)鍵詞w。 首先,計(jì)算labv←P(K1,v‖′lab′);然后,為輸入的關(guān)鍵詞w 構(gòu)造模糊集Sw,ed,并初始化一個(gè)空集Labw,對(duì)模糊集Sw,ed中的每個(gè)元素wi,計(jì)算labwi←P(K2,wi‖′lab′)并插入Labw,獲得w 的加密模糊集;最后,算法輸出查詢令牌T=(k,labv,Labw)。

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

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

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

輸出:加密結(jié)果R

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

Lv←DX2[labv];

初始化空集L′w和Temp;

FOR (Labwi,Lwi)∈DX2and Labw∩LabwiDO

檢查每對(duì)∈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 個(gè)加密節(jié)點(diǎn)作為R;

RETURN R.

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

圖4 查詢過(guò)程示例

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

4 安全性分析和性能評(píng)估

4.1 安全性分析

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

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

泄露函數(shù)Λ2。 Λ2表示查詢過(guò)程引起泄露的信息。 設(shè)Q={q1,q2…qn}是一個(gè)非空查詢序列,Λ2(I,Q)= {ΛQP(Q),ΛI(xiàn)P(I,Q)},包括查詢模式泄露ΛQP(Q)和索引模式泄露ΛI(xiàn)P(I,Q)。 ΛQP(Q)揭示當(dāng)前查詢是否與已執(zhí)行的查詢存在重復(fù),即查詢的節(jié)點(diǎn)、關(guān)鍵詞和整數(shù)參數(shù)k 的重復(fù)情況,由于使用偽隨機(jī)函數(shù)對(duì)節(jié)點(diǎn)和關(guān)鍵詞進(jìn)行了混淆,不泄露真實(shí)的節(jié)點(diǎn)和關(guān)鍵詞。 ΛI(xiàn)P(I,Q)揭示在查詢過(guò)程中出現(xiàn)的泄露,包括兩部分:(1)查詢結(jié)果和查詢過(guò)程訪問(wèn)了哪些索引條目;(2)查詢過(guò)程中獲取的索引內(nèi)部關(guān)聯(lián)情況,包括相同元素及部分距離順序。

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

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

模擬I?:給定Λ1(G)= { | V|,| W|,len1,len2,info},Σ 在虛擬的密鑰集、節(jié)點(diǎn)標(biāo)識(shí)符和關(guān)鍵詞上模擬構(gòu)建加密索引I?=(DX1

?,DX2

?)。 DX1?包含|V|個(gè)條目,根據(jù)len1確定每個(gè)條目需包含的加密節(jié)點(diǎn)距離對(duì)的數(shù)量;DX2

?包含|W|個(gè)條目,根據(jù)len2確定模糊集中元素個(gè)數(shù)和對(duì)應(yīng)節(jié)點(diǎn)集包含的節(jié)點(diǎn)密文數(shù)。

模擬Q?:給定Λ2(I,Q)={ΛQP(Q),ΛI(xiàn)P(I,Q)},Σ 模擬查詢令牌如下。 Σ 首先根據(jù)ΛQP(Q)檢查待查詢的節(jié)點(diǎn)和關(guān)鍵詞和k 是否在之前的查詢中出現(xiàn)過(guò),如果是,使用先前的值;否則,Σ 根據(jù)ΛI(xiàn)P(I,Q)泄露的查詢過(guò)程信息,選擇模擬索引I?中未使用過(guò)的對(duì)應(yīng)項(xiàng)構(gòu)造模擬令牌T?。

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

4.2 性能評(píng)估

本節(jié)對(duì)提出的方案進(jìn)行實(shí)驗(yàn)評(píng)估。 實(shí)驗(yàn)在Intel(R) Core(TM) i7 CPU 2.30 GHz,16 GB 內(nèi)存的PC上進(jìn)行,利用Vmware 搭載開(kāi)源項(xiàng)目OpenStack,使用Python 編程,選用斯坦福網(wǎng)絡(luò)分析平臺(tái)的ego -facebook 數(shù)據(jù)集進(jìn)行測(cè)試,從中選取不同節(jié)點(diǎn)數(shù)的子圖,選擇500 個(gè)單詞隨機(jī)分配給各節(jié)點(diǎn)。 設(shè)安全參數(shù)λ=256,利用pycroptodome 庫(kù)實(shí)現(xiàn)P 和SKE。

4.2.1 評(píng)估方案各階段算法的存儲(chǔ)開(kāi)銷

用戶先生成4 個(gè)密鑰,所需存儲(chǔ)共128 B;構(gòu)造加密的圖索引I=(DX1,DX2)是一次性計(jì)算。 如圖5 所示,展示在具有不同節(jié)點(diǎn)數(shù)的子圖上,DX1存儲(chǔ)開(kāi)銷和模糊集Sw,ed的參數(shù)ed=1,2,3 時(shí),DX2存儲(chǔ)開(kāi)銷變化。 DX1是加密的2-Hop 標(biāo)簽索引,存儲(chǔ)和圖的大小正相關(guān);DX2存儲(chǔ)在受圖的大小影響的同時(shí),ed 越大,關(guān)鍵詞模糊集越大,所需存儲(chǔ)空間越大。

圖5 加密索引存儲(chǔ)開(kāi)銷

4.2.2 測(cè)試方案各階段的時(shí)間開(kāi)銷

KeyGen 算法生成4 個(gè)密鑰,時(shí)間開(kāi)銷固定,在測(cè)試中低于0.1 ms。 令牌生成算法生成模糊集并計(jì)算若干偽隨機(jī)函數(shù),時(shí)間開(kāi)銷受模糊集大小影響,當(dāng)關(guān)鍵詞包含8 個(gè)字符且模糊集參數(shù)ed = 1 時(shí),約為0.12 ms。

運(yùn)行HopIndex 算法生成DX1、運(yùn)行KeywordIndex算法生成DX2以及運(yùn)行Query 算法進(jìn)行查詢所需時(shí)間如圖6 所示。 HopIndex 算法生成2-Hop 標(biāo)簽并加密,所需時(shí)間與圖的大小正相關(guān); ed = 1 時(shí),KeywordIndex 算法所需時(shí)間開(kāi)銷隨圖的規(guī)模增大而增大;在4 000 節(jié)點(diǎn)的子圖上運(yùn)行HopIndex 和KeywordIndex 算法,所需時(shí)間約為8.5 s 和0.64 s。查詢所需時(shí)間主要受加密索引的大小影響,當(dāng)節(jié)點(diǎn)數(shù)為4 000 時(shí),查詢所需時(shí)間為0.01 s,在實(shí)際應(yīng)用中是可接受的。

圖6 各階段時(shí)間開(kāi)銷

4.2.3 分析方案的通信開(kāi)銷

用戶完成對(duì)圖數(shù)據(jù)的加密后,將加密的圖索引發(fā)送給云服務(wù)器,這一過(guò)程是一次性操作,通信開(kāi)銷與加密圖數(shù)據(jù)的存儲(chǔ)開(kāi)銷一致。 在查詢過(guò)程中,用戶和云服務(wù)器之間的通信包括用戶發(fā)送令牌給云服務(wù)器和云服務(wù)器返回加密結(jié)果給用戶兩部分。 本方案的令牌包括一個(gè)整數(shù)k 和若干λ 位偽隨機(jī)函數(shù)值,在僅考慮ed=1 時(shí),若關(guān)鍵詞長(zhǎng)為8,通信開(kāi)銷約為1.19 KB。 在云服務(wù)器將加密結(jié)果發(fā)送給用戶的過(guò)程中,通信開(kāi)銷與k 有關(guān),返回k 個(gè)SKE 加密的密文所需通信開(kāi)銷為16 KB。

5 結(jié)語(yǔ)

本文提出一個(gè)在加密圖上進(jìn)行top-k 最近模糊關(guān)鍵詞查詢方案。 結(jié)合基于通配符的方法和2-Hop標(biāo)簽技術(shù)構(gòu)造圖索引并對(duì)標(biāo)記圖數(shù)據(jù)加密,利用OPE的性質(zhì)對(duì)距離值進(jìn)行比較,找出距離給定節(jié)點(diǎn)最近的可能具有所需關(guān)鍵詞k 個(gè)節(jié)點(diǎn)。 安全性和實(shí)驗(yàn)評(píng)估表明本文方案是安全高效的。 然而,現(xiàn)實(shí)中各種網(wǎng)絡(luò)往往是動(dòng)態(tài)變化的,未來(lái)將進(jìn)一步研究動(dòng)態(tài)圖的加密搜索,并將繼續(xù)豐富本文方案的設(shè)計(jì),使其支持更復(fù)雜的功能。