林 慶，滕 飛，田 波,趙 越,,祝錦燁,馮 力

(1.西南交通大學(xué)計算機與人工智能學(xué)院,四川 成都 611756;2.保密通信重點實驗室,四川 成都 610041)

1 引言

知識圖譜[1]是智能化數(shù)據(jù)應(yīng)用的核心,其對抽取后的信息數(shù)據(jù)進行關(guān)聯(lián),將信息組織成一個龐大的知識庫,從而賦能數(shù)據(jù)應(yīng)用。近年來,知識圖譜在醫(yī)療、金融及生活服務(wù)等多個領(lǐng)域得到了廣泛的應(yīng)用,在智能搜索、智能問答和大數(shù)據(jù)風(fēng)控等應(yīng)用中發(fā)揮出重要的作用。例如,利用知識圖譜技術(shù)可以在金融領(lǐng)域?qū)崿F(xiàn)反洗錢、識別高危用戶及團伙等功能。這些知識圖譜的構(gòu)建建立在海量數(shù)據(jù)的基礎(chǔ)之上,而這些數(shù)據(jù)中往往有著隱私敏感和多模態(tài)等特性。

知識圖譜的存儲與應(yīng)用需要占用系統(tǒng)大量的存儲和計算資源,將知識圖譜數(shù)據(jù)外包到云服務(wù)器上,是一種節(jié)約資源成本且使資源高效利用的方式。由于云服務(wù)商不是完全可信的,其可以透明地竊取、篡改和泄露云服務(wù)器上的數(shù)據(jù),造成數(shù)據(jù)機密性和完整性的破壞,所以將知識圖譜存儲到云服務(wù)器上有著隱私泄露等安全風(fēng)險[2]。

防止數(shù)據(jù)泄漏的普遍共識是加密,直接對數(shù)據(jù)進行非確定性加密，如AES-CTR(Advanced Encryption Standard-CounTeR)[3]，可以使數(shù)據(jù)具有很高的安全性,但是這將造成加密后的數(shù)據(jù)難以高效地進行操作(如檢索)。因此，密碼學(xué)研究人員開始研究如何在保證數(shù)據(jù)一定安全性的同時使數(shù)據(jù)可以高效地被使用,現(xiàn)在可搜索加密、同態(tài)加密和保序加密等方向有了很大的突破,其中可搜索加密可以使數(shù)據(jù)在密態(tài)條件下被檢索[4]。2000年,Song等人[5]提出了第1個可搜索加密方案,該方案通過輸入關(guān)鍵字可以在服務(wù)器上對密態(tài)文件進行檢索；2012年,Kamara等人[6]首次提出了動態(tài)對稱可搜索加密DSSE(Dynamic Symmetric Searchable Encryption)的概念；2014年,Cash等人[7]提出一種滿足RCPA(Random-ciphertext- secure against Chosen-Plaintext Attack)安全的動態(tài)對稱可搜索加密方案,該方案可高效地搜索百億條記錄關(guān)鍵字對,在方案設(shè)計上對本文有很大的參考意義。

現(xiàn)在已有較為成熟的關(guān)系型數(shù)據(jù)庫加密方案如CryptDB[8]和Blind Seer[9]等,通過使用可搜索加密、同態(tài)加密等加密模型,可在密態(tài)條件下對關(guān)系型數(shù)據(jù)庫進行有限的SQL操作。將知識圖譜存儲在關(guān)系型數(shù)據(jù)庫上也是目前常用的一種方式[10],但是有許多關(guān)系型數(shù)據(jù)庫加密方案不支持連接操作,而且密態(tài)條件下的連接操作是一個非常耗時的操作。由于知識圖譜中有大量的多對多的關(guān)系,當使用關(guān)系型的數(shù)據(jù)模型來存儲、管理知識圖譜時,在查詢、檢索等操作上將需要大量的連接操作,所以使用關(guān)系型數(shù)據(jù)庫加密方案并不適用于知識圖譜的加密存儲。

針對知識圖譜在云服務(wù)器上存儲所面臨的問題,本文提出了一種基于可搜索加密的密態(tài)知識圖譜EKG(Encrypted Knowledge Graph)存儲方案,該方案支持知識圖譜實體的一跳子圖查詢,主要工作如下所示：

(1) 提出了基于可搜索加密的密態(tài)知識圖譜方案,該方案在不失去知識圖譜的檢索能力的前提下,為知識圖譜提供機密性和完整性保護,通過使用密鑰生成陷門的機制,也使得該方案有一定的身份認證能力。

(2) 考慮知識圖譜中實體和其關(guān)系的關(guān)聯(lián)性,對密態(tài)索引進行優(yōu)化,在索引設(shè)計上加強了密態(tài)知識圖譜在磁盤中存儲的局部性,提高了檢索效率。

