Geohash編碼的k匿名位置隱私保護方案

殷鳳梅，陳 鴻

合肥師范學院計算機學院，安徽 合肥 230601

0 引言

基于位置的服務（location based service，LBS）是通過無線電通信技術(shù)或全球定位系統(tǒng)（global positioning system，GPS）獲取移動終端用戶的位置信息，在地理信息系統(tǒng)（geographic information sys?tem，GIS）的支持下，為移動終端用戶提供相應服務［1］。隨著通信技術(shù)和GPS的發(fā)展，LBS得到廣泛的應用。人們在享受交通導航、網(wǎng)上訂票等LBS帶來便捷的同時，也在承擔著個人位置隱私泄露的風險。攻擊者能夠從位置信息中，推測出用戶的家庭地址、工作地點、常去的服務場所等隱私信息，了解到用戶的行動軌跡［2］。隨著LBS使用規(guī)模的不斷增長，位置隱私的安全問題成為了重要的研究課題［3，4］。

位置隱私保護按照體系結(jié)構(gòu)大致分為兩類：基于匿名中心的位置隱私保護方案［5，6］和基于移動終端的位置隱私保護方案［7~11］。在基于匿名中心的位置隱私保護方案中，用戶和LBS服務器之間，引入可信的匿名中心，匿名中心通過隱私保護技術(shù)［12，13］將用戶的位置服務信息匿名化，再發(fā)送給LBS服務器請求服務，并將LBS服務器反饋的服務結(jié)果返回給用戶。在這類方案中，匿名中心承擔著主要的計算和通信工作，成為整個系統(tǒng)的安全瓶頸，一旦被攻克，所有用戶的隱私信息都將被泄露。Peng等［14］使用半可信匿名中心替代匿名中心，但半可信匿名中心依舊會成為系統(tǒng)的安全瓶頸。為了避免單匿名中心的安全瓶頸問題，張少波等［3］引入多個分布式匿名服務器，但該方案會引起系統(tǒng)開銷的增加。隨著移動終端不斷智能化，計算和存儲能力大大增強，出現(xiàn)了基于移動終端的位置隱私保護方案。這類方案不再設置匿名中心，移動終端用戶直接與LBS服務器通信，獲得請求查詢服務的結(jié)果，從而避免了匿名中心的安全瓶頸和單點泄露問題。很多學者基于移動終端展開位置隱私保護研究，例如，李維皓等［8］使用移動模型預測用戶移動軌跡，利用時空關(guān)聯(lián)性生成偽位置來避免位置隱私泄露。Hayashida等［9］利用旅行推銷商貪心算法生成虛假軌跡來隱藏用戶的隱私位置。Niu等［10］使用背景信息中的歷史查詢概率，并盡量選擇相隔較遠的匿名位置來實現(xiàn)位置隱私保護。李維皓等［11］在背景信息的基礎上，考量了用戶和LBS服務器短期緩存的查詢記錄，實現(xiàn)自關(guān)聯(lián)隱私保護算法。

位置隱私保護通常使用k匿名技術(shù)，它是由Gruteser等［15］最先提出的。該技術(shù)將用戶的真實位置與其他k-1個虛假位置組成匿名位置集，發(fā)送給LBS服務器請求服務，如此一來，用戶的真實位置被猜測成功的概率為1/k，從而有效地實現(xiàn)了用戶位置的匿名。其中，k代表隱私度，由用戶根據(jù)需求確定數(shù)值。為了構(gòu)建匿名位置集，通常需要查詢歷史請求記錄，可是檢索龐大的歷史記錄，時間開銷較大，使得位置服務失去了即時的優(yōu)越性。為了給用戶提供即時的位置服務，本文借助Geohash編碼［16］，實現(xiàn)了面向移動終端用戶的k匿名位置隱私保護方案。

1 基本概念

1.1 區(qū)間區(qū)域

lat代表緯度（Latitude），lng代表經(jīng)度（Longi?tude）。通常約定緯度在前，經(jīng)度在后，經(jīng)度與緯度組成地理坐標系統(tǒng)（geographic coordinate system，GCS），簡稱坐標系統(tǒng)。GCS使用三維球面來定義地球表面位置，能夠標示地球上的任何一個位置。經(jīng)度的區(qū)間范圍為［-180°，180°］，東經(jīng)為正數(shù)，西經(jīng)為負數(shù)；緯度的區(qū)間范圍為［-90°，90°］，北緯為正數(shù)，南緯為負數(shù)。

