基于網(wǎng)格的位置隱私保護方法*

李向東，張少波,2，郭 敏，王國軍,4+

1.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

2.湖南科技大學(xué) 計算機科學(xué)與工程學(xué)院，湖南 湘潭 411201

3.中南大學(xué) 軟件學(xué)院，長沙 410075

4.廣州大學(xué) 計算機科學(xué)與教育軟件學(xué)院，廣州 510006

基于網(wǎng)格的位置隱私保護方法*

李向東1，張少波1,2，郭 敏3，王國軍1,4+

1.中南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410083

2.湖南科技大學(xué) 計算機科學(xué)與工程學(xué)院，湖南 湘潭 411201

3.中南大學(xué) 軟件學(xué)院，長沙 410075

4.廣州大學(xué) 計算機科學(xué)與教育軟件學(xué)院，廣州 510006

在基于位置的服務(wù)（location based service，LBS）中，可信第三方模型是當(dāng)前位置隱私保護中的主要模型，該模型中匿名器知道用戶的具體位置，若它被攻擊者攻破，將會造成用戶位置信息的泄露。為此，提出一種基于網(wǎng)格的位置隱私保護方法，該方法將可信第三方模型中可信的第三方（trusted third party，TTP）替換為一個半可信的第三方（semi-trusted third party，STTP）作為匹配服務(wù)器。該匹配服務(wù)器只起匹配和緩存的作用，無法獲得用戶具體位置，從而能夠更好地保護用戶的位置隱私。安全分析表明，該方法能有效保護用戶的位置隱私；同時與可信第三方模型進行了對比分析，實驗結(jié)果表明，其性能比可信第三方模型更好。

基于位置的服務(wù)；位置隱私保護；網(wǎng)格；半可信第三方

1 引言

目前，移動互聯(lián)網(wǎng)得到飛速發(fā)展，智能移動終端變得相當(dāng)普及，基于位置的服務(wù)（location based service，LBS）[1-2]因此有著令人欣喜的前景。它改變了人們的生活方式，使用戶可隨時隨地獲得和其當(dāng)前位置有關(guān)的各種信息或服務(wù)，例如緊急救援、路線導(dǎo)航和社交娛樂等。

然而，基于位置的服務(wù)都需要用戶輸入其當(dāng)前位置信息，有的甚至需要用戶實時發(fā)送位置信息，如果這些信息保護不好，用戶的位置隱私就會被泄露，通過分析就能夠推斷出用戶的很多真實情況。比如，某用戶患有一種不便公開的疾病，當(dāng)其查詢某?？漆t(yī)院位置及前往路線時，如果攻擊者將其截獲，就可推測出該用戶或其家人可能患有此種疾病，而這往往是用戶不愿意讓別人知道的。由此可見，用戶位置隱私的保護非常重要。

目前，可信第三方模型[3-4]是位置隱私保護中的主要模型（如圖1）。匿名器的主要任務(wù)是跟蹤用戶的具體位置，并將其進行k-匿名處理，之后發(fā)送給服務(wù)提供商；同時接收服務(wù)提供商返回的查詢結(jié)果，處理后再返回給用戶。

可信第三方模型有以下幾個缺點：（1）若匿名器被攻擊者攻破，將會造成用戶位置信息的泄露，甚至?xí)绊懻麄€結(jié)構(gòu)的穩(wěn)定和安全；（2）若用戶數(shù)量密度較大時，所選的匿名區(qū)域就比較小，用戶位置就比較容易確定；（3）當(dāng)大量移動用戶頻繁更新位置信息時，匿名區(qū)域需要擴大，大幅增加了查詢處理的開銷；（4）在連續(xù)的基于位置的服務(wù)中，用戶位置在不斷變化，匿名器和服務(wù)提供商的計算開銷和通信開銷較大。

針對上述問題，本文提出了一種基于網(wǎng)格的位置隱私保護方法。該方法包括用戶、服務(wù)提供商和位于二者之間的匹配服務(wù)器3個實體。用戶使用網(wǎng)格[5-6]劃分查詢面積，加密查詢并產(chǎn)生加密標(biāo)識符來隱匿具體位置，匹配服務(wù)器只起匹配和緩存的作用，服務(wù)提供商提供查詢服務(wù)。匹配服務(wù)器和服務(wù)提供商均不知道用戶具體位置，從而能更好地保護用戶的位置隱私。