(3) 提供了一種非密態(tài)知識圖譜方案,該方案是一種知識圖譜的非原生屬性圖存儲方式，其圖譜上的檢索避免了關(guān)系型數(shù)據(jù)庫上大量的連接操作，本文在其基礎(chǔ)之上引入可搜索加密的設(shè)計思想,提出密態(tài)知識圖譜方案。在真實數(shù)據(jù)集上對2個方案分別進行性能測試,并對密態(tài)方案進行安全分析,表明了所提出的加密方案在效率、有效性及安全性上取得了平衡。

2 預(yù)備知識

2.1 知識圖譜數(shù)據(jù)模型

目前,主流的知識圖譜數(shù)據(jù)模型有2種,分別為RDF(Resource Description Framework)圖模型和屬性圖模型[10]。在知識圖譜的存儲管理中,RDF圖模型和屬性圖模型最主要的區(qū)別在于屬性的表達。在RDF圖中,邊可以作為屬性謂詞指向一個屬性值,而所有的屬性值都存儲為節(jié)點,這給知識圖譜上的圖計算帶來了更大的靈活性；在屬性圖中,屬性結(jié)構(gòu)是鍵-值對結(jié)構(gòu),這使得屬性圖在實現(xiàn)上更加簡單。根據(jù)屬性圖的存儲方式可以將屬性圖分為原生屬性圖和非原生屬性圖,原生屬性圖(如Neo4J)最大的特點是具有“無索引鄰接(Index-free Adjacency)”特性,其底層存儲設(shè)計是針對圖數(shù)據(jù)庫定制和優(yōu)化的；而非原生屬性圖(如JanusGraph)使用通用的NoSQL數(shù)據(jù)庫,比如HBase和鍵-值數(shù)據(jù)庫(如RocksDB[11])等。由于屬性圖的簡單特性，以及其與可搜索加密的適配度更高,本文方案中的知識圖譜數(shù)據(jù)模型將采用屬性圖模型。

屬性圖由一組節(jié)點、邊、屬性和標簽表示,數(shù)據(jù)節(jié)點和其邊都用唯一ID命名,并且可以存儲由鍵-值對表示的屬性。屬性圖的形式化定義[10]如定義1所示:

定義1屬性圖G是五元組(V,E,ρ,λ,σ),其中,

(1)V是節(jié)點的有限集合;

(2)E是邊的有限集合;

(3) 函數(shù)ρ:E→(V×V)將邊關(guān)聯(lián)到節(jié)點對,如ρ(e)=(v1,v2)表示e是從節(jié)點v1到節(jié)點v2的有向邊;

(4)設(shè)Lab是標簽集合,函數(shù)λ:(V∪E)→Lab為節(jié)點或邊賦予標簽,如v∈V(或e∈E)且λ(v)=l(或λ(e) =l),則l為節(jié)點v(或邊e)的標簽;

(5)設(shè)Prop是屬性集合,Val是值集合,函數(shù)σ:(V∪E)×Prop→Val為節(jié)點或邊關(guān)聯(lián)屬性,如v∈V(或e∈E)，p∈Prop且σ(v,p)=val(或σ(e,p)=val),則節(jié)點v(或邊e)上屬性p的值為val。

如圖1所示為病例圖譜的屬性圖示例,其中每個節(jié)點和邊都有唯一ID(如節(jié)點v2和邊e3),節(jié)點和邊都具有標簽(如節(jié)點v2上的Guardianship和邊e3上的suffer_from),節(jié)點和邊上均可具有一組屬性,每個屬性由屬性名和屬性值組成(如節(jié)點v2上的屬性name=“Bob”)。

Figure 1 Property graph example:Case knowledge graph圖1 屬性圖示例：病例知識圖譜

2.2 可搜索加密

可搜索加密技術(shù)是搜索技術(shù)和加密技術(shù)的結(jié)合,其可分為對稱可搜索加密SSE(Symmetric Searchable Encryption)和公鑰可搜索加密PEKS(Public-key Encryption with Keyword Searching)[12]。SSE的構(gòu)建方法一般分為基于存儲結(jié)構(gòu)和基于索引2種。基于存儲結(jié)構(gòu)的SSE方案的效率往往比較低,在搜索時需要服務(wù)器對整個加密數(shù)據(jù)集進行線性掃描并依次進行匹配；基于索引的構(gòu)建方法的優(yōu)勢在于不需要特定的加密手段和存儲結(jié)構(gòu),并且在搜索時有很高的效率。Curtmola等人[13]第一次正式定義了基于索引的SSE算法框架,具體如定義2所示：