如果將用戶的經(jīng)緯度坐標，泛化到一個經(jīng)緯度區(qū)間（［lat1，lat2］，［lng1，lng2］），那么這個區(qū)間所表示的區(qū)域稱為區(qū)間區(qū)域。

一個用戶的經(jīng)緯度坐標（30.299 4°，70.153 6°），泛化后的區(qū)間區(qū)域（［30.273°，30.311 9°］，［70.130 6°，70.176 6°］），如圖1中紅色方框。泛化的方法將在2.3節(jié)描述。

圖1 位置坐標泛化后的區(qū)間區(qū)域Fig.1 Interval region after generalization of position coordinates

1.2 Geohash編碼

Geohash算法［17］將二維經(jīng)緯度坐標轉(zhuǎn)換為一維字符串的地理位置編碼。Geohash算法利用數(shù)據(jù)結(jié)構(gòu)的二分法，沿著經(jīng)度和緯度兩個不同方向，交替地二分地球表面。具體過程如下。

Step 1經(jīng)度區(qū)間的劃分。對［-180°，180°］進行二分，區(qū)間的中位值=（-180°+180°）/2=0°，小于中位值則為左區(qū)間［-180°，0°），標記為0；否則將右區(qū)間［0°，180°］標記為1。采用同樣的方法繼續(xù)對左右經(jīng)度區(qū)間進行二分，直到需要的精度停止，得到一個由0和1組成的經(jīng)度編碼序列。

Step 2緯度區(qū)間的劃分。對［-90°，90°］進行二分，區(qū)間的中位值=（-90°+90°）/2=0°，小于中位值則為左區(qū)間［-90°，0°），標記為0；否則將右區(qū)間［0°，90°］標記為1。采用同樣的方法繼續(xù)對左右緯度區(qū)間進行二分，直到需要的精度停止，得到一個由0和1組成的緯度編碼序列。

Step 3交錯排列。按照偶數(shù)位放經(jīng)度編碼，奇數(shù)位放緯度編碼，將經(jīng)度字符串和緯度字符串合并成一個新的編碼序列。

Step 4分組轉(zhuǎn)換。將新的編碼序列從右向左，每5位成一組，最后一組不夠5位，左邊補0。每組的5位編碼轉(zhuǎn)換成一個十進制數(shù)。

Step 5Base32編碼。對照Base32編碼表，將每個十進制數(shù)轉(zhuǎn)換成Base32碼，按序存放各個Base32碼，形成Geohash編碼。

例如，對圖1中的用戶經(jīng)緯度坐標（30.299 4°，70.153 6°），緯度30.299 4°按照表1進行緯度編碼，得到二進制編碼序列101010110001011，經(jīng)度70.153 6°按照表2進行經(jīng)度編碼，得到二進制編碼序列101100011110001。緯度編碼和經(jīng)度編碼交錯排列后，形成新的二進制編碼序列11001 11001 00011 11010 10010 00111，轉(zhuǎn)換成十進制數(shù)序列25 25 3 26 18 7。按照表3將十進制數(shù)序列轉(zhuǎn)換成Geo?hash編碼tt3uk7。

表1 緯度編碼Table 1 Latitude Encoding

表2 經(jīng)度編碼Table 2 Longitude Encoding

表3 Base32編碼表Table 3 Base32 Elphabet

Geohash編碼代表的是一個矩形區(qū)域，編碼的長度越短，矩形區(qū)域越大；編碼的長度越長，矩形區(qū)域越小。當緯度相同時，經(jīng)度每隔0.000 01°，寬度相差大約1 m；每隔0.000 1°，寬度相差大約10 m。以此類推，每隔0.1°，寬度相差大約10 000 m。當經(jīng)度相同時，緯度每隔0.000 01°，寬度相差大約1.1 m；每隔0.000 1°，寬度相差大約11 m。以此類推，每隔0.1°，寬度相差大約11 132 m。可見，Geohash編碼長度越長，所表示的范圍就越精確。例如，編碼長度為5時，精度大約為4 900 m；編碼長度為8時，精度大約為19 m。Geohash編碼長度取決于位置隱私保護的強度，由用戶指定。用戶想獲得較高的位置隱私保護強度，矩形區(qū)域需要較大，對應的編碼長度就短一些。

