結構化加密圖數據的Top-H 跳節點查詢*

胡夢迪, 陳蘭香

福建師范大學 計算機與網絡空間安全學院 福建省網絡安全與密碼技術重點實驗室, 福州350117

1 引言

隨著互聯網的飛速發展, 不同類型的數據已經應用于各個領域, 為了節約對大規模數據的管理成本,越來越多的用戶選擇將數據外包到第三方云服務器[1,2].隨著數據外包的不斷發展, 數據加密和密文檢索的研究得到了極大的關注.近年來, 研究者在可搜索對稱加密研究領域取得了極大的進展.Song 等人[3]首次引入可搜索對稱加密(searchable symmetric encryption, SSE) 的概念, 并構建了第一個SSE 方案.該方案的思想主要是對文檔的每個關鍵字進行特殊的兩層加密, 然后存儲在云服務器, 云服務器接收陷門并對每個關鍵字執行順序掃描.此后可搜索對稱加密還擴展到多關鍵字搜索[4,5]、動態關鍵字搜索[6–8]及范圍搜索[9]等.然而, 這些搜索方案大多針對文本類型的數據.

2010 年, Kamara 等人[10]提出結構化加密(structured encryption, STE) 的概念, 可以實現各種類型數據的高效查詢, 包括文本、矩陣及圖數據等.同時, Kamara 等人[10]提出可鏈接性(chainability) 的思想, 主要用于多種數據類型之間建立關聯.在一個可鏈接的結構化加密方案中, 半私密項yi和數據項zi是相關聯的, 即查詢操作返回指針j和半私密項yi.通過半私密項yi可以將兩種復雜數據結構建立關聯.但是當前的結構化加密方案只能實現鄰居節點的查詢, 不能實現多跳節點查詢.因此, 本文基于結構化加密中可鏈接的思想, 提出了第一個結構化加密圖數據的top-H跳節點查詢方案, 從而實現鄰居節點的迭代查詢.

首先, 本文定義了外包圖上的隱私保護top-H跳節點查詢問題, 即給定一個無向圖和一個待查詢節點v, 返回距離查詢節點v的H跳內的所有節點.其次, 為了支持隱私保護top-H跳節點查詢, 本文利用結構化加密思想, 構建鄰居索引表, 并使用對稱加密方案和偽隨機函數進行加密, 生成特殊的安全索引.最后, 針對構建的索引設計了一種用于top-H跳節點查詢的算法.本文的貢獻如下:

(1) 提出第一個結構化加密圖數據的top-H跳節點查詢方案.利用結構化加密的可鏈接性, 設計特殊的安全索引, 實現鄰居節點的迭代查詢.

(2) 對結構化加密圖數據的top-H跳節點查詢方案構建安全模型, 并進行安全性分析.

(3) 在真實數據集上進行測試, 對存儲開銷、時間開銷和查詢效率進行比對, 結果表明, 本方案安全性強, 查詢效率高.

本文的組織結構如下: 第2 節介紹可搜索對稱加密和結構化加密的相關工作;第3 節介紹系統模型、泄露函數及安全模型; 第4 節是符號定義和top-H跳節點查詢方案模型; 第5 節介紹方案的算法以及安全性分析; 第6 節通過實驗對本方案進行評估; 第7 節總結全文.

2 相關工作

隨著網絡的飛速發展, 云計算憑借其海量資源、動態擴展等優勢成為學者研究重點.用戶可以將大規模數據外包給云服務器, 以節約管理成本和存儲空間.然而, 數據外包使得數據所有權和數據管理權分離,從而帶來新的數據安全問題.為保護數據安全, 數據擁有者在外包數據之前對數據加密.但是, 傳統的數據加密技術使得密文檢索耗費大量的通信開銷和本地計算開銷.因此, 如何對加密數據執行高效檢索仍是一個具有挑戰性的工作.