定義2一個單用戶的 SSE 方案的參與者包含1個用戶和1個服務(wù)器,假設(shè)Δ是關(guān)鍵字字典,D? 2Δ是文件集合,用戶希望將文件集合D存儲于服務(wù)器上,并且服務(wù)器可以提供對字典Δ的搜索服務(wù),基于索引的對稱可搜索加密算法SSE=(Gen,Enc,Trpdr,Search,Dec)的定義如下：

(1)K←Gen(1λ)：由用戶運行的一個密鑰生成的概率性算法,以安全參數(shù)λ作為輸入,輸出密鑰K。

(2) (I,c)←Enc(K,D)：由用戶運行的一個概率加密算法,以密鑰K和文件集合D=(D1,…,Dn)作為輸入,生成一個安全索引I和一系列密文集合c=(c1,…,cn)。

(3)t←Trpdr(K,w)：由用戶運行的一個確定性算法,輸入密鑰K和關(guān)鍵字w,輸出一個用于檢索的陷門t。

(4)X←Search(I,t)：由服務(wù)器運行的一個確定性算法,通過索引I和陷門t來查找文件集D中是否含有關(guān)鍵字w的文件,并返回文件標識符的集合X。

(5)D←Dec(K,ci)：由用戶運行的一個確定性算法,根據(jù)X中標識符得到對應(yīng)密文,用密鑰K進行解密輸出最終明文文件。

3 本文方案

本節(jié)將重點介紹密態(tài)知識圖譜EKG方案的構(gòu)建和檢索過程。在介紹該方案之前將先介紹一種非密態(tài)知識圖譜NEKG(Non-Encrypted Knowledge Graph)方案,主要闡述了將知識圖譜數(shù)據(jù)編碼為鍵-值存儲模型的方式,以及在該方式下如何對知識圖譜數(shù)據(jù)進行檢索。該編碼方式使得每個實體和其關(guān)系編碼后的鍵-值數(shù)據(jù)有很好的局部性,在一跳子圖查詢時只需在磁盤中進行順序讀取。EKG方案在NEKG方案的基礎(chǔ)上引入可搜索加密方案思想,該方案支持知識圖譜數(shù)據(jù)的密態(tài)存儲以及一跳子圖查詢。由于對編碼后的鍵值數(shù)據(jù)經(jīng)過加密后,數(shù)據(jù)原有的局部特性會喪失,所以在EKG方案中也考慮了實體和其關(guān)系的存儲局部性。EKG方案引入了pos值,使其在檢索過程中有更高的緩存命中率,從而減少IO次數(shù)。

Figure 2 Key-value storage format for property graph圖2 屬性圖的鍵-值存儲格式

在這2個方案中所實現(xiàn)的檢索方案為一跳子圖查詢,在知識圖譜中,一跳子圖查詢是圖譜查詢的一個核心操作,通過一跳子圖查詢,可以在知識圖譜上進行許多簡單的推理[14]。一跳子圖查詢的定義如定義3所示：

定義3給定一個知識圖譜KG和一個實體標識h,在KG中查詢實體h以及實體h相關(guān)的所有關(guān)系Rh,在查詢的過程中同時返回了實體和關(guān)系的屬性,則稱這個查詢?yōu)橐惶訄D查詢。

本節(jié)在方案描述過程中所使用的符號如表1所示。

Table 1 Description of main symbols

3.1 NEKG方案

在NEKG方案中,知識圖譜通過屬性圖進行數(shù)據(jù)管理,該方式與關(guān)系型組織方式相比,避免了查詢時要用到的大量連接操作。該方案將屬性圖的數(shù)據(jù)編碼成鍵值數(shù)據(jù)并進行持久化存儲,持久化后的鍵值數(shù)據(jù)存儲于鍵-值數(shù)據(jù)庫中的一個分區(qū)中。在屬性圖的存儲中主要的數(shù)據(jù)是節(jié)點和邊,其中節(jié)點可以用來表示知識圖譜上的實體,邊可以用來表示知識圖譜上的關(guān)系。接下來將對NEKG方案中實體/節(jié)點和關(guān)系/邊的鍵-值存儲格式進行介紹。

如圖2所示,在實體/節(jié)點鍵值存儲格式中,VertexNameLength字段為實體名的長度,VertexName為一個獨一無二的實體名稱。在關(guān)系/邊鍵值存儲格式中,鍵的各個字段的含義如表2所示,EdgeType用來表示邊的方向,大于0表示出邊,小于0表示入邊。關(guān)系/邊在鍵值存儲中的值(Value)為其屬性的序列化。實體可以根據(jù)前綴VertexNameLength‖VertexName來匹配與其相關(guān)的關(guān)系。

Figure 3 Example of encrypted key-value storage pattern 圖3 鍵-值存儲模式示例