1.3 雙線性映射

對于階為q的加法循環(huán)群G1和乘法循環(huán)群GT，雙線性映射e：G1×G1→GT具有如下性質(zhì)：

1）雙線性：任意的Q1，Q2∈G1，x，y∈?p，滿足e(x Q1，yQ2)=e(Q1，Q2)xy；

2）可 計 算 性：任 意 的Q1，Q2∈G1，均 可 計 算e(Q1，Q2)；

3）非退化性：任意的Q1，Q2∈G1，滿足e(Q1，Q1)≠I，I為GT中的單位元；

4）對稱性：任意的Q1，Q2∈G1，滿足e(Q1，Q2)=e(Q2，Q1)。

1.4 雙線性映射的相關(guān)問題假設

1）橢圓曲線離散對數(shù)(elliptic curve discrete logarithm,ECDL)問題

橢圓曲線上階為q的循環(huán)群G，P為G的生成元，給定Q=x P∈G（隨機數(shù)x∈?*q值未知），敵手在多項式時間內(nèi)計算x。若滿足AdvECDLA=Pr[A(Q，P)=x]≥ε，則說明：不存在概率多項式時間算法A，以不可忽略的概率ε解決ECDL問題。

2）雙線性Diffie?Hellman(bilinear Diffie?Hell?man,BDH)問題

對于階為q的加法循環(huán)群G1和乘法循環(huán)群GT，P為G1的生成元，雙線性映射e：G1×G1→G T，給定輸 入(P，x P，yP，zP)∈G1（隨 機 數(shù)x，y，z∈?*q值 未知），敵手在多項式時間內(nèi)計算e(P，P)xyz∈GT。若滿足

則說明：不存在概率多項式時間算法A，以不可忽略的概率ε解決BDH問題。

3）判定雙線性Diffie?Hellman(decisional bilinear Diffie?Hellman,DBDH)問題

對于階為q的加法循環(huán)群G1和乘法循環(huán)群GT，P為G1的生成元，雙線性映射e：G1×G1→G T，給定輸入(P，x P，yP，zP，C)（隨機數(shù)x，y，z∈?*q值未知，C∈GT），敵手在多項式時間內(nèi)判斷等式C=e(P，P)xyz是否成立。若滿足

則說明：不存在概率多項式時間算法A，以不可忽略的概率ε解決DBDH問題。

1.5 位置熵

匿名區(qū)域AA中包括k個候選位置，假設各個候選位置被檢索的概率分別為Q i(i∈[1，k])，則每個候，位選位置成為真實位置的概率為如果候選位置熵［18］為置的位置熵越大，隱私度就越高。

2 k匿名位置隱私保護方案

本文提出的位置隱私保護方案由兩類實體：移動終端用戶（mobile user，MU）和LBS服務器組成，如圖2所示。

圖2 位置隱私保護系統(tǒng)模型Fig.2 System model of location privacy preservation

位置隱私保護方案采用k匿名機制，兩類實體之間的操作步驟和信息交流如下。

Step 1MU通過智能手機向GPS請求自身位置，獲得經(jīng)緯度坐標（lat，lng）后，在周圍生成k-1個虛假位置和虛假查詢，然后將自身位置、真實查詢和k-1個虛假位置、虛假查詢，組成k個查詢請求，發(fā)送給LBS服務器。

Step 2LBS服務器收到查詢請求后，獲取k個查詢結(jié)果，加密查詢結(jié)果并通過基站返回給MU。

Step 3MU收到加密的查詢結(jié)果后，解密獲得想要的查詢結(jié)果。

2.1 系統(tǒng)初始化

對于LBS服務器，按照下面的步驟獲取系統(tǒng)私鑰，公開系統(tǒng)公共參數(shù)。

Step 1選擇一個大素數(shù)p，q是p-1的大素因子，階為q的加法循環(huán)群G1和乘法循環(huán)群G2，P為G1的生成元，存在雙線性映射e：G1×G1→G2。

Step 2設置3個哈希函數(shù)H2：G2→{0，1}n，H3：SHA 256哈希函數(shù)。其中，n是一個整數(shù)，{0，1}*是任意長度的二進制字符串。