可搜索對稱加密2000 年, Song 等人[3]首次提出可搜索對稱加密的概念, 并構造了第一個SSE 方案SWP.該方案的基本思想是: 數據擁有者對文檔中的每個關鍵字采用特殊的兩層加密, 然后將加密的文檔集合存儲在云端.數據擁有者對查詢的關鍵字生成特定陷門并發送給云服務器, 云服務器接收陷門并對密文文檔集合執行順序掃描.但是這種方案需要云服務器對每個文檔的關鍵字進行檢索, 從而使得檢索效率很低.為了提高檢索效率, 2003 年, Goh 等人[11]提出新的SSE 方案.該方案的思想是為每個文檔構建一個布隆過濾器, 并將關鍵字插入其中.當數據擁有者需要檢索時, 服務器只需對布隆過濾器進行檢索,判斷關鍵字是否存在, 從而提高檢索效率.2006 年, Curtmola 等人[12]提出了基于倒排索引的SSE 方案.他們首先構建倒排索引來存儲從關鍵字到包含關鍵字的相應文檔集合的映射, 然后服務器利用檢索陷門定位到匹配項, 最后返回對應的文檔集合.2014 年, Cash 等人[13]設計并構建了一個動態的SSE 方案.近幾年隨著研究者對可搜索對稱加密的深入研究, 大量的SSE 方案被提出來.2020 年, Wang 等人[14]對當前可搜索加密方案進行了詳細的分析, 包括多關鍵字搜索[4,5]和范圍搜索[9]等方案.2022 年, Liu 等人[15]為了能夠支持形式多樣化的密文搜索, 提出了復雜語義可搜索加密方案, 該方案基于一種新的關鍵字特征提取方式, 將通配符可搜索加密轉化為一般的多關鍵詞可搜索加密.然而上述方案大多只針對于文本類型的數據, 并不適用于現實世界中的社交網絡、線路規劃及社區查找等數據類型.

結構化加密 2010 年, Kamara 等人[10]引入結構化加密的概念, 同時還提出了對加密圖執行保密查詢的圖加密方案,例如: 鄰居、鄰接查詢和聚焦子圖查詢.他們將圖結構的數據視為一種數據結構δ和數據項z={z1,z2,···,zn}, 然后將結構化數據(δ,z) 加密后得到數據結構γ和密文序列c=(c1,c2,···,cn)并存儲云端.用戶使用私鑰, 可以為任何查詢構造令牌τ, 云服務器根據令牌從γ和τ恢復指向(zi)i∈I(I ∈[1,n]) 的指針, 返回密文ci.2011 年, Cao 等人[16]提出在加密圖上實現隱私保護的查詢方案, 該方案支持加密域中的內積計算.2017 年, Liu 等人[17]提出了一種top-K最近鄰關鍵字搜索的圖加密方案.2018 年, Liu 等人[18]提出了一種基于2HCL 索引的圖加密方案, 用于查詢存儲在遠端云服務器圖上的最短距離.2018 年, Shen 等人[19]提出了近似最短距離查詢圖加密方案, 該方案結合了同態加密和基于順序顯示加密的基于樹的密文比較協議.2021 年, Sun 等人[20]進一步提出在加密圖上執行約束top-K最近關鍵字查詢方案, 該方案利用2HCL 構建新的索引來計算約束最短距離, 同時還支持模糊關鍵字查詢.2022 年, Yang 等人[21]為了實現對加密社交網絡圖的計算和統計分析, 提出了結構化加密的PSI 方案STE_max-PSI.該方案通過引入混亂布隆過濾器, 在確保數據隱私的前提下, 實現了更復雜數據結構的更加豐富的查詢功能.2022 年, Wang 等人[22]提出top-K社交空間關鍵字搜索圖加密方案.2022 年, Ge等人[23]為了實現搜索模式隱私, 提出了基于兩個非共謀云服務器的加密圖的近似最短距離查詢圖加密方案.本文在結構化加密的基礎上, 第一個提出基于結構化加密圖數據top-H跳節點查詢方案.該方案以結構化加密可鏈接思想構建特殊安全索引, 通過迭代查詢實現H跳節點查詢.

3 系統模型

3.1 系統模型

系統模型包括三個實體: 數據擁有者、云服務器和數據使用者, 如圖1 所示.數據擁有者擁有一個社交網絡圖G, 同時授權數據使用者以執行top-H跳節點查詢.云服務器具有強大的計算資源和充足的存儲空間, 用于提供top-H跳節點查詢服務.云服務器接收到用戶的查詢請求后, 對外包的數據集執行查詢并將查詢結果返回給用戶.數據使用者在獲得授權后, 向云服務器發送top-H跳節點查詢令牌.

圖1 系統模型Figure 1 System model

Top-H跳節點查詢方案主要包括六個步驟, 可以定義為六元組Π = (GenKey, BuildIndex, Encrypt,Token, Query, Decrypt), 具體描述如下:

(1) GenKey(λ)→K: 數據擁有者輸入安全參數λ, 輸出密鑰K={K1,K2,K3}, 其中K1和K3用于加密鄰居節點索引N,K2用于加密節點標識符.

(2) BuildIndex(G)→N: 構建鄰居節點表.數據擁有者對圖G中每個節點提取鄰居節點并生成鄰居節點索引表N.