Table 2 Meaning of each field in edge key format

將圖1中的節(jié)點v1、v3和邊e2轉(zhuǎn)化為鍵-值存儲模式,轉(zhuǎn)化后的格式如圖 3所示。從圖3中可以明顯看到,在NEKG方案中,屬性圖中的每條邊在鍵值存儲中被建模為2個獨立的鍵值對,分別表示出邊和入邊,而這樣的設(shè)計可以通過前綴匹配,找出與節(jié)點相關(guān)聯(lián)的所有邊。

在NEKG方案中,構(gòu)建和檢索知識圖譜非常簡單。在構(gòu)建中,只需要將實體和關(guān)系編碼為鍵-值結(jié)構(gòu),然后直接存儲到鍵值數(shù)據(jù)的一個分區(qū)中。在一跳子圖的檢索中,只需要將檢索實體的標識(如實體名)編碼為鍵-值結(jié)構(gòu)中的鍵,之后通過鍵值數(shù)據(jù)庫提供的前綴匹配功能,可以順序讀取到實體及其所對應(yīng)的所有關(guān)系,由于都有相同的前綴,這個過程中所讀取到的數(shù)據(jù)在磁盤存儲中有很好的局部性。

3.2 EKG方案

可搜索加密方案通過對關(guān)鍵字建立密態(tài)索引,以支持對密態(tài)數(shù)據(jù)的檢索。該思想在密態(tài)知識圖譜的檢索、存儲設(shè)計中有重大的作用,可以將鍵-值數(shù)據(jù)庫中的每個鍵作為關(guān)鍵字建立密態(tài)索引,以此來支持屬性圖模型下的密態(tài)操作。因此,在本文的EKG方案中使用基于鍵-值數(shù)據(jù)庫的非原生屬性圖數(shù)據(jù)模型。

EKG方案主要實現(xiàn)了知識圖譜數(shù)據(jù)在云服務(wù)器中的加密存儲,同時可以支持用戶對該加密的知識圖譜進行一跳子圖的查詢。如圖4所示,EKG方案中的系統(tǒng)結(jié)構(gòu)可分為可信區(qū)域和不可信區(qū)域,其中，可信區(qū)域為用戶和數(shù)據(jù)擁有者內(nèi)部的代理服務(wù)器,不可信區(qū)域為云服務(wù)器。在構(gòu)建過程中,代理服務(wù)器將加密后的密態(tài)數(shù)據(jù)和陷門交給云服務(wù)器,云服務(wù)器對密態(tài)數(shù)據(jù)進行進一步處理后在鍵-值數(shù)據(jù)庫中進行持久化。在檢索過程中,用戶向代理服務(wù)器發(fā)起查詢請求,代理服務(wù)器通過用戶的查詢請求,產(chǎn)生查詢陷門,在云服務(wù)器上進行密態(tài)檢索,云服務(wù)器將密態(tài)檢索到的密文數(shù)據(jù)返回給代理服務(wù)器,代理服務(wù)器將密態(tài)數(shù)據(jù)解密后發(fā)送給用戶。本節(jié)將對EKG方案的構(gòu)建和檢索過程進行詳細介紹。

Figure 4 Diagram of system structure圖4 系統(tǒng)結(jié)構(gòu)圖

3.2.1 構(gòu)建方法

在構(gòu)建過程中,代理服務(wù)器需要將陷門傳遞給云服務(wù)器,云服務(wù)器通過陷門再進行進一步的加密處理,從而構(gòu)建密態(tài)索引。陷門的生成算法如算法1所示。

算法1陷門生成算法(GenTd)

輸入：實體或關(guān)系編碼為鍵-值模式后的鍵key;代理服務(wù)器上的密鑰k。

輸出：一對陷門〈tdx,tdy〉。

1.tdx←MAC(k,1‖key);

2.tdy←MAC(k,2‖key);

3.RETURNtdx,tdy

如圖5所示,EKG方案的知識圖譜構(gòu)建主要分為以下4個步驟：

Figure 5 Knowledge graph construction process圖5 密態(tài)知識圖譜構(gòu)建過程

(1)將知識圖譜中的實體和關(guān)系編碼為鍵值結(jié)構(gòu),該步驟與NEKG方案中的編碼方案一致。

(2)對編碼后的鍵值數(shù)據(jù)按鍵進行排序,并為其產(chǎn)生一個有序的pos值,生成〈ki,vi,posi〉(1≤i≤|E|+|R|×2)元組集合。

(3)對每個〈ki,vi,posi〉中的ki產(chǎn)生一對陷門,并對ki,vi進行加密,生成〈tdxi,tdyi,eki,evi,posi〉元組,并將該元組發(fā)送到云服務(wù)器中。

