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

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

0 概述

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

為了解決上述問題，學術(shù)界不斷探索新的解決方案，如k-匿名［4］、差分隱私［5］、加密算法［6-7］、安全多方計算［8-9］等圖數(shù)據(jù)隱私保護方法?，F(xiàn)有的各類圖數(shù)據(jù)隱私保護方法中，基于密碼算法與協(xié)議的方法能夠嚴格保護圖數(shù)據(jù)信息且不改變圖數(shù)據(jù)的原有結(jié)構(gòu)特征，故該類方法在面向圖數(shù)據(jù)結(jié)構(gòu)特征計算的外包服務場景中［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ù)分析等眾多查詢服務中均有廣泛的應用。由于對圖數(shù)據(jù)安全的緊迫需求，基于加密圖數(shù)據(jù)的最短距離查詢外包計算在實際應用中有廣泛的需求，其主要過程為：圖數(shù)據(jù)所有者在本地加密其持有的原始圖數(shù)據(jù)集，并將加密后的圖數(shù)據(jù)外包給云服務提供商；云服務提供商向圖數(shù)據(jù)查詢請求者（數(shù)據(jù)所有者或查詢請求用戶）提供基于密文圖數(shù)據(jù)的最短距離查詢外包服務；查詢請求者對查詢請求加密后提交給云服務提供商；云服務提供商對密文查詢請求進行計算處理，并返回密文計算結(jié)果；查詢請求者對收到的密文查詢結(jié)果解密，得到明文結(jié)果。該方法一方面憑借云服務提供商強大的存儲和計算能力解決數(shù)據(jù)擁有者的本地計算資源問題；另一方面利用加密的方法對原始圖數(shù)據(jù)和查詢請求進行保護，保證圖數(shù)據(jù)的節(jié)點隱私、邊隱私和用戶查詢請求隱私。

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

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

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

1 相關(guān)工作

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

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

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

2 基本定義

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

2.1 符號定義

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

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

表1 符號及其描述 Table 1 Symbols and their descriptions

2.2 相關(guān)知識

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

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

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

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

該實例的具體計算過程如下：

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

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

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

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

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

3.1 系統(tǒng)模型

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

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

圖2 中每個實體的描述如下：

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

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

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

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

3.2 形式化定義

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

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

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

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

τs,t←TokenGen(K,q)：查詢請求者執(zhí)行查詢令牌生成算法，根據(jù)查詢請求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)計算密文最短距離Ds,t。

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

3.3 安全定義

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

RealC,A(λ)：敵手A構(gòu)造一個圖G并將其轉(zhuǎn)發(fā)給C。C首先對圖G進行預處理，基于二跳覆蓋生成原始標記并對其修剪計算，生成標記集合{L(v)}v?G；然后，執(zhí)行密鑰生成算法(K,pk,sk)←KeyGen(λ)；最后，執(zhí)行加密算法I←Encrypt(K,pk,{L(v)}v?G)，對標記集合中的節(jié)點和距離加密，得到一個安全索引結(jié)構(gòu)I并返回給A。A自適應發(fā)出最短距離查詢請求q=(s,t)，A首先計算該請求的查詢令牌τ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并將其轉(zhuǎn)發(fā)給C。C將泄露函數(shù)L1(G)的輸出轉(zhuǎn)發(fā)給模擬器S，S模擬一個安全的索引結(jié)構(gòu)I*返回給A。給定I*，A自適應地發(fā)出最短距離查詢。對于每個最短距離查詢q=(s,t)，C將泄漏函數(shù)L2(G,q)的輸出發(fā)送給S，S模擬生成相應的查詢令牌發(fā)送給A。A計算密文最短距離，得到結(jié)果并返 回b←{0,1}作為游戲輸出。

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

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

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

4 方案設(shè)計

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

4.1 預處理階段

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

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

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

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

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

算法1prunedBFS

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

4.2 加密階段

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

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

算法2KeyGen

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

具體標記加密如算法3 所示。

算法3Encrypt

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

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

4.3 最短距離查詢階段

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

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

4.3.1 查詢令牌生成算法

算法4TokenGen

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

4.3.2 距離查詢算法

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

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

算法5DistQuery

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

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

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

4.3.3 安全比較協(xié)議

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

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

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

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

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

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

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

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

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

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

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

5 安全分析

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

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

證明：

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

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

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

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

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

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

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

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

證明：

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

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

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

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

6 實驗結(jié)果與分析

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

6.1 方案分析與對比

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

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

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

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

6.2 結(jié)果與分析

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

6.2.1 實驗設(shè)置

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

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

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

6.2.2 實驗結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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