Step 3選取一個隨機數(shù)s∈?q*作為系統(tǒng)的私鑰并保密存儲，計算對應的公鑰PK=s?P。Step 4g是?q*上的q階元素，將S=g smodp保密，計算驗證參數(shù)SPK=S?P，以便用戶驗證注冊信息。

Step 5公 開 系統(tǒng) 公 共 參 數(shù)：｛G1，G2，H1，H2，q，P，e，n，PK，SPK｝。

2.2 用戶注冊

移動終端用戶MU需要向系統(tǒng)注冊，注冊過程如下。

Step 1MU將k個身份信息組成的集合ID=｛ID1，ID2，…，IDu，…，IDk｝發(fā)送給LBS服務器進行注冊申請。其中，IDu作為MU的真實身份，隱藏在集合ID中，u∈[1，k]，其值由MU指定。

Step 2LBS服務器選擇隨機數(shù)IDanony∈?q*，為每個IDi計算假名PIDi=H3(IDi+IDanony)、公鑰PKIDi=H1(IDi)和私鑰SKIDi=S?PKIDi，生成信息Reg=｛（PID1，PKID1，SKID1），（PID2，PKID2，SKID2），…，（PIDk，PKIDk，SKIDk）｝，并通過安全信道反饋給MU。

Step 3MU收到Reg后先計算PKIDu=H1(IDu)，然 后 驗 證 等 式e(SKIDu，P)=e(PKIDu，SPK)是否成立。若成立，則MU收到了正確的假名、公鑰和私鑰；否則，MU轉(zhuǎn)Step 1重新注冊。

2.3 位置泛化

MU通過GPS獲得自己的經(jīng)緯度坐標位置（lat，lng）后，將坐標位置泛化到一個區(qū)間區(qū)域內(nèi)。MU根據(jù)自身所處的位置是在人口密集的城市還是在稀疏的鄉(xiāng)村，選擇不同大小的隨機數(shù)來構(gòu)建區(qū)間區(qū)域。若處在人口較為稀疏的鄉(xiāng)村，為了提高位置隱私保護的強度，MU匿名的泛化區(qū)域設置大一點，隨機數(shù)選擇也大一些。反之，若處在人口較為密集的城市，為了提高查詢服務的精度，MU匿名的泛化區(qū)域設置小一點，隨機數(shù)選擇也小一些。

1）人口較為稀疏的鄉(xiāng)村：從［0°~0.025°］區(qū)間中隨機選擇4個隨機數(shù)r1，r2，r3，r4，為了避開區(qū)間的對稱性猜測，泛化區(qū)間時不同時向前或向后波動隨機數(shù)，泛化后的區(qū)間區(qū)域可以表示為（［lat-r1，lat+r2］，［lng-r3，lng+r4］）。從1.2節(jié)可知，經(jīng)度0.025°大約對應2.5 km的距離，緯度0.025°大約對應2.75 km的距離。若經(jīng)緯度向前后各波動0.025°，泛化的區(qū)間范圍大約為（0.025×2/0.025）×2.5×（0.025×2/0.025）×2.75=27.5 km2。通常，隨機數(shù)的產(chǎn)生遵循正態(tài)分布，即在區(qū)間的中位值（0°+0.025°）/2=0.0125°左右波動，而接近區(qū)間的端點0°和0.025°較少。因此，按照平均波動0.012 5°來計算，泛化的區(qū)間范圍平均為（0.0125×2/0.025）×2.5×（0.0125×2/0.025）×2.75=6.875 km2。

2）人口較為密集的城市：從［0°~0.01°］區(qū)間中隨機選擇4個隨機數(shù)r1，r2，r3，r4，泛化后的區(qū)間區(qū)域（［lat-r 1，lat+r 2］，［lng-r 3，lng+r 4］）。經(jīng)度0.01°大約對應1 km的距離，緯度0.01°大約對應1.1 km的距離。若經(jīng)緯度向前后各波動0.01°，泛化的區(qū)間范圍大約為（0.01×2/0.01）×1×（0.01×2/0.01）×1.1=4.4 km2。通常，隨機數(shù)在區(qū)間的中位值（0°+0.01°）/2=0.005°左右波動，而接近區(qū)間的端點0°和0.01°較少。因此，按照平均波動0.005°來計算，泛化的區(qū)間范圍 平均為（0.005×2/0.01）×1×（0.005×2/0.01）×1.1=1.1 km2。

2.4 反向檢索位置

