連續(xù)服務(wù)請(qǐng)求下基于假位置的用戶隱私增強(qiáng)方法

劉海，李興華，王二蒙，馬建峰

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

連續(xù)服務(wù)請(qǐng)求下基于假位置的用戶隱私增強(qiáng)方法

劉海，李興華，王二蒙，馬建峰

（西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院，陜西 西安 710071）

基于假位置的隱私保護(hù)方案在為用戶提供準(zhǔn)確位置服務(wù)查詢結(jié)果的同時(shí)，還無需第三方和共享密鑰。然而，當(dāng)用戶連續(xù)請(qǐng)求位置服務(wù)時(shí)，由于現(xiàn)有保護(hù)單次查詢的假位置方案未考慮相鄰位置集合間的時(shí)空關(guān)系，使攻擊者能推斷出假位置，降低用戶的位置隱私保護(hù)等級(jí)。針對(duì)上述問題，采用現(xiàn)有假位置方案生成候選假位置，并通過連續(xù)合理性檢查和單次隱私增強(qiáng)對(duì)其進(jìn)行篩選，提出一個(gè)適用于連續(xù)請(qǐng)求的假位置隱私保護(hù)增強(qiáng)方法。安全性分析表明，所提方法能保證連續(xù)請(qǐng)求中形成的移動(dòng)路徑在時(shí)空上不可區(qū)分，有效保護(hù)連續(xù)請(qǐng)求中的用戶位置隱私。大量實(shí)驗(yàn)表明，所提方法在不增加用戶計(jì)算開銷的同時(shí)，與采用的候選假位置生成方案相比，還能提高用戶單次查詢的隱私保護(hù)等級(jí)。

基于位置的服務(wù)；隱私增強(qiáng)；連續(xù)請(qǐng)求；假位置；連續(xù)合理性檢查

1 引言

基于位置的服務(wù)[1～4]（LBS, location-based service）是指服務(wù)提供商為用戶提供其指定位置的地理信息，或與其指定位置信息相關(guān)的其他業(yè)務(wù)。隨著無線通信技術(shù)的迅猛發(fā)展和移動(dòng)智能終端設(shè)備的普及，LBS已成為人們?nèi)粘Ｉ畈豢苫蛉钡闹匾M成。

然而，位置服務(wù)提供商在為用戶提供便捷服務(wù)的同時(shí)，還可能搜集并濫用用戶提交的數(shù)據(jù)，從而非法獲取他們的個(gè)人隱私信息。因此，位置服務(wù)中的用戶隱私保護(hù)得到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注[5～14]。基于假位置的方法[5,6]作為一種最常用的位置隱私保護(hù)方法，與其他位置隱私保護(hù)方法相比，它具有以下優(yōu)點(diǎn)：1) 不依賴第三方；2) 可讓用戶獲得準(zhǔn)確的查詢結(jié)果；3) 無需用戶存儲(chǔ)密鑰。這就使基于假位置的方法已被廣泛用于保護(hù)單次查詢中的用戶位置隱私[5, 6, 15～18]。

在現(xiàn)實(shí)生活中，除了使用單次LBS外，用戶還會(huì)連續(xù)地發(fā)送LBS請(qǐng)求。例如，在駕車前往度假的途中，司機(jī)可能會(huì)不斷地查詢最近加油站的位置；到陌生城市旅行時(shí)，游客也會(huì)不斷地查詢周圍的景點(diǎn)和美食，從而更好地享受假期。在連續(xù)LBS請(qǐng)求中，用戶提交的相鄰位置集合在地理時(shí)空上存在緊密的關(guān)聯(lián)性。如果將現(xiàn)有保護(hù)單次查詢的假位置方案直接用于連續(xù)請(qǐng)求場(chǎng)景時(shí)，攻擊者就可利用相鄰位置集合間的地理時(shí)空關(guān)系，通過識(shí)別虛假移動(dòng)路徑的方法正確推測(cè)出假位置，降低用戶的位置隱私保護(hù)等級(jí)，甚至推測(cè)出用戶的真實(shí)位置。

針對(duì)上述問題，本文利用現(xiàn)有保護(hù)單次查詢的假位置方案生成候選假位置，從時(shí)間可達(dá)性檢查、方向相似判斷和出入度這3個(gè)方面評(píng)估候選假位置的連續(xù)合理性，對(duì)其進(jìn)行篩選，提出了一種適用于連續(xù) LBS請(qǐng)求的基于假位置的用戶隱私保護(hù)增強(qiáng)方法。此外，本方法還基于個(gè)人查詢熵和位置分散度，從單次查詢隱私保護(hù)的角度再次對(duì)剩余的候選假位置進(jìn)行篩選，使最終生成的位置集合在有效保護(hù)連續(xù)LBS請(qǐng)求中用戶位置隱私的同時(shí)，還能為用戶的單次請(qǐng)求提供更好的隱私保護(hù)。本文的主要貢獻(xiàn)如下。

1) 通過實(shí)驗(yàn)發(fā)現(xiàn)，現(xiàn)有保護(hù)單次查詢的假位置方案直接用于連續(xù)LBS請(qǐng)求場(chǎng)景時(shí)，攻擊者可通過相鄰位置集合間的地理時(shí)空關(guān)系，正確推測(cè)出假位置，從而降低用戶的位置隱私保護(hù)等級(jí)，甚至推測(cè)出用戶的真實(shí)位置。

2) 從時(shí)間可達(dá)性、方向相似性和出入度這 3個(gè)方面考慮連續(xù)請(qǐng)求中相鄰位置集合間的地理時(shí)空關(guān)系，提出一個(gè)基于假位置的連續(xù) LBS請(qǐng)求位置隱私保護(hù)增強(qiáng)方法。安全性分析表明，本方法能保證在連續(xù)請(qǐng)求中形成的移動(dòng)路徑在地理時(shí)空上具有不可區(qū)分性，有效保護(hù)用戶在連續(xù)請(qǐng)求中的位置隱私。

3) 大量實(shí)驗(yàn)對(duì)比表明，與采用的候選假位置生成方案相比，本方法在不降低單次請(qǐng)求中個(gè)人查詢熵的同時(shí)，能增大位置分散度，為用戶提供更高的單次查詢隱私保護(hù)等級(jí)。此外，該方案還具有較低的計(jì)算開銷。

2 相關(guān)工作

本節(jié)主要介紹現(xiàn)有連續(xù) LBS請(qǐng)求中的用戶位置隱私保護(hù)方案和現(xiàn)有保護(hù)單次查詢的假位置方案。

2.1 連續(xù)請(qǐng)求下的位置隱私保護(hù)

