沈蒙 趙夢蕉 祝烈煌 馬寶利

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

關(guān)鍵詞 近似最短距離；K-mediods聚類；圖壓縮

中圖分類號TP301

文獻(xiàn)標(biāo)志碼A

0 引言

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

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

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

1 相關(guān)工作

1.1 圖加密搜索技術(shù)

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

2 問題定義與描述

2.1 系統(tǒng)模型

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

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

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

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

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

2.2 相關(guān)定義

2.2.1 問題描述

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

2.2.2 保序加密算法方案

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

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

3.2 圖加密算法

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

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

3.3 檢索算法

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

3.4 安全性分析

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

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

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

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

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

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

4 實驗結(jié)果與性能評價

4.1 實驗設(shè)置

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

4.2 實驗方案

4.2.1 索引時間和大小

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

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

4.2.2 查詢時間和準(zhǔn)確性

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

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

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

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

5 結(jié)束語

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

參考文獻(xiàn)

References

[1] Vieira M V，F(xiàn)onseca 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] 朱旭東，李暉，郭禎.云計算環(huán)境下加密圖像檢索[J].西安電子科技大學(xué)學(xué)報 （自然科學(xué)版），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