(4)云服務(wù)器對(eki,evi)進行序列化后,將{posi,Serialize(eki,evi)}存入DataBucket中,持久化密態(tài)知識圖譜數(shù)據(jù)。將{MAC(tdxi,1),Enc(tdyi,posi)}存儲到IndexBucket中,構(gòu)建密態(tài)索引。

在EKG方案中,加密索引存儲于鍵-值數(shù)據(jù)庫的IndexBucket分區(qū)中,加密數(shù)據(jù)存儲于鍵-值數(shù)據(jù)庫的DataBucket分區(qū)中。通過在索引IndexBucket中找到epos,并將該值解密,便可在DataBucket中找到所對應(yīng)的數(shù)據(jù)。由于密態(tài)知識圖譜中有大量的實體和關(guān)系,采用內(nèi)存數(shù)據(jù)庫(如Redis)來存儲構(gòu)建后的密態(tài)知識圖譜不太現(xiàn)實,所以在設(shè)計EKG方案時所考慮的場景是基于磁盤鍵值數(shù)據(jù)庫存儲的,而不是基于內(nèi)存的。磁盤鍵值數(shù)據(jù)庫大多數(shù)都是基于LSM-Tree(Log Structured Merge Tree)[15]實現(xiàn)的,因此使用有序的pos值可以使實體及其關(guān)系在磁盤中存儲在同一個或相鄰的SSTable段,這樣的設(shè)計可以讓檢索過程具有更高的緩存命中率,避免了過多的磁盤IO次數(shù),從而提高了檢索效率。

3.2.2 檢索方法

在鍵-值模式中,一跳子圖查詢需要通過實體標識(鍵)檢索到實體所對應(yīng)的屬性(值),同時檢索該實體相關(guān)的關(guān)系(鍵)及關(guān)系的屬性(值)。

如算法2所示,在代理服務(wù)端中,一跳子圖查詢依賴于SecGet和SecNext算法。如算法3所示,SecGet算法用于查詢實體的屬性值,在查詢的過程中,通過將實體在鍵-值存儲模式中的鍵所產(chǎn)生的陷門發(fā)送到云服務(wù)器上,云服務(wù)器利用陷門在密態(tài)索引IndexBucket中得到epos值,通過epos解密得到的pos值檢索到存儲在DataBucket中的對應(yīng)的密態(tài)數(shù)據(jù),并將檢索到的密態(tài)數(shù)據(jù)返回給代理服務(wù)端。SecNext算法用于檢索實體對應(yīng)的關(guān)系和關(guān)系屬性,其實現(xiàn)借助本方案所設(shè)計的pos值,pos值是按明文狀態(tài)下鍵的字典序所獲得的一個有序值,由于實體和其對應(yīng)的關(guān)系編碼為鍵-值模式后,其鍵在字典序上是連續(xù)的,這意味著對應(yīng)的加密數(shù)據(jù)在Databucket中也是連續(xù)存儲的,所以通過該算法可以獲得實體相關(guān)的邊及其屬性。因此，將這2個算法調(diào)用所獲得的明文數(shù)據(jù)組織起來,將是一個一跳子圖查詢的結(jié)果。在云服務(wù)器的整個查詢過程中,所查詢的數(shù)據(jù)始終是加密狀態(tài)的。這2個算法都需要向云服務(wù)端傳遞陷門。該陷門有2個作用,第1個作用是用于在密態(tài)索引中檢索到密態(tài)知識圖譜數(shù)據(jù),第2個作用是用于身份認證,只有代理服務(wù)端擁有生成陷門的密鑰。因此，其他沒有密鑰的攻擊者想偽造陷門進行檢索是不可行的,能夠成功檢索到數(shù)據(jù)的就只能是安全區(qū)域中的代理服務(wù)器。

算法2一跳子圖查詢

輸入：在鍵-值存儲模式下實體所對應(yīng)的鍵w;代理服務(wù)器上的密鑰k。

輸出：所檢索實體的一跳子圖SubG。

1.h←SecGet(w);

2.it←w;

3.w*,r*←SecNext(it);

4.WHILEw*≠ ⊥do

5.Add(w*,r*) toRh;

6.it←w*;

7.w*,r*←SecNext(it);

8.ENDWHILE

9.SubG←Build(w,h,Rh);

10.RETURNSubG

算法3實體查詢算法(SecGet)

輸入：在鍵-值存儲模式下實體所對應(yīng)的鍵w;代理服務(wù)器上的密鑰k。

輸出：在鍵-值存儲模式下鍵w所對應(yīng)的值ew′,即實體的屬性。

1.//run in proxy server

2.tdx,tdy←GenTd(w,k);

