基于字典的壓縮加密查詢方案研究

田萍芳,郭萬濤

(1.武漢科技大學 計算機科學與技術學院,湖北 武漢 430065;2.武漢科技大學 智能信息處理與實時工業系統湖北省重點實驗室,湖北 武漢 430065)

0 引 言

隨著互聯網的快速發展,越來越多的組織和個人開始關注RDF數據的組織、管理和共享問題[1]。同時,有許多關于金融、醫療、個人或其他敏感的數據[2],這類數據需要采用數據保護機制,如加密和匿名。為了確保數據的機密性[3],不僅需要在傳輸過程中加密數據,還需要在靜止狀態下加密數據。在這種情況下,多個用戶對數據的不同部分具有不同的訪問權限,用戶應該只能訪問他們被允許訪問的數據。但RDF數據使用方必須面對RDF數據的存儲壓力,如果不能有效地管理RDF數據集,可能會導致系統性能下降和查詢效率降低。隨著結構化RDF數據的不斷擴展,RDF壓縮已成為一個日益重要的研究領域。同樣,對于敏感數據數據的安全,如何有效加密以及在密文數據上執行查詢也是一個重要的研究領域。

目前國內外一些學者對RDF數據壓縮和RDF加密進行了研究。國外的Fernández[4]在2010年提出了HDT壓縮方案,Fernández通過將RDF三元組轉換成字典、ID三元組,將長的資源描述定位符(Uniform Resource Identifier,URI)轉換成短的ID值,有效減少了URI的結構冗余,從而壓縮了RDF數據集的大小并且支持對壓縮數據的訪問。隨后基于HDT的優化方案陸續被學者提出,進一步壓縮了數據集的大小,如HDT-FoQ[5](HDT Focused on Querying),Waterfowl[6],HDT++[7],RDF-TR[8](RDF Triples Reorganizer)等。Sandra[9]提出一種k2-triples壓縮方案,為ID三元組中的每個謂詞分配一個矩陣,矩陣中的每個點代表一個(主題,對象),然后用一個四叉樹壓縮矩陣,實現了RDF數據集的有效壓縮。Maneth[10]提出的方案先通過gRePair算法預處理RDF數據集,處理后的數據集再進一步壓縮,實現了RDF數據集的有效壓縮。Sultana[11-12]提出的另外兩種壓縮方案也是基于gRePair算法來壓縮圖的結構,然后再通過k2-tree進一步壓縮RDF數據集。國內的彭燊[13]提出的基于關系矩陣的關聯數據壓縮查詢模型HDVM(Header Dictionary Vector Matrix),將ID三元組進行一系列合并,轉成主題向量、謂詞向量、對象矩陣形式存儲,也實現了RDF數據集的有效壓縮與查詢。國外的Mark[14]提出了一種部分RDF加密的方案PRE(Partial RDF Encryption),其中RDF-graph中的敏感數據針對一組接收者進行加密,而所有非敏感數據仍然公開可讀,實現了RDF數據集的加密,保障了RDF數據的安全性。Kasten[15]提出了一種方法,可以在加密數據上執行用戶定義的SPARQL(SPARQL Protocol and RDF Query Language)查詢。RDF圖數據僅部分顯示給那些授權執行查詢的用戶,實現了RDF數據集的加密,保障了RDF數據的安全性。Javier[16]提出的壓縮加密方案,使用AES[17](Advanced Encryption Standard)對稱加密來加密壓縮后的數據,將用戶的ID作為對稱密鑰的唯一標識符,只有對應的用戶才能解密密文信息,實現了敏感數據的有效保護。

上述的RDF壓縮方案可以有效壓縮RDF數據集,但無法保證RDF數據的安全;RDF加密方案提高了RDF數據的安全性,但是,查詢加密數據集需要解密所有的數據,然后再對解密后的數據進行查詢操作,解密全部數據,相對比較耗時。

鑒于此,該文提出一種綜合RDF壓縮和RDF加密的方案,即基于字典的壓縮加密查詢方案(Dictionary Encrypted Query,DEQ),DEQ通過建立字典將原始RDF數據集中地轉化成短的ID,將原始三元組轉化成ID三元組,形成密文,并將數據的核心部分字典存放在可信區域,把密文ID三元組存放在不可信區域。DEQ不僅可以壓縮原始RDF數據集,降低RDF數據集占用的空間,還能防止隱私數據被不可信的第三方破解,而且支持對密文數據的查詢。最后通過實驗驗證了該方案的有效性與可行性。

1 相關理論

1.1 RDF