現(xiàn)有連續(xù)請(qǐng)求下的用戶隱私保護(hù)大多采用K匿名的方法。Xu和Cai[19]提出利用匿名集合大小來度量LBS連續(xù)請(qǐng)求中的用戶的位置隱私保護(hù)需求。在他們的方案中，用戶通過在最小邊界圓（minimum bounding circle）中查找不在上一匿名區(qū)內(nèi)其他用戶的方法來構(gòu)造匿名集合。文獻(xiàn)[20]則通過讓用戶制定公共區(qū)域來表示自己的隱私保護(hù)需求，提出了基于感覺（feeling）的連續(xù)LBS請(qǐng)求用戶隱私保護(hù)模型。不幸的是，上述2個(gè)方案均不能避免LSP利用查詢追蹤攻擊[21]推測(cè)出用戶的真實(shí)位置。為了抵抗查詢追蹤攻擊，潘曉等[22]通過預(yù)測(cè)用戶未來發(fā)送LBS請(qǐng)求的位置，讓用戶在連續(xù)請(qǐng)求的最初時(shí)刻為所有請(qǐng)求生成統(tǒng)一匿名區(qū)，來保護(hù)連續(xù)請(qǐng)求中的用戶位置隱私。Wang等[23]指出，在連續(xù)LBS請(qǐng)求中，用戶可能具有不同隱私保護(hù)需求。他們讓匿名服務(wù)器查找能滿足用戶所有隱私需求的歷史足跡來構(gòu)造匿名區(qū)。Li等[24]指出，在利用其他用戶歷史足跡構(gòu)造匿名區(qū)時(shí)，會(huì)出現(xiàn)匿名區(qū)域過大、服務(wù)質(zhì)量降低的問題。他們通過抑制用戶的少量LBS請(qǐng)求，在滿足用戶連續(xù)請(qǐng)求中個(gè)性化位置隱私保護(hù)需求的同時(shí)，通過刪除最遠(yuǎn)足跡縮小匿名區(qū)面積，提高服務(wù)質(zhì)量。然而，一旦用戶在預(yù)定/預(yù)測(cè)位置之外進(jìn)行 LBS請(qǐng)求，上述方案仍不能抵抗查詢追蹤攻擊。

Schlegel等[24]基于密文匹配的思想，提出了首個(gè)基于密碼學(xué)方法的連續(xù) LBS請(qǐng)求位置隱私保護(hù)方案。然而，在他們的方案中，一旦半可信第三方與LSP進(jìn)行合謀，就能縮小用戶真實(shí)位置所屬的區(qū)域，降低用戶的隱私保護(hù)。

與基于假位置的方法相比，現(xiàn)有連續(xù)請(qǐng)求位置隱私保護(hù)的方法均引入第三方，這會(huì)導(dǎo)致用戶與第三方之間存在通信瓶頸。并且，在基于K匿名的方法中，還要求第三方是完全可信的。然而在現(xiàn)實(shí)環(huán)境中，完全可信的第三方難以找到，這都降低了現(xiàn)有連續(xù)請(qǐng)求隱私保護(hù)方案的實(shí)用性。

2.2 單次請(qǐng)求下基于假位置的用戶隱私保護(hù)

基于假位置的用戶隱私保護(hù)方案最早是由 Kido等[5,6]于2005年提出的。其基本思想是指用戶根據(jù)自己的隱私保護(hù)需求生成假位置，并將這些假位置與真實(shí)位置一同發(fā)送給服務(wù)提供商，使服務(wù)提供商無法正確推測(cè)出用戶的真實(shí)位置。Lu等[15]指出如果生成的假位置過于集中，會(huì)降低用戶的位置隱私保護(hù)等級(jí)。在他們的方案中，用戶根據(jù)自己的隱私需求，將匿名區(qū)域等份劃分，使每個(gè)位置（包括用戶的真實(shí)位置）均位于不同的圓半徑或矩形頂點(diǎn)上。Niu等[16]指出，上述方案均未考慮攻擊者所擁有的背景知識(shí)。一旦攻擊者掌握如地圖信息等某些背景知識(shí)，這些方案生成的如位于河流中和山峰頂?shù)募傥恢镁湍鼙还粽咻p易地識(shí)別。因此，他們提出在假位置生成過程中，首先應(yīng)讓每個(gè)假位置的查詢頻率與其真實(shí)位置的查詢頻率盡可能地相等，避免生成不合理的假位置；其次，在確保查詢頻率不發(fā)生改變的同時(shí)，讓位置分散度變大，從而更好地保護(hù)用戶的位置隱私。隨后，他們還對(duì)文獻(xiàn)[15]未考慮攻擊者背景知識(shí)的缺陷進(jìn)行改進(jìn)[17]，通過平移原方案生成的各個(gè)假位置，使最終生成的位置集合的查詢信息熵達(dá)到最大。此外，Niu等[18]又提出利用接入熱點(diǎn)的緩存來存儲(chǔ)用戶歷史查詢結(jié)果的方法，避免用戶在同一位置頻繁地生成假位置和向LBS服務(wù)器發(fā)送請(qǐng)求，從而降低其通信開銷和計(jì)算開銷。

從上述介紹中可知，現(xiàn)有基于假位置的隱私保護(hù)方法的研究?jī)H集中在單次LBS請(qǐng)求場(chǎng)景。因此，將這些方案直接用于連續(xù)請(qǐng)求場(chǎng)景時(shí)，攻擊者就能利用相鄰位置集合間的地理時(shí)空關(guān)系正確推測(cè)出假位置，甚至直接推測(cè)出用戶的真實(shí)位置。

3 基于假位置的隱私增強(qiáng)方法

針對(duì)現(xiàn)有保護(hù)單次查詢的假位置方案并不適用于連續(xù)請(qǐng)求場(chǎng)景的問題，本文采用現(xiàn)有假位置方案生成候選假位置，并利用連續(xù)合理性檢查和單次請(qǐng)求隱私增加對(duì)候選假位置進(jìn)行篩選，提出了一個(gè)適用于連續(xù) LBS請(qǐng)求的基于假位置的用戶隱私增強(qiáng)方法。該方法主要由2個(gè)部分組成：連續(xù)合理性檢查算法和單次請(qǐng)求隱私增強(qiáng)算法。其基本框架如圖1所示。

圖1 連續(xù)LBS請(qǐng)求下基于假位置的用戶隱私增強(qiáng)流程

1) 候選假位置