3.ed←CloudGet(tdx,tdy)/*remote procedure call,send a pair of trapdoor to cloud server,receive the encrypted data*/

4.ek,ev←Deserialization(ed)；

5.w′←Dec(k,ek)；

6.ew′← ⊥；

7.IFw′=wTHEN

8.ew′←Dec(ev,k)；

9.ENDIF

10.RETURNew′

11.//run in cloud server

12.CloudGet(tdx,tdy)

13.idx←MAC(tdx,1)；

14.epos←Get(IndexBucket,idx)；

15.pos←Dec(tdy,epos)；

16.ed←Get(DataBucket,pos)；

17.RETURNed

SecNext算法(如算法4所示)中體現(xiàn)了pos值的設(shè)計給方案帶來的好處,每次調(diào)用SecNext所檢索的數(shù)據(jù)在磁盤中的存放位置總與上一次迭代檢索的數(shù)據(jù)相鄰,不僅大幅度減少了磁盤隨機讀的次數(shù),而且也使得一跳子圖查詢過程有更高的緩存命中率。

算法4關(guān)系查詢算法(SecNext)

輸入：在鍵-值存儲模式下實體或關(guān)系所對應(yīng)的鍵w;代理服務(wù)器上的密鑰k。

輸出：在鍵-值存儲模式下與w有相同前綴的關(guān)系對應(yīng)的鍵值對〈w′,rw′〉。

1.//run in proxy server

2.tdx,tdy←GenTd(w,k)；

3.ed←CloudNext()；//remote procedure call

4.ek,ev←Deserialization(ed)；

5.w′←Dec(k,ek)；

6.rw′← ⊥；

7.IFmatchPrefix(w′,w) is trueTHEN

8.rw′←Dec(ev,k)；

9.RETURNw′,rw′；

10.ELSE

11.RETURN⊥；

12.ENDIF

13. //run in cloud server

14.CloudNext(tdx,tdy)

15.idx←MAC(tdx,1)；

16.epos←Get(IndexBucket,idx)；

17.pos←Dec(tdy,epos)；

18.ed←Next(DataBucket,pos)；

19.RETURNed

4 安全分析

4.1 存儲安全性分析

在EKG方案中,加密索引和加密數(shù)據(jù)分別存儲在IndexBucket和DataBucket 2個分區(qū)中。在IndexBucket中,{index,epos}分別為ek的消息認證碼MAC(Message Authentication Code)和pos經(jīng)過非確定性加密后形成的密文。在DataBucket中,{pos,Serialize(ek,ev)}分別為有序標識pos值和鍵值數(shù)據(jù)經(jīng)過非確定性加密后所序列化成的二進制串。EKG方案在整個存儲過程中需要使用MAC生成算法和非確定性加密算法。

對于涉及的MAC生成算法,本文方案均采用HMAC-SHA256,HMAC的安全性取決于底層哈希函數(shù)的安全性。SHA256是一種安全的哈希算法,目前仍未找到有效的攻擊算法能在多項式時間內(nèi)找出SHA256的一對碰撞,所以本文所采用的HMAC-SHA256是安全的,其可以抵抗選擇信息攻擊,攻擊者并不能在多項式有效的時間內(nèi)找到存在性偽造。

涉及的對稱加密算法的設(shè)計均采用AES-CTR模式,其滿足選擇明文攻擊下的不可區(qū)分性安全IND-CPA(INDistinguishability under Chosen-Plaintext Attack)[16],對比更普遍常用的AES-CBC(Advanced Encryption Standard-Cipher Block Chaining)模式[17],有著可并行、不需要填充以及安全性更高等優(yōu)勢。在同樣選用AES-128的情況下,CTR模式在加密264個AES 塊后必須更換密鑰,而CBC模式則在加密248個AES塊后必須更換密鑰,相比之下CTR模式的安全性更加優(yōu)越。CTR模式中對每個分組是可以獨立運算的,這也意味著該模式可以通過并行計算來提高系統(tǒng)效率,這一點對于鏈式結(jié)構(gòu)的CBC模式來說是做不到的。

在整個構(gòu)建和存儲過程中,為了獲得更快的檢索效率,密態(tài)知識圖譜會向服務(wù)器泄露有序的pos值,但是所泄露的pos值不會向攻擊者泄露任何明文信息。綜上所述,當本文所設(shè)計的密態(tài)知識圖譜暴露在惡意環(huán)境下時,攻擊者所能夠獲取到的只有隱私數(shù)據(jù)的索引對數(shù),以及有序的pos值。由于知識圖譜數(shù)據(jù)經(jīng)過滿足IND-CPA安全性的非確定性加密算法加密,因此攻擊者不會獲得有關(guān)知識圖譜的任意實體/關(guān)系的明文信息。