本文方法具有以下優(yōu)點：（1）不需要完全可信的第三方服務(wù)器，只需要一個半可信第三方（semi-trusted third party，STTP）作為匹配服務(wù)器，負責(zé)執(zhí)行簡單的匹配操作及一定的緩存操作；（2）確保匹配服務(wù)器無法得知當(dāng)前查詢用戶的具體位置信息，服務(wù)提供商也只能知道用戶在查詢面積內(nèi)，但無法推斷出用戶的具體位置。

Fig.1 Trusted third party model圖1 可信第三方模型

2 基于網(wǎng)格的位置隱私保護方法

2.1 查詢處理過程及各實體分析

基于網(wǎng)格的位置隱私保護方法主要包括3個實體：用戶、匹配服務(wù)器和服務(wù)提供商（如圖2）。

Fig.2 Location privacy protection method based on Grid圖2 基于網(wǎng)格的位置隱私保護方法

該方法整個查詢處理過程如下：

（1）用戶指定提供服務(wù)的服務(wù)提供商，確定一個大的查詢面積，并將其分為大小相同的網(wǎng)格單元。然后，加密包含有查詢面積、網(wǎng)格劃分及服務(wù)提供商信息的查詢。用戶所在網(wǎng)格單元及其附近網(wǎng)格單元構(gòu)成一個查詢區(qū)域，加密該區(qū)域中網(wǎng)格單元的標(biāo)識，產(chǎn)生一組加密標(biāo)識符。接下來，用戶將加密后的查詢和加密標(biāo)識符通過網(wǎng)絡(luò)發(fā)送給匹配服務(wù)器。

（2）匹配服務(wù)器緩存加密標(biāo)識符，將加密后的查詢通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)給用戶指定的服務(wù)提供商。

（3）服務(wù)提供商從服務(wù)器數(shù)據(jù)庫中選擇出合適的信息點（point of interest，POI）。對于每個選定的POI，服務(wù)提供商找到覆蓋該POI的網(wǎng)格單元，對其進行加密，并加密網(wǎng)格單元標(biāo)識產(chǎn)生加密標(biāo)識符。加密后的POI和加密標(biāo)識符一起通過網(wǎng)絡(luò)返回給匹配服務(wù)器。

（4）匹配服務(wù)器緩存加密后的POI和加密標(biāo)識符，將與（1）中用戶發(fā)送的加密標(biāo)識符相匹配的POI的子集通過網(wǎng)絡(luò)返回給用戶。

（5）用戶接收后進行解密，得到這些POI的具體位置，然后執(zhí)行一定的過濾操作，從中計算出需要的查詢結(jié)果。

2.2 使用k近鄰查詢保護位置隱私

2.2.1 k近鄰查詢過程分析

基于網(wǎng)格的位置隱私保護方法使用k近鄰查詢保護用戶位置隱私，當(dāng)中包含6個主要步驟，如圖3，其中k=3。

步驟1用戶使用網(wǎng)格劃分查詢面積。

用戶指定提供服務(wù)的服務(wù)提供商，確定一個大的查詢面積，假設(shè)它是一個正方形區(qū)域，由其左下角頂點(xa,ya)到右上角頂點(xb,yb)表示（不規(guī)則空間區(qū)域通過使用最小邊界矩形可模擬為正方形區(qū)域）。用戶不一定位于查詢面積的中心，可在該區(qū)域的任何地方。然后把查詢面積劃分為m×m個大小相同的網(wǎng)格單元，其中m由用戶指定（如圖3（a），m=6）。每個網(wǎng)格單元用(c,r)表示，c是從左到右的列索引，r是從下到上的行索引，滿足0≤c,r＜m。給定網(wǎng)格單元左下角頂點的坐標(biāo)(xc,yc)，則該網(wǎng)格單元的標(biāo)識可通過式（1）計算：

步驟2用戶產(chǎn)生一個請求。

用戶選擇一個隨機值K，派生出3個不同的值：

其中，KDF(?)是一個值推導(dǎo)方程[7]。

對于指定的服務(wù)提供商，一個加密的查詢?nèi)缡剑?）所示：

其中，SP是用戶指定的服務(wù)提供商；IBE.Encsp(.)是基于指定服務(wù)提供商的加密[8]；POI-type是POI的類型。使用網(wǎng)格劃分的查詢面積由m、(xa,ya)和(xb,yb)指定。