本文的目的是針對(duì)現(xiàn)有基于假位置的用戶隱私保護(hù)方案提出一個(gè)適用于連續(xù)請(qǐng)求情形的用戶隱私保護(hù)增強(qiáng)算法。在本方法中，候選假位置可由現(xiàn)有保護(hù)單次查詢的假位置方案直接生成。對(duì)于任意的第Qi次連續(xù)LBS請(qǐng)求，首先生成的n個(gè)候選假位置，用集合表示。其中，∈Ci表示用戶在第Qi次請(qǐng)求中生成第 l(1 ≤l≤n)個(gè)候選假位置；n >Ki，Ki表示用戶在第Qi次連續(xù)LBS請(qǐng)求中對(duì)當(dāng)前真實(shí)位置的隱私保護(hù)需求。

2) 連續(xù)合理性檢查

將用戶第Qi次連續(xù)請(qǐng)求生成的n個(gè)候選假位置,,…與用戶在第Q次請(qǐng)求中最終提交的i?1Ki?1個(gè)位置進(jìn)行連續(xù)合理性檢查，包括時(shí)間可達(dá)性檢查、方向相似性判斷和出入度評(píng)估，最終得到滿足連續(xù)合理性檢查的連續(xù)假位置集合候選組。

3) 單次請(qǐng)求位置隱私增強(qiáng)

對(duì)于每一個(gè)滿足連續(xù)合理性檢查的連續(xù)假位置集合候選組，對(duì)其為用戶提供的單次隱私保護(hù)等級(jí)進(jìn)行比較，選擇提供單次隱私保護(hù)等級(jí)最高的連續(xù)假位置集合候選組作為最終生成的假位置集合與真實(shí)位置一起提交給服務(wù)提供商。

當(dāng)用戶第一次進(jìn)行LBS請(qǐng)求時(shí)，仍由原始方案初始生成n個(gè)候選假位置，并對(duì)個(gè)假位置集合進(jìn)行單次請(qǐng)求的位置隱私增強(qiáng)檢查后，得到最終的假位置集合。

3.1 連續(xù)合理性檢查算法

該算法主要是對(duì)利用現(xiàn)有保護(hù)單次查詢的假位置方案生成的候選假位置進(jìn)行篩選，使連續(xù)請(qǐng)求中形成的移動(dòng)路徑在地理時(shí)空上具有不可區(qū)分性，具體流程如圖2所示。候選假位置在經(jīng)過連續(xù)合理性檢查后，可得到適用于連續(xù)LBS請(qǐng)求的連續(xù)假位置集合候選組。如果經(jīng)過連續(xù)合理性檢查后未產(chǎn)生滿足用戶位置隱私需求的候選組，即篩選后剩下的假位置個(gè)數(shù)小于用戶的隱私保護(hù)需求，則擴(kuò)大生成的候選假位置個(gè)數(shù)，并重新生成候選假位置。

圖2 連續(xù)請(qǐng)求的可達(dá)性檢查流程

3.1.1 時(shí)間可達(dá)性檢查

時(shí)間可達(dá)性檢查的目的是為了讓用戶在相鄰LBS請(qǐng)求中形成的虛假移動(dòng)路徑能在請(qǐng)求時(shí)間間隔內(nèi)可達(dá)。這將使攻擊者無法利用城市交通地圖等公共信息，通過識(shí)別虛假移動(dòng)路徑的方法，正確推測(cè)出某些假位置，從而降低連續(xù)請(qǐng)求中用戶的位置隱私保護(hù)等級(jí)。

假設(shè)用戶相鄰2次LBS請(qǐng)求分別為第Qi?1次和第Qi次請(qǐng)求，可利用有向圖 GT=來表示在第Qi次請(qǐng)求中滿足時(shí)間可達(dá)性檢查的候選假位置。

3.1.2 方向相似性判斷

方向相似性判斷的目的是為了避免在相鄰請(qǐng)求中形成的可達(dá)虛假路徑的移動(dòng)方向與用戶真實(shí)路徑的移動(dòng)方向相差過大，防止攻擊者通過移動(dòng)方向識(shí)別出可達(dá)虛假移動(dòng)路徑，推測(cè)出某些假位置，從而降低連續(xù)請(qǐng)求中用戶的位置隱私保護(hù)等級(jí)。

在方向相似性判斷中，利用可達(dá)的虛假移動(dòng)路徑與真實(shí)移動(dòng)路徑間的方向夾角作為判斷標(biāo)準(zhǔn)。同樣地，利用有向圖 GD=來表示第Qi次請(qǐng)求下滿足方向相似性判斷的候選假位置。

下的候選假位置集合，其滿足

3.1.3 出入度評(píng)估

本文借用出入度的概念來度量相鄰請(qǐng)求中形成移動(dòng)路徑的數(shù)量，即用各個(gè)位置的出度來表示以它為起點(diǎn)的移動(dòng)路徑的數(shù)量，用入度來表示以它為終點(diǎn)的移動(dòng)路徑的數(shù)量。出入度評(píng)估是為了避免在相鄰請(qǐng)求形成的方向相似的可達(dá)移動(dòng)路徑中，用戶真實(shí)位置的出入度值與假位置的出入度值相差過大，使攻擊者能以較大概率直接推測(cè)出用戶的真實(shí)位置。為了實(shí)現(xiàn)上述目的，分別將用戶真實(shí)位置的出度值和入度值作為期望值，利用方差來度量生成的候選假位置集合中假位置出度值與入度值的波動(dòng)情況。

本文繼續(xù)用有向圖 GN=來表示第Qi次請(qǐng)求中滿足出入度評(píng)估后，篩選剩下的候選假位置。

綜上所述，連續(xù)合理性檢查算法如下所示。

算法1 連續(xù)合理性檢查算法

輸入 Qi?1次請(qǐng)求最終生成的位置集合Si?1=

Qi次請(qǐng)求的候選假位置候選集合

輸出 Qi請(qǐng)求的連續(xù)假位置集合候選組

1) for each ci∈C do

i

direction (< ci?1,c?i>,< ci?1,ci>)

3) C′′← ci;

i

4) end if

5) end for

6) if |Ci′′ |< Ki? 1 then

7) exit;

8) end if

10) for each j∈ [1,m ′] do

and

13) end if

14) end for

3.2 單次請(qǐng)求的位置隱私增強(qiáng)

