圖數(shù)據(jù)精確最短距離的隱私保護(hù)外包計(jì)算方案

于瑩瑩，丁紅發(fā)，2，蔣合領(lǐng)，3

（1.貴州財(cái)經(jīng)大學(xué) 信息學(xué)院，貴陽 550025；2.貴州省大數(shù)據(jù)統(tǒng)計(jì)分析重點(diǎn)實(shí)驗(yàn)室，貴陽 550025；3.貴安新區(qū)科創(chuàng)產(chǎn)業(yè)發(fā)展有限公司，貴陽 550025）

0 概述

隨著在線社交網(wǎng)絡(luò)、出行導(dǎo)航、通信網(wǎng)絡(luò)、生物蛋白分析等圖數(shù)據(jù)應(yīng)用與服務(wù)的蓬勃發(fā)展，海量圖數(shù)據(jù)的收集、管理和分析技術(shù)受到業(yè)界的廣泛關(guān)注。海量圖數(shù)據(jù)的廣泛應(yīng)用和大規(guī)模分析所需的資源已超出數(shù)據(jù)所有者提供資源的能力，加之云計(jì)算的日益普及，數(shù)據(jù)外包成為數(shù)據(jù)應(yīng)用的主流方式。使用云服務(wù)對(duì)圖數(shù)據(jù)進(jìn)行存儲(chǔ)和計(jì)算，能顯著降低本地的存儲(chǔ)和管理成本。例如，東部發(fā)達(dá)地區(qū)的圖數(shù)據(jù)服務(wù)企業(yè)將數(shù)據(jù)存儲(chǔ)和計(jì)算遷移至西部低成本的云計(jì)算中心。然而，海量圖數(shù)據(jù)中包含大量個(gè)人隱私（如身份信息、位置信息等）［1-2］、商業(yè)秘密等敏感信息，外包過程中數(shù)據(jù)所有者失去了對(duì)數(shù)據(jù)的實(shí)際控制，個(gè)人隱私和商業(yè)秘密極易受到損害。例如，F(xiàn)acebook 用戶社交網(wǎng)絡(luò)、滴滴道路網(wǎng)絡(luò)等隱私泄露事件。因此，隱私敏感的數(shù)據(jù)在外包前，特別是在云服務(wù)提供商不可信的情況下，應(yīng)該在本地進(jìn)行加密。然而，傳統(tǒng)加密工具阻礙了數(shù)據(jù)的利用和計(jì)算，直接破壞了數(shù)據(jù)的可用性［3］。如何在數(shù)據(jù)外包等非受控環(huán)境下進(jìn)行數(shù)據(jù)保護(hù)和高效計(jì)算已成為學(xué)術(shù)界和產(chǎn)業(yè)界關(guān)注的熱點(diǎn)問題。

為了解決上述問題，學(xué)術(shù)界不斷探索新的解決方案，如k-匿名［4］、差分隱私［5］、加密算法［6-7］、安全多方計(jì)算［8-9］等圖數(shù)據(jù)隱私保護(hù)方法?，F(xiàn)有的各類圖數(shù)據(jù)隱私保護(hù)方法中，基于密碼算法與協(xié)議的方法能夠嚴(yán)格保護(hù)圖數(shù)據(jù)信息且不改變圖數(shù)據(jù)的原有結(jié)構(gòu)特征，故該類方法在面向圖數(shù)據(jù)結(jié)構(gòu)特征計(jì)算的外包服務(wù)場(chǎng)景中［10-11］備受關(guān)注。

最短距離查詢作為圖數(shù)據(jù)最基本的結(jié)構(gòu)查詢［12-13］，在社交網(wǎng)絡(luò)的用戶間最短社交次數(shù)分析、生物網(wǎng)絡(luò)蛋白質(zhì)功能的相關(guān)性分析、通信網(wǎng)絡(luò)中最短呼叫次數(shù)分析等眾多查詢服務(wù)中均有廣泛的應(yīng)用。由于對(duì)圖數(shù)據(jù)安全的緊迫需求，基于加密圖數(shù)據(jù)的最短距離查詢外包計(jì)算在實(shí)際應(yīng)用中有廣泛的需求，其主要過程為：圖數(shù)據(jù)所有者在本地加密其持有的原始圖數(shù)據(jù)集，并將加密后的圖數(shù)據(jù)外包給云服務(wù)提供商；云服務(wù)提供商向圖數(shù)據(jù)查詢請(qǐng)求者（數(shù)據(jù)所有者或查詢請(qǐng)求用戶）提供基于密文圖數(shù)據(jù)的最短距離查詢外包服務(wù)；查詢請(qǐng)求者對(duì)查詢請(qǐng)求加密后提交給云服務(wù)提供商；云服務(wù)提供商對(duì)密文查詢請(qǐng)求進(jìn)行計(jì)算處理，并返回密文計(jì)算結(jié)果；查詢請(qǐng)求者對(duì)收到的密文查詢結(jié)果解密，得到明文結(jié)果。該方法一方面憑借云服務(wù)提供商強(qiáng)大的存儲(chǔ)和計(jì)算能力解決數(shù)據(jù)擁有者的本地計(jì)算資源問題；另一方面利用加密的方法對(duì)原始圖數(shù)據(jù)和查詢請(qǐng)求進(jìn)行保護(hù)，保證圖數(shù)據(jù)的節(jié)點(diǎn)隱私、邊隱私和用戶查詢請(qǐng)求隱私。

然而，在大規(guī)模密文圖數(shù)據(jù)上計(jì)算最短距離消耗資源巨大，且在查詢計(jì)算過程中會(huì)因圖數(shù)據(jù)信息的存儲(chǔ)不當(dāng)造成在計(jì)算時(shí)隱私信息泄露；此外，云服務(wù)提供商往往并非完全誠(chéng)實(shí)，甚至是惡意的，其會(huì)旁路觀測(cè)或攻擊計(jì)算過程以獲取真實(shí)圖數(shù)據(jù)。因此，設(shè)計(jì)高效的圖數(shù)據(jù)最短距離安全外包計(jì)算方案，并進(jìn)一步減少信息泄露是當(dāng)前亟待解決的問題。

現(xiàn)有的密文圖數(shù)據(jù)最短距離安全外包計(jì)算可分為兩類。第1 類聚焦加密圖上的模糊最短距離查詢，常采用距離預(yù)言的方法對(duì)預(yù)言距離值進(jìn)行加密，以有效計(jì)算任意兩個(gè)頂點(diǎn)之間的近似距離。該類方法以犧牲計(jì)算精度為代價(jià)提高查詢效率，在距離預(yù)言的預(yù)計(jì)算階段資源消耗過大且圖數(shù)據(jù)的相關(guān)隱私信息存在泄露的風(fēng)險(xiǎn)。第2 類聚焦密文圖數(shù)據(jù)的精確最短距離計(jì)算，通過對(duì)原始圖數(shù)據(jù)進(jìn)行實(shí)例化加密，并在此基礎(chǔ)上進(jìn)行精確計(jì)算，能夠通過減少存儲(chǔ)過程中的信息泄露問題保護(hù)圖數(shù)據(jù)隱私。該方法在復(fù)雜密文圖數(shù)據(jù)上計(jì)算高準(zhǔn)確性的結(jié)果，其計(jì)算時(shí)間復(fù)雜度高，導(dǎo)致效率降低。因此，如何在密文圖數(shù)據(jù)上設(shè)計(jì)高效、安全的精確最短距離查詢計(jì)算方案成為當(dāng)前的重要挑戰(zhàn)之一。

針對(duì)密文圖數(shù)據(jù)的最短距離查詢存在效率低、安全性差的問題，本文基于二跳覆蓋標(biāo)記提出加密圖數(shù)據(jù)精確最短距離外包計(jì)算方案，以實(shí)現(xiàn)隱私保護(hù)的最短距離查詢，并在減少圖數(shù)據(jù)隱私泄露的同時(shí)提高計(jì)算和存儲(chǔ)效率。首先，基于二跳覆蓋標(biāo)記對(duì)原始圖數(shù)據(jù)生成原始標(biāo)記集合，再通過廣度優(yōu)先搜索修剪策略對(duì)原始標(biāo)記集合進(jìn)行修剪，獲得修剪后的標(biāo)記集合。然后，利用偽隨機(jī)函數(shù)對(duì)標(biāo)記中的鄰接節(jié)點(diǎn)構(gòu)造虛假的節(jié)點(diǎn)信息，結(jié)合加法同態(tài)對(duì)標(biāo)記中的距離值進(jìn)行加密，保證加密圖數(shù)據(jù)的節(jié)點(diǎn)隱私和邊隱私。最后，基于節(jié)點(diǎn)令牌和加密標(biāo)記構(gòu)造安全索引結(jié)構(gòu)，并根據(jù)查詢請(qǐng)求遞歸計(jì)算索引中對(duì)應(yīng)的距離候選結(jié)果集合，實(shí)現(xiàn)高效的密文圖數(shù)據(jù)外包最短距離查詢計(jì)算。

1 相關(guān)工作

圖數(shù)據(jù)作為一種能夠刻畫事物普遍聯(lián)系的數(shù)據(jù)結(jié)構(gòu)，在被眾多挖掘分析應(yīng)用需求的同時(shí)，其隱私和安全外包計(jì)算也受到廣泛關(guān)注。CHASE 等［14］把可搜索加密技術(shù)引入圖數(shù)據(jù)，首次提出圖加密的概念以保護(hù)圖數(shù)據(jù)的隱私和查詢請(qǐng)求，并實(shí)現(xiàn)了密文圖數(shù)據(jù)上的鄰接查詢和標(biāo)記圖上的集中子圖查詢。CAO 等［15］通過預(yù)先構(gòu)建基于特征的索引來提供加密圖數(shù)據(jù)的特征相關(guān)信息，解決了云計(jì)算中加密圖數(shù)據(jù)的關(guān)鍵字查詢與相交子圖查詢問題。與此同時(shí)，安全多方計(jì)算也被用于解決隱私保護(hù)的圖數(shù)據(jù)查詢問題，然而其并不適用于大規(guī)模圖數(shù)據(jù)。