用戶所在網(wǎng)格單元及其附近網(wǎng)格單元構(gòu)成一個查詢區(qū)域Sc。對于Sc中的每個網(wǎng)格單元i，其標(biāo)識(ci,ri)被加密產(chǎn)生加密標(biāo)識符Ci：

其中，H(?)是抵抗沖突的哈希方程[9]；SE.Enckey(?)是在key值下的一個對稱加密算法（比如AES）。Sc中的所有網(wǎng)格單元的加密標(biāo)識符Ci構(gòu)成一個加密標(biāo)識符集Se。需要注意，用戶將確保Se中加密標(biāo)識符的排列是隨機的。

最后，用戶產(chǎn)生如下請求，然后通過網(wǎng)絡(luò)發(fā)送給匹配服務(wù)器。

Fig.3 Usingk-NN query to protect location privacy圖3 使用k近鄰查詢保護位置隱私

如圖3（a），用戶位于網(wǎng)格(3,3)，因此通過匹配服務(wù)器請求在單元(3,3)和它鄰接的網(wǎng)格單元構(gòu)成的查詢區(qū)域（圖中陰影單元表示）內(nèi)的POI。

步驟3匹配服務(wù)器處理請求。

匹配服務(wù)器接收到用戶的請求后，緩存加密標(biāo)識符集Se，將加密后的查詢轉(zhuǎn)發(fā)給服務(wù)提供商。

步驟4服務(wù)提供商處理查詢。

服務(wù)提供商接收后進行解密，得到POI-type、K和由m、(xa,ya)及(xb,yb)確定的查詢面積。然后從服務(wù)器數(shù)據(jù)庫中，在用戶指定的查詢面積內(nèi)，選擇與所需的POI-type匹配的np個POI。對于每個選定的POIj，帶有一個位置(xj,yj)(1≤j≤np)，服務(wù)提供商即可通過式（1）計算出其標(biāo)識(cj,rj)。

然后，計算如下：

其中，MACkey(?)是在值 key 下的消息認證碼[10]；Cj是POI對應(yīng)的加密標(biāo)識符；lj包含了加密表中POI的具體位置；σj是為了防止匹配服務(wù)器的某些攻擊（如篡改加密的POI）。

最后，服務(wù)提供商以式（11）所示形式將選中的POI集通過網(wǎng)絡(luò)返回給匹配服務(wù)器：

步驟5用戶確定搜索區(qū)域。

匹配服務(wù)器將服務(wù)提供商返回的加密POI的加密標(biāo)識符，與步驟2中用戶發(fā)送的加密標(biāo)識符集Se進行匹配，然后將相匹配的加密POI發(fā)送給用戶。

圖3（b）的粗線矩形內(nèi)是用戶最早的查詢區(qū)域，該區(qū)域內(nèi)包含的POI少于3個（只有p1和p2）。因此，繼續(xù)請求匹配服務(wù)器上與該區(qū)域鄰近的網(wǎng)格單元（圖3（b）中粗線矩形周圍的陰影單元），又發(fā)現(xiàn)了p3，一共發(fā)現(xiàn)了3個POI，即p1、p2和p3，如圖3（c）。

用戶通過這3個POI確定出搜索區(qū)域（圖3（c）中的圓形區(qū)域），該區(qū)域以用戶所在位置為圓心，以用戶與第3個最近的POI之間的距離為半徑。該區(qū)域與用戶還未請求的8個網(wǎng)格單元相交（即粗線矩形外的8個單元）。用戶將對這些網(wǎng)格單元發(fā)布一個新的請求。

步驟6用戶對結(jié)果進行求精。

假設(shè)用戶收到了μ個匹配的POI。對于每個匹配的POI，如 lj,σj(1≤j≤np)，用戶通過EK解密lj，即可訪問到POI的具體位置(xj,yj)。最后通過選擇k個最近的POI來確定精確的結(jié)果。如圖3（d），用戶找到了k近鄰查詢的精確結(jié)果，包括3個離其最近的POI：p1、p2和p4。

2.2.2 查詢結(jié)果更新維護

在連續(xù)的基于位置的服務(wù)中，用戶在不斷移動，需要查詢面積內(nèi)未被用戶請求過的其他網(wǎng)格單元內(nèi)的POI信息，因此需要對查詢結(jié)果進行更新維護。

該階段有以下3個主要步驟。

步驟1用戶發(fā)送更新維護請求。