當(dāng)生成的候選假位置經(jīng)過連續(xù)合理性檢查算法篩選后，可得到滿足連續(xù)合理性的連續(xù)假位置集合候選組。當(dāng)把任意一個(gè)連續(xù)假位置集合候選組與當(dāng)前真實(shí)位置一同提交給服務(wù)提供商時(shí)，由于它們與第Qi?1次服務(wù)請(qǐng)求中最終提交的位置集合所形成的移動(dòng)路徑在地理時(shí)空上具有不可區(qū)分性，因此攻擊者將無法推測(cè)出假位置，從而有效保護(hù)連續(xù)請(qǐng)求中用戶的位置隱私，并且，為了避免降低用戶單次請(qǐng)求中的位置隱私保護(hù)等級(jí)，本文還利用個(gè)人查詢熵和位置分散度[4,16]，對(duì)上述生成的連續(xù)假位置集合候選組再次進(jìn)行篩選，使最后剩下的連續(xù)假位置集合候選組還能從單次請(qǐng)求隱私保護(hù)的角度，為用戶提供最高的位置隱私保護(hù)等級(jí)。其流程如圖3所示。

當(dāng)攻擊者長(zhǎng)期收集某用戶發(fā)送的服務(wù)請(qǐng)求時(shí)，他能計(jì)算出這個(gè)用戶在每個(gè)位置上發(fā)送服務(wù)請(qǐng)求的次數(shù)。若用戶在生成的假位置上的個(gè)人查詢次數(shù)與其在真實(shí)位置上的個(gè)人查詢次數(shù)相差較大，則攻擊者就能推測(cè)出用戶此次請(qǐng)求的假位置，從而降低用戶真實(shí)位置的隱私保護(hù)等級(jí)。為了避免上述問題，利用個(gè)人查詢熵對(duì)經(jīng)過連續(xù)合理性檢查后形成的連續(xù)假位置集合候選組進(jìn)行度量，確保在最終篩選出的連續(xù)假位置集合候選組中，用戶在每個(gè)假位置的個(gè)人查詢次數(shù)與其真實(shí)位置的個(gè)人查詢次數(shù)盡可能相同。個(gè)人查詢熵越大，則表示該連續(xù)假位置集合候選組中每個(gè)假位置的個(gè)人查詢次數(shù)與真實(shí)位置的個(gè)人查詢次數(shù)就越相近。因此，用戶會(huì)將篩選出的個(gè)人查詢熵最大的連續(xù)假位置集合候選組作為最終的假位置集合，與用戶真實(shí)位置一同發(fā)送給服務(wù)提供商。

此外，若存在多個(gè)連續(xù)假位置集合候選組的個(gè)人查詢熵相等且均是最大值時(shí)，將利用位置分散度對(duì)它們?cè)俅芜M(jìn)行篩選，得到最終的假位置集合。假位置集合的位置分散度越大，則表示其所形成的區(qū)域面積就越大，能避免由于生成的假位置過于集中，使攻擊者能推測(cè)出用戶真實(shí)位置所屬區(qū)域的隱私泄露問題。具體的單次請(qǐng)求位置隱私增強(qiáng)算法如下所示。

輸入 Qi次請(qǐng)求的假位置集合候選組

輸出 Qi請(qǐng)求的最終假位置集合

3) F[ l] ←H( Al)； //計(jì)算集合 Al的個(gè)人查詢熵

4) end for

7)

10) for each

12) end for

13) A′← argmax_ dispersion( A ′′[?]);

1)

3.3 安全性分析

在本文所提的基于假位置的連續(xù) LBS請(qǐng)求用戶隱私保護(hù)增強(qiáng)方法中，候選假位置是由現(xiàn)有保護(hù)單次查詢的假位置方案直接生成的。因此，本文不再?gòu)膯未尾樵兊慕嵌葘?duì)本方法能否抵抗相應(yīng)的推測(cè)攻擊進(jìn)行闡述，而僅通過安全性分析說明本方法能保證在連續(xù)請(qǐng)求中形成的可達(dá)移動(dòng)路徑在地理時(shí)空上具有不可區(qū)分性，使攻擊者無法通過識(shí)別可達(dá)的虛假移動(dòng)路徑的方法推測(cè)出假位置，有效保護(hù)連續(xù)請(qǐng)求中用戶的位置隱私。

與現(xiàn)有基于假位置的隱私保護(hù)方案一樣，假設(shè)攻擊者的目的是得到用戶的準(zhǔn)確位置，從而獲得與用戶位置信息緊密相關(guān)的個(gè)人隱私信息。本文假定攻擊者具有如下的背景知識(shí)：1) 攻擊者能攻陷LBS服務(wù)器，即他能知道用戶提交的LBS請(qǐng)求的時(shí)間和位置信息。其中，位置信息包括用戶的真實(shí)位置和生成的假位置。此外，攻擊者還會(huì)長(zhǎng)期收集并統(tǒng)計(jì)該用戶在各個(gè)位置發(fā)送請(qǐng)求的頻率；2) 攻擊者具備地圖背景知識(shí)，即他知道任意2個(gè)位置的距離和地圖顯示的可達(dá)時(shí)間。

在本文所提的連續(xù)合理性檢查算法中，通過時(shí)間可達(dá)性檢查、方向相似性判斷和出入度評(píng)估對(duì)候選假位置進(jìn)行篩選，最終生成假位置集合候選組。從時(shí)間可達(dá)性檢查描述中可以發(fā)現(xiàn)，在利用時(shí)間可達(dá)性檢查，對(duì)第Qi次請(qǐng)求生成的候選假位置進(jìn)行篩選后，可保證篩選剩下的候選假位置與第次請(qǐng)求提交的位置間至少存在1條在σ time <,>

T時(shí)間內(nèi)可達(dá)的虛假移動(dòng)路徑。隨著σT的變小，所形成的可達(dá)虛假移動(dòng)路徑的可達(dá)時(shí)間與用戶真實(shí)移動(dòng)路徑的可達(dá)時(shí)間越相近。并且，方向相似性判斷又對(duì)經(jīng)時(shí)間可達(dá)性檢查篩選后剩下的候選假位置再次進(jìn)行篩選，使篩選后剩下的候選假位置與第Qi?1次請(qǐng)求最終提交的位置間形成的可達(dá)虛假移動(dòng)路徑與用戶真實(shí)移動(dòng)路徑間的方向夾角不大于σD。隨著σD的變小，所形成的可達(dá)虛假路徑在移動(dòng)方向上與用戶真實(shí)路徑的移動(dòng)方向越相似。而在最后的出入度評(píng)估中，所形成的連續(xù)假位置集合候選組能避免用戶真實(shí)位置的出入度值與假位置的出入度值相差過大，使攻擊者能以較大概率推測(cè)出用戶的真實(shí)位置。隨著用戶指定的評(píng)估閾值σin?D和 σout?D的不斷變小，在位置集合S與 ∪ {}形成的方

