支持近似最短距離查詢的高效圖加密機制

沈蒙 趙夢蕉 祝烈煌 馬寶利

摘要 近似最短距離查詢是圖檢索的基本模式.為了保護外包數據安全，通常對圖數據進行加密.已有加密方案使用兩跳覆蓋模型構建加密圖索引，導致索引結構復雜，降低了查詢效率.本文提出了一種基于圖壓縮的加密機制，可以提高圖的檢索效率，并且支持加密圖最短路徑查詢.該機制使用K-mediods聚類使得圖中的節點按照距離分成K個簇，每個簇內的節點使用其中心節點代理，當查詢2個點間最短距離時，對于相同簇內的點直接查詢，對于簇間的點使用代理節點查詢距離.實驗結果表明該機制有效地減少了查詢時間，提高了查詢效率，且查詢結果誤差度在可接受范圍內.

關鍵詞 近似最短距離；K-mediods聚類；圖壓縮

中圖分類號TP301

文獻標志碼A

0 引言

隨著信息時代的迅猛發展，云計算更加方便和普及，個人和企業將大量的數據外包給云服務器，使用第三方的云平臺服務器進行計算處理和數據存儲.但是，由于云服務器是半可信的，外包數據存在安全隱患.因此，需要既能夠保持云計算的優勢，又要保護數據的隱私不被泄露.圖結構數據在現實生活中具有廣泛應用，如道路信息或社交網絡[1-3]等.因此，關于圖的加密搜索成為研究的重點內容.

由于云服務器的半可信特征，常常將數據本地加密上傳到云服務器，在密文下進行查詢，在服務器端計算復雜度較高，如何有效地提高云服務器的查詢效率是研究的難點問題.現有的加密圖查詢研究，將圖使用哈希函數或二叉樹等形式構建查詢索引，在云服務器查詢時仍需要耗費大量時間，需要優化查詢搜索的構建方案.

為了解決上述問題，本文提出了支持近似最短距離查詢的高效圖加密機制（Efficient graph encryption mechanism for Approximate shortest distance Search，EAS）.該機制對于原始圖中的節點進行預處理，根據節點間距離分成K個簇，同一個簇內的節點使用其中心節點代理.當查詢2個簇內的點的最短距離時，使用代理點間的距離代替.這樣使得在云服務器上的查詢計算時間大大縮短，且降低的精確度在可接受的范圍內.實驗結果表明，與準確查詢方法相比，EAS可以有效地減少查詢時間，提高查詢效率.

1 相關工作

1.1 圖加密搜索技術

圖加密是一種結構化加密，是將圖的數據結構加密，且能在隱私保護的情況下進行查詢.結構化加密首先是由Chase等[4]提出的.由于最短路徑的查詢是最常使用的關于圖的查詢，近年來，對于最短路徑查詢的方案取得了很多研究成果.Cash等[5]提出了支持大量數據進行可搜索加密的方案，但是該方案只支持布爾查詢.Zhu等[6]提出一個使用干擾算法以及支持同義詞查詢的最短路徑搜索加密機制（SPSQ）.Meng等[7]提出了在對圖加密之前構造距離預言機（distance oracle）的數據結構，有效地提高了檢索的效率，并且支持近似地查詢最短距離.該方法通過犧牲一定準確度來達到有效計算，且沒有支持圖的動態更新.Wang 等[8]和Haynberg 等[9]針對以上問題提出了一種支持有效更新的確切最短路徑查詢的圖加密搜索方案，使用額外的存儲空間存儲圖的相關信息（節點鄰居信息和連接表），便于在密文上進行可修改的同態加密，并利用歷史查詢信息作為緩存，可以快速返回查詢過的信息.Wu等[10]提出了對于原始街道地圖信息壓縮，使用基于隱私信息查詢PIR（Private Information Retrieval）和混亂電路（garbled circuits）支持導航隱私保護的加密方案.但是該方案中涉及到計算查詢的每一個中間跳時都需要客戶與服務器的交互.

2 問題定義與描述

2.1 系統模型

支持近似最短距離查詢的高效圖加密機制是圖擁有者將圖預處理后加密發送到云服務器，用戶通過查詢條件從云服務器返回加密的圖信息[11].通常這類系統模型中主要涉及的實體至少有3個，其中包括圖的擁有者（Graph Owner）、云服務器（Cloud Server）以及查詢用戶（User），其模型如圖1所示.

在該模型圖中，各部分實體的功能介紹如下：

1）圖擁有者是圖結構的提供者.通常，圖結構只有圖的擁有者可以知道，因此在將圖外包上傳給云服務器之前，為了保護圖結構的隱私，將對圖結構進行加密，同時為了提高查詢效率，會考慮本地完成索引結構，并加密后一并交給云服務器進行管理，提供給自己或他人進行圖結構的相關搜索.