用戶請求過的網(wǎng)格單元構(gòu)成緩存區(qū)域（圖4中淺色陰影網(wǎng)格單元）。搜索區(qū)域與緩存區(qū)域外的4個網(wǎng)格單元相交，它們構(gòu)成網(wǎng)格單元集Sc′，其加密標(biāo)識符集為Se′。用戶同樣產(chǎn)生一個針對這4個網(wǎng)格單元的請求，并通過網(wǎng)絡(luò)發(fā)送給匹配服務(wù)器。

步驟2匹配服務(wù)器處理請求。

Fig.4 k-NN query result maintenance圖4 k近鄰查詢查詢結(jié)果更新維護

匹配服務(wù)器已緩存了查詢面積內(nèi)的POI及其加密標(biāo)識符，因此不需要聯(lián)系服務(wù)提供商去處理結(jié)果更新請求。匹配服務(wù)器將與用戶發(fā)送的結(jié)果更新維護請求中的加密標(biāo)識符集Se′相匹配的POI返回給用戶。

步驟3用戶對結(jié)果進行求精。

用戶將匹配服務(wù)器新返回的POI和緩存區(qū)域中的POI，按照與用戶距離遠近升序排列，距離用戶最近的k個POI組成了新的查詢結(jié)果。如圖4（b），用戶從匹配服務(wù)器獲得兩個新的POI：p5和p6。距離用戶最近的3個POI組成新的查詢結(jié)果：p1、p2和p5。

2.3 方法安全性分析與證明

2.3.1 服務(wù)提供商端安全性分析與證明

本小節(jié)將證明服務(wù)提供商無法獲得用戶的具體位置。下面通過挑戰(zhàn)游戲進行詳細分析。形式上，定義一個挑戰(zhàn)者C（即匹配服務(wù)器）和一個敵手S（即惡意的服務(wù)提供商）。

挑戰(zhàn)C準(zhǔn)備系統(tǒng)參數(shù)，發(fā)送給S。S指定POI-type、網(wǎng)格劃分查詢面積以及兩個位置(x0,y0)和(x1,y1)，發(fā)送給C。C隨機選擇一個bit位b∈{0,1}，使用(xb,yb)、網(wǎng)格信息和POI-type產(chǎn)生Msg2，將Msg2作為挑戰(zhàn)密文發(fā)送給S。

猜測S提交對b的猜測b′∈{0,1}，如果b′=b，則稱敵手成功。

定義1如果對于任何服務(wù)提供商，它贏得上述挑戰(zhàn)游戲的概率都不超過1/2+negl(l)，此處negl(l)是一個可忽略函數(shù)，則一種基于網(wǎng)格的位置隱私保護方法實現(xiàn)了服務(wù)提供商端的安全。

引理1一種基于網(wǎng)格的位置隱私保護方法實現(xiàn)了服務(wù)提供商端的安全。

證明從匹配服務(wù)器到服務(wù)提供商的信息流Msg2=query。由式（3），query是在指定服務(wù)提供商的情況下，對POI-type、K和網(wǎng)格信息的加密，與用戶位置無關(guān)，因此，S在通過Msg2猜測b的時候，無法獲得任何有幫助的信息。

2.3.2 匹配服務(wù)器端安全性分析與證明

本小節(jié)將證明匹配服務(wù)器不能從來自用戶的請求或者來自服務(wù)提供商的內(nèi)容中，獲得用戶的具體位置。下面仍通過挑戰(zhàn)游戲進行詳細分析。形式上，定義一個挑戰(zhàn)者C（用戶和所有的服務(wù)提供商）和一個敵手Q（惡意的匹配服務(wù)器）。

挑戰(zhàn)給定系統(tǒng)參數(shù)，Q執(zhí)行多項式次的私有值查詢：Q提交指定服務(wù)提供商的信息給C，并接收相應(yīng)的私有值。Q接著指定POI-type、（故意的）服務(wù)提供商（其私有值已被查詢）、網(wǎng)格信息、查詢面積，及查詢面積內(nèi)的兩個用戶位置(x0,y0)和(x1,y1)，然后發(fā)送給C。C隨機選擇一個bit位b∈{0,1}，使用(xb,yb)和其他由Q指定的信息，產(chǎn)生Ms和Ms，并返回給Q。Q繼續(xù)執(zhí)行上述查詢（但不請求服務(wù)提供商的私有值）。

猜測Q提交對b的猜測b′∈{0,1}，如果b′=b，則稱敵手成功。

定義2如果對于所有的概率多項式時間，Q贏得上述挑戰(zhàn)游戲的概率無限接近于1/2，則基于網(wǎng)格的位置隱私保護方法實現(xiàn)了匹配服務(wù)器端的安全。