為在大規(guī)模密文圖數(shù)據(jù)上實(shí)現(xiàn)高效的計(jì)算查詢，YIN 等［16］探索了圖數(shù)據(jù)的隱私保護(hù)可達(dá)查詢外包計(jì)算問題，基于隱私保護(hù)的二跳標(biāo)記設(shè)計(jì)了圖數(shù)據(jù)的可達(dá)性查詢方案，并提出近似最短距離查詢方案。MENG 等［17］通過計(jì) 算距離 預(yù)言機(jī)（distance oracle），并利用部分同態(tài)加密構(gòu)造圖數(shù)據(jù)同態(tài)加密方案，在加密的距離預(yù)言上實(shí)現(xiàn)近似最短路徑查詢，但該方案在距離值相差較大時(shí)會(huì)犧牲準(zhǔn)確率，造成較大誤差。ZHU 等［18］提出一種基于加密圖數(shù)據(jù)的支持同義詞查詢的最短路徑搜索方案，通過詞干算法和加密機(jī)制將節(jié)點(diǎn)轉(zhuǎn)化為令牌并建立安全索引，查詢索引中節(jié)點(diǎn)的同義詞進(jìn)行最短路徑搜索。沈蒙等［19］提出一種基于圖壓縮的支持近似最短距離查詢的圖數(shù)據(jù)加密機(jī)制，提高了圖數(shù)據(jù)計(jì)算的查詢效率。LIU等［20］提出基于二跳覆蓋標(biāo)記索引的圖數(shù)據(jù)加密框架，構(gòu)造一種保序加密方案以執(zhí)行近似最短距離查詢，并精確定義圖數(shù)據(jù)加密方案的隱私泄露程度。為在加密圖數(shù)據(jù)上實(shí)現(xiàn)帶約束的最短距離查詢，SHEN 等［21］基于部分同態(tài)加密和保序加密提出一種高效的近似約束查詢的圖加密方案，但該方案泄露了路徑開銷的順序信息。加密圖數(shù)據(jù)的近似最短距離查詢雖然效率高，卻犧牲了最短距離結(jié)果的精度。在無線通信、物聯(lián)網(wǎng)等場(chǎng)景中往往需要查詢精確的最短距離，因此，密文圖數(shù)據(jù)上的精確最短距離計(jì)算亦十分重要。為實(shí)現(xiàn)密文圖數(shù)據(jù)上的精確最短距離查詢，WANG 等［22］提出基于加法同態(tài)的安全圖數(shù)據(jù)加密方案，該方案支持加密圖數(shù)據(jù)上邊動(dòng)態(tài)更新的精確最短路徑查詢外包計(jì)算。GHOSH 等［23］提出支持遞歸的結(jié)構(gòu)化加密方案，能夠有效查詢密文圖數(shù)據(jù)單源最短路徑，采用SP 矩陣優(yōu)化數(shù)據(jù)結(jié)構(gòu)以提高查詢速度。DU 等［24］提出一種結(jié)構(gòu)化的圖數(shù)據(jù)加密方案并擴(kuò)展至密文圖數(shù)據(jù)查詢系統(tǒng)，支持精確最短距離等多類基礎(chǔ)性圖數(shù)據(jù)查詢服務(wù)。為進(jìn)一步提升精確最短距離查詢的靈活性，ZHANG 等［25］提出支持帶約束的精確最短距離查詢的隱私保護(hù)圖數(shù)據(jù)加密方案，利用安全整數(shù)比較協(xié)議及安全最小值協(xié)議保護(hù)圖數(shù)據(jù)隱私，但該方案的計(jì)算效率較低。相比近似最短距離查詢，帶約束的最短距離查詢［26-27］是一種既考慮最短距離又考慮成本條件的特殊查詢。最短距離查詢的外包隱私計(jì)算吸引了眾多學(xué)者深入研究［28-29］。

綜上可知，密文圖數(shù)據(jù)上最短距離外包計(jì)算方案難以同時(shí)提升結(jié)果準(zhǔn)確性、計(jì)算效率和安全性。在密文圖數(shù)據(jù)的最短距離查詢過程中，如何在降低計(jì)算時(shí)間和空間開銷的同時(shí)提高計(jì)算結(jié)果的準(zhǔn)確性，仍是一個(gè)難題。針對(duì)該問題，本文設(shè)計(jì)密文圖數(shù)據(jù)上安全、高效的精確最短距離查詢外包計(jì)算方案。該方案基于二跳覆蓋標(biāo)記生成圖數(shù)據(jù)的原始標(biāo)記集合，并通過廣度優(yōu)先搜索修剪策略對(duì)原始標(biāo)記集合進(jìn)行修剪，減少預(yù)計(jì)算的標(biāo)記，減小索引結(jié)構(gòu)的尺寸。同時(shí)，在所構(gòu)造的同態(tài)加密索引結(jié)構(gòu)基礎(chǔ)上，利用安全索引計(jì)算精確最短距離并提高圖計(jì)算的檢索效率。

2 基本定義

本節(jié)介紹圖數(shù)據(jù)最短路徑計(jì)算相關(guān)的符號(hào)定義，并介紹所涉及的基礎(chǔ)知識(shí)。

2.1 符號(hào)定義

G=(V,E)是一個(gè)具有頂點(diǎn)集V和邊集E的圖，G的頂點(diǎn)總數(shù)可表示為|V|，邊的總數(shù)表示為|E|。圖G的頂點(diǎn)集和邊集分別由V(G)和E(G)表示，頂點(diǎn)v?V的鄰居節(jié)點(diǎn)表示為NG(v)，即NG(v)={u?V|(u,v)?E}；v的標(biāo)記信息存儲(chǔ)其鄰接頂點(diǎn)及邊長(zhǎng)，由L(v)表示。設(shè)dG(u,v)表示頂點(diǎn)u和v之間的距離，若u和v在G中不相連，則定義dG(u,v)=∞。給定最短距離查詢請(qǐng)求q=(s,t)，查詢頂點(diǎn)s到頂點(diǎn)t之間的最短距離ds,t，密文最短距離用Ds,t表示。概率算法A 的輸出x用x←A 表示，確定性算法? 的輸出x用x：=? 來表示。在整個(gè)過程中，所有算法都隱式地將安全參數(shù)λ（λ?N）作為輸入。

為了便于閱讀，表1 列出了本文方案涉及的符號(hào)及其描述。

表1 符號(hào)及其描述 Table 1 Symbols and their descriptions

2.2 相關(guān)知識(shí)

本節(jié)主要介紹二跳覆蓋標(biāo)記、偽隨機(jī)函數(shù)、偽隨機(jī)排列、字典等相關(guān)知識(shí)。

1）二跳覆蓋標(biāo)記。對(duì)于圖G中的任意頂點(diǎn)v，選取一個(gè)候選頂點(diǎn)集合S(v)，S(v)存儲(chǔ)頂點(diǎn)v的鄰接節(jié)點(diǎn)。任意頂點(diǎn)對(duì)(s,t)之間的最短路徑上至少有一個(gè)頂點(diǎn)u滿足u?S(s),u?S(t)。對(duì)于每個(gè)頂點(diǎn)s和一個(gè)頂點(diǎn)u?S(s)，預(yù)先計(jì)算兩者間的距離dG(s,u)，稱集合L(s)={(u,dG(s,u))u?S(s)}是頂點(diǎn)s的標(biāo)記，L(s)的長(zhǎng)度為L(zhǎng)(s)中(u,dG(s,u))對(duì)的個(gè)數(shù)。所有頂點(diǎn)的標(biāo)記集合{L(v)}v?G即為二跳覆蓋標(biāo)記。利用標(biāo)記可以清楚計(jì)算出兩個(gè)頂點(diǎn)s和t之間的距離dG(s,t)，并通過“min”計(jì)算出最短距離。圖1 所示為二跳覆蓋標(biāo)記下獲得頂點(diǎn)s和t之間的最短距離示例。

圖1 二跳覆蓋標(biāo)記方案示例Fig.1 Example of 2-hop cover labeling scheme

在圖1 中，先計(jì)算兩者的標(biāo)記L(s)和L(t)，再選取具有公共頂點(diǎn)的路徑計(jì)算最短距離，計(jì)算公式為：min{δ+δ'|(u,δ)?L(s),(u,δ')?L(t)}。

該實(shí)例的具體計(jì)算過程如下：

如果L(s) 和L(t) 不存在相同頂點(diǎn)，則定義Query(s,t,L)=∞。

2）偽隨機(jī)函數(shù)和偽隨機(jī)排列。偽隨機(jī)函數(shù)Function：{0,1}λ×{0,1}*→{0,1}*是一個(gè)多項(xiàng)式時(shí)間可計(jì)算函數(shù)，任何概率多項(xiàng)式時(shí)間敵手都無法將其與隨機(jī)函數(shù)區(qū)分。當(dāng)偽隨機(jī)函數(shù)是雙射時(shí)，則稱其為偽隨機(jī)排列。

3）字典。安全索引結(jié)構(gòu)是以字典數(shù)據(jù)結(jié)構(gòu)為基礎(chǔ)構(gòu)建的，一個(gè)字典I以(kkey,vvalue)對(duì)的形式進(jìn)行存儲(chǔ)。給定I中的一個(gè)kkey，其對(duì)應(yīng)vvalue可在O(1)時(shí)間內(nèi)返回。用I[kkey]：=vvalue表示字典I中通過kkey標(biāo)記的值vvalue，若kkey在I中不存在，則返回⊥。

3 系統(tǒng)模型和定義

本節(jié)設(shè)計(jì)一個(gè)基于路徑標(biāo)記的圖數(shù)據(jù)外包計(jì)算方案，實(shí)現(xiàn)高效、安全的密文圖數(shù)據(jù)最短距離查詢。

3.1 系統(tǒng)模型

系統(tǒng)構(gòu)造圖數(shù)據(jù)隱私保護(hù)外包計(jì)算模型涉及到3 個(gè)實(shí)體，即數(shù)據(jù)所有者（Data Owner，DO）、可信的查詢請(qǐng)求者（Query Requester，QR）和半誠(chéng)實(shí)的云服務(wù)提供商（Cloud Service Provider，CSP）。西部地區(qū)的圖數(shù)據(jù)存儲(chǔ)中心作為數(shù)據(jù)所有者，東部發(fā)達(dá)地區(qū)的圖數(shù)據(jù)服務(wù)企業(yè)作為查詢請(qǐng)求者，低成本的圖數(shù)據(jù)存儲(chǔ)中心無法提供高效快速的計(jì)算，第三方云服務(wù)商應(yīng)運(yùn)而生。此時(shí)查詢請(qǐng)求者是可信的，且不會(huì)與第三方云服務(wù)提供商合謀。圖2 所示為密文圖數(shù)據(jù)上最短距離外包計(jì)算模型。

圖2 密文圖數(shù)據(jù)上最短距離外包計(jì)算模型Fig.2 Outsourced computation model of the shortest distance over encrypted graph data

圖2 中每個(gè)實(shí)體的描述如下：