2）云服務器主要對圖結構擁有者提供的加密圖結構和加密索引表進行管理，以及對查詢用戶提交的圖相關的檢索請求進行檢索并返回結果.通常來說，云服務器無法了解到圖的明文結構，但是云服務器是半可信的.

3）查詢用戶將待查詢問題加密后提交給云服務器進行檢索，并對云返回的檢索結果圖像進行解密得到結果.

2.2 相關定義

2.2.1 問題描述

給予有向圖G=（V，E），節點總數為n=|V|，邊的總數為m=|E|.最短路徑的查詢條件為q=（u，v），是要求的點u和點v之間的最短路徑長度，記為distq.問題描述為：對于給定的圖G，比如代表道路或社交網絡，以加密的形式外包到云服務器，用戶需要在隱私保護的情況下查詢從源點s到目的點t的最短距離distq[12].

2.2.2 保序加密算法方案

本文對于圖中的邊加密使用保序加密算法方案，其中ORE（Order-Revealing Encryption）是一種保序加密方案且安全性很高[13].該方案包含∏ore=（Gen，Enc，Cmp）3個多項式時間算法：

在算法1中，首先對原始圖中的節點聚類得到結果集和中心點集，然后判斷分成的簇內的點之間是否有邊，若有邊則計算中心點距離并加入到新生成的圖中，如第2—10行所示.

3.2 圖加密算法

在加密圖的時候，包括對于聚類后代理點表、圖和預處理后圖的加密.其中原圖和預處理后圖加密的原理相同，都使用如算法2進行加密.算法2中輸入原圖和密鑰，得到加密的圖索引.其中使用到2個偽隨機函數h和g以及一個帶有安全參數的同態加密的函數f，例如AES算法[14].

在算法2中，生成圖的索引結構[15]為u （v，du，v），分別對密鑰和節點u取哈希值加密.對于每個與頂點u有邊的頂點v，對他們之間的距離使用AES加密和ORE加密，并將加密結果保存到索引中，如第4—9行所示.距離使用2種加密方式，原因是需要對加密距離值進行比較并滿足返回到用戶處可以解密的要求.

3.3 檢索算法

本文提出的云服務器上查詢算法如算法3所示.用戶提出要查詢的初始點s和終點t，即查詢條件為q=（s，t），使用密鑰sk進行加密后τs=h（sk，s||1），τt=h（sk，t||2）發送到云服務器.服務器通過查詢加密代理表，查看頂點所在類簇信息.如果頂點在不同的2個類簇中，則使用聚類后的新圖形成的索引△2查詢，代理點的距離即可近似地看作查詢的距離.另外，若頂點在相同的2個類簇中，就可以減少查詢的點到某一個特定的類簇中，減小查詢圖的規模.

3.4 安全性分析

對加密圖搜索機制EAS提出的加密方案∏進行安全性分析.將圖結構外包到云服務器時，由于云服務器是半可信的，可以對圖結構的密文進行一定操作，那么就有可能泄露一定的信息，經分析本文提出的加密方案∏是隱私安全的.

定義1 在半可信的云環境下，方案∏是隱私安全的：

1） 方案∏保證在云服務器不能推斷出原始的明文或最終結果；

2） 方案∏是抗選擇查詢攻擊的.

由于對圖結構的點加密是使用帶鹽的哈希函數，每個相同的點都具有不同的加密值.對點間距離值的同態加密使用長度為128的安全參數，使用窮舉法攻擊破解時的時間復雜度為O（2n），復雜度按照指數增長，因此方案是實際有效安全的.

選擇查詢攻擊的攻擊者A偽造查詢條件和加密索引結構，由于加密函數f，g，h和ORE都是安全的，因此偽造的與真實值是可區分的.那么對于任意多項式時間敵手A對于真實查詢和模擬查詢具有不可區分性.

4 實驗結果與性能評價

4.1 實驗設置

對上述機制的基本加密函數實現是基于OpenSSL數據庫完成的，實驗環境的配置為處理器2.5 GHz，內存8 GB.數據集采用隨機生成的3個不同規格的無向圖，如表1所示.實驗對比方案涉及明文和密文、不同聚類的K值以及不同查詢條件下的圖最短路徑搜索.以構建索引時間和大小，查詢時間和準確性4個方面作為衡量提出加密圖搜索機制EAS的效率指標.

4.2 實驗方案

4.2.1 索引時間和大小

在構建索引的時候，包括明文生成圖的索引和加密索引2部分.定義明文生成索引時間包含對圖的聚類，以及對生成聚類后的圖和原圖的兩跳索引的總時間.構建索引的時間和大小如表2所示.