MU按照1.2節(jié)的方法生成Geohash編碼，其對應一個矩形區(qū)間，如圖3所示。該區(qū)間內(nèi)的所有位置，其Geohash編碼相同。

圖3 Geohash位置區(qū)間Fig.3 Geohash location interval

檢查相同Geohash編碼的位置個數(shù)，如果與k值相等，則返回這k個位置組成的匿名位置集C。如果小于k值，則擴大到相鄰的8個矩形區(qū)域。倘若擴大區(qū)域后匿名位置的個數(shù)仍然小于k值，可以再擴大一圈矩形區(qū)間，當然這種情況一般很少出現(xiàn)。如果大于k值或經(jīng)過擴大區(qū)域后大于k值，轉(zhuǎn)篩選多余位置。

2.5 篩選多余位置

如圖4所示，將匿名位置的分布區(qū)域等分為8×8的位置單元，根據(jù)歷史查詢概率［19］，每個位置單元填充不同的灰度。其中，灰度越深，代表歷史查詢概率越高；反之，灰度越淺，代表歷史查詢概率越低。

圖4 匿名位置的分布Fig.4 Distribution of anonymous locations

假設k=5，則除了MU自身位置外，還需要再篩選出k-1=4個匿名位置。在t時刻，MU位于位置單元C1中，其歷史查詢概率為P（C1）。而C2~C10各個區(qū)間的歷史查詢概率P（Ci）=P（C1）（i=2，3，…，10）。若在t-1時刻，MU剛剛在C5處發(fā)起過相似查詢。當兩個時刻之間的差值Δt足夠小時，攻擊者會發(fā)現(xiàn)MU在短時間內(nèi)搜索過C5處的服務，從而使得該位置被泄露的概率由1/5增加到1/4，提高了隱私泄露的風險。因此，排除查詢過的C5位置，匿名查詢位置集C=｛C1，C2，C3，C6，C10｝。

2.6 請求位置服務

假設經(jīng)過反向檢索后，MU得到的匿名位置集C=｛C1，C2，…，Cu，…，Ck｝。其中，Cu是MU的真實位置，隱藏在集合C中，只有MU知道u的值。MU請求位置服務過程如下。

Step 1LBS服務器隨機選擇n(n≥k)個隨機數(shù)d i∈?q*，計算Pi=d i?PK，將｛P1，P2，…，Pn｝作為選擇基點公布。

Step 2MU隨機選擇k個基點和k個隨機數(shù)ai∈?q*，計算V i=ai?Pi，i=1，2，…，k。Step 3MU結(jié)合注冊階段獲得的k個假名集合，反向檢索階段獲得的k個匿名位置集合，以及偽查詢內(nèi)容集合，生成查詢信息Msg=｛（PID1，C1，Q1，V1），（PID2，C2，Q2，V2），…，（PIDk，Ck，Qk，V k）｝發(fā)送給LBS服務器請求位置服務。其中，Qu是Cu的真實查詢請求。

Step 4LBS服務器收到Msg后，獲取k個查詢結(jié)果的集合M=｛m1，m2，…，mu，…，mk｝，選取隨機 數(shù)b∈?q*，計 算Y0=b?PK，Y i=b?V i，ni=mi⊕H2(e(Pi+S?PK，PKIDMU)b)將 Res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，nk）｝反饋給MU。

Step 5MU收到Res信息后，判斷e(V u，Y0)=e(Y u，PK)是否 成立。若成立，計算乘法逆元au

-1∈?q*和解密密鑰A u=au-1?Y u，計 算mu=nu⊕H2(e(A u，PKIDMU)，e(Y0，SKIDMU))，獲取需要的查詢結(jié)果。

3 方案分析

3.1 性質(zhì)分析

定理1正確性：用戶可以通過計算mu=nu⊕H2(e(A u，PKIDMU)，e(Y0，SKIDMU))獲 得 正 確的查詢結(jié)果。

證

則

因此，用戶可通過計算nu⊕H2(e(A u，PKIDMU)，e(Y0，SKIDMU))獲得查詢結(jié)果mu。

定理2驗證性：用戶可以驗證來自LBS服務器信息的真?zhèn)巍?/p>