(3) Encrypt(K,N)→I: 加密鄰居節點表.數據擁有者使用偽隨機函數f和g加密鄰居節點表N,生成安全索引I.

(4) Token(K,H,v)→τ: 數據使用者向數據擁有者發出查詢請求、跳數H和節點v, 數據擁有者返回查詢令牌τ=(gK1(v),fK3(v),H).

(5) Query(I,τ)→R: 檢索并返回結果.數據使用者將令牌τ發送給云服務器, 云服務器得到令牌τ后, 通過對安全索引I查詢, 找到最終的密文集R并返回給數據使用者.

(6) Decrypt(K2,R)→v: 解密密文.數據使用者收到云服務器返回的密文集合R, 使用密鑰K2對其進行解密.

3.2 泄露函數

針對top-H跳圖加密方案, 我們給出兩個泄露函數Lsetup(G) 和Lquery(G,q).具體定義如下:

-Lsetup(G): 主要是在設置階段, 表示敵手A可以從安全索引I中學到的信息.從安全索引I中,A可以學習到節點的數n, 最大集合I(v) 的大小|I(v)| 信息.即Lsetup(G)={n,|I(v)|}.

-Lquery(G,q): 主要由查詢模式和交集模式組成, 即Lquery(G,q)=QP(v)+IP(v).

· 查詢模式QP(v): 給定一系列的top-H查詢, 敵手A可以通過檢查兩次查詢是否包含相同的令牌了解查詢的節點是否已經被先前查詢過.

· 交集模式IP(v): 從top-H查詢的結果中, 敵手A可以得知兩個查詢結果是否包含相同的節點信息.

3.3 安全模型

本文方案采用自適應選擇查詢攻擊(adaption chosen query attacks, CQA2[10]) 安全模型進行安全性分析.在CQA2 安全模型中, 敵手A適應性地進行詢問.

定義1 (CQA2 安全模型) 給定一個top-H跳圖加密方案Π = (GenKey, BuildIndex, Encrypt,Token, Query, Decrypt), 一個安全參數λ、一個敵手A和一個模擬器S, 其中泄露函數為Lsetup和Lquery, 定義游戲Real 和Ideal 如下所示:

- RealA(λ):A首先生成一個圖G.挑戰者分別運行K ←GenKey(λ) 和I ←Encrypt(K,N) 生成密鑰K和安全索引I.給定安全索引I, 敵手A自適應地發出查詢.對于每一個查詢(H,v), 挑戰者通過T ←Token(K,H,v) 生成并發送給敵手A.最后, 敵手A輸出一個bit 位b ∈{0,1}作為游戲的輸出.

- IdealA,S(λ): 敵手A生成一個圖G.模擬器S根據泄露函數Lsetup(G) 生成安全索引結構I?.給定安全索引I?, 敵手A自適應地發出查詢.對于每一個查詢q, 模擬器S根據挑戰者提供的Lquery(G,q) 模擬的一個令牌T?并發送給敵手A.最后, 敵手A輸出一個bit 位b ∈{0,1}作為游戲的輸出.

如果對于所有多項式時間的敵手A, 總存在一個多項式時間模擬器S滿足公式(1):

那么該圖加密方案自適應選擇查詢攻擊(CQA2) 安全的, 其中negl 是一個可忽略函數.

4 預備知識

4.1 符號定義

本文符號定義如表1 所示, 文中使用的幾個函數定義如下.

表1 符號定義Table 1 Symbol definition

偽隨機函數fK3和偽隨機函數gK1如公式(2)所示:

生成密鑰的偽隨機函數P如公式(3)所示:

對稱密鑰加密(symmetric-key encryption, SKE) 方案由加密算法SKE.Enc 和解密算法SKE.Dec組成.

- SKE.Enc(K2,v)→c: 是一種概率算法, 輸入密鑰K2和節點v, 返回密文c, 表示為EncK2(v);

- SKE.Dec(K2,c)→v: SKE.Dec 是一種確定性算法, 輸入密鑰K2和密文c, 返回節點v, 表示為DecK2(c).

4.2 Top-H 跳模型

在top-H模型中, 我們使用字典和集合數據結構.其中集合Lv存儲社交網絡節點v的所有鄰居節點, 字典則用于存儲節點v和鄰居節點集合Lv的映射.圖2 給出了一個具體的例子.圖2(a) 是一個含有7 個節點的社交網絡圖.圖2(b) 是由BuildIndex 算法構建的一個字典N.BuildIndex 通過廣度優先算法遍歷每一個節點v的鄰居節點并將其添加到集合Lv中, 然后將(v,Lv) 添加到字典N中, 直至所有節點遍歷結束.

