梁麗莎 盧 來* 吳衛(wèi)祖

1(廣東海洋大學(xué)寸金學(xué)院 廣東 湛江 524094) 2(廣東海洋大學(xué)數(shù)學(xué)與計算機學(xué)院 廣東 湛江 524088)

0 引 言

數(shù)據(jù)庫外包是常見的云計算服務(wù)范例，數(shù)據(jù)所有者可以充分利用其存儲和計算資源。為了減少成本，資源受限的公司可以將他們大量的數(shù)據(jù)外包給具有動態(tài)存儲和計算能力的第三方服務(wù)提供商。云計算由于其方便性引起了較高的關(guān)注度，但是大量數(shù)據(jù)被不受信任的第三方控制會引起機密性和隱私性的安全問題。

移動設(shè)備和導(dǎo)航系統(tǒng)普遍使用基于位置服務(wù)(Location Based Service,LBS)，導(dǎo)致需要妥善管理的空間數(shù)據(jù)增加。日常生活中有大量用戶使用LBS，他們以匿名的方式發(fā)起空間查詢并在有效時間內(nèi)收到響應(yīng)。同樣，數(shù)據(jù)所有者為了保護數(shù)據(jù)隱私性，不想將其透露給服務(wù)提供商(Service Provider,SP)，因此將數(shù)據(jù)外包給云服務(wù)提供商(例如：百度地圖)。認證用戶向SP發(fā)送信息查詢請求時，數(shù)據(jù)所有者和用戶都不想把真實數(shù)據(jù)透露給服務(wù)提供商。

在把空間數(shù)據(jù)庫外包到云平臺上時，必須考慮以下幾點情況。對于惡意攻擊者和服務(wù)提供商來說，數(shù)據(jù)庫內(nèi)容必須保持隱藏。通過數(shù)據(jù)加密可以簡單地保護用戶數(shù)據(jù)隱私，即數(shù)據(jù)所有者加密整個數(shù)據(jù)庫，并且將加密數(shù)據(jù)(不帶任何其他信息)發(fā)送給SP。在查詢期間，認證用戶從SP處獲取所有的加密數(shù)據(jù)，然后解密并搜索需要的數(shù)據(jù)點。這樣雖能保證安全，但是由于其產(chǎn)生的通信開銷極高，尤其是當用戶只需要一小部分數(shù)據(jù)點時，在實時應(yīng)用中并不可用。

現(xiàn)有的保護外包數(shù)據(jù)的方法大部分采用空間變換機制[1-3]或者密碼學(xué)技術(shù)[4-6]。然而大多數(shù)的保護機制都會在數(shù)據(jù)機密性和查詢過程有效性之間權(quán)衡。為了解決這些問題，本文提出一種兩層編碼方法，先轉(zhuǎn)換數(shù)據(jù)，然后對轉(zhuǎn)換空間加密。此外，查詢過程只需要在用戶和云服務(wù)提供商之間通信一次就可實現(xiàn)。采用Hilbert空間填充曲線(用戶定義曲線參數(shù))來變換空間數(shù)據(jù)點。由Hilbert索引范圍定義數(shù)據(jù)包列表，然后用順序保留加密(Order-Preserving Encryption, OPE)技術(shù)[7]對列表加密，OPE支持在服務(wù)器處執(zhí)行空間kNN查詢。采用OPE的優(yōu)勢在于其將原始距離值隱藏，在SP處通過簡單的對比來正確評估。另外，數(shù)據(jù)所有者向認證用戶提供密鑰，用轉(zhuǎn)換密鑰和加密密鑰向SP發(fā)送編碼查詢，最后用OPE密鑰解密查詢響應(yīng)。

云架構(gòu)模型主要由三類實體構(gòu)成，分別為：數(shù)據(jù)所有者(Data Owner,DO)，服務(wù)提供商(Service Provide,SP)和認證用戶(Authorized User,AU)，如圖1所示。DO外包其空間數(shù)據(jù)點，在外包給SP之前通過變換和加密數(shù)據(jù)庫確保數(shù)據(jù)的安全性。AU利用變換密鑰向SP發(fā)起加密的kNN查詢。該查詢在SP處在加密數(shù)據(jù)庫上處理并將結(jié)果返回給用戶。AU利用密鑰解密查詢響應(yīng)來獲取真實的查詢結(jié)果。