4.2 檢索安全性分析

在密態(tài)知識圖譜的檢索過程中,代理服務(wù)端通過基于密鑰的消息認證碼算法HMAC,利用知識圖譜鍵-值存儲模式下的鍵構(gòu)造一對陷門〈tdx,tdy〉,并將陷門對發(fā)送到云服務(wù)端。由于本文方案HMAC算法所依賴的散列函數(shù)有著可靠的抗碰撞性及不可逆性,所以構(gòu)造出來的陷門并不會泄露任何明文信息。云服務(wù)器收到陷門對后,系統(tǒng)將利用tdx來生成一個MAC值,通過該MAC值在索引分區(qū)IndexBucket中找到epos值,再通過tdy將epos解密得到pos值,通過pos值在DataBucket分區(qū)中找到對應(yīng)的加密知識圖譜數(shù)據(jù)返回給代理服務(wù)器。在這個過程中,涉及到的被檢索數(shù)據(jù)對敵手來說都是密態(tài)的,對應(yīng)的每個實體和關(guān)系的存儲都是被滿足IND-CPA安全的對稱加密算法所加密保護的,因此敵手無法在此過程中獲取到用戶隱私數(shù)據(jù)。本文方案的安全索引是基于Cash等人[7]的動態(tài)可搜索加密方案所構(gòu)建的,其整個構(gòu)建被嚴格證明為符合Cash等人所提出的RCPA(pseudo Random Ciphertexts under chosen-Plaintext Attack)安全性。

5 實驗及其結(jié)果

本文在Freebase Film Data數(shù)據(jù)集上對NEKG方案和EKG方案進行了全面的實驗分析。NEKG和EKG方案通過Golang實現(xiàn),鍵-值數(shù)據(jù)庫使用Badger DB v3.2。代理服務(wù)端和云服務(wù)端實驗運行環(huán)境均為Ubuntu20.04 LTS,處理器的核心數(shù)為4,內(nèi)存容量為4 GB。其中EKG方案系統(tǒng)原型部署在代理服務(wù)端和云服務(wù)端,而NEKG方案的系統(tǒng)原型部署在云服務(wù)端,為了避免網(wǎng)絡(luò)環(huán)境不穩(wěn)定對實驗數(shù)據(jù)的影響,代理服務(wù)端和云服務(wù)端均為本機上的2臺虛擬機。

為了測試隨著數(shù)據(jù)規(guī)模的增加EKG方案和NEKG方案的構(gòu)建時間和空間的變化情形,以及對比和分析不同數(shù)據(jù)規(guī)模下2個方案在構(gòu)建時間和空間上的差異,本文分別在不同數(shù)據(jù)規(guī)模下對這2個方案進行性能測試。構(gòu)建知識圖譜的測試規(guī)模如表 3所示,其中最大規(guī)模的實體數(shù)量達到了百萬級別。構(gòu)建時間的實驗結(jié)果如圖 6所示,其中，y軸表示構(gòu)建時間,x軸表示實體和關(guān)系數(shù)量的總和。從實驗結(jié)果可以看出,構(gòu)建時間與實體和關(guān)系數(shù)量的總和呈線性關(guān)系,并且EKG和NEKG之間的構(gòu)建時間差異并沒有高于一個數(shù)量級。

Table 3 Test scales of knowledge graph construction

構(gòu)建后的知識圖譜所占空間如圖 7所示,其中,y軸表示圖譜所占空間,x軸表示實體和關(guān)系數(shù)量的總和。從實驗結(jié)果可以看出,知識圖譜的存儲空間與實體和關(guān)系數(shù)量的總和呈線性關(guān)系,EKG方案中知識圖譜所占空間大小約為NEKG方案的3倍,而這相對于現(xiàn)今的磁盤存儲成本是可接受的。下面分析空間膨脹的原因：在EKG方案中,每個實體或關(guān)系所編碼成的鍵-值將被加密,加密的填充機制會導(dǎo)致加密后的數(shù)據(jù)在字節(jié)數(shù)上膨脹；另一方面,對于每對明文鍵-值，其密態(tài)存儲時需要分別在IndexBucket和DataBucket中存儲密態(tài)索引和密態(tài)數(shù)據(jù)。

Figure 6 Test results of knowledge graph construction time 圖6 知識圖譜構(gòu)建時間測試結(jié)果

Figure 7 Test results of knowledge graph storage space 圖7 知識圖譜存儲空間測試結(jié)果