1）數(shù)據(jù)所有者。數(shù)據(jù)所有者在本地將擁有的原始圖數(shù)據(jù)預(yù)處理生成標(biāo)記信息，并對(duì)標(biāo)記信息加密，得到密文安全索引結(jié)構(gòu)。然后將圖數(shù)據(jù)安全索引結(jié)構(gòu)發(fā)送至云服務(wù)提供商，并將部分密鑰發(fā)送至查詢請(qǐng)求者。在查詢階段，數(shù)據(jù)所有者和云服務(wù)提供商協(xié)同執(zhí)行一個(gè)安全比較協(xié)議。

2）查詢請(qǐng)求者。在查詢階段，查詢請(qǐng)求者根據(jù)最短距離查詢請(qǐng)求，使用令牌生成算法對(duì)請(qǐng)求節(jié)點(diǎn)進(jìn)行加密，將查詢令牌發(fā)送給云服務(wù)提供商。在查詢執(zhí)行階段，云服務(wù)提供商計(jì)算出密文查詢結(jié)果，并將其返回給查詢請(qǐng)求者。在解密階段，查詢請(qǐng)求者對(duì)密文最短距離結(jié)果進(jìn)行解密計(jì)算，得到真實(shí)最短距離。

3）云服務(wù)提供商。假設(shè)系統(tǒng)模型中CSP 是誠(chéng)實(shí)但好奇的，能誠(chéng)實(shí)地執(zhí)行計(jì)算協(xié)議，但在協(xié)議執(zhí)行過程中會(huì)對(duì)數(shù)據(jù)所有者、查詢請(qǐng)求者等用戶的數(shù)據(jù)好奇，甚至窺探或推斷隱私數(shù)據(jù)。在執(zhí)行最短距離查詢階段，CSP 根據(jù)圖數(shù)據(jù)的加密安全索引結(jié)構(gòu)及查詢令牌進(jìn)行計(jì)算，在比較最短距離時(shí)與數(shù)據(jù)所有者協(xié)同執(zhí)行安全比較協(xié)議，得出密文結(jié)果后返回給查詢請(qǐng)求者。

系統(tǒng)模型包括4 個(gè)階段，即預(yù)處理階段、加密階段、最短距離查詢階段和解密階段。在預(yù)處理階段，數(shù)據(jù)所有者將本地原始圖數(shù)據(jù)G預(yù)處理生成標(biāo)記信息。在加密階段，數(shù)據(jù)所有者使用加密方案對(duì)標(biāo)記信息加密生成圖數(shù)據(jù)的密文索引結(jié)構(gòu)I，并將I發(fā)送給CSP，將加密圖數(shù)據(jù)的部分密鑰發(fā)送給查詢請(qǐng)求者，以便計(jì)算查詢令牌和密文結(jié)果解密。在最短距離查詢階段，為查詢?nèi)我夤?jié)點(diǎn)間的最短距離，查詢請(qǐng)求者根據(jù)查詢節(jié)點(diǎn)(s,t?G)計(jì)算對(duì)應(yīng)的查詢令牌τs,t，并將查詢令牌提交給CSP；CSP 根據(jù)圖數(shù)據(jù)的密文安全索引結(jié)構(gòu)I和查詢令牌τs,t進(jìn)行最短距離計(jì)算。CSP 具體查詢計(jì)算過程為：首先，根據(jù)查詢令牌τs,t解析對(duì)應(yīng)的查詢節(jié)點(diǎn)；其次，通過安全索引結(jié)構(gòu)I計(jì)算密文距離集合，協(xié)同數(shù)據(jù)所有者執(zhí)行安全比較協(xié)議并獲取最小值Ds,t；最后將密文查詢結(jié)果Ds,t返回給查詢請(qǐng)求者。在解密階段，查詢請(qǐng)求者將密文最短距離結(jié)果Ds,t解密為明文最短距離結(jié)果ds,t。

3.2 形式化定義

本節(jié)結(jié)合圖2 所示的模型提出基于二跳覆蓋修剪標(biāo)記的圖數(shù)據(jù)隱私保護(hù)最短距離外包查詢計(jì)算框架的形式化定義，實(shí)現(xiàn)加密圖數(shù)據(jù)上保護(hù)隱私的最短距離查詢。

定義1（Graph-SPD）圖數(shù)據(jù)隱私保護(hù)最短距離外包查詢計(jì)算框架由多項(xiàng)式時(shí)間算法構(gòu)成，表達(dá)式為{prunedBFS,KeyGen,Encrypt,TokenGen,Dist Query,Decrypt}，其中：{L(v)}v?G←prunedBFS(G)，即數(shù)據(jù)所有者在本地對(duì)原始圖數(shù)據(jù)G進(jìn)行預(yù)處理。該算法基于二跳覆蓋標(biāo)記生成原始標(biāo)記后執(zhí)行廣度優(yōu)先遍歷修剪策略，輸出最終標(biāo)記集合{L(v)}v?G。

(K,pk,sk)←KeyGen(λ)：由數(shù)據(jù)所有者執(zhí)行該密鑰生成算法。算法以一個(gè)安全參數(shù)λ作為輸入，輸出密鑰(K,pk,sk)。

I←Encrypt(K,pk,{L(v)}v?G)：數(shù)據(jù)所 有者執(zhí)行該加密算法。數(shù)據(jù)所有者輸入密鑰K,pk和標(biāo)記集合{L(v)}v?G，輸出安全索引結(jié)構(gòu)I。

τs,t←TokenGen(K,q)：查詢請(qǐng)求者執(zhí)行查詢令牌生成算法，根據(jù)查詢請(qǐng)求q=(s,t)及密鑰K，生成查詢令牌τs,t并輸出發(fā)送給CSP。

Ds,t←DistQuery(I,τs,t)：CSP 執(zhí)行最 短距離查詢算法，以安全索引結(jié)構(gòu)I和查詢令牌Ds,t←DistQuery(I,τs,t)為輸入，解析查詢令牌并結(jié)合索引結(jié)構(gòu)計(jì)算密文最短距離Ds,t。

ds,t←Decrypt(sk,Ds,t)：查詢請(qǐng)求者執(zhí)行解密操作算法。該算法以密鑰sk和密文最短距離結(jié)果Ds,t作為輸入，輸出明文距離ds,t。

3.3 安全定義

定義2（自適應(yīng)語義安全）給定一個(gè)Graph-SPD 框架{prunedBFS,KeyGen,Encrypt,TokenGen,DistQuery,Decrpt}，設(shè)在執(zhí)行加密和查詢的過程中泄露信息所對(duì)應(yīng)的泄露函數(shù)是L1和L2，同時(shí)設(shè)置λ為安全參數(shù)，挑戰(zhàn)者C、敵手A和模擬器S，定義游戲RealC,A(λ)和IdealC,A,S(λ)。

RealC,A(λ)：敵手A構(gòu)造一個(gè)圖G并將其轉(zhuǎn)發(fā)給C。C首先對(duì)圖G進(jìn)行預(yù)處理，基于二跳覆蓋生成原始標(biāo)記并對(duì)其修剪計(jì)算，生成標(biāo)記集合{L(v)}v?G；然后，執(zhí)行密鑰生成算法(K,pk,sk)←KeyGen(λ)；最后，執(zhí)行加密算法I←Encrypt(K,pk,{L(v)}v?G)，對(duì)標(biāo)記集合中的節(jié)點(diǎn)和距離加密，得到一個(gè)安全索引結(jié)構(gòu)I并返回給A。A自適應(yīng)發(fā)出最短距離查詢請(qǐng)求q=(s,t)，A首先計(jì)算該請(qǐng)求的查詢令牌τs,t←TokenGen (K,q)，然 后A結(jié)合I和τs,t執(zhí)行密 文最短 距離查 詢Ds,t←DistQuery(I,τs,t)，最后A返回(b) ←{0,1}并作為游戲輸出。

IdealC,A,S(λ)：敵手A構(gòu)造一個(gè)圖G并將其轉(zhuǎn)發(fā)給C。C將泄露函數(shù)L1(G)的輸出轉(zhuǎn)發(fā)給模擬器S，S模擬一個(gè)安全的索引結(jié)構(gòu)I*返回給A。給定I*，A自適應(yīng)地發(fā)出最短距離查詢。對(duì)于每個(gè)最短距離查詢q=(s,t)，C將泄漏函數(shù)L2(G,q)的輸出發(fā)送給S，S模擬生成相應(yīng)的查詢令牌發(fā)送給A。A計(jì)算密文最短距離，得到結(jié)果并返 回b←{0,1}作為游戲輸出。

為進(jìn)一步提供方案的可證明安全性，對(duì)該方案的泄露函數(shù)L1和L2進(jìn)行描述并定義自適應(yīng)(L1,L2)-安全。

在加密過程中，通過觀察密文安全索引I的長(zhǎng)度，敵手可獲取修剪后標(biāo)記中(u,δuv)對(duì)的總數(shù)。給定一個(gè)圖G，定義泄露函數(shù)。在對(duì)查詢請(qǐng)求q=(s,t)進(jìn)行密文最短距離查詢過程中，敵手獲取L(s)和L(t)中各自的(u,δuv)對(duì)數(shù)，同時(shí)通過令牌和偽隨機(jī)函數(shù)計(jì)算模糊存儲(chǔ)位置和標(biāo)識(shí)符，敵手學(xué)習(xí)L(s)和L(t)的公共節(jié)點(diǎn)數(shù)nnum。在多次查詢請(qǐng)求q=(s1,t1),(s2,t2),…,(sq,tq)中，敵手可通過學(xué)習(xí)多次查詢，獲取查詢節(jié)點(diǎn)間是否被重復(fù)查詢以及重復(fù)信息rrep。由給定的圖G和查詢序列q，定義泄露函數(shù)L2(G,q)=(nnum,rrep)。

定義3（自適應(yīng)(L1,L2)-安全）由定義1 給出的Graph-SPD 方案，其泄露函數(shù)L1和L2的定義如前所述。若對(duì)于所有的概率多項(xiàng)式時(shí)間的敵手A，可以構(gòu)造一個(gè)滿足概率多項(xiàng)式時(shí)間的模擬器S，使|Pr[RealC,A(λ)=1] -Pr[IdealC,A,S(λ)=1]| ≤negl(λ)，其中：negl(·)是一個(gè)可忽略的函數(shù)，則該密文圖數(shù)據(jù)精確最短距離外包計(jì)算方案是自適應(yīng)(L1,L2)-安全的，能夠抵抗自適應(yīng)選擇查詢攻擊。

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

本節(jié)基于加法同態(tài)、部分同態(tài)加密及兩個(gè)特定的偽隨機(jī)函數(shù)f和g提出基于二跳覆蓋標(biāo)記的圖數(shù)據(jù)最短距離查詢外包計(jì)算方案，分為3 小節(jié)對(duì)方案中預(yù)處理階段、加密階段、最短距離查詢階段進(jìn)行詳細(xì)闡述和具體算法的實(shí)現(xiàn)與設(shè)計(jì)。