圖2 示例圖Figure 2 Example graph

加密字典N如表2 所示.使用偽隨機函數g和密鑰K1對字典N的索引入口加密, 例如: 對索引入口v加密得到gK1(v); 對于節點v的每一個鄰居節點(ui) 構建一個三元組(EncK2(ui),αvui,βvui),并存儲在集合L?v中.其中EncK2(ui) 表示使用對稱加密方案SKE 和密鑰K2對節點ui加密;αvui=gK1(ui)⊕fK3(v), 表示使用偽隨機函數f和密鑰K3對節點v加密后的結果和加密的節點ui的索引入口異或;βvui=fK3(v)⊕fK3(ui) 表示使用偽隨機函數f和密鑰K3分別對節點v和ui加密后的結果異或.這樣構造的好處是, 可以通過輸入的令牌τ= (gK1(v),fK3(v),H), 在查詢過程中計算出隱藏的鄰居節點索引入口, 從而生成新的令牌以執行下一跳查詢.對每個節點的鄰居節點執行上述加密方案.但由于每個節點的鄰居節點個數并不一樣多, 最后需要對加密后的鄰居集合L?v進行填充, 使其大小相同.

表2 加密索引表Table 2 Encrypted index

如果想要檢索節點v的H跳節點, 具體步驟如下:

(1) 首先生成一個令牌τ=(gK1(v),fK3(v),H) 并發送到云服務器;

(2) 云服務器接收到之后, 按照預先設定的算法執行檢索.云服務器首先從令牌中讀取gK1(v),找到索引表的索引入口, 從而獲取節點v的鄰居節點集合L?v.云服務器從鄰居節點集合L?v中, 依次獲得節點v的鄰居節點密文信息, 并存放在集合R中, 假設獲取的節點信息為R={EncK2(u1),EncK2(u2),···,EncK2(ut)};

(3) 對于每一個ui, 利用τ中的fK3(v), 計算gK1(ui)=αvui ⊕fK3(v) 和fK3(ui)=βvui ⊕fK3(v),得到節點ui的τui=(gK1(ui),fK3(ui),H ?1);

(4) 利用每個ui的令牌τui進一步查詢節點v的第二跳鄰居節點, 過濾掉已查詢的節點, 將未查詢的節點添加到集合R中;

(5) 按照上述迭代式的查詢下一跳節點直至查詢到H跳為止;

(6) 最后云服務器返回最終結果集R.

5 Top-H 跳查詢方案

5.1 算法描述

本文提出的基于結構化加密圖數據的top-H跳節點查詢方案包括六個算法: (GenKey, BuildIndex,Encrypt, Token, Query, Decrypt), 其中三個算法(GenKey, BuildIndex, Encrypt) 由數據擁有者負責執行, Query 由云服務器執行, Decrypt 由授權的數據使用者執行, 具體步驟及算法描述如下:

5.1.1 GenKey(1λ)→K

數據擁有者進行初始化, 生成密鑰, 具體見算法1.數據擁有者輸入安全參數λ, 輸出密鑰集合K={K1,K2,K3}.其中K1偽隨機函數g的密鑰,K2是對稱加密方案SKE 的密鑰,K3是偽隨機函數f的密鑰.

算法1 GenKey(1λ)→K Input: A security parameter λ Output: K = {K1,K2,K3}1 for each i ∈[1,3] do 2 Ki ←?Pk1(λ);3 end 4 Output K = {K1,K2,K3}.

5.1.2 BuildIndex(G)→N

數據擁有者利用廣度優先遍歷算法遍歷每個節點v的鄰居節點并存放于集合Lv中, 然后以鍵值對(v,Lv) 的形式存儲于鄰居節點表N中.詳細過程見算法2.

算法2 BuildIndex(G)→N Input: A graph G Output: A neighbor index N 1 Parse G as (V,E);2 Initialize a dictionary N;3 for each v ∈V do 4 Let Lv be a set of vertices which are neighbor to v;5 N(v) ←Lv;6 end 7 Output N.

5.1.3 Encrypt(K,N)→I

數據擁有者輸入密鑰集合K和鄰居節點表N, 生成安全索引I, 詳細算法見算法3.第10 行表示對加密后的鄰居節點集合L?v進行填充, 使其具有相同長度.其中max|L?v|表示填充后的長度.