由表2可以看出3種數據集構建索引大小和時間有較大的差別，這是因為由于圖的結構不同造成的.同一個數據集的密文和明文構建索引時間相近，密文下構建索引的大小是明文的4倍左右.

4.2.2 查詢時間和準確性

查詢時間體現算法的有效性，定義查詢時間為提交查詢條件到得到查詢結果這一段時間.使用準確查詢和近似查詢2種方法做對比.本實驗中隨機生成50個查詢條件，比較數據集DataSet1不同K值的情況下查詢時間的變化.觀察K值對查詢時間的影響，如圖2所示.

由圖2可以看出，當使用確切查詢方法的時候，耗費查詢時間較多，是使用近似距離查詢機制EAS的10倍左右，且K值過大或過小都會導致EAS機制的查詢時間增長，這是因為K值較小或較大時都與原圖差距較小，聚類的效果不明顯.

近似距離查詢機制會使結果失去一定精度，通過K值的選取控制誤差率.定義準確率為近似查詢機制的結果與準確查詢的比值.如圖3所示為幾個特定的K值對查詢準確率的影響.

觀察圖3可以看出聚類簇的K值越小，查詢的準確度越高，越接近確切查詢結果值.綜合比較K值對時間和準確度的影響，使用K值為10時，能夠得到較好的結果，準確度達到90%左右.

5 結束語

本文針對現有加密圖檢索時間長的問題，提出一種支持近似最短距離查詢的高效圖加密機制.該機制使用圖聚類的算法和“代理點”的思想，通過可搜索加密的框架對圖進行加密，并能夠支持近似最短路徑的查詢.使用真實的數據集實驗結果表明，該機制有效地提升了查詢效率，并且誤差率在可接受范圍內.

參考文獻

References

[1] Vieira M V，Fonseca B M，Damazio R，et al.Efficient search ranking in social networks[C]∥Sixteenth ACM Conference on Information & Knowledge Management，2007：563-572

[2] Wei F.Tedi：Efficient shortest path query answering on graphs[M]∥Sakr S，Pardede E.Graph data management：Techniques and applications.Hershey，PA：IGI Global，2010：99-110

[3] Yahia S A，Benedikt M，Lakshmanan L V S，et al.Efficient network aware search in collaborative tagging sites[J].Proceedings of the VLDB Endowment，2008，1（1）：710-721

[4] Chase M，Kamara S.Structured encryption and controlled disclosure[C]∥International Conference on the Theory and Application of Cryptology and Information Security，2010：577-594

[5] Cash D，Jarecki S，Jutla C S，et al.Highly-scalable searchable symmetric encryption with support for Boolean queries[C]∥Advances in Cryptology-CRYPTO，2013：353-373

[6] Zhu H，Wu B，Xie M Y，et al.Secure shortest path search over encrypted graph supporting synonym query in cloud computing[C]∥IEEE Trustcom/BigDataSE/ISPA，2016：497-504

[7] Meng X R，Kamara S，Nissim K，et al.GRECS：Graph encryption for approximate shortest distance queries[C]∥Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security，2015：504-517

[8] Wang Q，Ren K，Du M X，et al.SecGDB：Graph encryption for exact shortest distance queries with efficient updates[C]∥The 6th International Conference on Frontier Computing，2017，Accepted

[9] Haynberg R，Rill J，Achenbach D，et al.Symmetric searchable encryption for exact pattern matching using directed acyclic word graphs[C]∥International Conference on Security and Cryptography，2013：1-8

[10] Wu D J，Zimmerman J，Planul J，et al.Privacy-preserving shortest path computation[J].arXiv e-print，2016，arXiv：1601.02281

[11] 朱旭東，李暉，郭禎.云計算環境下加密圖像檢索[J].西安電子科技大學學報 （自然科學版），2014，41（2）：151-158

ZHU Xudong，LI Hui，GUO Zhen.Privacy-preserving query over the encrypted image in cloud computing[J].Journal of Xidian University （Natural Science），2014，41（2）：151-158

[12] Samanthula B K，Rao F Y，Bertino E，et al.Privacy-preserving protocols for shortest path discovery over outsourced encrypted graph data[C]∥IEEE International Conference on Information Reuse and Integration，2015：427-434

[13] Lewi K，Wu D J.Order-revealing encryption：New constructions，applications，and lower bounds[C]∥Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security，2016：1167-1178

[14] Katz J，Lindell Y.Introduction to modern cryptography[M].London：CRC Press，2007

[15] Akiba T，Iwata Y，Yoshida Y.Fast exact shortest-path distance queries on large networks by pruned landmark labeling[C]∥Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data，2013：349-360