4.1 預(yù)處理階段

為快速應(yīng)答最短距離查詢，可以通過基于標(biāo)記的方法進(jìn)行處理。其中，一種簡(jiǎn)單的標(biāo)記方法是：對(duì)于每個(gè)節(jié)點(diǎn)v?V，從v開始進(jìn)行廣度優(yōu)先搜索并存儲(chǔ)v與其他所有節(jié)點(diǎn)之間的距離，即預(yù)先計(jì)算標(biāo)記L(v)。相較于直接在圖上進(jìn)行最短距離查詢，預(yù)先計(jì)算標(biāo)記并在標(biāo)記上進(jìn)行查詢的計(jì)算效率更高。二跳覆蓋標(biāo)記已廣泛應(yīng)用于基于標(biāo)記的距離查詢方案［13］。受修剪地標(biāo)標(biāo)記（Pruned Landmark Labeling，PLL）［30］的啟發(fā)，本文方案不直接對(duì)原始圖數(shù)據(jù)或原始二跳覆蓋標(biāo)記數(shù)據(jù)進(jìn)行加密外包，而是利用基于二跳覆蓋標(biāo)記方法對(duì)原始圖數(shù)據(jù)在廣度優(yōu)先搜索（Breadth First Search，BFS）期間進(jìn)行修剪，通過修剪預(yù)處理構(gòu)造原始圖數(shù)據(jù)的修剪二跳覆蓋標(biāo)記，以減小明文標(biāo)記數(shù)量的規(guī)模和密文圖數(shù)據(jù)安全索引結(jié)構(gòu)的尺寸，提高后續(xù)圖數(shù)據(jù)加密和最短路徑查詢的效率。

在圖數(shù)據(jù)預(yù)處理階段對(duì)標(biāo)記修剪的工作原理為：在修剪BFS 過程中，給定一個(gè)預(yù)先定義圖G中所有節(jié)點(diǎn)的標(biāo)記順序(v1,v2,…,v|V|)，按照標(biāo)記順序依次執(zhí)行廣度優(yōu)先搜索修剪策略。在以vk為根節(jié)點(diǎn)的修剪過程中，使用δ[u]表示vk和u之間的距離，從空標(biāo)記L'0開始，L'k-1是第k-1 次執(zhí)行修剪BFS 生成的 標(biāo)記，根據(jù)L'k-1計(jì)算L'k，即以vk為根節(jié)點(diǎn)執(zhí)行第k次修剪生成的標(biāo)記。若Query(vk,u,L'k-1)≤δ[u]，則對(duì)頂點(diǎn)u進(jìn)行修剪并不再從u遍歷其他邊，L'k(u)=L'k-1(u)，即不添 加(vk,δ[u])，否則設(shè) 置L'k(u)=L'k-1(u)∪ {(vk,δ[u])}，并繼續(xù)從u開始遍歷到其他邊。標(biāo)記{L'0,L'1,…,L'k-1,L'k}共同構(gòu)成標(biāo)記集合{L(v)}v?G，標(biāo)記中存儲(chǔ)圖數(shù)據(jù)所有節(jié)點(diǎn)與其鄰接節(jié)點(diǎn)的信息，包含鄰接節(jié)點(diǎn)名稱和距離值。

為了進(jìn)一步闡明圖數(shù)據(jù)預(yù)處理階段的標(biāo)記數(shù)據(jù)修剪過程，圖3 給出一個(gè)具體的廣度優(yōu)先搜索修剪策略實(shí)例，其中斜線節(jié)點(diǎn)表示根節(jié)點(diǎn)，網(wǎng)格節(jié)點(diǎn)表示已訪問并標(biāo)記過的節(jié)點(diǎn)，豎線節(jié)點(diǎn)表示已訪問但修剪的節(jié)點(diǎn)，陰影節(jié)點(diǎn)表示已經(jīng)用作根的節(jié)點(diǎn)。圖3中，初始節(jié)點(diǎn)順序?yàn)関=(1,2,…,n)，按照該順序依次進(jìn)行修剪。以原始圖數(shù)據(jù)作為初始示例，執(zhí)行二跳覆蓋標(biāo)記［圖3（a）］；按照順序從節(jié)點(diǎn)1 進(jìn)行第1 次修剪BFS，此時(shí)以節(jié)點(diǎn)1 為根節(jié)點(diǎn)利用二跳覆蓋訪問其余節(jié)點(diǎn)，完成所有節(jié)點(diǎn)的訪問［圖3（b）］，無任何節(jié)點(diǎn)被修剪掉；然后，按照順序從節(jié)點(diǎn)2 執(zhí)行第2 次修剪策略［圖3（c）］，此時(shí)節(jié)點(diǎn)1 已用作根節(jié)點(diǎn)，以陰影表示，以節(jié)點(diǎn)2 為根節(jié)點(diǎn)，利用二跳覆蓋能夠訪問的節(jié)點(diǎn)用網(wǎng)格表示，但以節(jié)點(diǎn)2為根節(jié)點(diǎn)時(shí)節(jié)點(diǎn)6與節(jié)點(diǎn)12未能訪問，在以節(jié)點(diǎn)1 為根節(jié)點(diǎn)時(shí)節(jié)點(diǎn)6 及節(jié)點(diǎn)12卻能被訪問，又因?yàn)镼uery(2,6,L'1)=dG(2,1)+dG(1,6)=3=dG(2,6)，故修剪節(jié)點(diǎn)6 并不再從此頂點(diǎn)遍歷到其他邊，同理修剪節(jié)點(diǎn)12；此后，逐節(jié)點(diǎn)執(zhí)行修剪策略，隨修剪策略執(zhí)行次數(shù)的增加，訪問節(jié)點(diǎn)逐漸減少，最短距離的搜索空間也逐漸減少，從而提升查詢效率［圖3（d）、圖3（e）］；最后，以節(jié)點(diǎn)12 為根節(jié)點(diǎn)執(zhí)行第12 次修剪策略，結(jié)束所有修剪工作。

圖3 廣度優(yōu)先搜索修剪策略示例Fig.3 Example of breadth first searching pruning strategy

結(jié)合圖數(shù)據(jù)預(yù)處理階段的原理和實(shí)例，算法1給出了具體的圖數(shù)據(jù)預(yù)處理修剪過程。

算法1prunedBFS

在算法1 所示的圖數(shù)據(jù)預(yù)處理階段中，prunedBFS 算法以圖G作為輸入，以修剪后的最終標(biāo)記集合{L(v)}v?G作為輸出。具體而言，算法1 對(duì)圖G中的每個(gè)節(jié)點(diǎn)v遍歷并進(jìn)行廣度優(yōu)先搜索，并在廣度優(yōu)先搜索期間進(jìn)行修剪，將其鄰接節(jié)點(diǎn)和距離信息添加到對(duì)應(yīng)的標(biāo)記中。算法1 在從節(jié)點(diǎn)vk出發(fā)進(jìn)行廣度優(yōu)先搜索修剪時(shí)，使用δ[v]表示vk和v之間的距離，根據(jù)L'k-1計(jì)算L'k（算法1 中第3 行～第6 行），其中：L'k-1是指前序以節(jié)點(diǎn)vk-1執(zhí)行第k-1 次廣度優(yōu)先搜索修剪策略產(chǎn)生的標(biāo)記；L'k為以vk為根節(jié)點(diǎn)執(zhí)行第k次修剪生成的標(biāo)記。Query(vk,u,L'k-1)表示使用L'k-1中的標(biāo)記查詢vk和u之間的距離。修剪過程中結(jié)合隊(duì)列Q進(jìn)行存儲(chǔ)刪除，若Query(vk,u,L'k-1)≤δ[u]，則標(biāo)記(vk,δ[u])被修剪（算法1 中第7 行～第11行），此時(shí)標(biāo)記已覆蓋vk和u之間的最短距離；否則，遍歷頂點(diǎn)u的所有鄰接節(jié)點(diǎn)所對(duì)應(yīng)的邊并繼續(xù)計(jì)算最短距離，其中NG(v)為頂點(diǎn)v?V的鄰接節(jié)點(diǎn)集合（算法1 中第12 行～第14 行）。最終，遞歸標(biāo)記{L′0,L′1,…,L′k-1,L′k}共同構(gòu) 成標(biāo)記集合{L(v)}v?G。由算法1 可知，在處理大規(guī)模圖數(shù)據(jù)時(shí)，其構(gòu)建標(biāo)記的時(shí)間和空間復(fù)雜度分別為O(|V||E|)和O(|V2|)。

4.2 加密階段

為保證外包計(jì)算過程中標(biāo)記集合的隱私，數(shù)據(jù)所有者對(duì)原始圖數(shù)據(jù)進(jìn)行預(yù)處理并生成標(biāo)記集合后，需要進(jìn)一步對(duì)標(biāo)記集合進(jìn)行加密。該階段主要涉及兩個(gè)步驟：密鑰生成及標(biāo)記加密。

密鑰生成算法結(jié)合安全參數(shù)生成密鑰。選擇一個(gè)安全參數(shù)λ作為算法輸入，從偽隨機(jī)函數(shù)域中均勻隨機(jī)生成偽隨機(jī)函數(shù)值K←{0,1}λ，同時(shí)生成一個(gè)密鑰對(duì)(pk,sk)，然后將部分密鑰K,sk發(fā)送至查詢請(qǐng)求者。具體過程如算法2 所示。

算法2KeyGen

生成密鑰后，數(shù)據(jù)所有者對(duì)根據(jù)算法1 得到的標(biāo)記集合{L(v)}v?G進(jìn)行加密，構(gòu)造安全密文索引結(jié)構(gòu)I。在標(biāo)記加密過程中，首先對(duì)標(biāo)記集合的元素(u,δuv)?L(v)依次加密：數(shù)據(jù)所有者對(duì)節(jié)點(diǎn)標(biāo)識(shí)符u使用偽隨機(jī)函數(shù)f進(jìn)行編碼U：=f(K,u||0))，對(duì)距離值δuv使用部 分同態(tài) 加密進(jìn) 行密文處理Du,v←SWHE.Enc(pk,δuv)；其次，先對(duì)每個(gè)節(jié)點(diǎn)v?G計(jì)算其對(duì)應(yīng)的鍵，即令牌Tv：=f(K,v||1))，同時(shí)為節(jié)點(diǎn)v對(duì)應(yīng)的所有鄰接節(jié)點(diǎn)標(biāo)識(shí)集合構(gòu)造索引Lv并設(shè)置內(nèi)部鍵值對(duì)，即子令牌kkey,u,v：=f(cctr,v,U)⊕Tv，其中ctr為計(jì)數(shù)器；再次，利用多重索引并結(jié)合偽隨機(jī)函數(shù)模糊存儲(chǔ)位置，即eenc,u,v：=g(cctr,v,f(K,u||2)))，使各個(gè)邊之間難以區(qū)分；然后，為構(gòu)成安全的索引結(jié)構(gòu)，將密文節(jié)點(diǎn)和密文距離值與多重索引保護(hù)值進(jìn)行異或處理，生成不可區(qū)分的標(biāo)識(shí)值Hu,v，避免泄露查詢節(jié)點(diǎn)的存儲(chǔ)位置和真實(shí)值；最后，安全索引結(jié)構(gòu)I以(Tv,Lv)對(duì)形式存儲(chǔ)密文標(biāo)記。