算法3 Encrypt(K,N)→I Input: A neighbor index N and key K Output: An encrypted neighbor index I 1 Initialize a dictionary I;2 for each v ∈V do 5 αuv = gK1(u)⊕fK3(v);3 Initialize a set L?v;4 for each u ∈Lv do 6 βuv = fK3(u)⊕fK3(v);7 Encu =Enc(K2,u);L?v ←(Encu,αvu,βvu);9 end 10 Pad L?v to max|L?v|;11 I(gK1(v)) ←L?v;12 end 13 Output I.8

5.1.4 Token(K,H,v)→τ

數據使用者向數據擁有者發送要檢索的查詢節點v和查詢跳數H, 數據擁有者返回令牌τ:=(gK1(v),fK3(v),H) , 然后數據使用者發送令牌到云服務器進行檢索, 詳細過程見算法4.

算法4 Token(K,v,H)→τ :=(gK1(v),fK3(v),H)Input: K,v,H Output: τ 1 gK1(v) ←g(K1,v);2 fK3(v) ←f(K3,v);3 Output τ := (gK1(v),fK3(v),H).

5.1.5 Query(I,τ)→R

云服務器接收到用戶的查詢令牌后, 從查詢令牌中讀取gK1(v), 找到節點v的索引入口, 獲得鄰居節點集合L?v.對于集合L?v中的每個節點u使用τ中的fK3(v) 計算:gK1(u) =αvu ⊕fK3(v) 和fK3(u)=βvu ⊕fK3(v); 進而得到節點u的令牌τu=(gK1(u),fK3(u),H ?1), 然后利用每個節點的令牌τu進行迭代式下一跳查詢, 直至H跳為止, 最后將結果集R返回給用戶.詳細過程見算法5.

算法5 Query(I,τ)→R Input: A query token τ and an index structure I Output: An encrypted result set R 1 Parse τ as (gK1(v),fk3(v),H);2 Initialize set R, A;3 Initialize a Queue Q;4 Initialize a countl = 1, countr = 0;5 Add gK1(v) into Q, add (gK1(v),fK3(v)) into A;6 for each i ∈[1,H] do 7 while Q ?= ?do 8 Parse the queue header element as v′;9 for (encu,αv′u,βv′u) ∈L?v′ do 10 gK1(u) = αv′u ⊕fK3(v′);11 fK3(u) = βv′u ⊕fK3(v′);12 if ((gK1(u),fK3(u)) ?∈A) then 13 add (gK1(u),fK3(u)) into A;14 countr++;15 R ←encu;16 end 17 end 18 v′ ←Q 19 end 20 for i ∈[countl,countr] do 21 Q ←A[i]22 end 23 end 24 Output R.

5.1.6 Decrypt(K2,R)→v

數據使用者收到云服務器返回的加密結果集R后, 使用數據擁有者授權的密鑰K2進行解密, 得到明文下的數據.具體見算法6.

算法6 Decrypt(K2,R)→v Input: K2,R Output: v 1 Compute v = DecK2(R);2 Output v.

5.2 安全性分析

在本方案中, 云服務器被認為是“誠實但好奇” 的, 云服務器會正確地執行檢索任務并返回查詢結果.但是在此過程中,云服務器會對敏感數據感到好奇.根據定義1 中的泄露函數和安全模型,我們將對top-H跳查詢的圖加密方案安全性進行分析.

在一個可鏈接的結構化加密方案中, 我們需要對其附加兩個屬性, 即半私密結構獨立性和順序獨立性.半私密結構獨立性要求加密數據結構和密文所揭示的信息只能依賴于保密數據項, 而不依賴于半私密數據.順序獨立性確保以不同順序執行查詢不會更改泄露信息, 這是因為在可鏈接的結構化加密方案會預先計算子令牌并存儲在半私密數據項中, 當對復雜數據結構進行查詢時, 這些子令牌會以不同的順序顯示出來.將這兩種屬性詳細定義如下:

定義2 可鏈接性(Chainability): 一個結構化加密方案的泄露函數(Lsetup,Lquery) 針對自適應選擇查詢攻擊是安全的, 則該結構化加密方案是可鏈接的, 并且泄露函數滿足以下屬性:

半私密結構獨立性: 存在泄露函數L′setup滿足公式(4).其中,z為保密數據項集合,y為半私密數據項集合.

順序獨立性: 存在一個轉換T, 使得對于任何數據結構G、任何一系列查詢q1,q2,···,qt和任何隨機排列p滿足公式(5):

如果本文top-H跳節點查詢方案是一種可鏈接的結構化加密方案, 且滿足公式(6)–(7):