圖1 云架構(gòu)模型圖

1 相關(guān)研究

移動設(shè)備和導(dǎo)航系統(tǒng)的大量應(yīng)用使LBS迅速發(fā)展起來。文獻[8-9]提出通過在SP處增加一個中間設(shè)備或者防干擾設(shè)備來確保安全性。該設(shè)備通過對傳送的消息加密和解密來協(xié)助處理查詢。假設(shè)在服務(wù)器端存在一個可信設(shè)備，文獻[9]提出一種快速查找加密技術(shù)用于非順序保留AES加密。數(shù)據(jù)庫所有者先基于一維值建立一個B樹，然后加密每一個節(jié)點級的記錄來防御非受信任SP攻擊數(shù)據(jù)。

然而，在用戶數(shù)量越來越多的情況下，SP處單臺設(shè)備服務(wù)每一個 AU已經(jīng)不現(xiàn)實。為了解決這個問題，文獻[4]提出一種基于密碼的轉(zhuǎn)換機制來確保二維數(shù)據(jù)的安全性：DO采用R*樹架構(gòu)來索引數(shù)據(jù)庫并采用AES加密算法加密每一個節(jié)點；根據(jù)R*樹服務(wù)器與用戶之間的深度大小，查詢過程需要多個回合，導(dǎo)致通信開銷的增加；SP向AU發(fā)送加密的根節(jié)點，AU利用密鑰解密節(jié)點，然后請求子節(jié)點與查詢區(qū)域重疊，直到找到相應(yīng)數(shù)據(jù)點的葉節(jié)點。

類似地，文獻[5]提出一種基于Hilbert曲線轉(zhuǎn)換的密碼機制來平衡數(shù)據(jù)安全性和查詢效率之間的關(guān)系。采用Hilbert曲線將數(shù)據(jù)局部聚類，并用AES加密轉(zhuǎn)換數(shù)據(jù)。加密文件安全地存放在SP處。查詢過程首先將整個加密文件發(fā)送至AU，解密之后搜索與查詢內(nèi)容相關(guān)的記錄。但該方法后來被證明需要消耗大量的時間。

除上面提到的密碼技術(shù)以外，學(xué)者還提出了基于空間位置分割和再分配的空間變換方法，如：空間層次劃分(Hierarchical Space Division,HSD)、基于誤差變換(Error-Based Transformation,ERB)和HSD/ERB混合變換[4]。文獻[10]提出另一種空間變換機制，通過切邊變換和路由變換提供數(shù)據(jù)安全性。然而，這些技術(shù)均需要保留原始空間點的坐標，并且假設(shè)攻擊者能夠獲取原始點和變換空間中原始點坐標的背景信息，暴露了數(shù)據(jù)點附近的信息。

對用戶而言，保證查詢過程的即時性是LBS的關(guān)鍵，因此數(shù)據(jù)庫外包必須使用低通信開銷技術(shù)，需要對空間數(shù)據(jù)和查詢區(qū)域進行編碼。大多數(shù)現(xiàn)有的研究成果并沒有利用SP的計算能力，基于此本文提出一種服務(wù)器端針對加密數(shù)據(jù)的安全有效的kNN查詢方法來解決這一問題。

2 加密空間變換

為了保證空間數(shù)據(jù)的機密性，原始空間的二維數(shù)據(jù)點以兩種方式隱藏：(1) 利用Hilbert空間填充曲線將空間中的二維點轉(zhuǎn)換成一維點；(2) 利用OPE[11]加密生成的Hilbert單元值，然后用AES加密產(chǎn)生的數(shù)據(jù)點。變換密鑰和加密密鑰都通過SSL協(xié)議由DO直接發(fā)送至AU。

2.1 Hilbert數(shù)據(jù)包列表設(shè)計

首先將靜態(tài)空間數(shù)據(jù)點分配到網(wǎng)格中，網(wǎng)格由Hilbert空間密鑰[2](Hilbert Space Key,HSK)根據(jù)曲線生成。HSK={x0,y0,θ,n}，其中:(x0,y0)是曲線起始點，θ為曲線方向，n為曲線順序。HSK支持單向轉(zhuǎn)換，有可能出現(xiàn)兩個或者多個點在曲線中有相同的單元索引。