具體標(biāo)記加密如算法3 所示。

算法3Encrypt

在算法3 中，數(shù)據(jù)所有者對(duì)圖數(shù)據(jù)的標(biāo)記集合進(jìn)行加密，遍歷節(jié)點(diǎn)進(jìn)行加密操作（算法3 中第3 行～第15 行），包括節(jié)點(diǎn)u偽標(biāo)識(shí)加密和距離值δuv加密（算法3 中第6 行～第7 行），根據(jù)節(jié)點(diǎn)生成令牌（算法3 中第4 行）及其對(duì)應(yīng)的子令牌（算法3 中第8 行），結(jié)合偽隨機(jī)函數(shù)和多重索引進(jìn)行異或操作，生成不可區(qū)分的節(jié)點(diǎn)標(biāo)識(shí)，最終由令牌和密文標(biāo)記集合共同構(gòu)成安全索引結(jié)構(gòu)I（算法3 中第9 行～第14 行），并將其發(fā)送給CSP。

算法3 的時(shí)間復(fù)雜度為O(md)，其中：m為圖數(shù)據(jù)的節(jié)點(diǎn)總數(shù)；d是經(jīng)過修剪后單個(gè)節(jié)點(diǎn)的標(biāo)記條目數(shù)量。在標(biāo)記加密過程中，逐節(jié)點(diǎn)找尋鄰接節(jié)點(diǎn)構(gòu)成原始標(biāo)記，原始標(biāo)記與節(jié)點(diǎn)的度相關(guān)，通過修剪原始標(biāo)記可獲得修剪后的標(biāo)記集合，修剪后各節(jié)點(diǎn)的標(biāo)記數(shù)量大幅減少，單個(gè)節(jié)點(diǎn)的標(biāo)記條目d遠(yuǎn)小于該節(jié)點(diǎn)的度。隨機(jī)選定圖數(shù)據(jù)集，邊數(shù)為頂點(diǎn)數(shù)的n/m倍，在通常情況下d

4.3 最短距離查詢階段

密文圖數(shù)據(jù)的最短距離查詢階段使用令牌生成算法和距離查詢算法，由數(shù)據(jù)所有者、查詢請(qǐng)求者和CSP 交互完成。首先，令牌生成算法中查詢請(qǐng)求者對(duì)查詢節(jié)點(diǎn)計(jì)算出查詢令牌，根據(jù)查詢請(qǐng)求q=(s,t)及密鑰K生成查詢令牌τs,t，其中查詢令牌τs,t由Ts和Tt構(gòu)成，并將令牌τs,t發(fā)送給CSP。其次，距離查詢算法中CSP 對(duì)收到的查詢令牌τs,t進(jìn)行解析，并根據(jù)安全索引結(jié)構(gòu)I計(jì)算距離集合，結(jié)合數(shù)據(jù)所有者執(zhí)行安全比較協(xié)議，獲取密文最短距離結(jié)果。

為便于理解，本節(jié)分為3 個(gè)小節(jié)，將在第4.3.1 節(jié)簡(jiǎn)單介紹查詢令牌生成算法，在第4.3.2 節(jié)闡述距離查詢算法，在第4.3.3 節(jié)提出支撐距離查詢算法執(zhí)行的安全比較協(xié)議。

4.3.1 查詢令牌生成算法

算法4TokenGen

在算法4 中，查詢請(qǐng)求者根據(jù)最短距離查詢請(qǐng)求q=(s,t)及密鑰K，生成對(duì)應(yīng)節(jié)點(diǎn)令牌并構(gòu)成查詢令牌τs,t（算法4 中第1 行～第4 行）。算法執(zhí)行完后，查詢請(qǐng)求者將τs,t發(fā)送給CSP。

4.3.2 距離查詢算法

在距離查詢算法中，CSP 首先對(duì)收到的查詢令牌τs,t進(jìn)行解析，獲取到密文源點(diǎn)令牌Ts及密文終點(diǎn)令牌Tt，并根據(jù)節(jié)點(diǎn)令牌計(jì)算其對(duì)應(yīng)的子令牌kkey,u,s及kkey,u,t。其次，根據(jù)子令牌查詢鄰接節(jié)點(diǎn)標(biāo)識(shí)集合索引Lv中對(duì)應(yīng)的密文節(jié)點(diǎn)和邊長(zhǎng)，并將兩者對(duì)應(yīng)的(U,Du,v)對(duì)存儲(chǔ)在集合L(s)與集合L(t)中。再次，CSP基于標(biāo)記集合L(s)與L(t)篩選其中存在包含公共節(jié)點(diǎn)的(U,Du,v)對(duì)。篩選過程為：遍歷標(biāo)記集合L(s)與L(t)中的每個(gè)條目，如果在L(s)中存在Ui，在L(t)中存在Uj，滿足Ui==Uj（即兩個(gè)頂點(diǎn)相同），此時(shí)存在包含公共節(jié)點(diǎn)Ui==Uj的(Ui,Dsi)和(Uj,Djt)；然后，CSP計(jì)算兩者距離和Di=Add(Dsi+Djt)并作為新的距離值。由于采用加法同態(tài)密碼系統(tǒng)加密距離值，故可對(duì)密文距離值執(zhí)行相加操作。最后，在同態(tài)相加后基于CSP 與數(shù)據(jù)所有者的安全比較協(xié)議計(jì)算距離最小值，通過對(duì)候選距離集合中的所有整數(shù)進(jìn)行比較來查找最小值，并將密文最短距離值Ds,t作為最終結(jié)果返回給查詢請(qǐng)求者。

安全比較協(xié)議計(jì)算距離最小值的具體內(nèi)容如第4.3.3 節(jié)所示。若存在相同最短距離，則將存在多個(gè)候選結(jié)果，忽略路徑返回密文最短距離值作為最終結(jié)果返回。具體的距離查詢算法如算法5 所示。

算法5DistQuery

在算法5 中，CSP 首先計(jì)算令牌對(duì)應(yīng)的密文標(biāo)記集合：將τs,t解析為節(jié)點(diǎn)令牌Ts和Tt（算法5 中第1行），根據(jù)當(dāng)前節(jié)點(diǎn)，令牌Ts計(jì)算該節(jié)點(diǎn)與鄰接節(jié)點(diǎn)的子令牌kkey,u,s，結(jié)合模糊存儲(chǔ)位置eenc,u,s計(jì)算節(jié)點(diǎn)標(biāo)識(shí)值Hu,s，進(jìn)而結(jié)合異或操作推出密文標(biāo)記(U,Du,s)，將所有標(biāo)記存儲(chǔ)至集合L(s)中（算法5 中第3 行～第11 行）。同理計(jì)算節(jié)點(diǎn)令牌Tt對(duì)應(yīng)的密文標(biāo)記集合L(t)（算法5 中第12 行）。其次，篩選標(biāo)記集合L(s)與L(t)包含公共節(jié)點(diǎn)的(U,Du,v)對(duì)，若節(jié)點(diǎn)相同，則根據(jù)加法同態(tài)加密執(zhí)行密文距離值相加操作，否則遍歷標(biāo)記集合L(s)中的鄰接節(jié)點(diǎn)，繼續(xù)篩選及判斷鄰接節(jié)點(diǎn)的標(biāo)記集合L(i)與L(t)的公共節(jié)點(diǎn)，進(jìn)而計(jì)算出源節(jié)點(diǎn)s至目的節(jié)點(diǎn)t的所有連通的密文距離值，并存儲(chǔ)至密文距離集合DDist中（算法5 中第13 行～第19 行）。最后，結(jié)合數(shù)據(jù)所有者和CSP 之間的安全比較協(xié)議，計(jì)算密文距離最小值Ds,t并返回給查詢請(qǐng)求者（算法5 中第20 行～第24 行）。

此外，算法5 的時(shí)間復(fù)雜度為O(d)，其中d為單個(gè)節(jié)點(diǎn)的標(biāo)記條目數(shù)量。在最短距離查詢過程中，通過解析已知的查詢令牌，然后確定源節(jié)點(diǎn)令牌和目的節(jié)點(diǎn)令牌，在安全索引結(jié)構(gòu)中搜索查詢節(jié)點(diǎn)令牌對(duì)應(yīng)的標(biāo)記，進(jìn)而在標(biāo)記中尋找共同節(jié)點(diǎn)并計(jì)算距離集合。由于查詢令牌確定，因此可從安全索引結(jié)構(gòu)中直接計(jì)算標(biāo)記，至多執(zhí)行d次比較就能得出公共節(jié)點(diǎn)，進(jìn)而從公共節(jié)點(diǎn)中計(jì)算距離集合。查詢最短距離結(jié)果后返回結(jié)果，在此過程中無需額外存儲(chǔ)，僅返回密文距離值，故空間復(fù)雜度為O(1)。

查詢請(qǐng)求者接收到CSP 發(fā)送的密文最短距離Ds,t后，僅需密鑰sk對(duì)其進(jìn)行解密即可得到明文最短距離ds,t，故對(duì)解密階段省略描述。

4.3.3 安全比較協(xié)議

假定實(shí)體間不合謀，安全比較協(xié)議由CSP 和數(shù)據(jù)所有者共同執(zhí)行。CSP 可以通過使用混淆電路與同態(tài)加密相結(jié)合的方案來實(shí)現(xiàn)兩個(gè)密文距離值的比較。受混淆電路塊［31］的啟發(fā)，安全比較協(xié)議中安全比較電路由CMP 電路和SUB 電路構(gòu)造，CMP 電路用于位比較，SUB 電路用于位減，兩者均采用自由異或技術(shù)。該協(xié)議中安全比較電路的具體實(shí)現(xiàn)如圖4所示。

圖4 密文距離值安全比較電路Fig.4 Secure comparison circuit for encrypted distance values