為了測試EKG方案和NEKG方案的一跳子圖平均檢索效率以及對比這2個方案的差異,本文在所構(gòu)建的1 000 000實體規(guī)模的知識圖譜上進行查詢測試,從中隨機抽取出100 000個實體標識作為查詢集,分別對NEKG和EKG方案進行20 000,40 000,60 000,80 000和100 000次一跳子圖查詢。查詢時間的測試結(jié)果如圖 8所示,其中,y軸為一跳子圖查詢時間,x軸為從查詢集中順序讀取實體標識進行檢索的個數(shù)。從實驗結(jié)果可以看到,在100 000次檢索測試中,EKG的檢索時間為NEKG的2.09倍,EKG方案中對于每一個實體或關(guān)系,其在云服務(wù)器中需要2次讀數(shù)據(jù)庫操作,而NEKG方案只需要1次讀數(shù)據(jù)庫操作,并且在EKG方案中,在代理服務(wù)端中需要生成查詢陷門,并且對從云服務(wù)器中獲取到的密文進行解密,在云服務(wù)端也需要額外的加解密計算,可見2.09倍是一個可觀的實驗結(jié)果。

Figure 8 Test results of one-hop subgraph query time 圖8 一跳子圖查詢時間測試結(jié)果

為了更好地了解NEKG和EKG方案在查詢的各個步驟的耗時,本文將查詢劃分為4個子步驟,如表 4所示。通過前文的方案介紹可知,對于NEKG方案,一跳子圖查詢主要為2個步驟,分別為從鍵值數(shù)據(jù)庫中讀取鍵值數(shù)據(jù)(T2-NEKG)，以及鍵值模型和圖模型之間的轉(zhuǎn)換(T4)。對于EKG方案,一跳子圖查詢主要有4個步驟,在查詢實體/關(guān)系所對應(yīng)的鍵值之前,需要先生成陷門(T1),將生成后的陷門發(fā)送到云服務(wù)器中,云服務(wù)端將檢索到的加密數(shù)據(jù)返回給代理服務(wù)器(T2-NEKG),將加密數(shù)據(jù)解密為明文的鍵-值數(shù)據(jù)(T3),最后再將鍵值模型數(shù)據(jù)轉(zhuǎn)化為圖模型數(shù)據(jù)(T4)。本文在100 000次一跳子圖查詢下對各個子步驟的總耗時進行測試,測試結(jié)果如圖 9所示。EKG方案和NEKG方案查詢過程最大的區(qū)別在于T2-EKG和T2-NEKG,其中T2-EKG為T2-NEKG的2.54倍,原因在于EKG每查詢一個明文鍵值需要讀取2次鍵值數(shù)據(jù)庫,并且云服務(wù)端在讀取完數(shù)據(jù)之后,需要執(zhí)行Hash算法和解密算法。

Table 4 Query substep of one-hop subgraph

目前所有實驗都是基于多次查詢時間的總和所得出的結(jié)論,而對于某些熱點實體,其可能擁有很多關(guān)系也有可能擁有很多屬性,這些實體往往在查詢時需要更多時間,而對于這些實體恰好是最有可能被用戶所檢索的實體。所以，本文對100 000次查詢測試結(jié)果中的百分位數(shù)進行了統(tǒng)計,如圖 10所示,在P999百分位點中,EKG方案的查詢時間為NEKG方案的2.26倍。從實驗結(jié)果可以得出,熱點實體對于EKG方案和NEKG方案之間的查詢速度比影響很小,這充分表明EKG方案在安全性和效率上取得了很好的平衡。

Figure 9 Substep time-consuming of one-hop subgraph query 圖9 一跳子圖查詢子步驟耗時情況

Figure 10 Percentile points among 100 000 queries圖10 100 000次查詢中的百分位點

6 結(jié)束語

本文提出了一種基于可搜索加密的密態(tài)知識圖譜方案,該方案支持知識圖譜的密態(tài)存儲以及一跳子圖查詢。為了獲得更好的檢索性能,該方案引入了一個有序的pos值,使實體及其所對應(yīng)的關(guān)系能在磁盤中局部存儲,增加緩存的命中率,減少IO次數(shù)。經(jīng)過與非密態(tài)的知識圖譜之間的性能對比,證實了該方案在安全性和效率上取得了良好的平衡。后續(xù)將在此研究的基礎(chǔ)之上,對存儲和加密計算進行并行優(yōu)化,并引入同態(tài)加密和保序加密等功能性加密方案,使密態(tài)知識圖譜方案實現(xiàn)更多的密態(tài)知識計算。目前該方案僅支持全密態(tài)化的知識圖譜存儲,而對于知識圖譜中的非隱私數(shù)據(jù)往往可以不需要密態(tài)化存儲,因此,未來如何設(shè)計并實現(xiàn)僅針對隱私數(shù)據(jù)加密的半密態(tài)知識圖譜將是研究的一大關(guān)鍵。