殷鳳梅，陳 鴻

合肥師范學(xué)院計(jì)算機(jī)學(xué)院，安徽 合肥 230601

0 引言

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

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

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

1 基本概念

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

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

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

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

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

1.2 Geohash編碼

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

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

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

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

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

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

例如，對(duì)圖1中的用戶經(jīng)緯度坐標(biāo)（30.299 4°，70.153 6°），緯度30.299 4°按照表1進(jìn)行緯度編碼，得到二進(jìn)制編碼序列101010110001011，經(jīng)度70.153 6°按照表2進(jìn)行經(jīng)度編碼，得到二進(jìn)制編碼序列101100011110001。緯度編碼和經(jīng)度編碼交錯(cuò)排列后，形成新的二進(jìn)制編碼序列11001 11001 00011 11010 10010 00111，轉(zhuǎn)換成十進(jìn)制數(shù)序列25 25 3 26 18 7。按照表3將十進(jìn)制數(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編碼代表的是一個(gè)矩形區(qū)域，編碼的長度越短，矩形區(qū)域越大；編碼的長度越長，矩形區(qū)域越小。當(dāng)緯度相同時(shí)，經(jīng)度每隔0.000 01°，寬度相差大約1 m；每隔0.000 1°，寬度相差大約10 m。以此類推，每隔0.1°，寬度相差大約10 000 m。當(dāng)經(jīng)度相同時(shí)，緯度每隔0.000 01°，寬度相差大約1.1 m；每隔0.000 1°，寬度相差大約11 m。以此類推，每隔0.1°，寬度相差大約11 132 m?？梢?，Geohash編碼長度越長，所表示的范圍就越精確。例如，編碼長度為5時(shí)，精度大約為4 900 m；編碼長度為8時(shí)，精度大約為19 m。Geohash編碼長度取決于位置隱私保護(hù)的強(qiáng)度，由用戶指定。用戶想獲得較高的位置隱私保護(hù)強(qiáng)度，矩形區(qū)域需要較大，對(duì)應(yīng)的編碼長度就短一些。

1.3 雙線性映射

對(duì)于階為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）可 計(jì) 算 性：任 意 的Q1，Q2∈G1，均 可 計(jì) 算e(Q1，Q2)；

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

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

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

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

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

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

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

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

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

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

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

1.5 位置熵

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

2 k匿名位置隱私保護(hù)方案

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

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

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

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

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

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

2.1 系統(tǒng)初始化

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

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

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

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

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

2.2 用戶注冊(cè)

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

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

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

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

2.3 位置泛化

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

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

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

2.4 反向檢索位置

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

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

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

2.5 篩選多余位置

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

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

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

2.6 請(qǐng)求位置服務(wù)

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

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

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

Step 4LBS服務(wù)器收到Msg后，獲取k個(gè)查詢結(jié)果的集合M=｛m1，m2，…，mu，…，mk｝，選取隨機(jī) 數(shù)b∈?q*，計(jì) 算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)是否 成立。若成立，計(jì)算乘法逆元au

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

3 方案分析

3.1 性質(zhì)分析

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

證

則

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

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

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

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

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

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

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

3.2 安全性分析

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

攻擊①：攻擊者A企圖將自己的查詢服務(wù)信息隱藏在用戶MU的查詢請(qǐng)求信息Msg=｛（PID1，C1，Q1，V1），（PID2，C2，Q2，V2），…，（PIDa，Ca，Qa，V a），…，（PIDk，Ck，Qk，V k）｝中，發(fā)送給LBS服務(wù)器申請(qǐng)位置服務(wù)。LBS服務(wù)器反饋加密的查詢結(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的身份，獲得位置請(qǐng)求服務(wù)。

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

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

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

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

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

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

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

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

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

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

4 仿真分析

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

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

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

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

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

4.2 匿名隱私度

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

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

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

5 結(jié)語

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