i?1向相似的可達(dá)移動(dòng)路徑中，Si?1中各假位置的出度與的出度越接近，而中各假位置的入度則與的入度也越接近。因此，當(dāng)用戶與攻擊者具有相同的連續(xù)合理性檢查知識(shí)時(shí)，本方法能保證在連續(xù)請(qǐng)求中形成的移動(dòng)路徑在地理時(shí)空上具有不可區(qū)分性，使攻擊者無法通過識(shí)別虛假移動(dòng)路徑的方法推測(cè)出假位置，從而有效保護(hù)連續(xù)請(qǐng)求中用戶的位置隱私。

4 實(shí)驗(yàn)仿真

為了說明現(xiàn)有假位置隱私保護(hù)方案不適用于連續(xù)請(qǐng)求場(chǎng)景，本文進(jìn)行了大量的實(shí)驗(yàn)仿真。在此，本文選取2014年INFOCOM會(huì)議上的方案[16]作為實(shí)例，說明將該方案直接用于連續(xù)請(qǐng)求場(chǎng)景時(shí)，并不能有效保護(hù)用戶的位置隱私。并通過與其進(jìn)行比較，表明本方法在不增加用戶計(jì)算開銷的同時(shí)，不僅能有效保護(hù)連續(xù)請(qǐng)求中用戶的位置隱私，還能為用戶的單次請(qǐng)求提供更高的隱私保護(hù)等級(jí)。

4.1 實(shí)驗(yàn)數(shù)據(jù)及平臺(tái)

本文首先選取 enhanced-DLS算法[16]為本方案生成候選假位置。為了保證候選假位置的篩選成功率，首先生成4K個(gè)候選假位置，其中，K表示用戶的位置隱私保護(hù)需求。當(dāng)經(jīng)過時(shí)間可達(dá)性檢查、方向相似性判斷和出入度評(píng)估后，若篩選剩下的候選假位置個(gè)數(shù)少于K?1，就再次使用enhanced-DLS算法重新生成8K個(gè)候選假位置。

本文采用基于網(wǎng)絡(luò)的移動(dòng)對(duì)象生成器（network-based generator of moving objects）[26]生成實(shí)驗(yàn)數(shù)據(jù)。該生成器是以德國(guó)城市Oldenberg（面積大約為16 km× 16 km）的城市交通路線圖為基礎(chǔ)，通過設(shè)置移動(dòng)速度，可生成一系列用戶的移動(dòng)路徑。選取該地圖中心部分作為實(shí)驗(yàn)區(qū)域，面積為8 km×8 km，將其劃分為6 400個(gè)網(wǎng)格，其中，每個(gè)網(wǎng)格的面積為100 m× 100 m。并且，本文使用上述生成器的默認(rèn)設(shè)置，隨機(jī)生成38 000條移動(dòng)路徑（包含約150 000個(gè)不同的位置信息）作為用戶歷史LBS請(qǐng)求數(shù)據(jù)，用于統(tǒng)計(jì)用戶在各個(gè)網(wǎng)格中所發(fā)送的歷史服務(wù)請(qǐng)求次數(shù)。虛假移動(dòng)路徑的可達(dá)時(shí)間是通過查詢Google地圖獲得。另外，在本實(shí)驗(yàn)中，用戶的位置隱私需求K的變化范圍為 3～20，并針對(duì)不同的K值，分別做了10次連續(xù)LBS請(qǐng)求假位置生成實(shí)驗(yàn)。本實(shí)驗(yàn)的算法均采用C++編程語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為3.00 GHz Core 2 Duo CPU，4 GB DDR3-1600 RAM，操作系統(tǒng)為Windows 7-64 bit。

4.2 連續(xù)請(qǐng)求對(duì)現(xiàn)有基于假位置方案帶來的影響

為了證明現(xiàn)有保護(hù)單次查詢的假位置保護(hù)方案并不適用于連續(xù)請(qǐng)求場(chǎng)景，本文選用enhanced-DLS算法[16]為用戶不同的隱私保護(hù)需求，分別連續(xù)生成 10次服務(wù)請(qǐng)求位置集合。具體實(shí)驗(yàn)過程如下：1) 針對(duì)不同的隱私保護(hù)需求，使用缺省設(shè)置，利用移動(dòng)對(duì)象生成器為分別生成1條包含10個(gè)位置的移動(dòng)路徑，從而模擬用戶連續(xù) 10次發(fā)送服務(wù)請(qǐng)求時(shí)的真實(shí)位置；2) 根據(jù)每條移動(dòng)路徑中的10個(gè)真實(shí)位置的經(jīng)緯度，確定其所屬的網(wǎng)格，并統(tǒng)計(jì)相應(yīng)網(wǎng)格的用戶歷史查詢次數(shù)；3) 利用enhanced-DLS算法為每個(gè)真實(shí)位置生成相應(yīng)的假位置集合；4) 利用Goolge地圖獲取相鄰請(qǐng)求是可達(dá)時(shí)間，并將該時(shí)間作為用戶相鄰2次請(qǐng)求的時(shí)間間隔；5) 構(gòu)造用戶相鄰請(qǐng)求各位置間的移動(dòng)路徑，設(shè)置時(shí)間可達(dá)性檢查閾值σ=對(duì)它們進(jìn)行篩選，

T獲得用戶相鄰請(qǐng)求中形成的可達(dá)移動(dòng)路徑，若在第Qi+1次請(qǐng)求生成的位置集合中的每個(gè)位置至少能與第Qi次請(qǐng)求生成的位置集合中的任意一個(gè)位置構(gòu)成可達(dá)的移動(dòng)路徑，則繼續(xù)進(jìn)行方向相似性判斷；6) 設(shè)置方向相似性判斷閾值 σD=75°對(duì)上述形成的可達(dá)移動(dòng)路徑進(jìn)行判斷，若無法篩選出均由假位置構(gòu)成的可達(dá)虛假移動(dòng)路徑，就繼續(xù)進(jìn)行出入度評(píng)估；7) 統(tǒng)計(jì)相鄰請(qǐng)求中，形成的方向相似的可達(dá)移動(dòng)路徑，并基于此計(jì)算出各位置的出入度，對(duì)假位置進(jìn)行識(shí)別。在本文中，其他部分的實(shí)驗(yàn)過程基本與本部分的實(shí)驗(yàn)相似，唯一不同的就是各閾值的設(shè)定。因此，在之后的實(shí)驗(yàn)中不在對(duì)具體的實(shí)驗(yàn)過程進(jìn)行描述。