在實(shí)際密文距離值比較過程中，CSP 擁有查詢節(jié)點(diǎn)間的密文距離集合DDist={[D1],[D2],…,[Dn]}，數(shù)據(jù)所有者擁有密鑰。安全比較協(xié)議基于樸素最小值算法，CSP 依次比較DDist集合中的密文距離值，獲取最短距離。假設(shè)DDist集合中所有值均位于范圍2l內(nèi)，即所有密文距離值是l位整數(shù)。CSP 不會(huì)直接向數(shù)據(jù)所有者發(fā)送密文距離值，而是通過同態(tài)加密特性利用一個(gè)k位隨機(jī)數(shù)ri對(duì)密文距離值進(jìn)行掩碼處理，即[Di+ri]=[Di]?[ri]，其中k是一個(gè) 參數(shù)且k>l。掩碼通過對(duì)整數(shù)執(zhí)行加法操作進(jìn)行統(tǒng)計(jì)隱藏，對(duì)l位整數(shù)[Di]和k位整數(shù)[ri]來說，發(fā)送[Di+ri]可以為密文距離值提供約2l-k的統(tǒng)計(jì)安全性。選擇合適的k，可以使得統(tǒng)計(jì)差異變得任意小。此時(shí)數(shù)據(jù)所有者輸入隨機(jī)數(shù)[r1]和[r2]，CSP 輸入[D1+r1]和[D2+r2]，在通過安全比較電路后，輸出位b表示比較結(jié)果，如果[D1]>[D2]，則b=1，否則b=0。逐密文值進(jìn)行比較最終得出最短距離。

具體密文距離的安全比較協(xié)議如協(xié)議1 所示。

協(xié)議1安全比較協(xié)議

步驟1CSP 整理密文距離值集合DDist={[D1],[D2],…,[Dn]}，并依次選取兩個(gè)密文距離值[D1]和[D2]；

步驟2數(shù)據(jù)所有者利用同態(tài)性選取隨機(jī)數(shù)ri并輸入對(duì)應(yīng)的隨機(jī)數(shù)[r1]和[r2]，將其發(fā)送至安全比較電路；

步驟3CSP 利用隨機(jī)數(shù)[r1]和[r2]對(duì)密文距離值[D1]和[D2]進(jìn)行掩碼處理，即輸入[D1+r1]和[D2+r2]至安全比較電路；

步驟4通過安全比較電路后，輸出位b表示比較結(jié)果，即，選出最小值后繼續(xù)與集合中的密文距離值進(jìn)行比較；

步驟5最終將Ds,t=min{DDist}=min{[D1],[D2],…,[Dn]}作為結(jié)果返回。

協(xié)議1 中密文距離值的安全比較協(xié)議采用樸素最小值比較，基于安全比較電路依次對(duì)密文距離集合中的元素進(jìn)行比較，最終獲取密文最短距離。

5 安全分析

本節(jié)對(duì)第4 節(jié)所提方案進(jìn)行安全性分析，分別分析方案中圖數(shù)據(jù)加密系統(tǒng)的安全性和密文圖數(shù)據(jù)最短距離外包計(jì)算方案的安全性。

定理1本文所提密文圖數(shù)據(jù)精確最短距離計(jì)算方案在隨機(jī)預(yù)言模型下滿足選擇明文攻擊不可區(qū)分的安全性（即IND-CPA 安全）。

證明：

假設(shè)存在任何多項(xiàng)式時(shí)間的敵手A 攻擊密文圖數(shù)據(jù)精確最短距離的計(jì)算過程，可以構(gòu)建挑戰(zhàn)者?以可忽略的概率保證IND-CPA 安全。

敵手A 考慮以下攻擊實(shí)驗(yàn)：在初始化階段，挑戰(zhàn)者? 產(chǎn)生加密系統(tǒng)，敵手A 獲得系統(tǒng)的密鑰。

模擬密文最短距離查詢，敵手A 為獲取加密圖數(shù)據(jù)與標(biāo)記的信息，輸出查詢請(qǐng)求，其中包含兩個(gè)不同的節(jié)點(diǎn)信息，即q=(s,t)；然后對(duì)其進(jìn)行加密，得到查詢令牌，并對(duì)當(dāng)前查詢請(qǐng)求進(jìn)行結(jié)果詢問。

敵手A 繼續(xù)對(duì)任意節(jié)點(diǎn)執(zhí)行最短距離計(jì)算詢問，根據(jù)查詢令牌和安全索引結(jié)構(gòu)，判斷當(dāng)前查詢節(jié)點(diǎn)是否存在，若存在，則依據(jù)查詢令牌和安全索引結(jié)構(gòu)計(jì)算密文最短距離Ds,t，否則返回空值，使其重新發(fā)起查詢請(qǐng)求。

最后敵手A 停止詢問并輸出一組查詢請(qǐng)求q*=(s*,t*)的猜測(cè)密文最短距離結(jié)果D's*,t*，根據(jù)(s*,t*)的查詢令牌τs*,t*可得真實(shí)密文最短距離結(jié)果Ds*,t*，若Ds*,t*=D's*,t*，則敵手A 攻擊成功。

敵 手 A 的優(yōu)勢(shì) 可定義 為 ：AOPE,A(k)=，其中k為用于加密方案中的安全參數(shù)。

設(shè)方案存在一個(gè)可忽略的函數(shù)negl(k)，使得，即保證該方案在隨機(jī)預(yù)言模型下以概率negl(k)滿足IND-CPA 安全。

定理2如果對(duì)稱加密算法、偽隨機(jī)函數(shù)是安全的，則所提出的基于二跳覆蓋標(biāo)記的圖數(shù)據(jù)最短距離外包計(jì)算方案實(shí)現(xiàn)(L1,L2)安全。

證明：

在查詢請(qǐng)求者發(fā)出查詢令牌之前，敵手A 僅可獲取安全索引結(jié)構(gòu)，并進(jìn)一步推斷方案在加密階段中泄露圖的相關(guān)信息。具體而言，敵手A 通過觀察加密索引的長(zhǎng)度可得二跳覆蓋標(biāo)記索引中(u,δuv)對(duì)的數(shù)量，即給定 圖G可得。在查詢階段，當(dāng)查詢請(qǐng)求者發(fā)出查詢請(qǐng)求q=(s,t)時(shí)，敵手A 了解到在L(s)和L(t)中的共同頂點(diǎn)數(shù)量nnum。由于偽隨機(jī)函數(shù)是確定的，因此敵手A 通過觀察標(biāo)記兩個(gè)查詢q1=(s1,t1)和q2=(s2,t2)，能夠識(shí)別兩者間的等價(jià)關(guān)系。給定圖G和查詢序列q=(s1,t1),(s2,t2),…,(sp,tp)，可 得L2(G)=(rrep,q,nnum)，其中rrep,q存儲(chǔ)查詢頂點(diǎn)的重復(fù)信息，判斷頂點(diǎn)是否被重復(fù)查詢；nnum為存儲(chǔ)共同頂點(diǎn)數(shù)量的數(shù)組。

在游戲中構(gòu)造一個(gè)模擬器S，使用L1,L2模擬一個(gè)適當(dāng)?shù)乃饕齀*并根據(jù)查詢(s,t)生成查詢令牌。模擬器S根據(jù)查詢令牌計(jì)算索引I*中對(duì)應(yīng)的距離值，模擬一組二跳覆蓋標(biāo)記中的(u,δuv)對(duì)的距離值集合，即，判斷在集合C*中的大小關(guān)系，然后模擬器S通過索引I*模擬計(jì)算t個(gè)節(jié)點(diǎn)標(biāo)識(shí)符，并將插入到標(biāo)記集合中。當(dāng)中的共同節(jié)點(diǎn)數(shù)等于nnum時(shí)，模擬器S刪除重復(fù)的標(biāo)記并將標(biāo)記重新表示。

由于安全索引結(jié)構(gòu)的構(gòu)造使用偽隨機(jī)函數(shù)、部分同態(tài)加密、多重索引等，每個(gè)節(jié)點(diǎn)的密文值均不相同，且索引中距離值的加密使用長(zhǎng)度為128 的安全參數(shù)難以破解安全索引結(jié)構(gòu)，因此方案是實(shí)際安全有效的。

敵手A 偽造查詢條件和密文索引結(jié)構(gòu)，由于對(duì)稱加密和偽隨機(jī)函數(shù)兩個(gè)密碼原語是安全的，故在查詢請(qǐng)求前與查詢過程中，索引I和I*的距離計(jì)算過程和結(jié)果是不可區(qū)分的，即任意多項(xiàng)式時(shí)間敵手A對(duì)于RealC,A(λ)和IdealC,A,S(λ)具有不可區(qū)分性，因此方案實(shí)現(xiàn)(L1,L2)安全。

6 實(shí)驗(yàn)結(jié)果與分析

本節(jié)首先將本文提出的加密圖數(shù)據(jù)最短距離查詢外包計(jì)算方案與文獻(xiàn)［17］、文獻(xiàn)［20］、文獻(xiàn)［21］、文獻(xiàn)［22］、文獻(xiàn)［25］方案進(jìn)行分析對(duì)比，然后通過在8 個(gè)公開的真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，驗(yàn)證本文方案性能。

6.1 方案分析與對(duì)比

本文所提出Graph-SPD 方案的開銷主要在加密階段與查詢階段。加密階段的時(shí)間開銷和空間開銷取決于二跳覆蓋標(biāo)記生成標(biāo)記的數(shù)量，其時(shí)間復(fù)雜度為O(md)，空間復(fù)雜度為O(md)。在查詢階段對(duì)密文索引結(jié)構(gòu)查詢最短距離時(shí)依據(jù)查詢頂點(diǎn)檢索安全索引結(jié)構(gòu)中對(duì)應(yīng)的標(biāo)記，其時(shí)間復(fù)雜度為O(d)，空間復(fù)雜度為O(1)。