引理2基于網(wǎng)格的位置隱私保護方法實現(xiàn)了匹配服務(wù)器端的安全。

證明通過一系列游戲G0,G1,…,Gi證明引理2。當(dāng)Q贏得游戲Gi后，用Xi來表示。

G0：同上述挑戰(zhàn)。注意：存在兩個范圍，分別以(x0,y0)和(x1,y1)為圓心，R0和R1為半徑，這兩個范圍包含相同數(shù)目的POI。由于范圍是用戶選擇的，從而敵手是未知的。

G1：改變(HK,EK,MK)的產(chǎn)生。從空間 κH×κE×κM中隨機選擇這3個值。由KDF保證安全，得出|Pr[X1]-Pr[X0]|是可忽略的[8,11]。

G2：改變 Ms中l(wèi)j的產(chǎn)生。代替對用戶具體位置的加密，lj加密一個在值EK下隨機選擇的位置（與(x0,y0)和(x1,y1)不同）。由SE保證安全，得出|Pr[X2]- Pr[X1]|是可忽略的[12-13]。

G3：改變 Ms和Ms中所有的Ci。約束：在相同網(wǎng)格單元內(nèi)的POI與網(wǎng)格單元共享相同的hi。由SE保證安全，得出|Pr[X3]- Pr[X2]|是可忽略的[12-13]。

G4：改變用戶端消息的請求，成為長度相同的隨機數(shù)組的加密。由IBE的安全，得出|Pr[X4]-Pr[X3]|是可忽略的[8]。在G4中，Ms和Ms與C選擇的b是獨立的，因此Q能夠成功地提交正確猜測的可能性至多是1 2，由此得出是可忽略的。

2.3.3 查詢結(jié)果完整性分析與證明

本小節(jié)將證明匹配服務(wù)器不能修改返回給用戶的任何一個POI的信息，也無法新增虛假POI。下面再次通過挑戰(zhàn)游戲進行詳細分析。形式上，定義一個挑戰(zhàn)者C（用戶和所有的服務(wù)提供商）和一個敵手Q（惡意的匹配服務(wù)器）。

挑戰(zhàn)給定系統(tǒng)參數(shù)，Q執(zhí)行多項式次的以下查詢。私有值查詢：Q提交指定的服務(wù)提供商信息，然后被返回相應(yīng)的私有值。服務(wù)查詢：Q產(chǎn)生Msg1并發(fā)送給服務(wù)提供商，接著接收到Msg3。Q提交POI-type、（故意的）服務(wù)提供商（其私有值還未被查詢）、網(wǎng)格信息、查詢面積，以及用戶的位置(x,y)。C產(chǎn)生Ms和Ms，發(fā)送給Q。Q產(chǎn)生Ms。

猜測如果Ms?Msg4，但用戶接受了Ms，則稱敵手成功。

定義3如果在概率多項式時間內(nèi)，Q無法以不可忽略的概率贏得上述挑戰(zhàn)游戲，則基于網(wǎng)格的位置隱私保護方法實現(xiàn)了查詢結(jié)果的完整性。

引理3基于網(wǎng)格的位置隱私保護方法實現(xiàn)了查詢結(jié)果的完整性。

證明通過一系列游戲G0,G1,…,Gi證明引理3。當(dāng)敵手Q贏得游戲Gi后，用Xi來表示。

G0：同引理2。

G1：改變 Ms和Ms的產(chǎn)生。代替輸入一個隨機的K然后由KDF輸出，MK從κM中隨機選擇。由KDF保證安全，得出|Pr[X1]-Pr[X0]|是可忽略的[8,11]。

通過Q去構(gòu)造一個算法τ，該算法破壞了MAC的強不可偽造性[8,11]。給出預(yù)言機OM，τ產(chǎn)生了包含IBE值的系統(tǒng)參數(shù)。然后借助Q輸入系統(tǒng)參數(shù)，開始下面的查詢。私有值查詢：給出服務(wù)提供商，τ使用IBE產(chǎn)生服務(wù)提供商的私有值，返回給Q。服務(wù)查詢：給出Msg1=SP,request,Se，τ使用服務(wù)提供商的私有值（可以從IBE計算出來）解密查詢，然后獲得POI-type、K、m、(xa,ya)和(xb,yb)。根據(jù)服務(wù)提供商規(guī)定的策略，產(chǎn)生Msg3并返回給Q。