證在用戶注冊階段，為了防止LBS服務器發(fā)來的信息Reg=｛（PID1，PKID1，SKID1），（PID2，PKID2，SKID2），…，（PIDk，PKIDk，SKIDk）｝中（PIDu，PKIDu，SKIDu）被篡改，用戶MU先計算PKIDu=H1(IDu)，再驗證等式e(SKIDu，P)=e(PKIDu，SPK)是否成立。因 為e(SKIDu，P)=e(S?PKIDu，P)=e(PKIDu，S?P)=e(PKIDu，SPK)，可見，在用戶注冊階段，MU可以驗證來自LBS服務器信息的真?zhèn)巍?/p>

在請求服務階段，當MU收到來自LBS服務器發(fā)來的信息Res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，nk）｝后，判斷e(V u，Y0)=e(Y u，PK)是否成立。因為e(V u，Y0)=e(V u，b?PK)=e(b?V u，PK)=e(Y u，PK)。因此，在請求服務階段，MU可以驗證來自LBS服務器信息的真?zhèn)巍?/p>

綜上所述，用戶可以驗證來自LBS服務器信息的真?zhèn)巍?/p>

定理3匿名性：用戶位置服務滿足匿名性。

證假設攻擊者A從LBS服務器發(fā)送給用戶MU的信息res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，nk）｝中，獲取了k個密文結(jié)果｛n1，n2，…，nk｝，其中，nu=mu⊕H2(e(Pu+S?PK，PKIDMU)b)。A企圖獲得MU的真實查詢結(jié)果mu，需要通過mu=nu⊕H2(e(Pu+S?PK，PKIDMU)b)=nu⊕H2(e(d u?PK+S?PK，PKIDMU)b)完成計算，這就需要獲取u、d u、s和b這4個數(shù)值。如果A可以獲得這4個數(shù)值，就能獲得MU的真實查詢結(jié)果，用戶失去匿名性保護。反之，A不能獲得MU的真實查詢結(jié)果，用戶保持匿名性。下面的任務就轉(zhuǎn)換到A能否獲得上述4個數(shù)值。A獲得的k個密文結(jié)果｛n1，n2，…，nk｝，其中，nu是與MU的真實身份和真實位置相關(guān)聯(lián)的，u的值是由用戶指定的，A并不知道，u值被猜測出來的概率為1/k。另外，s、d u和b是LBS服務器從Zq*中選擇的隨機數(shù)，對A保密。如果A試圖從公開的PK=s?P中獲得s，信息Res的Y0=b?PK中獲得b，LBS服務器公布的基點Pu=d u?PK中獲得d u，就需要攻克ECDL難題，而在現(xiàn)階段這種計算是不可行的。綜上所述，本文方案滿足匿名性。

3.2 安全性分析

攻擊1偽裝攻擊：①攻擊者企圖通過獲得的信息，偽裝成用戶MU的身份，獲得位置請求服務。②攻擊者企圖偽裝成LBS服務器，完成用戶的注冊申請和請求位置服務。

攻擊①：攻擊者A企圖將自己的查詢服務信息隱藏在用戶MU的查詢請求信息Msg=｛（PID1，C1，Q1，V1），（PID2，C2，Q2，V2），…，（PIDa，Ca，Qa，V a），…，（PIDk，Ck，Qk，V k）｝中，發(fā)送給LBS服務器申請位置服務。LBS服務器反饋加密的查詢結(jié)果信息Res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，na，…，nk）｝，A需要通過ma=na⊕H2(e(Pu+S?PK，PKIDMU)b)或ma=na⊕H2(e(A u，PKIDMU)，e(Y0，SKIDMU))=na⊕H2(e(au-1?Y u，PKIDMU)，e(Y0，SKIDMU))獲 取解密的查詢結(jié)果。通過3.1節(jié)分析可知，A無法獲得b和s，因而無法通過ma=na⊕H2(e(Pu+S?PK，PKIDMU)b)獲得解密的查詢結(jié)果。同理，A無法獲得MU選擇的au和私鑰SKIDMU，因而無法通過ma=na⊕H2(e(au-1?Y u，PKIDMU)，e(Y0，SKIDMU))獲得解密的查詢結(jié)果。因此，攻擊者不能偽裝成用戶MU的身份，獲得位置請求服務。