其中,n表示節點個數,|I(v)| 表示索引表中最大索引項大小, QP(v) 表示當前查詢節點是否已經被查詢過, IP(v) 表示何時那些相同的密文數據項被訪問過, QP(i) 表示I(v) 的第i個節點是否出現在先前查詢中, IP(i) 表示I(v) 的第i個節點的鄰居節點是否為當前或先前查詢的節點的鄰居節點.那么本文的方案針對自適應選擇查詢攻擊是(Lsetup,Lquery) 安全的.

定理1 本文提出的top-H圖加密方案滿足CQA2 安全性.

證明: 首先構造一個模擬器S, 給定泄露函數Lsetup和Lquery,S構建一個偽造的加密索引I?和一個大小為x的查詢列表q?.如果對于所有多項式時間的敵手A都無法區分Real 和Ideal 兩個游戲, 那么本文的top-H圖加密方案是(Lsetup,Lquery)-針對自適應選擇查詢攻擊安全的.其中,A為敵手,S為模擬器,B為挑戰者.

Game0: 該游戲執行真實實驗RealA(λ).首先, 挑戰者B通過GenKey(λ) 生成密鑰K={K1,K2,K3}; 然后, 敵手A輸出數據(G,N) 并接受挑戰者B通過Encrypt(N) 生成的安全索引I.敵手A自適應的輸出查詢并且對于每一個查詢敵手A接收令牌τv ←Token(K,H,v).最后, 敵手A返回游戲輸出一個比特位b.

Game1: 首先, 挑戰者B通過GenKey(λ) 生成密鑰K={K1,K2,K3}; 然后, 敵手A輸出數據(G,N) 并接收模擬器S通過泄露函數Lsetup(G,N) 生成的索引I?.對于每個節點v的查詢令牌τ計算如下: 使用R(v) 表示節點v的鄰居節點集,yv:= (τi)i∈R(v)表示節點v的鄰居節點的半私密數據項集合, 敵手A接收τv ←S(Lquery(G,I?,v,H),yv).最后, 敵手A返回游戲輸出一個比特位b.

在Game1中, 給定泄露函數Lsetup(G,N) , 模擬器S生成密鑰K2←GenKey(1λ), 構造一個包含n個隨機對(k,s) 的索引字典I?, 并計算密文c=(EncK2(v1),EncK2(v2),···,EncK2(vn)).對于每一個查詢(v,H), 模擬器會收到(Lquery(G,I?,v,H),yv).使用Lquery(G,I?,v,H) 的查詢模式來確定查詢是否為新的.如果不是, 則返回之前生成的相同的令牌, 否則就考慮兩種情況.如果|I?(v)|=0, 則隨機選擇未存儲在I?中的搜索節點k和隨機值t, 并輸出令牌τ= (t,k,H).否則就使用交叉模式來確定當前查詢訪問的位置之前是否被訪問過.如果沒有, 就將其設置為未使用的隨機值, 否則, 就將其設置為先前選擇的值.然后, 隨機選擇I?中尚未使用的搜索節點k, 將s表示為(s1,s2), 計算并返回令牌τ= (t,k,H),其中t=yv ⊕s2,s是I?中與k相關的值.

對于k的每一個隨機選擇都將與偽隨機函數g的輸出無法區分.由于表I?中的所有值s都是隨機選擇的, 因此t=yv ⊕s2將是隨機分布的, 因此偽隨機函數f的輸出是不可區分的.因為敵手不能區分偽隨機函數g、偽隨機函數f和真正的隨機數, 所以Game0和Game1是不可區分的.

Game2: 與Game1相似, 區別在于對τ的計算, Game2只有在需要時才計算.對于每一個節點v,τ的計算如下:

(1) 對于所有的i ∈R(v),τi=(αij,βij)j∈|I(v)|,i∈R(v),αij=gK1(j)⊕fK3(i),βij=fK3(j)⊕fK3(i);

(2)τv ←S(Lquery(G,I?,v,H),yv),yv:=(τi)i∈R(v).

因為令牌的產生是無狀態的, 所以Game1等價于Game2.

Game3: 與Game2相似, 只是Lsetup(G,N) 和Lquery((G,I?,v,H),yv) 是直接提供的而不是通過(G,N,v,H) 計算得到的.

由上述分析得知, Game3相當于模擬器S執行IdealA,S(λ).可以得出Game2和Game3的輸出分布是相同的, 他們是不可區分的.

通過上述分析, 本文方案除了會泄露當前查詢的節點之前是否查詢過, 那些密文何時被再次訪問、節點是否出現在先前的查詢過程中以及訪問節點的鄰居節點是否為當前或先前查詢的節點的鄰居節點, 沒有額外的泄露.本方案滿足公式(7), 所以針對自適應選擇查詢攻擊是Lquery安全的.