當(dāng)Q接收到Msg3后，輸出（故意的）服務(wù)提供商、POI-type、網(wǎng)格信息、查詢面積和用戶的位置(x,y)。τ然后使用Q給出的信息產(chǎn)生Ms和Ms，如下：

對于所有的POI，τ使用嵌入在UMsg*中的K推導(dǎo)出的值來計算Ci和li。然后發(fā)送(Ci,li)給預(yù)言機OM，被返回 σi=MACMK(Ci,li)。

3 實驗與分析

3.1 模擬實驗環(huán)境

（1）軟硬件環(huán)境

硬件環(huán)境：Intel?CoreTMi5-4590 CPU處理器，主頻3.30 GHz，內(nèi)存4.00 GB RAM。

軟件環(huán)境：64位Windows 7操作系統(tǒng)，編譯環(huán)境Java 1.7，編程語言采用Java語言。

（2）實驗數(shù)據(jù)

本實驗使用Thomas Brinkhoff軌跡生成器[14]生成模擬移動對象數(shù)據(jù)，模擬生成20 000個移動用戶在某市城區(qū)1 606km2的真實交通網(wǎng)中的運動軌跡作為數(shù)據(jù)集。使用了10 000個POI，k近鄰查詢中默認的POI請求數(shù)為k=10，可信第三方模型的k-匿名度為200。

使用OpenSSL（http://www.openssl.org）、GMP（http://www.gmplib.org）和PBC（http://crypto.stan ford.edu/pbc/）進行基于身份的加密。

3.2 實驗結(jié)果分析

3.2.1 POI數(shù)目增加時兩種方法性能對比分析

圖5顯示了隨著服務(wù)提供商數(shù)據(jù)庫中POI的數(shù)目從10增加到100 000，其他參數(shù)不變，基于網(wǎng)格的位置隱私保護方法（STTP）和可信第三方模型（TTP）的性能對比。

（1）計算開銷分析

基于網(wǎng)格的位置隱私保護方法在各種情況下，其計算開銷均小于可信第三方模型的計算開銷，前者的性能好于后者。

基于網(wǎng)格劃分的隱私保護方法中，隨著POI數(shù)目的增多，計算開銷也在增大。因為服務(wù)提供商在接收到用戶請求并解密后，得到查詢面積，然后在該查詢面積內(nèi)，從數(shù)據(jù)庫中選擇相應(yīng)的POI。查詢面積內(nèi)的POI數(shù)目增多，因此計算開銷會增大。

可信第三方模型中，當(dāng)POI的數(shù)目在1 000以上時，隨著POI數(shù)目的增加，它必須擴大匿名區(qū)域的面積，因此大幅增加了計算開銷。

（2）通信開銷分析

當(dāng)POI數(shù)目較?。?0和100）時，可信第三方模型的通信開銷比基于網(wǎng)格的位置隱私保護方法稍大，因為其匿名區(qū)域非常小，POI數(shù)目也少。當(dāng)POI數(shù)目在1 000以上時，其通信開銷增長得更快，也比基于網(wǎng)格的位置隱私保護方法的通信開銷更大。

3.2.2 移動用戶數(shù)增加時兩種方法性能對比分析

圖6顯示了隨著移動用戶數(shù)從10 000增加到50 000，其他參數(shù)不變，兩種方法的性能對比。

（1）計算開銷分析

Fig.5 Performance comparison of two schemes when the number of POIs is increased圖5 POI數(shù)目增加時兩種方法性能對比

Fig.6 Performance comparison of two schemes when the number of mobile users is increased圖6 移動用戶數(shù)增加時兩種方法性能對比

基于網(wǎng)格的位置隱私保護方法的計算開銷保持不變，始終在1 ms以下，因為它與移動用戶數(shù)相獨立，只與查詢用戶指定的查詢面積有關(guān)。

可信第三方模型的計算開銷比基于網(wǎng)格的位置隱私保護方法的高10～20倍。隨著移動用戶數(shù)的遞增，可信第三方模型的匿名區(qū)域就越小，計算開銷在逐漸減少。

（2）通信開銷分析

基于網(wǎng)格的位置隱私保護方法的通信開銷保持不變，且遠遠低于可信第三方模型。

3.2.3 k-匿名度增加時兩種方法性能對比分析