攻擊②：攻擊者A企圖偽裝成LBS服務器，完成用戶的注冊申請和請求位置服務。在用戶注冊階段，A為了偽裝成LBS服務器，需要將Reg=｛（PID1，PKID1，SKID1），（PID2，PKID2，SKID2），…，（PIDk，PKIDk，SKIDk）｝反饋 給 注 冊 用戶，則 需要 計 算 出SKIDi=S?PKIDi。由于S=g smodp是保密的，并且A在現(xiàn)階段很難攻克ECDL難題，便不能從SPK=S?P求出S，繼而計算出SKIDi。當無法計算出SKIDi，A可能偽造一對PKIDu和SKIDu，試圖通過e(SKIDu，P)=e(PKIDu，PK)驗 證，則 需 要 解 決DBDH難題，而在現(xiàn)階段仍無法攻克DBDH難題。因而，攻擊者無法偽裝成LBS服務器完成用戶注冊申請。在請求位置服務階段，A為了偽裝成LBS服務器，需要將Res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，nk）｝反饋給請求用戶，則需要計算出Y0=b?PK，Y i=b?V i，ni=mi⊕H2(e(Pi+S?PK，PKIDMU)b)，這時，A同樣需要面臨ECDL難題。當無法計算出Res，A可能會偽造數(shù)據(jù)，企圖通過e(V u，Y0)=e(Y u，PK)驗證，則同樣需要攻克現(xiàn)階段無法攻克的DBDH難題。因而，攻擊者無法偽裝成LBS服務器完成用戶請求位置服務。

綜上所述，本文方案可以抵抗偽裝攻擊。

攻擊2重放攻擊：假設攻擊者截獲了已注冊用戶MU的注冊請求信息和請求位置服務信息，重新發(fā)送給LBS服務器，企圖獲得與MU同樣的服務。

攻擊者A可以獲得的信息：①系統(tǒng)的公共參數(shù)｛G1，G2，H1，H2，q，P，e，n，PK｝；②用戶MU的注冊請求信息ID=｛ID1，ID2，…，IDu，…，IDk｝；③LBS服務器公布的基點信息｛P1，P2，…，Pn｝；④MU的查詢請求信息Msg=｛（PID1，C1，Q1，V1），（PID2，C2，Q2，V2），…，（PIDk，Ck，Qk，V k）｝；⑤LBS服務器反饋的查 詢 結(jié) 果 信 息Res=｛Y0，（Y1，Y2，…，Y k），（n1，n2，…，nk）｝。

當A將MU已注冊的請求信息ID=｛ID1，ID2，…，IDu，…，IDk｝重新發(fā)送給LBS服務器申請注冊時，LBS服務器會重新選擇一次性隨機數(shù)ID′anony∈?q*，生成不同的假名PIDi′=H3(IDi+ID′anony)。因而，即使A使用雷同的身份信息再次注冊，LBS服務器也不會返回相同的假名，即不會獲得相同的注冊請求結(jié)果。

當A將MU已請求的查詢信息Msg=｛（PID1，C1，Q1，V1），（PID2，C2，Q2，V2），…，（PIDk，Ck，Qk，V k）｝重新發(fā)送給LBS服務器申請位置服務時，LBS服務器會重新選擇一次性隨 機數(shù)b′∈?q*，計算mi⊕H2(e(Pi+S?PK，PKUMU)b′)，生成不同的服務結(jié)果因而，即使A使用雷同的請求查詢信息再次請求服務，LBS服務器也不會返回相同的服務結(jié)果，且A也 無 法 解 密 其中的密文信息(n1′，n2′，…，nk′)。

綜上所述，攻擊者不能通過重放已注冊的請求信息和請求位置服務信息，獲得與已注冊用戶同樣的服務，本文方案可以抵抗重放攻擊。

攻擊3共謀攻擊：攻擊者企圖與位置服務器或某些惡意用戶共謀，猜測出用戶MU的真實身份。

假設攻擊者A與位置服務器LBS服務器共謀。由于本文方案在泛化區(qū)間時使用了4個隨機數(shù)，且不同時向前或向后波動，防止了區(qū)間對稱性猜測。可見，泛化區(qū)間的生成存在隨機因素，匿名位置的產(chǎn)生沒有任何規(guī)律。A或LBS服務器也只能從MU發(fā)送的請求位置服務信息中猜測MU的真實身份，概率為1/k。因此，本文方案可以抵抗攻擊者與位置服務器的合謀攻擊。