本文所提的Graph-SPD 方案實(shí)現(xiàn)了加密圖數(shù)據(jù)上的精確最短距離查詢，其基于二跳覆蓋標(biāo)記和修剪策略生成標(biāo)記集合，利用加法同態(tài)加密、偽隨機(jī)函數(shù)、部分同態(tài)加密等密碼原語來加密標(biāo)記集合并生成相應(yīng)的密文安全索引結(jié)構(gòu)，根據(jù)查詢令牌在索引中計(jì)算標(biāo)記，找尋公共節(jié)點(diǎn)對(duì)距離值進(jìn)行同態(tài)加法計(jì)算，進(jìn)而比較距離集合實(shí)現(xiàn)最短距離查詢。該方案與現(xiàn)有的加密圖數(shù)據(jù)外包計(jì)算方案具有明顯差異，如表2所示，其中：m為節(jié)點(diǎn)數(shù)；n為邊數(shù)；u為結(jié)構(gòu)圖的節(jié)點(diǎn)數(shù)；η為構(gòu)造結(jié)構(gòu)圖的尺寸；l為標(biāo)記中的條目數(shù)；d為安全索引結(jié)構(gòu)的標(biāo)記長(zhǎng)度。由表2 可知，文獻(xiàn)［17］、文獻(xiàn)［20］、文獻(xiàn)［21］方案均實(shí)現(xiàn)了密文圖數(shù)據(jù)的近似最短距離查詢，其中文獻(xiàn)［17］方案采用距離預(yù)言和同態(tài)加密的方式處理原始圖數(shù)據(jù)，在安全性方面存在泄露節(jié)點(diǎn)總數(shù)和最大距離值的問題。文獻(xiàn)［20］、文獻(xiàn)［21］方案均采用二跳覆蓋標(biāo)記存儲(chǔ)距離值，其中：文獻(xiàn)［20］方案使用保序加密以保證距離值之間的順序信息，進(jìn)而計(jì)算近似最短距離，該方案存在泄露順序信息、索引長(zhǎng)度、重復(fù)信息的問題；文獻(xiàn)［21］方案聚焦帶約束的最短距離查詢問題，其基于同態(tài)加密實(shí)現(xiàn)隱私與效率共存的近似最短距離計(jì)算，在安全方面存在泄露圖數(shù)據(jù)的節(jié)點(diǎn)數(shù)量、邊數(shù)量和公共頂點(diǎn)信息的問題。以上3 個(gè)方案均為提高計(jì)算效率而降低了查詢精度，而本文方案在保證查詢計(jì)算效率［即密文查詢時(shí)間復(fù)雜度O(d)］的前提下實(shí)現(xiàn)了密文圖數(shù)據(jù)上精確最短距離查詢，提高了查詢精度。

表2 加密圖數(shù)據(jù)下不同外包計(jì)算方案的對(duì)比 Table 2 Comparison among different outsourced computation schemes under encrypted graph data

本文和文獻(xiàn)［22］、文獻(xiàn)［25］均設(shè)計(jì)了精確最短距離查詢方案，其中：文獻(xiàn)［22］方案采用鄰接表實(shí)例化原始圖數(shù)據(jù)，能保證查詢精度，然而查詢時(shí)間復(fù)雜度較高，鄰接表數(shù)量和重復(fù)信息也容易被泄露；文獻(xiàn)［25］方案采用二跳覆蓋標(biāo)記和同態(tài)加密方法實(shí)現(xiàn)帶約束的精確最短距離查詢，卻無法直接應(yīng)用于無約束的精確最短距離查詢，同樣在查詢過程中容易泄露查詢的重復(fù)信息。相較文獻(xiàn)［22］、文獻(xiàn)［25］方案，本文的加密和密文查詢機(jī)制不同，因此本文提出基于修剪二跳覆蓋標(biāo)記和加法同態(tài)加密的圖數(shù)據(jù)精確最短距離查詢外包計(jì)算方案。此外，在安全性方面，相較(L1,L2,L3)安全［22］或CQA2 安全［25］，本文方案更加安全，能夠同時(shí)滿足IND-CPA 安全和(L1,L2)安全。在計(jì)算效率方面，相較于文獻(xiàn)［22］方案，本文方案在加密階段采用了不同的數(shù)據(jù)結(jié)構(gòu)處理原始圖數(shù)據(jù)。文獻(xiàn)［22］方案生成3 個(gè)字典加密圖數(shù)據(jù)，時(shí)間復(fù)雜度和空間復(fù)雜度均為O(m+n)，而本文方案逐節(jié)點(diǎn)對(duì)其標(biāo)記進(jìn)行加密，時(shí)間復(fù)雜度和空間復(fù)雜度均為O(md)；在查詢階段，文獻(xiàn)［22］方案使用斐波那契堆加速Dijkstra 算法，同時(shí)添加輔助結(jié)構(gòu)存儲(chǔ)歷史查詢，獲得了O(m+nlogan) 的時(shí)間復(fù)雜度和O(m)的空間復(fù)雜度，本文方案直接對(duì)查詢節(jié)點(diǎn)的標(biāo)記計(jì)算最短距離并在查詢結(jié)束后僅返回密文距離，因此時(shí)間復(fù)雜度為O(d)，空間復(fù)雜度為O(1)。相較于文獻(xiàn)［25］方案，本文方案在加密階段不需要對(duì)所有頂點(diǎn)的全部標(biāo)記進(jìn)行加密，將計(jì)算復(fù)雜度和空間復(fù)雜度都從文獻(xiàn)［25］的O(l)提升為O(d)；在查詢階段本文方案無需計(jì)算所有節(jié)點(diǎn)的標(biāo)記，通過找尋修剪后的標(biāo)記集合間共同節(jié)點(diǎn)得出距離值，使計(jì)算復(fù)雜度從O(n)提升為O(d)，空間復(fù)雜度保持O(1)不變。

6.2 結(jié)果與分析

為進(jìn)一步驗(yàn)證本文所提Graph-SPD 方案的實(shí)際計(jì)算效率，本文在不同的公開真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與文獻(xiàn)［22］、文獻(xiàn)［25］所提出的密文圖數(shù)據(jù)的精確最短距離計(jì)算方案進(jìn)行實(shí)驗(yàn)對(duì)比。由于文獻(xiàn)［22］的方案無標(biāo)記處理這一預(yù)處理過程，所以標(biāo)記處理生成的標(biāo)記數(shù)量和時(shí)間開銷對(duì)比僅在本文方案和文獻(xiàn)［25］方案之間進(jìn)行，圖數(shù)據(jù)加密、查詢令牌生成、最短距離查詢、查詢結(jié)果解密等時(shí)間開銷對(duì)比在3 個(gè)方案之間進(jìn)行。

6.2.1 實(shí)驗(yàn)設(shè)置

為了使實(shí)驗(yàn)結(jié)果具有客觀性，本文選取與文獻(xiàn)［22］、文獻(xiàn)［25］部分相同的真實(shí)圖數(shù)據(jù)集來測(cè)試方案性能。實(shí)驗(yàn)均由C++編程語言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為Ubuntu 18.04 Linux X86 64 位操作系統(tǒng)，客戶端配置為Intel?CoreTMi5-7200U（2.70 GHz）CPU，12 GB RAM，服務(wù)器配置為2.7 GHz Intel Xeon CPU 8 核、16 GB RAM。偽隨機(jī)函數(shù)和對(duì)稱密鑰算法由哈希運(yùn)算消息認(rèn)證碼（Hash-based Message Authentication Code，HMAC）和高級(jí)加密標(biāo)準(zhǔn)（Advanced Encryption Standard，AES）實(shí)例化，安全參數(shù)設(shè)為128 bit。

實(shí)驗(yàn)選用SNAP 網(wǎng)站公開的圖數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，表3 總結(jié)了所選的8 個(gè)數(shù)據(jù)集的主要特征，包含數(shù)據(jù)集名稱、圖類型、節(jié)點(diǎn)數(shù)和邊數(shù)。在表3 中，數(shù)據(jù)集ego-Facebook（簡(jiǎn)稱Facebook）來自Facebook的社交網(wǎng)絡(luò)，是由用戶好友列表組成的特征集合；數(shù)據(jù)集p2p-Gnutella（簡(jiǎn)稱Gnutella）是Gnutella 對(duì)文件共享網(wǎng)絡(luò)的快照序列，表示網(wǎng)絡(luò)拓?fù)渲械闹鳈C(jī)連接關(guān)系；數(shù)據(jù)集ca-AstroPh（簡(jiǎn)稱AstroPh）是涵蓋提交到Astrophysics 類別的作者論文之間的合作網(wǎng)絡(luò)；數(shù)據(jù)集email-Enron（簡(jiǎn)稱Enron）記錄了與安然電子郵件地址往來的郵件通信，構(gòu)成電子郵件通信網(wǎng)絡(luò)；數(shù)據(jù)集ca-CondMat（簡(jiǎn)稱CondMat）是凝聚態(tài)物質(zhì)研究相關(guān)的論文作者之間的學(xué)術(shù)合作網(wǎng)絡(luò)；數(shù)據(jù)集loc-Brightkite（簡(jiǎn)稱Brightkite）是由用戶簽到數(shù)據(jù)構(gòu)成的社交網(wǎng)絡(luò)；數(shù)據(jù)集soc-Slashdot（簡(jiǎn)稱Slashdot）是由新聞網(wǎng)站中特定用戶構(gòu)成的社交網(wǎng)絡(luò)；數(shù)據(jù)集email-EuAll（簡(jiǎn)稱EuAll）是歐洲研究機(jī)構(gòu)對(duì)收發(fā)的電子郵件匿名化處理生成的電子郵件網(wǎng)絡(luò)。與文獻(xiàn)［22］、文獻(xiàn)［25］相同，本文在實(shí)驗(yàn)過程中為表3 中所有圖數(shù)據(jù)的邊分配了隨機(jī)的距離值，范圍為［0，10］，精度為0.01。在實(shí)驗(yàn)過程中，為保證實(shí)驗(yàn)結(jié)果的客觀性，在預(yù)處理、圖數(shù)據(jù)加密、查詢令牌生成、最短距離查詢和查詢結(jié)果解密這幾個(gè)階段，分別進(jìn)行30 次重復(fù)實(shí)驗(yàn)，將平均時(shí)間開銷作為實(shí)驗(yàn)結(jié)果數(shù)據(jù)。在最短距離查詢階段，采用中心極限定理的思想，在不同數(shù)據(jù)集中隨機(jī)選取5 組頂點(diǎn)對(duì)進(jìn)行最短距離查詢，每組執(zhí)行30 次查詢，得到隨機(jī)抽樣查詢時(shí)間開銷的平均值，即最短距離查詢平均時(shí)間。

表3 本文數(shù)據(jù)集的主要特征 Table 3 Key characteristics of data sets in this paper

6.2.2 實(shí)驗(yàn)結(jié)果

本文方案與文獻(xiàn)［25］方案均在對(duì)原始圖數(shù)據(jù)進(jìn)行加密之前分別利用二跳覆蓋標(biāo)記處理機(jī)制對(duì)圖數(shù)據(jù)進(jìn)行預(yù)處理，生成原始圖數(shù)據(jù)的標(biāo)記集合，以提高圖數(shù)據(jù)加密、最短距離查詢等操作的效率。本文方案與文獻(xiàn)［25］方案在預(yù)處理階段相同數(shù)據(jù)集下生成的標(biāo)記數(shù)量以及花費(fèi)的時(shí)間有很大差異，圖5 所示為標(biāo)記數(shù)量及標(biāo)記生成時(shí)間開銷對(duì)比，其標(biāo)記數(shù)量對(duì)比如圖5（a）所示，標(biāo)記生成時(shí)間開銷對(duì)比如圖5（b）所示。