另外, 在本方案中, 云服務器僅知道加密的數據結構I、查詢令牌t和查詢過程中的半私密數據項y.因此, 云服務器可以在本方案模型中進行唯密文攻擊(ciphertext only attack, COA).在本方案中, 采用密鑰K2和對稱密鑰加密方案SKE 對節點標識符進行加密, 并存儲在云服務器端.因為密鑰是由數據擁有者管理, 且可以授權給數據使用者, 而云服務器不保護加密的密文, 所以概率多項式時間敵手A不能以超過1/2 的概率區分一個密文是對哪個節點標識符加密得到的.敵手A對節點v進行H跳查詢, 可以獲得節點v的最大鄰居節點數|I(v)|.通過對所有H跳查詢結果的統計可以獲取節點個數n, 其滿足公式(6).因此, 本文提出的方案對自適應選擇查詢攻擊是Lsetup安全的.

對于所有多項式時間的敵手A都無法區分Real 和Ideal 兩個游戲.如公式(8)所示:

綜上所述, 本文的top-H圖加密方案針對自適應選擇查詢攻擊是(Lsetup,Lquery) 安全的.

6 實驗評估

本節評估所提出的圖加密方案的性能.實驗環境為一臺Intel(R) Core(TM) i5-8300H CPU @2.30 GHz 和8.00 GB RAM 的Windows 機器.PRF 和SKE 是使用安全參數λ= 128 的PyCrypto 實現,字典則使用Python 的字典數據結構實現.實驗數據集使用來自斯坦福網絡分析項目(SNAP) 的真實世界圖形數據集.本文使用Facebook 社交網絡數據集, 其中每個節點表示一個人, 而每條邊表示兩個節點之間的朋友關系.數據集詳細信息如表3 所示.

表3 數據集Table 3 Data set

6.1 復雜度分析

本小節主要分析top-H節點查詢圖加密方案的空間復雜度和時間復雜度.在一個含有n個節點的圖G中,I表示構建的安全索引,|I(v)|表示安全索引I中最大索引項大小,m表示邊數.在top-H節點查詢圖加密方案中, 安全索引I為主要存儲開銷.因此, 空間復雜度為O(n×m).對于時間復雜度, 主要包括生成令牌和執行檢索.算法Token 用于生成令牌,其時間復雜度為O(1).算法Query 用于執行檢索,對于每一個查詢令牌τ:= (gK1(v),fK3(v),H), 云服務器需要對每個節點的鄰居節點迭代H次.假設,H跳以內的節點數為n, 執行檢索的時間復雜度為O(n×(1+|I(v)|)), 總的時間復雜度為O(n×(1+|I(v)|)).

本文是第一個提出結構化加密圖數據的top-H跳節點查詢方案, 同時將本方案與相近且具有代表性的圖加密方案進行對比, 具體見表4.其中n表示節點總數,m表示邊的總數,H表示迭代次數,|W| 表示關鍵字總數,|I(v)| 表示安全索引I中最大索引項大小.

表4 方案比較Table 4 Scheme comparison

由表4 可知, 許多top-K方案都選擇以2-Hop 作為基本索引結構, 為每個節點v分配一個標簽, 在標簽中存儲二元組(u,H), 其中u表示節點v可達的頂點,H表示u和v之間的跳數.然而, 這種索引結構存在一定的不足, 包括索引本身和功能性不足.當待處理的節點數量達到十萬或百萬數量級時, 構建2-Hop 索引的初始化時間以及自身存儲開銷會變得很大, 使得在密文檢索過程中計算量增大, 進而極大地降低了密文檢索的效率.在社交網絡中, 用戶節點之間的跳數反映著用戶之間的緊密程度, 限定跳數的節點查詢可以幫助分析用戶社區間的關系等, 而2-Hop 索引結構對于這種查詢存在一定的局限性.而本方案極大地降低了索引的存儲開銷、提高了查詢效率, 同時也實現了限定跳數的節點查詢.

相比于文獻[20,22,24] 的圖加密方案, 本文的top-H跳節點查詢圖加密方案存儲開銷最少, 空間復雜度最優.本方案的時間復雜度是線性函數, 而文獻[20] 和文獻[22] 時間復雜度是指數函數, 所以本文的top-H跳節點查詢圖加密方案的時間復雜度優于二者.

6.2 時間開銷

本文測試了方案生成鄰居索引表和構建安全索引I的時間開銷.為了更直觀地看出時間開銷, 本文計算了構建鄰居索引表和加密索引的時間之和, 時間開銷如圖3 所示.

