LBS中外包空間數據的kNN安全查詢方法

梁麗莎 盧 來* 吳衛祖

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

0 引 言

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

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

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

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

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

圖1 云架構模型圖

1 相關研究

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

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

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

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

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

2 加密空間變換

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

2.1 Hilbert數據包列表設計

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

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

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

圖2 Hilbert空間變換和Hilbert數據列表

2.2 OPE

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

3 kNN查詢過程

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

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

圖3 kNN查詢交換過程

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

算法1空間kNN查詢

輸入：查詢點Q。

輸出：kNN結果為k個空間數據點。

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 實 驗

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

4.1 Hilbert空間密鑰

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

圖4 Hilbert曲線順序與點數平均值關系圖

4.2 空間kNN查詢處理時間

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

圖5 kNN查詢大小與查詢處理時間關系圖

4.3 kNN查詢通信開銷

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

圖6 查詢大小與通信開銷關系圖

5 結 語

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