基于網格的位置隱私保護方法*

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

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

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

3.中南大學 軟件學院，長沙 410075

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

基于網格的位置隱私保護方法*

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

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

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

3.中南大學 軟件學院，長沙 410075

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

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

基于位置的服務；位置隱私保護；網格；半可信第三方

1 引言

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

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

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

可信第三方模型有以下幾個缺點：（1）若匿名器被攻擊者攻破，將會造成用戶位置信息的泄露，甚至會影響整個結構的穩定和安全；（2）若用戶數量密度較大時，所選的匿名區域就比較小，用戶位置就比較容易確定；（3）當大量移動用戶頻繁更新位置信息時，匿名區域需要擴大，大幅增加了查詢處理的開銷；（4）在連續的基于位置的服務中，用戶位置在不斷變化，匿名器和服務提供商的計算開銷和通信開銷較大。

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

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

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

2 基于網格的位置隱私保護方法

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

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

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

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

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

（2）匹配服務器緩存加密標識符，將加密后的查詢通過網絡轉發給用戶指定的服務提供商。

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

（4）匹配服務器緩存加密后的POI和加密標識符，將與（1）中用戶發送的加密標識符相匹配的POI的子集通過網絡返回給用戶。

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

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

2.2.1 k近鄰查詢過程分析

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

步驟1用戶使用網格劃分查詢面積。

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

步驟2用戶產生一個請求。

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

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

對于指定的服務提供商，一個加密的查詢如式（3）所示：

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

用戶所在網格單元及其附近網格單元構成一個查詢區域Sc。對于Sc中的每個網格單元i，其標識(ci,ri)被加密產生加密標識符Ci：

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

最后，用戶產生如下請求，然后通過網絡發送給匹配服務器。

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

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

步驟3匹配服務器處理請求。

匹配服務器接收到用戶的請求后，緩存加密標識符集Se，將加密后的查詢轉發給服務提供商。

步驟4服務提供商處理查詢。

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

然后，計算如下：

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

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

步驟5用戶確定搜索區域。

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

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

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

步驟6用戶對結果進行求精。

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

2.2.2 查詢結果更新維護

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

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

步驟1用戶發送更新維護請求。

用戶請求過的網格單元構成緩存區域（圖4中淺色陰影網格單元）。搜索區域與緩存區域外的4個網格單元相交，它們構成網格單元集Sc′，其加密標識符集為Se′。用戶同樣產生一個針對這4個網格單元的請求，并通過網絡發送給匹配服務器。

步驟2匹配服務器處理請求。

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

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

步驟3用戶對結果進行求精。

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

2.3 方法安全性分析與證明

2.3.1 服務提供商端安全性分析與證明

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

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

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

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

引理1一種基于網格的位置隱私保護方法實現了服務提供商端的安全。

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

2.3.2 匹配服務器端安全性分析與證明

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

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

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

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

引理2基于網格的位置隱私保護方法實現了匹配服務器端的安全。

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

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

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

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

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

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

2.3.3 查詢結果完整性分析與證明

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

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

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

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

引理3基于網格的位置隱私保護方法實現了查詢結果的完整性。

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

G0：同引理2。

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

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

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

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

3 實驗與分析

3.1 模擬實驗環境

（1）軟硬件環境

硬件環境：Intel?CoreTMi5-4590 CPU處理器，主頻3.30 GHz，內存4.00 GB RAM。

軟件環境：64位Windows 7操作系統，編譯環境Java 1.7，編程語言采用Java語言。

（2）實驗數據

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

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

3.2 實驗結果分析

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

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

（1）計算開銷分析

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

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

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

（2）通信開銷分析

當POI數目較小（10和100）時，可信第三方模型的通信開銷比基于網格的位置隱私保護方法稍大，因為其匿名區域非常小，POI數目也少。當POI數目在1 000以上時，其通信開銷增長得更快，也比基于網格的位置隱私保護方法的通信開銷更大。

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

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

（1）計算開銷分析

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

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

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

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

（2）通信開銷分析

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

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

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

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

3.2.4 用戶所需POI數增加時的性能分析

圖8顯示了用戶所需POI數（即k-近鄰查詢中的k值）從5增加到500，其他參數不變，基于網格劃分的隱私保護方法（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數增加時STTP的性能分析

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

（2）通信開銷分析

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

4 結束語

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

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

[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年于中南大學獲得博士學位，現為廣州大學和中南大學教授、博士生導師，主要研究領域為系統安全，隱私保護，可信計算，大數據安全。

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—），男，山西呂梁人，中南大學碩士研究生，主要研究領域為信息安全，隱私保護。

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—），男，湖南邵陽人，中南大學博士研究生，主要研究領域為隱私保護，云計算安全。

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—），女，山東濟南人，中南大學碩士研究生，主要研究領域為軟件工程，可信計算，隱私保護。

A

：TP309

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

CNKI網絡優先出版: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