RDF圖G是來自((I∪B)×I×(I∪B∪L)的一組有限三元組(subject,predicate,object)[18],其中I表示URI,B表示空節點、L表示RDF文字。RDF圖可以組合在一起管理,組成一個RDF數據集,即一組RDF圖[19]。RDF數據集是一個由默認圖G和命名圖gi組成的集合DS:DS={G,(g1,G1),…,(gn,Gn)},其中gi∈I,gi是圖的名字。RDF數據集圖示例如圖1所示,RDF數據集三元組結構示例如圖2所示。

圖1 RDF數據集圖示例

圖2 RDF數據集三元組示例

1.2 HDT

HDT是一種二進制序列化格式,其核心思想是通過字典將RDF數據集中的所有數據換成短的ID,將三元組轉化成ID三元組,從而減少結構冗余,來降低RDF數據集占用的空間。HDT通過三個邏輯組件來管理RDF數據集。三個組件分別是:

(1)Header組件:主要包括描述RDF數據集的邏輯和物理元數據,它作為數據集中信息的入口點;

(2)Dictionary:組件提供了數據集中使用的術語集合,并將它們映射到唯一的整數ID。它使術語可以被其相應的ID替換,實現數據的有效壓縮;

(3)Triples組件:表示ID替換后底層圖的純結構。

1.3 鄰接表

鄰接表是一種用于表示圖的數據結構。在鄰接表中,圖中的每個節點都與一個列表相對應,該列表包含與該節點直接相連的所有其他節點。這個列表可以是一個數組、鏈表或者其他數據結構,其中存儲的元素為該節點所連接的節點的標識符或者對象。鄰接表是一種緊湊的數據結構,可以有效地表示具有大量節點和邊的圖。并且在某些圖算法中,鄰接表也比其他數據結構更有效率。

圖1對應的鄰接表結構如圖3(a)所示,其中每個節點中取的是URI的縮寫。在HDT方案中,將原始三元組轉換為ID三元組后,通過鄰接表形式存儲ID值,形式如圖3(b)所示,圖中的ID是原始RDF三元組經過字典轉換得到的唯一ID值。

圖3 鄰接表與ID鄰接表結構

2 模型總體架構與技術實現

壓縮加密查詢模型架構如圖4所示。架構包括壓縮加密模塊、可信區域、不可信區域三個部分。壓縮加密模塊包括數據壓縮(構建字典)和數據加密(生成密文三元組)。字典通過原始RDF數據集中的三元組中的元素生成,字典主要是降低RDF數據集中的URI冗余,并且通過字典建立起URI與短ID的一一映射,降低三元組的大小。密文ID三元組是原始RDF數據集中的三元組通過構建的字典,將原始三元組中的主題、謂詞、對象替換成ID值,最終生成ID三元組集,即是密文ID三元組。可信區域包括查詢轉換器和結果翻譯器。查詢轉換器主要是重寫用戶的查詢語句。查詢翻譯器主要是將密文結果轉化成原始的三元組。不可信區域主要是緩解可信區域的存儲壓力,存放密文數據,并對密文進行查詢。

圖4 總體架構

2.1 構建字典

構建字典主要是為了減少RDF數據集中URI的冗余,同時為每個不同的URI,不同的RDF文字,空節點生成一個唯一的ID,并在生成密文ID三元組時用ID替換對應的URI(或空節點或RDF文字)。構建字典應該遵循以下規則:

(1)URI是以“<”開頭,并以“>”結尾。若當前元素為URI,則獲取“<”和“>”之間的內容保存在字典中,并生成對應的ID。例如:“”是一個統一資源定位符(Uniform Resource Locator,URL),將“ http://example.com/xiaoming”保存在字典中,并生成對應的ID值1;

(2)空節點是以“_:”開頭的。如當前元素為空節點,則直接添加到字典中;例如:“_:xiaoyu”是一個空節點,直接將“_:xiaoyu”添加到字典中,并生成對應的ID值2;

(3)RDF文字是通過雙引號包起來的數據。如當前元素是RDF文字,則直接將RDF文字添加到字典中,并生成對應的ID。例如:“xiaohua”是一個RDF文字,直接將“xiaohua”添加到字典中,并生成對應的ID值3。

生成字典ID也應該遵循以下規則:

(1)SO字典:對于既出現在主題中,又出現在對象中的URI和空節點,將它們添加到SO字典,并且生成的ID值的范圍為[1,|SO|];

(2)S字典:對于只出現在主題中的URI和空節點,將它們添加到S字典,并且生成的ID值的范圍為[|SO|+1,|S|];

(3)O字典:對于只出現在對象中的URI、空節點和RDF文字,將它們添加到O字典,并且生成的ID值的范圍為[|SO|+1,|O|];

(4)P字典:對于出現在謂詞中的URI,將它們添加到P字典,并且生成的ID值的范圍為[1,|P|]。

圖5所示的是通過RDF數據集構建的字典。

圖5 構建字典過程

2.2 生成密文ID三元組

生成密文ID三元組主要結合上一步生成的字典,將RDF數據集中每個原始的三元組轉換成密文ID三元組。圖1中的RDF數據集生成密文ID三元組的過程如圖6所示。

圖6 生成密文ID三元組過程

2.3 重寫用戶查詢語句

查詢轉換器主要負責接收并重寫用戶的查詢語句,并將重寫后的查詢轉發給不可信區域。例如,查詢語句“http://example.com/xiaolu http://example.com/hasPhone ?o.”經過查詢轉換器轉換后得到查詢語句“2 2 ?o.”。

查詢轉換算法實現如表1所示。

表1 查詢轉換算法

2.4 解密解壓數據

結果翻譯器主要負責將不可信區域返回的密文數據進行轉換,轉換成真實RDF數據返回給用戶。例如,查詢返回的密文ID三元組結果為“2 2 2”,經過結果翻譯器翻譯后得到“http://e-xample.com/xiaolu http://example.com/hasPhone http://exa-mple.com/vivo”。

解密解壓算法實現如表2所示。

表2 解密解壓算法

2.5 查詢加密數據

不可信區域主要存儲加密的數據,緩解可信區域的內存空間,并在密文ID三元組中執行查詢操作,并將查詢的密文結果返回給可信區域中的結果翻譯器。例如在不可信區域執行的查詢為:“2 2 ?o.”,查詢得到的密文ID三元組為“2 2 2”。

密文查詢算法實現如表3所示。

表3 密文查詢算法

3 實驗結果

3.1 實驗數據集

在真實數據集和生成的數據集上進行對比實驗,來驗證提出的壓縮加密查詢方案。并且為了與Fernández提出的壓縮加密方案進行對比,選擇相似的數據集。真實數據集是DBpedia,并且使用 Lehigh University Benchmark (LUBM)數據生成器從100所大學(LUBM-100,包括0.13億三元組)到 400所大學(LUBM-400,包括0.53億三元組)獲得增量大小的合成數據集。LUBM以大學領域的本體為特征,其中大學的所有實體,如學生、教授和課程,都以三元組格式描述。5個數據集按照數據集的大小從低到高排列如表4所示,表中還包括每個數據集的一些統計信息,包括三元組數量、公共主題對象數量、主題數量、對象數量、謂詞數量(分別用|Triples|,|SO|,|S|,|O|,|P|表示)。在5個不同數據集上進行了對比實驗,主要從壓縮加密時間、壓縮加密結果、解密解壓時間、查詢時間四個方面將DEQ壓縮加密查詢方案與HDTcrypt壓縮加密方案進行對比。并從理論上對每個實驗做了分析,理論分析結果與實驗結果相吻合。

表4 數據集相關信息

3.2 壓縮加密時間

壓縮加密時間通過執行10次壓縮加密操作,10次加密操作,得到10次壓縮加密時間,最后取10次壓縮加密時間總和的平均值作為最終的壓縮加密時間。平均壓縮加密時間的計算結果如表5所示。

表5 平均壓縮加密時間 min

從理論上分析, DEQ的思想與HDTcrypt的思想一樣,都是將原始RDF數據集通過字典轉換成字典和ID三元組,所以在壓縮數據集方面,兩種方案的壓縮時間沒有很大差別。但是,HDTcrypt需要進一步對字典與ID三元組加密來保證數據的安全性,所以HDTcrypt的壓縮加密時間要比DEQ的多,因為對于HDTcrypt來說,原始RDF數據需要經過壓縮、加密兩個步驟,生成加密數據。DEQ只需要對RDF數據集進行一步處理,就能達到壓縮加密的效果。所以在理論上DEQ的壓縮加密時間要比HDTcrypt的壓縮加密時間更少。

從實驗結果來看,HDTcrypt壓縮加密RDF數據集的時間是DEQ的2倍以上,隨著數據集的增大,DEQ的性能優勢越明顯。兩種方案壓縮加密時間都是隨著數據集的增大而增大,即壓縮加密時間的大小與RDF數據集的大小成正相關。

3.3 壓縮加密結果

壓縮加密結果比較是通過HDTcrypt方案壓縮、HDTcrpty方案加密得到的數據大小與DEQ方案壓縮加密得到的數據大小進行比較。HDTcrypt方案壓縮、HDTcrypt方案加密與DEQ方案壓縮加密后的數據大小如表6所示。表中包括數據集的原始大小,HDTcrypt方案壓縮后的文件大小,HDTcrypt方案加密后的文件大小,DEQ方案壓縮加密后的文件大小。

表6 壓縮加密結果 G

從理論上分析,DEQ的思想與HDTcrypt的思想一樣,都是通過構建字典,將RDF數據集中的URI(或空節點或RDF文字)轉化成短的ID值,從而降低URI的冗余,進一步達到壓縮數據集的目的。所以在壓縮方面,兩種方案的壓縮結果沒有很大差別,但是,HDTcrypt需要進一步對字典與ID三元組通過加密算法加密數據來保證數據的安全性,而加密算法加密數據時會破壞壓縮后數據的結構,所以會導致數據集變大,所以HDTcrypt的壓縮加密結果要好于DEQ,因為DEQ只需要經過字典喜歡換后就形成了密文ID三元組,即同時實現了壓縮與加密。

從實驗結果來看,DEQ與HDTcrypt中的壓縮數據集的性能相當,DEQ壓縮加密性能要高于HDTcrypt。DEQ和HDTcrypt的壓縮結果表明,當數據集中的URI結構化程度越高,壓縮效果也越好。總體來說,DEQ在壓縮加密性能上優于HDTcrypt。

3.4 解密解壓時間

解密解壓時間通過執行10次解密操作,10次解壓操作,得到10次解密解壓時間,最后取10次解壓解密時間總和的平均值作為最終的解壓解密時間。平均解壓解密時間的計算結果如表7所示。

表7 解密解壓時間 s

從理論上分析,DEQ的密文數據解密解壓只需要將密文ID三元組通過字典直接轉換,即結合字典根據ID值獲取對應的URI(或空節點或RDF文字),得到原始的RDF三元組;而HDTcrypt加密得到的密文數據需要經過解密、解壓兩個步驟。即首先需要將所有的密文數據加載并解密,然后解壓所有數據,得到原始的RDF數據集。所以理論上DEQ在密文數據解密解壓時間上要優于HDTcrypt。

從實驗結果來看,DEQ的解密解壓時間更少,所以DEQ解密解壓性能更好。通過實驗結果可以看出,解密解壓的時間會隨著數據集的增大而逐漸增長,即解壓解密時間的大小與RDF數據集的大小成正相關,這一點在HDTcrypt和DEQ都有體現。

3.5 查詢時間

對7種查詢模式(SPO,SP?,S?O,S??,?PO,??O,?P?)分別進行查詢實驗,通過執行10次相同的查詢語句,得到10次查詢時間,最后取10次查詢時間總和的平均值作為最終的查詢時間。DEQ和HDTcrypt分別在LUBM-200數據集和DBpedia數據集上進行7種查詢模式的對比,平均查詢時間如表8所示。

表8 不同數據集上不同查詢模式的平均查詢時間 s

從理論上分析,對于查詢操作,HDTcrypt壓縮加密后得到的密文數據必須先獲取所有的密文數據,然后解密所有的數據,其次才能執行查詢操作,獲取滿足條件的壓縮后的三元組,最后將查詢得到的結果中的ID轉換成對應的URI(或空節點或RDF文字),才能得到原始的三元組。DEQ首先加載所有的密文ID三元組,然后執行查詢操作,獲取滿足添加的密文ID三元組,最后再將查詢的結果中的ID轉換成對應的URI(或空節點或RDF文字),得到原始的三元組。所以,理論上DEQ在查詢效率上要優于HDTcrypt,主要體現在DEQ比HDTcrypt少了一步解密操作。

從實驗結果來看,DEQ在查詢效率上要高于HDTcrypt。在LUBM數據集上執行?P?查詢模式時,查詢時間往往是其他模式的2倍以上,這是由于LUBM數據集的謂詞數量只有18個,所以每個謂詞相關聯的數據非常多,所以?P?查詢模式結果轉化也會花費比其他查詢模式更多的時間,從而增加了?P?查詢模式的查詢時間。

4 結束語

DEQ綜合了RDF壓縮方案與RDF加密方案的優點,不僅壓縮了原始RDF數據集的大小,而且支持在密文ID三元組上執行查詢操作。將密文ID三元組存儲在不可信區域,在不可信區域執行查詢,將字典數據存儲在可信區域,在可信區域執行解密操作,保障了數據的安全性。實驗結果表明DEQ有不錯的性能,不僅壓縮加密后的數據小于HDTcrypt的數據,而且在壓縮加密時間、解密解壓時間、查詢時間上都優于HDTcrypt,驗證了DEQ的可行性與有效性。

當然DEQ也存在不足,字典占用的空間比較大,并且密文轉換需要加載全部的字典。所以未來將研究如何對字典進行分塊存儲,從而實現在轉換密文ID三元組時,只加載部分字典數據,而不需要加載所有的字典數據。