DO創(chuàng)建Hilbert數(shù)據(jù)包列表(Hilbert Packet List,HPL)過程如下：首先，為空間中的每個數(shù)據(jù)點在網(wǎng)格中分配一個Hilbert單元值。其次，基于單元值將數(shù)據(jù)點存儲到數(shù)據(jù)包中，每個數(shù)據(jù)包包括：Ps(數(shù)據(jù)包起始Hilbert索引)，Pe(數(shù)據(jù)包結(jié)束Hilbert索引)和Pc(數(shù)據(jù)包原始空間點固定值)。Ps、Pe分別代表數(shù)據(jù)包中起始和結(jié)束數(shù)據(jù)點的位置，Pc由每個數(shù)據(jù)包存儲的數(shù)據(jù)點的數(shù)量c決定。

當曲線順序n為3，c為4時，HLP示意圖如圖2所示。第一個數(shù)據(jù)包Ps=0，以c個數(shù)據(jù)點填充Pc，Pe是數(shù)據(jù)包中第c個目標的單元索引。空Hilbert索引值表示沒有分配空間點，其一般不會在HPL中出現(xiàn)，除非索引在數(shù)據(jù)包填充完成之前發(fā)生沖突。

圖2 Hilbert空間變換和Hilbert數(shù)據(jù)列表

2.2 OPE

為了進一步對空間數(shù)據(jù)進行編碼，在將HLP發(fā)送至SP之前，DO采用OPE技術(shù)對其加密。這保證了數(shù)據(jù)不會被SP泄露給第三方中介。此外，為了阻止數(shù)據(jù)的非認證訪問，SP在使用數(shù)據(jù)之前沒有能力解密數(shù)據(jù)。因此，采用OPE機制確保明文數(shù)據(jù)的順序以加密的方式保存，并可以在加密數(shù)據(jù)上評估查詢。最后，DO向AU發(fā)送OPE密鑰來加密查詢Hilbert單元，并將SP返回的查詢結(jié)果解密。

3 kNN查詢過程

本文主要關(guān)注LBS中應(yīng)用最為廣泛的二維空間kNN查詢。評估期間，將kNN查詢轉(zhuǎn)換成一組一維Hilbert單元值(部分或者全部與周圍區(qū)域重疊)。SP和AU均參與處理查詢過程。數(shù)據(jù)點及其Hilbert單元值放入HPL，經(jīng)加密之后存放在SP。AU通過定義查詢點發(fā)起kNN查詢。通過定義圓形區(qū)域(Circular Region,CR)可以發(fā)現(xiàn)查詢點周圍的k個鄰近點。AU將查詢轉(zhuǎn)換成一組落入該區(qū)域的加密Hilbert單元值。利用OPE密鑰加密查詢請求然后將其發(fā)送至SP。SP通過比較加密的Hilbert起始和結(jié)束單元值范圍，將相關(guān)的加密返回給AU。AU利用密鑰解密返回的結(jié)果數(shù)據(jù)點，通過尋找查詢點的k個臨近點生成真實的查詢結(jié)果。

kNN查詢過程如圖3所示。查詢請求由Hilbert值重疊的CR組成。發(fā)送的Hilbert值相當于HPL的起始和結(jié)束元組。兩個元組中包含的加密數(shù)據(jù)點集返回AU，用戶從中取出需要的k個點。

圖3 kNN查詢交換過程

算法1列出了空間kNN查詢的處理過程。已知查詢點Q和點Q周圍的圓形區(qū)域CR。步驟2)中Hilbert單元與CR重疊生成查詢區(qū)域；步驟3)-步驟5)中加密查詢Hilbert單元并發(fā)送至SP；步驟6)-步驟12)、步驟15)在SP處完成。與查詢Hilbert單元值匹配的元組返回至AU。如果返回數(shù)據(jù)點的數(shù)量小于k，則重新定義個更大范圍的CR并另外發(fā)送Hilbert單元值給SP，之后的處理方法同上。此外，步驟16)-步驟20)中，空間數(shù)據(jù)點在AU處加密，獲得Q周圍的k個最近的數(shù)據(jù)點。