針對(duì)不同的隱私保護(hù)需求K值，在這10次連續(xù)LBS請(qǐng)求中，最多只有4次連續(xù)請(qǐng)求生成的位置集合能通過連續(xù)合理性檢查，如圖4所示。而在其他請(qǐng)求中，由于生成的位置集合因在經(jīng)過連續(xù)合理性檢查后，剩下的假位置數(shù)量小于用戶的隱私保護(hù)需求，從而無法保護(hù)連續(xù)請(qǐng)求中的用戶位置隱私。

圖4 enhanced-DLS假位置算法應(yīng)用在連續(xù)請(qǐng)求情形下的通過次數(shù)

因此，enhanced-DLS算法并不能有效保護(hù)連續(xù)請(qǐng)求中的用戶位置隱私。而造成這一問題的根本原因就是用戶在連續(xù)請(qǐng)求場(chǎng)景下生成假位置時(shí)，并未考慮生成的位置集合與上次請(qǐng)求生成的位置集合間的地理時(shí)空關(guān)系，從而使LSP能通過識(shí)別虛假移動(dòng)路徑的方法推測(cè)出生成的假位置。

4.3 本方法提供的隱私保護(hù)等級(jí)評(píng)估

1) 連續(xù)請(qǐng)求場(chǎng)景中的隱私保護(hù)等級(jí)

在連續(xù)LBS請(qǐng)求中，利用連續(xù)請(qǐng)求中所形成的連續(xù)合理的移動(dòng)路徑數(shù)量對(duì)用戶位置隱私保護(hù)等級(jí)進(jìn)行度量。當(dāng)設(shè)定用戶連續(xù)發(fā)送10次LBS請(qǐng)求、時(shí)間可達(dá)性檢查閾值方向相似性判斷閾值出入度評(píng)估閾值σin?D和σout?D分別選擇各次實(shí)驗(yàn)中的計(jì)算得到的最小方差值時(shí)，本方案在相鄰2次請(qǐng)求中，所生成的可達(dá)移動(dòng)路徑數(shù)量如圖5所示。

圖5 連續(xù)合理的移動(dòng)路徑數(shù)量與理想情況的對(duì)比

本文用“最優(yōu)解”來表示的理想狀態(tài)下應(yīng)形成的移動(dòng)路徑數(shù)量。通過圖5可以發(fā)現(xiàn)，隨著用戶位置隱私保護(hù)需求的提高，理想狀態(tài)下應(yīng)形成的移動(dòng)路徑數(shù)量與本文方法生成出的位置集合間形成的連續(xù)合理的移動(dòng)路徑的數(shù)量均隨之增多。以用戶在第Qi次和第Qi+1次請(qǐng)求時(shí)的隱私保護(hù)需求Ki= Ki+1= 6為例，在理想狀態(tài)下應(yīng)形成36條連續(xù)合理的移動(dòng)路徑。然而，由于用戶的下次服務(wù)請(qǐng)求具有很強(qiáng)的隨機(jī)性，如果將出入度評(píng)估的閾值設(shè)置為 σin?D= σout?D= 0，將難以生成滿足該條件的連續(xù)假位置集合候選組。雖然，本文在實(shí)驗(yàn)中將出入度評(píng)估閾值σin?D和 σout?D分別選擇為各次實(shí)驗(yàn)中的計(jì)算得到的最小方差值，使本方案在相鄰2次請(qǐng)求中形成的連續(xù)合理的移動(dòng)路徑數(shù)量少于理想狀態(tài)，但是仍能滿足用戶的隱私保護(hù)需求。

2) 單次請(qǐng)求場(chǎng)景中的隱私保護(hù)等級(jí)

基于個(gè)人查詢熵和位置分散度，從單次位置隱私保護(hù)的角度，對(duì)本文提出的隱私增強(qiáng)方法與enhanced-DLS算法進(jìn)行對(duì)比，以說明本方法在有效保護(hù)連續(xù)請(qǐng)求中用戶位置隱私的同時(shí)，也能為用戶提供更高的單次隱私保護(hù)等級(jí)。在本實(shí)驗(yàn)中，仍設(shè)定用戶連續(xù)發(fā)送10次LBS請(qǐng)求、時(shí)間可達(dá)性檢查閾值σ=、方向相似性判斷閾值σ=75°、出入

TD度評(píng)估閾值σin?D和 σout?D分別選擇各次實(shí)驗(yàn)中的計(jì)算得到的最小方差值。

本方法與 enhanced-DLS算法生產(chǎn)的位置集合的個(gè)人查詢熵如表1所示。從該表中可以發(fā)現(xiàn)，隨著用戶隱私保護(hù)需求K的增大，enhanced-DLS算法和本文提出的適用于連續(xù)請(qǐng)求下的基于假位置的用戶隱私增強(qiáng)算法所產(chǎn)生的信息熵均在增大。當(dāng)用戶隱私保護(hù)需求從K=3變化到K=7時(shí)，所生成位置集合的個(gè)人查詢熵值完全相等；而當(dāng)K=20時(shí)，本方法所生成的位置集合的個(gè)人查詢熵僅比enhanced-DLS算法降低了0.003。這表明本方法在利用連續(xù)合理性檢查對(duì) enhanced-DLS算法生成的候選假位置篩選后，從個(gè)人查詢熵的角度來說，并沒降低單次請(qǐng)求時(shí)用戶的隱私保護(hù)等級(jí)。

表1 平均信息熵值的對(duì)比

下面將對(duì)本文提出的隱私增強(qiáng)方法與enhanced-DLS算法在單次請(qǐng)求情形下生成的位置集合的匿名區(qū)面積和位置分散度進(jìn)行比較，分別如圖6和圖7所示。

圖6 位置分散度比較

圖6和圖7表明，隨著用戶隱私保護(hù)需求K的提高，本方法與 enhanced-DLS算法所生成的位置集合的位置分散度和形成的匿名區(qū)面積均呈增大趨勢(shì)。位置分散度反映了各位置之間距離的乘積。分散度越大，各位置間的距離就越大，所形成的匿名區(qū)域面積也就越大。雖然在圖 7中，匿名區(qū)域面積的增大存在一定的波動(dòng)，但是造成這個(gè)波動(dòng)的原因是由于本方法與enhanced-DLS算法均考慮假位置與真實(shí)位置間的查詢頻率。通過對(duì)比可以發(fā)現(xiàn)，本方法所生成的位置集合的分散度與形成的匿名區(qū)域面積始終大于enhanced-DLS算法，這表明與enhanced-DLS算法相比，本方法能為用戶提供更好的單次查詢隱私保護(hù)等級(jí)。

圖7 匿名區(qū)域面積比較

4.4 計(jì)算開銷