圖5 標(biāo)記數(shù)量及標(biāo)記生成時(shí)間開銷對(duì)比Fig.5 Comparison of the number of labels and the time overhead of label generation

圖5 表明，本文方案相比文獻(xiàn)［25］方案在不同數(shù)據(jù)集上生成的標(biāo)記數(shù)量降低46.74%～60.00%，且隨著數(shù)據(jù)集的規(guī)模增大，標(biāo)記數(shù)量的減少幅度愈大；在不同數(shù)據(jù)集上生成標(biāo)記的時(shí)間開銷上，相比于文獻(xiàn)［25］方案，本文方案的時(shí)間開銷增加了9.91%～30.44%，時(shí)間開銷的增加與圖數(shù)據(jù)規(guī)模、結(jié)構(gòu)復(fù)雜程度相關(guān)。

本文方案在圖數(shù)據(jù)預(yù)處理的標(biāo)記生成數(shù)量上有巨大優(yōu)勢(shì)，這是由于文獻(xiàn)［25］方案僅利用二跳覆蓋標(biāo)記方法構(gòu)建標(biāo)記集合，其生成的標(biāo)記數(shù)量與圖的節(jié)點(diǎn)規(guī)模相同；而本文方案采用修剪二跳覆蓋標(biāo)記構(gòu)建標(biāo)記集合，在生成標(biāo)記時(shí)，逐節(jié)點(diǎn)進(jìn)行遍歷并執(zhí)行廣度優(yōu)先搜索修剪策略，減少由二跳覆蓋標(biāo)記生成的原始標(biāo)記數(shù)量。

本文方案的標(biāo)記生成增加了額外的時(shí)間開銷，這是因?yàn)楸疚姆桨冈诙采w標(biāo)記的基礎(chǔ)上進(jìn)行廣度優(yōu)先搜索修剪策略，而標(biāo)記生成時(shí)間包括了標(biāo)記修剪時(shí)間。增加的時(shí)間開銷比例與圖數(shù)據(jù)規(guī)模和結(jié)構(gòu)復(fù)雜程度相關(guān)，規(guī)模越大、越復(fù)雜的圖數(shù)據(jù)其廣度優(yōu)先搜索策略的開銷越大。此外，如前所述，文獻(xiàn)［20］方案采用鄰接表實(shí)例化原始圖數(shù)據(jù)，未生成標(biāo)記，故不對(duì)其進(jìn)行比較。

在圖數(shù)據(jù)加密階段，文獻(xiàn)［22］方案直接對(duì)圖數(shù)據(jù)進(jìn)行加密，本文方案和文獻(xiàn)［25］方案分別對(duì)生成的標(biāo)記信息進(jìn)行加密，構(gòu)造安全索引結(jié)構(gòu)。3 個(gè)不同方案的加密時(shí)間開銷對(duì)比如圖6 所示。

圖6 圖數(shù)據(jù)加密時(shí)間開銷對(duì)比Fig.6 Time overhead comparison of encrypted graph data

由圖6 可知，3 個(gè)方案的加密時(shí)間開銷均與圖數(shù)據(jù)的規(guī)模呈線性相關(guān)，時(shí)間開銷隨圖數(shù)據(jù)規(guī)模的增加而增加。其中本文方案具有明顯優(yōu)勢(shì)，加密時(shí)間開銷比文獻(xiàn)［25］方案降低了13.04%～24.24%，比文獻(xiàn)［22］方案降低了23.08%～34.21%；本文方案在所有圖數(shù)據(jù)上的加密時(shí)間開銷均在可接受范圍內(nèi)，即使原始圖數(shù)據(jù)或標(biāo)記數(shù)量規(guī)模接近百萬，加密時(shí)間也僅需120 s。

本文方案在加密時(shí)間開銷方面具有顯著優(yōu)勢(shì)的主要原因是，本文方案對(duì)圖數(shù)據(jù)生成的原始標(biāo)記采用廣度優(yōu)先搜索修剪策略進(jìn)行修剪，使標(biāo)記數(shù)量大幅減少，降低了加密階段需要加密的明文長(zhǎng)度，提高了圖數(shù)據(jù)的加密效率。文獻(xiàn)［25］方案直接對(duì)原始標(biāo)記進(jìn)行加密處理，雖然標(biāo)記數(shù)量與原始圖數(shù)據(jù)的鄰接矩陣相比大幅減少了明文長(zhǎng)度，但該方案需要加密原始圖數(shù)據(jù)對(duì)應(yīng)的所有標(biāo)記，故仍有優(yōu)化空間。文獻(xiàn)［22］方案需要對(duì)鄰接表實(shí)例化后的圖數(shù)據(jù)進(jìn)行加密，鄰接表實(shí)例化構(gòu)造復(fù)雜，需要加密的明文長(zhǎng)度最長(zhǎng)，因此在3 個(gè)方案中該方案加密時(shí)間開銷最高。

在查詢令牌生成階段，本文方案與文獻(xiàn)［22］、文獻(xiàn)［25］方案的查詢請(qǐng)求者均會(huì)發(fā)出查詢請(qǐng)求，并對(duì)查詢請(qǐng)求加密生成查詢請(qǐng)求令牌，3 個(gè)方案的查詢令牌生成的時(shí)間開銷對(duì)比如圖7 所示。由圖7 可知，3 個(gè)方案中的令牌生成時(shí)間開銷均為常數(shù)級(jí)，約為0.4 ms。這是由于3 個(gè)方案中的查詢請(qǐng)求模式一樣，即發(fā)出一個(gè)頂點(diǎn)對(duì)之間的最短距離查詢請(qǐng)求，在生成查詢令牌時(shí)僅需要對(duì)待查詢的2個(gè)頂點(diǎn)進(jìn)行加密。

圖7 生成查詢令牌的時(shí)間開銷對(duì)比Fig.7 Time overhead comparison of generating query token

在最短距離查詢階段，CSP 根據(jù)查詢請(qǐng)求者提交的查詢令牌，查詢兩點(diǎn)之間的密文最短距離，本文與文獻(xiàn)［22］、文獻(xiàn)［25］方案的最短距離查詢時(shí)間開銷對(duì)比如圖8 所示。圖8 表明，3 個(gè)方案的最短距離查詢時(shí)間開銷均與圖數(shù)據(jù)的規(guī)模大小和結(jié)構(gòu)復(fù)雜程度正相關(guān)，規(guī)模越大、復(fù)雜程度越高，所需要的時(shí)間開銷越大。其中，本文方案的最短距離查詢時(shí)間開銷最小，相比文獻(xiàn)［22］、文獻(xiàn)［25］方案具有巨大優(yōu)勢(shì)，相比文獻(xiàn)［22］方案降低了90% 以上，相比文獻(xiàn)［25］方案降低了36.44%～46.13%。

圖8 最短距離查詢的時(shí)間開銷對(duì)比Fig.8 Time overhead comparison of the shortest distance querying

本文方案的最短距離查詢時(shí)間開銷顯著降低的原因是文獻(xiàn)［22］方案為實(shí)現(xiàn)精確最短距離查詢?cè)O(shè)計(jì)構(gòu)造了斐波那契堆，增加了時(shí)間開銷，同時(shí)為支持圖數(shù)據(jù)的動(dòng)態(tài)更新，該方案構(gòu)建了輔助數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)歷史查詢的查詢結(jié)果，若當(dāng)前節(jié)點(diǎn)未曾查詢，則需重新計(jì)算，故綜合而言，文獻(xiàn)［22］方案最短距離查詢時(shí)間開銷較高。文獻(xiàn)［25］方案基于部分同態(tài)加密進(jìn)行帶約束的精確最短距離計(jì)算，計(jì)算代價(jià)的約束以及準(zhǔn)確性的影響使得查詢效率降低，查詢時(shí)間增加。而本文方案基于加法同態(tài)加密并結(jié)合標(biāo)記修剪策略執(zhí)行精確最短距離計(jì)算，一方面由于密文長(zhǎng)度相比文獻(xiàn)［22］、文獻(xiàn)［25］方案得到了大幅降低，因此縮小了密文數(shù)據(jù)上的查詢搜索空間；另一方面由于在密文圖數(shù)據(jù)上保留了供最短距離查詢的鄰居信息，因此在進(jìn)行密文距離對(duì)比時(shí)效率更高。

在密文結(jié)果解密階段，本文方案與文獻(xiàn)［22］、文獻(xiàn)［25］方案中的查詢請(qǐng)求者只需使用密鑰對(duì)密文距離值解密，其密文結(jié)果解密的時(shí)間開銷對(duì)比如圖9所示。

圖9 密文結(jié)果解密的時(shí)間開銷對(duì)比Fig.9 Time overhead comparison of decrypting ciphertext results

由圖9 可知，與查詢令牌生成時(shí)間開銷類似，3 個(gè)方案中的密文結(jié)果解密時(shí)間均為常數(shù)，約為0.018 ms。類似的，由于3 個(gè)方案都僅需要對(duì)單個(gè)密文結(jié)果進(jìn)行解密，因此時(shí)間開銷均為常數(shù)。

7 結(jié)束語

本文針對(duì)云計(jì)算環(huán)境下的密文圖數(shù)據(jù)最短距離查詢外包服務(wù)場(chǎng)景，提出一種基于二跳覆蓋標(biāo)記修剪策略的加密圖數(shù)據(jù)精確最短距離外包計(jì)算方案。利用廣度優(yōu)先搜索修剪策略對(duì)原始標(biāo)記進(jìn)行修剪，以減少明文數(shù)據(jù)長(zhǎng)度，提高密文最短距離查詢效率。結(jié)合安全的密碼原語隱藏圖數(shù)據(jù)的結(jié)構(gòu)信息，減少圖數(shù)據(jù)泄露信息，提高方案的安全性。實(shí)驗(yàn)結(jié)果表明，所提方案在半誠(chéng)實(shí)假設(shè)下同時(shí)滿足隨機(jī)預(yù)言模型下的IND-CPA 安全和(L1,L2)安全，大幅降低了加密時(shí)間開銷和最短距離查詢時(shí)間開銷。本文方案的時(shí)間開銷相比文獻(xiàn)［22］方案降低了13.04%以上，最短距離查詢時(shí)間開銷相比文獻(xiàn)［25］方案降低了36.44%以上。下一步將研究惡意模型下的圖數(shù)據(jù)外包計(jì)算及其可驗(yàn)證性問題，即在假設(shè)云服務(wù)器為惡意狀態(tài)的前提下，保證返回結(jié)果的正確性可驗(yàn)證。