算法1空間kNN查詢

輸入：查詢點Q。

輸出：kNN結(jié)果為k個空間數(shù)據(jù)點。

1) while (k>size(Result))

2) QueryCells=cells contained in CR around Q

3) for all (c∈QC)

4) HilbertCells=HilbertCells∪(encrypt) Hilbert(c)

5) end for

6) for all (p∈HPL)

7) while (HilbertCells≤Psi)

8) if (HilbertCells∈[Psi,Pei])

9) Result=Result∪Pci

10) end if

11) end while

12) end for

13) Increase the radius of circular region, CR

14) end while

15) Return Result to AU

16) for all (r∈Result)

17) rD=Decrypt r

18) distNN=Compute distance between Q and rD

19) end for

20) kNNResult=FindkNN(distNN)

4 實 驗

通過實驗對該方法進行有效性評估，采用多個參數(shù)來衡量Hilbert變換效果，均展示出快速的系統(tǒng)響應(yīng)。實際環(huán)境為Intel Core i7-3770 CPU @ 3.40 GHz。以兩個不同大小的真實空間數(shù)據(jù)集[12]為例：(1) 奧爾登堡市(Oldenburg City,OC)道路網(wǎng)，包含1 104個點；(2) 美國東北部(North East,NE)，包含123 593個點。

4.1 Hilbert空間密鑰

Hilbert空間變換利用HSK對空間數(shù)據(jù)庫進行編碼。為了突出HSK的全面性，通過改變Hilbert曲線順序來分配數(shù)據(jù)點。n值越大表示網(wǎng)格粒度越大，安全性越高。分配給每個Hilbert索引值的平均點數(shù)量如圖4所示。隨著n的增加，每個Hilbert索引值的平均點數(shù)量急劇減少。對于數(shù)據(jù)集OC和NE，當n=5和n=8時，平均點數(shù)量小于2。

圖4 Hilbert曲線順序與點數(shù)平均值關(guān)系圖

4.2 空間kNN查詢處理時間

兩個數(shù)據(jù)集中SP處理kNN查詢(如搜索加密HPL)的消耗時間如圖5所示，每個kNN查詢的查詢點從區(qū)域空間隨機生成。不同查詢大小的查詢時間均為毫秒級別。k值越小，查詢時間越短，且兩個數(shù)據(jù)集性能趨勢大致相同。

圖5 kNN查詢大小與查詢處理時間關(guān)系圖

4.3 kNN查詢通信開銷

實驗中根據(jù)不同的k值生成隨機kNN查詢，并測量在此交換過程中SP和AU之間的數(shù)據(jù)量，通信開銷包括：1) AU利用HSK將查詢區(qū)域轉(zhuǎn)換成一組Hilbert單元值并將其發(fā)送至服務(wù)器；2) SP搜索HPL中相應(yīng)的空間點并返回加密結(jié)果，用4個字節(jié)代表Hilbert單元值，每個空間點為16字節(jié)。OC和NE中，k取4種不同大小值，100次查詢的平均通信開銷如圖6所示?？梢钥闯觯S著查詢大小的增加，發(fā)送的Hilbert單元值和返回數(shù)據(jù)點也增加，通信開銷呈線性增長。當k=20時，與同樣采用AES加密的CRT技術(shù)[4]相比，該方法響應(yīng)時間比CRT技術(shù)快了1.75倍。

圖6 查詢大小與通信開銷關(guān)系圖

5 結(jié) 語

云計算服務(wù)可以通過在服務(wù)器端虛擬存儲和計算資源，向認證用戶提供數(shù)據(jù)的方式將數(shù)據(jù)集外包。為了平衡服務(wù)器端數(shù)據(jù)的機密性和查詢的有效性，本文提出一種安全有效的kNN查詢方法。利用Hilbert曲線變換空間數(shù)據(jù)集，并引入順序保留加密方法變換數(shù)據(jù)來提高安全性。實驗證明該方法比現(xiàn)有的加密方法性能更好。該雙重變換方法不僅為數(shù)據(jù)提供保護，而且使認證用戶能及時收到空間kNN查詢回復(fù)。