圖7顯示了k-匿名度增加時兩種方法的性能對比。基于網(wǎng)格的位置隱私保護方法通過加密標(biāo)識符來保護用戶位置隱私，其性能不受k-匿名度變化的影響，因此計算開銷和通信開銷保持不變。

當(dāng)k增大時，可信第三方模型的計算開銷增長得很快，因為可信第三方模型必須產(chǎn)生更大的匿名區(qū)域來滿足用戶位置隱私保護要求。其匿名區(qū)域的擴大，同樣導(dǎo)致返回給用戶的POI集更大，通信開銷因此增長很快。

3.2.4 用戶所需POI數(shù)增加時的性能分析

圖8顯示了用戶所需POI數(shù)（即k-近鄰查詢中的k值）從5增加到500，其他參數(shù)不變，基于網(wǎng)格劃分的隱私保護方法（STTP）的性能分析。

（1）計算開銷分析

Fig.7 Performance comparison of two schemes whenk-anonymity level is increased圖7 k-匿名度增加時兩種方法性能對比

Fig.8 Performance analysis of STTP when the number of POIs required is increased圖8 用戶所需POI數(shù)增加時STTP的性能分析

隨著用戶所需POI數(shù)的增多，基于網(wǎng)格劃分的隱私保護方法的計算開銷也在增加。其增加只影響了用戶和匹配服務(wù)器，因為隨著用戶所需POI數(shù)的增多，用戶和匹配服務(wù)器上的計算開銷就更大。由于用戶所需POI數(shù)的增多，沒有改變查詢面積的大小，而服務(wù)提供商的負載只與查詢面積的大小有關(guān)，從而服務(wù)提供商的計算開銷保持不變。

（2）通信開銷分析

隨著用戶所需POI數(shù)的增多，通信開銷也增加了。然而，只增加了用戶端的通信開銷，因為用戶請求了近鄰處更多的POI。

4 結(jié)束語

針對可信第三方模型中匿名器若被攻擊者攻破，將會造成用戶位置信息泄露的問題，本文提出了一種基于網(wǎng)格的位置隱私保護方法，它能夠有效地保護用戶的位置隱私，且性能明顯比可信第三方模型更好。

本文只分析了基于網(wǎng)格的位置隱私保護方法如何使用k近鄰查詢保護用戶的位置隱私，該方法在其他空間查詢下的情況，如范圍查詢、反近鄰查詢[15]和密度查詢[16]等，是下一步研究的內(nèi)容。

[1]Krishnan RB,Prasad N H,Gokul U,et al.Privacy preserving location based services[J].International Journal of Engineering Science and Computing,2016,6(3):2710-2714.

[2]Liutkauskas V,Matulis D,Pl??tysR.Location based services[J].Elektronika ir Elektrotechnika,2004,52(3):35-40.

[3]Song D,Sim J,Park K,et al.Aprivacy-preserving continuous location monitoring system for location-based services[J].International Journal of Distributed Sensor Networks,2015:14.

[4]Relish M,Young P,Vogel V,et al.Trusted third party for medication adherence[J].Circulation:Cardiovascular Quality and Outcomes,2016,9(S2):A266.

[5]Pooranian Z,Shojafar M,Abawajy J H,et al.An efficient meta-heuristic algorithm for grid computing[J].Journal of Combinatorial Optimization,2015,30(3):413-434.

[6]Carpenter F,Manson D,Jeffery K,et al.Grid cells form a global representation of connected environments[J].Current Biology,2015,25(9):1176-1182.

[7]IEEE.Std 1363TM-2000 Standard specifications for public-key cryptography[S].New York,2000.

[8]Susilo W,Guo Fuchun,Mu Yi.Efficient dynamic threshold identity-based encryption with constant-size ciphertext[J].Theoretical Computer Science,2016,609:49-59.

[9]Ye Junwei.Analysis of hash table conflict processing method[J].Science&Technology Vision,2014(6):230.

[10]Smart N P.Hash functions,message authentication codes and key derivation functions[M]//Cryptography Made Simple.Switzerland:Springer International Publishing,2016:271-294.

[11]Yau S S,An H G.Anonymous service usage and payment in service-based systems[C]//Proceedings of the 13th International Conference on High Performance Computing Communication,Banff,Canada,Sep 2-4,2011.Washington:IEEE Computer Society,2011:714-720.

[12]Gao Shang,Krogstie J,Thingstad T,et al.Amobile service using anonymous location-based data:finding reading rooms[J].The International Journal of Information and Learning Technology,2015,32(1):32-44.