假設攻擊者A與惡意用戶共謀。本文方案將用戶MU的經(jīng)緯度坐標位置泛化到一個區(qū)間區(qū)域內(nèi)，并進行Geohash編碼。如果相同Geohash編碼的位置個數(shù)等于k，直接組成匿名位置集，這時攻擊者猜測出MU真實身份的概率為1/k。如果相同Geohash編碼的位置個數(shù)小于k，則擴大到相鄰的8個矩形區(qū)域。擴大區(qū)域后，匿名位置的個數(shù)一般會大于k。MU剔除自己剛剛查詢過的位置，篩選出歷史查詢概率相同的k-1個位置，再融入自身位置，構(gòu)成k個匿名位置集。在這個過程中，攻擊者A只能獲得共謀用戶的歷史查詢概率，并不能獲得被攻擊用戶MU的歷史查詢概率，攻擊者猜測出MU真實身份的概率為1/k。因此，本文方案可以抵抗攻擊者與惡意用戶的合謀攻擊。

4 仿真分析

基于位置隱私保護的系統(tǒng)模型，從處理數(shù)據(jù)的時間開銷和匿名隱私度兩個方面進行仿真分析。仿真實驗硬件環(huán)境i3-8100T CPU、8 GB RAM，軟件 環(huán) 境Windows 10 64bit OS、codeblocks-17.12軟件。

4.1 處理數(shù)據(jù)的時間開銷

本文方案采用Geohash編碼技術(shù)來生成匿名位置集，匿名位置集還可以通過曼哈頓距離［20］或歐氏距離［21］的計算來構(gòu)造。實驗位置數(shù)據(jù)集選用Geo?life數(shù)據(jù)集［22］，其中，第一條位置數(shù)據(jù)作為用戶的真實位置，然后采用三種不同方法生成匿名位置集。

如圖5所示，當數(shù)據(jù)量增加時，三種方法的時間開銷都在增加。其中，歐氏距離方法存在乘法運算，時間開銷增長最快；Geohash編碼方法只是將二維的位置數(shù)據(jù)轉(zhuǎn)換成一維的字符串，相比較而言，基本沒有計算量，時間開銷增長很小。

圖5 生成匿名位置集的時間開銷比較Fig.5 Comparison of the time cost of constructing anonymous location set

4.2 匿名隱私度

用戶位置匿名保護的程度常用位置熵來度量，熵值越大，隱私保護度就越高，當匿名位置集里的所有位置點查詢概率均相等，熵值將達到最大。匿名熵與用戶選擇的匿名度k值有關(guān)，k值越大，用戶真實位置的隱藏效果就越好，但會增加系統(tǒng)的通信開銷和效率。

仿真實驗k值?。?0，80］，效果如圖6所示。當k值增加時，位置熵會增大，但k值增加到一定數(shù)值后，位置熵增長的速度會趨于平緩，說明在一定的匿名區(qū)域內(nèi)，假位置過于密集，混淆能力也趨于飽和，這時再增加假位置的數(shù)量，對用戶真實位置的保護效果欠佳。在本文方案中，當匿名位置的個數(shù)小于k，選用查詢概率相同的k-1個位置構(gòu)成匿名位置集，位置熵達到最大，隱私保護度較高。

圖6 位置熵與k值的關(guān)系Fig.6 Relationship between position entropy and k value

5 結(jié)語

現(xiàn)有的很多k匿名位置隱私保護方案因為檢索歷史數(shù)據(jù)庫的時間開銷較大，位置服務失去了即時的優(yōu)越性。本文方案通過Geohash編碼，將用戶的真實位置泛化到一個區(qū)間區(qū)域，該區(qū)域內(nèi)所有位置的Geohash編碼相同，通過反向檢索構(gòu)成匿名位置集，篩選多余位置時兼顧歷史查詢概率，這樣可以避免檢索的時間滯后性，給用戶提供即時的位置服務。通過性質(zhì)分析，在雙線性映射的相關(guān)問題假設前提下，方案滿足正確性、驗證性和匿名性，可以抵抗偽裝攻擊、重放攻擊和共謀攻擊。仿真實驗顯示，在處理數(shù)據(jù)的時間開銷和匿名隱私度上，本文方案具有更好的優(yōu)越性。位置數(shù)據(jù)不是一個離線的靜態(tài)數(shù)據(jù)，而是一段持續(xù)的動態(tài)數(shù)據(jù)，未來的工作還需要處理運動用戶的位置請求匿名服務。