圖3 不同數據集下構建索引時間Figure 3 Time to build indexes for different datasets

本方案構建安全索引I主要分為兩步.首先, 對社交網絡圖中每一個節點提取其鄰居節點構建鄰居節點表N.然后使用偽隨機函數和對稱密鑰加密方案加密索引表中的元素以生成安全索引I.從方案的構造可以看出, 構建索引的主要影響因素是數據集中邊的數量.因此, 我們用四個不同數據集來評估構建安全索引的時間開銷.為了更直觀地看出時間開銷, 我們計算了構建鄰居索引表和加密索引的時間之和, 時間開銷如圖3 所示.

從圖3 可以看出, 構建索引的時間開銷隨著數據集中邊數的增加而線性增加.這是因為在構建安全索引I過程中, 對于n個節點的圖G, 每個節點的鄰居節點集合大小為|I(v)|,t為構建一個三元組使用偽隨機函數的次數, 則構建安全索引需要執行n×|I(v)|×t次偽隨機函數進行加密.

6.3 存儲開銷

本方案分別計算了鄰居索引表N和安全索引I的存儲開銷.由圖4 可以看出, 存儲開銷主要取決于安全索引I的大小.這是因為在安全索引I中, 每個節點的鄰居節點以三元組(EncK2(u),αvu,βvu) 形式存儲于數組L?v.每個數組填充后的大小為|I(v)|, 節點個數為n, 總存儲為O(n×|I(v)|).當邊數m=20000 時, 所需要的存儲開銷為299.65 MB; 當邊數m= 40000 時, 所需要的存儲開銷為618.19 MB.通過對比可以看出, 存儲開銷隨著邊數的增加而線性增加.

圖4 不同數據集下構建索引開銷Figure 4 Index overhead for different datasets

6.4 查詢效率

對于top-H節點查詢圖加密方案的查詢效率, 本文對不同跳數和不同數據集的查詢時間進行比對.同時, 為了更直觀地展現本方案的查詢效率, 本文還測試了相同數據集和相同跳數H下的明文和密文的查詢時間.對于每個數據集隨機選取100 個節點進行查詢且每個節點重復查詢50 次, 最后以平均值作為實驗評估值.

根據top-H跳節點查詢方案的構造和查詢模式可以看出, 影響top-H跳節點查詢方案效率的因素主要包括兩個方面, 分別為數據集中邊的數量以及查詢跳數H.由圖5 可以看出, 在同一數據集下, 查詢時間隨著查詢跳數H的增加而增加.這是因為隨著跳數H的增大, 所涉及的鄰居節點增多, 在密文檢索過程中, 需要掃描和過濾的頂點增多, 進而使得查詢時間增多.當查詢跳數不變時, 隨著數據集的增大, 節點和邊同樣隨之增多, 進而使得查詢時間增加.

圖5 不同數據集和跳數下的查詢時間Figure 5 Query time for different datasets

從圖6 可以看出, 當數據集和跳數H相同時, 明文和密文的查詢時間差別在幾秒之間.對于明文的查詢可直接對節點進行迭代.但是對于密文的查詢, 需要對密文進行處理, 包括過濾填充信息等.

圖6 明文和密文下的查詢時間Figure 6 Query time for different hops

6.5 小結

通過實驗分析可知, 本文提出的第一個結構化加密圖數據top-H跳節點查詢方案的存儲開銷比文獻[20,22,24] 更優.Top-H跳節點查詢方案的時間復雜度也是最優的.本方案構建的安全索引I的空間復雜度為O(n×m), 查詢時間復雜度為O(n×(1+|I(v)|)).數據集的大小和查詢跳數H的大小影響查詢過程中所涉及的節點和邊, 進而影響查詢效率.同時, 本文還對明文和密文的查詢效率進行了對比, 結果表明在密文下的查詢是高效的.

7 總結

本文提出了第一個結構化加密圖數據的top-H跳節點查詢方案, 可以應用于社交網絡好友查詢等.為了能夠實現更快更多的查詢功能, 本文結合結構化加密可鏈接思想, 設計一個特殊的安全索引.利用特定的迭代查詢算法可以更高效、更安全地執行查詢操作.本文也對top-H跳圖加密方案的安全性進行證明, 同時使用真實世界的圖形數據集對本方案進行了評估測試.在接下來的工作中, 我們將進一步把結構化加密和分布式技術結合.當數據集非常大且查詢跳數H很大時, 本文的迭代算法查詢的效率就會隨之下降,但是如果采用分布式技術來執行top-H跳節點查詢,可以實現更高效的查詢.