首先分析時(shí)間可達(dá)性檢查閾值σT與方向相似性判斷閾值σD的設(shè)定對(duì)本方案在計(jì)算開銷上的影響。由于在發(fā)送當(dāng)前服務(wù)請(qǐng)求時(shí)，用戶無法預(yù)測(cè)下次進(jìn)行服務(wù)請(qǐng)求時(shí)的真實(shí)位置，這就使在連續(xù)請(qǐng)求所形成的方向相似的可達(dá)移動(dòng)路徑中，用戶真實(shí)位置的出入度具有很強(qiáng)的隨機(jī)性。因此，在此并不考慮出入度評(píng)估閾值σin?D和 σout?D的設(shè)定對(duì)本方案在計(jì)算開銷上的影響。

在這部分實(shí)驗(yàn)中，設(shè)定用戶的隱私保護(hù)需求K= 6，連續(xù)發(fā)送10次LBS請(qǐng)求，出入度評(píng)估閾值σin?D和 σout?D分別選擇各次實(shí)驗(yàn)中的計(jì)算得到的最小方差值。即在利用出入度對(duì)候選假位置集合進(jìn)行篩選時(shí)，選擇出入度方差最小的候選假位置集合進(jìn)行單次隱私增強(qiáng)篩選。在對(duì)時(shí)間合理性判斷閾值設(shè)定對(duì)本文所提方案的性能影響實(shí)驗(yàn)中，設(shè)定方向相似性的閾值 σD=75°；而在對(duì)方向相似性的判斷閾值變化對(duì)本文所提方案的性能影響實(shí)驗(yàn)中，設(shè)定時(shí)間可達(dá)性檢查閾值σ=。具體的實(shí)驗(yàn)結(jié)果如

T

圖8所示。

圖8 本方法性能測(cè)試

通過圖8可以發(fā)現(xiàn)，隨著時(shí)間可達(dá)性檢查閾值σT與方向相似性判斷閾值σD的不斷變大，本方法所需要的計(jì)算時(shí)間也不斷變小。其主要原因是：隨著閾值的變大，滿足時(shí)間可達(dá)性檢查和方向相似性判斷的候選假位置逐漸增多，減少了由于篩選后剩下的候選假位置個(gè)數(shù)不滿足用戶隱私保護(hù)需求情況的出現(xiàn)，從而避免重新生成更多的候選假位置。以時(shí)間可達(dá)性檢查閾值σ的設(shè)定為例，當(dāng)σ=

TT時(shí)，連續(xù) 10次請(qǐng)求生成最后位置集合的平均時(shí)間為1.75 s，而當(dāng)σ=時(shí)，連續(xù)10次請(qǐng)求生成最后T位置集合的平均時(shí)間為0.05 s。

下面給出K值變化對(duì)本文所提方案的運(yùn)行時(shí)間的影響，從而說明所提方案具有較好的實(shí)用性，如表2所示。在這部分實(shí)驗(yàn)中，設(shè)定用戶連續(xù)發(fā)送10次LBS請(qǐng)求、時(shí)間可達(dá)性檢查閾值σ=、方

T向相似性判斷閾值 σD=75°、出入度評(píng)估閾值σin?D和 σout?D分別選擇各次實(shí)驗(yàn)中的計(jì)算得到的最小方差值。在此要強(qiáng)調(diào)的是，僅羅列出用戶的計(jì)算開銷，而不考慮訪問地圖接口的時(shí)間（受網(wǎng)速和接口的限制等客觀原因的約束）。

表2 本方法所需的計(jì)算時(shí)間

5 結(jié)束語(yǔ)

本文首先通過實(shí)驗(yàn)證明現(xiàn)有保護(hù)單次查詢的假位置方案并不適用于連續(xù)請(qǐng)求場(chǎng)景。造成上述問題的根本原因是用戶提交的相鄰位置集合間具有較為緊密的地理時(shí)空關(guān)系，使攻擊者能通過識(shí)別虛假移動(dòng)路徑的方式正確推測(cè)出某些假位置，甚至直接推測(cè)出用戶的真實(shí)位置。針對(duì)該問題，分別從時(shí)間可達(dá)性、方向相似性和出入度3個(gè)方面考慮相鄰請(qǐng)求中位置集合間的時(shí)空關(guān)系，對(duì)利用現(xiàn)有保護(hù)單次查詢的假位置方案生成的候選假位置進(jìn)行篩選，使用戶在相鄰請(qǐng)求中形成的連續(xù)合理的移動(dòng)路徑數(shù)量遠(yuǎn)大于其位置隱私保護(hù)需求，有效保護(hù)連續(xù)查詢中的用戶位置隱私。并且，本文還基于個(gè)人查詢熵和分散度，從單次查詢隱私保護(hù)的角度再次對(duì)剩余的候選假位置進(jìn)行篩選，使本方案與采用的候選假位置生成方案相比，在不降低單次請(qǐng)求中個(gè)人查詢熵的同時(shí)，能增大位置分散度，為用戶提供更高的單次隱私保護(hù)等級(jí)。同時(shí)，還通過大量實(shí)驗(yàn)證明了方案的有效性和實(shí)用性。

[1] KRUMM J. A survey of computational location privacy[J]. Personal and Ubiquitous Computing, 2009, 13(6)： 391-399.

[2] TIWARI S, KAUSHIK S, JAGWANI P, et al. A survey on LBS： system architecture, trends and broad research areas[C]//LNCS 7108： The 7th International Conference on Databases in Network Information Systems. Heidelberg： Springer. c2011： 223-241.

[3] 王璐, 孟小峰. 位置大數(shù)據(jù)隱私保護(hù)研究綜述[J]. 軟件學(xué)報(bào), 2014,25(4)： 693-712.WANG L, MENG X F. Location privacy preservation in big data era： a survey[J]. Journal of Software, 2014, 25(4)： 693-712.

[4] 王宇航, 張宏莉, 余翔湛. 移動(dòng)互聯(lián)網(wǎng)中的位置隱私保護(hù)研究[J].通信學(xué)報(bào), 2015, 36(9)： 2015167.WANG Y H, ZHANG H L, YU X Z. Research on location privacy in mobile Internet[J]. Journal on Communications, 2015, 36(9)： 2015167.

[5] KIDO H, YANAGISAWA Y, SATOH T. An anonymous communication technique using dummies for location-based services[C]//The International Conference on Pervasive Services 2005. Washington, IEEE,c2005： 88-97.

[6] KIDO H, YANAGISWA Y, SATOH T. Protection of location privacy using dummies for location-based services[C]//The 21st International Conference on Data Engineering Workshops. Washington, IEEE,c2005： 1248.