[13]Jager T.Verifiable random functions from weaker assumptions[C]//LNCS 9015:Proceedings of the 12th Theory of Cryptography Conference,Warsaw,Poland,Mar 23-25,2015.Berlin,Heidelberg:Springer,2015:121-143.

[14]Panagiotakis C,Pelekis N,Kopanakis I.Segmentation and sampling of moving object trajectories based on representativeness[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(7):1328-1343.

[15]HidayatA,Cheema MA,Taniar D.Relaxed reverse nearest neighbors queries[C]//LNCS 9239:Proceedings of the 14th International Symposium on Spatial and Temporal Databases,Hong Kong,China,Aug 26-28,2015.Switzerland:Springer International Publishing,2015:61-79.

[16]Heendaliya L,Wisely M,Lin Dan,et al.Influence-aware predictive density queries under road-network constraints[C]//LNCS 9239:Proceedings of the 14th International Symposium on Spatial and Temporal Databases,Hong Kong,China,Aug 26-28,2015.Switzerland:Springer International Publishing,2015:80-97.

附中文參考文獻：

[9]葉軍偉.哈希表沖突處理方法淺析[J].科技視界,2014(6):230.

Location Privacy Protection Method Based on Grid*

LI Xiangdong1,ZHANG Shaobo1,2,GUO Min3,WANG Guojun1,4+
1.School of Information Science and Engineering,Central South University,Changsha 410083,China
2.School of Computer Science and Engineering,Hunan University of Science and Technology,Xiangtan,Hunan 411201,China
3.School of Software,Central South University,Changsha 410075,China
4.College of Computer Science and Educational Software,Guangzhou University,Guangzhou 510006,China
+Corresponding author:E-mail:csgjwang@gmail.com

LI Xiangdong,ZHANG Shaobo,GUO Min,et al.Location privacy protection method based on grid.Journal of Frontiers of Computer Science and Technology,2017,11(8)：1258-1268.

In the location based service(LBS),trusted third party model is the main model of current location privacy protection.The anonymous server in this model knows the user's location,if it is attacked,which will cause the leakage of the user's location information.Therefore,this paper puts forward a location privacy protection method based on grid.The method replaces the trusted third party(TTP)as a semi-trusted third party(STTP),which is a matching server.The matching server only matches and caches,and cannot know the user's location,so as to protect user's location privacy better.Security analysis shows that this method can effectively protect the user's location privacy.At the same time,this paper compares this method with trusted third party model.The experimental results show that the performance of this method is better than trusted third party model.

un was born in 1970.He

the Ph.D.degree in computer science from Central South University in 2002.Now he is a professor and Ph.D.supervisor at Guangzhou University and Central South University.His research interests include system security,privacy protection,trusted computing and big data security. 王國軍（1970—），男，湖南長沙人，2002年于中南大學(xué)獲得博士學(xué)位，現(xiàn)為廣州大學(xué)和中南大學(xué)教授、博士生導(dǎo)師，主要研究領(lǐng)域為系統(tǒng)安全，隱私保護，可信計算，大數(shù)據(jù)安全。

LI Xiangdong was born in 1992.He is an M.S.candidate at Central South University.His research interests include information security and privacy protection.李向東（1992—），男，山西呂梁人，中南大學(xué)碩士研究生，主要研究領(lǐng)域為信息安全，隱私保護。

ZHANG Shaobo was born in 1979.He is a Ph.D.candidate at Central South University.His research interests include privacy protection and cloud computing security.張少波（1979—），男，湖南邵陽人，中南大學(xué)博士研究生，主要研究領(lǐng)域為隱私保護，云計算安全。

GUO Min was born in 1992.She is an M.S.candidate at Central South University.Her research interests include software engineering,trusted computing and privacy protection.郭敏（1992—），女，山東濟南人，中南大學(xué)碩士研究生，主要研究領(lǐng)域為軟件工程，可信計算，隱私保護。

A

：TP309

*The National Natural Science Foundation of China under Grant Nos.61472451,61272151,61402161,61502163(國家自然科學(xué)基金).Received 2016-07,Accepted 2016-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-10-18,http://www.cnki.net/kcms/detail/11.5602.TP.20161018.1622.010.html

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology 1673-9418/2017/11(08)-1258-11

10.3778/j.issn.1673-9418.1607017

E-mail:fcst@vip.163.com

http://www.ceaj.org

Tel:+86-10-89056056

Key words:location-based service;location privacy protection;grid;semi-trusted third party