[7] GRUTESER M, GRUNWALD. Anonymous usage of location-based services through spatial and temporal cloaking[C]//The 1st International Conference on Mobile, Systems, Applications and Services.New York, ACM, c2003： 31-42.

[8] TALUKDER N, AHAMED S I. Preventing multi-query attack in location-based services[C]//The 3rd ACM Conference on Wireless Network Security. New York, ACM, c2010： 25-36.

[9] BERSFORD A R, STAJANO F. Mix zones： user privacy in location-aware services[C]//The 2nd IEEE Annual Conference on Pervasive Computing and Communications Workshops. Washington, IEEE,c2004：127-131.

[10] GAO S, MA J F, SHI W S, et al. TrPF： a trajectory privacy-preserving framework for participatory sensing[J]. IEEE Transactions on Information Forensics and Security, 2013, 8(6)：874-887.

[11] ARDAGNA C, CREMONINI M, DAMIANI E, et al. Location privacy protection through obfuscation-based techniques[C]//The 21st Annual IFIP WG 11.3 Working Conference on Data and Applications Security,Berlin： Springer. c2007： 47-60.

[12] DAMIANI M L, BERTINO E, SILVESTRI. The probe framework for the personalized cloaking of private locations[J]. Transactions on Data Privacy, 2010, 3(2)：123-148.

[13] GHINITA G, KALNIS P, KHOSHGOZARAN A, et al. Private queries in location based services： anonymizers are not necessary[C]//The 2008 ACM SIGMOD International Conference on Management of Data. New York, ACM, c2008： 121-132..

[14] MASCETTI S, FRENI D, BETTINI C, et al. Privacy in geo-social networks： proximity notification with untrusted service providers and curious buddies[J]. VLDB Journal, 2011, 20(4)： 541-566.

[15] LU H, JENSEN C S, YIU M L. Pad： privacy-area aware, dummy based location privacy in mobile services[C]//The Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York, ACM, c2008： 16-23.

[16] NIU B, LI Q, ZHU X et al. Achieving k-anonymity in privacy-aware location-based services[C]//The 33rd Annual IEEE International Conference on Computer Communications. Washington, IEEE, c2014： 754-762.

[17] NIU B, ZHANG Z Y, LI X Q, et al. Privacy-area aware dummy generation algorithms for location-based services[C]//The 2014 IEEE International Conference on Communication. Washington, IEEE, c2014：957-962.

[18] NIU B, LI Q, ZHU X, et al. Enhancing privacy through caching in location-based services[C]//The 34th Annual IEEE International Conference on Computer Communications. Washington, IEEE, c2015：1017-1025.

[19] XU T, CAI Y. Exploring historical location data for anonymity preservation in location-based services[C]//The 27th Conference on Computer Communications. Washington, IEEE, c2008： 13-18.

[20] XU T, CAI Y. Feeling-based location privacy protection for location-based services[C]//The 16th ACM Conference on Computer and Communications Security. New York, ACM, c2009： 348-357.

[21] CHOW C Y, MOKBEL M. Enabling private continuous queries for revealed user locations[C]//The 10th International Symposium on Spatial and Temporal Databases. Berlin, Springer, c2007： 258-275.

[22] 潘曉, 郝興, 孟小峰. 基于位置服務(wù)中的連續(xù)查詢隱私保護(hù)研究[J].計(jì)算機(jī)研究與發(fā)展, 2010, 47(1)： 121-129.PAN X, HAO X, MENG X F. Privacy preserving towards continuous query in location-based services[J]. Journal of Computer Research and Development, 2010, 47(1)： 121-129.

[23] WANG Y, XU D B, HE X, et al. L2P2： location-aware location privacy protection for location-based services[C]//The 31st Annual IEEE International Conference on Computer Communication. Washington,IEEE, c2012： 1996-2004.

[24] LI X H, WANG E M, YANG W D, et al. DALP： a demand-aware location privacy protection scheme in continuous location-based services[J]. Concurrency and Computation： Practice and Experience,2016, 28(4)： 1219-1236.

[25] SCHLEGEL R, CHOW C Y, HUANG Q, et al. User-defined privacy grid system for continuous location-based services[J]. IEEE Transactions on Mobile Computing, 2015, 14(10)： 2158-2172.

[26] BRINKOFFff T. A framework for generating network-based moving objects[J]. Geo Informatica, 2002, 6(2)： 153-180.

Privacy enhancing method for dummy-based privacy protection with continuous location-based service queries

LIU Hai, LI Xing-hua, WANG Er-meng, MA Jian-feng
(School of Cyber Engineering, Xidian Universality, Xi’an 710071, China)

Without need for the third party and sharing key, the dummy-based privacy protection scheme enabled users to obtain the precise query result in location-based services. However, in continuous queries, since the existing dummybased privacy protection schemes ignored the spatio-temporal relevance of the submitted neighbor location sets, the adversary could infer dummies, making that the protection degree of users’ location privacy was reduced. To solve this problem, a dummy-based privacy protection enhancing method toward continuous queries was proposed. In the proposal,the candidate dummies were first generated by the existing dummy-based schemes, and could be filtered through the check of continuous reasonability and single privacy enhancement. Security analysis shows that, in the proposed method, the formed movement paths are indistinguishable in time and space, so that protecting the user’s location privacy effectively in continuous queries. Moreover, extensive experiments indicate that its computation cost is limited, and compared with the scheme adopted to generate candidate dummies, the user’s privacy protection is also enhanced in snapshot query.

location-based service, privacy enhancing, continuous queries, dummy, check of continuous reasonability

The National Natural Science Foundation of China (No.61372075, No.U1405255, No.61202389, No.61472310)

TP309

A

10.11959/j.issn.1000-436x.2016142

2015-10-25；

2016-05-20

李興華，xhli1@mail.xidian.edu.cn

國(guó)家自然科學(xué)基金資助項(xiàng)目（No.61372075, No.U1405255, No.61202389, No.61472310）

劉海（1984-），男，貴州貴陽(yáng)人，西安電子科技大學(xué)博士生，主要研究方向?yàn)殡[私保護(hù)和理性密碼協(xié)議。

李興華（1978-），男，河南南陽(yáng)人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)殡[私保護(hù)、網(wǎng)絡(luò)與信息安全。

王二蒙（1990-），女，陜西渭南人，西安電子科技大學(xué)碩士生，主要研究方向?yàn)槲恢秒[私保護(hù)。

馬建峰（1963-），男，陜西西安人，博士，西安電子科技大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾诺谰幋a、網(wǎng)絡(luò)與信息安全、密碼學(xué)。