k-匿名下通過本地差分隱私實現(xiàn)位置隱私保護

摘要：針對用戶位置隱私保護過程中攻擊者利用背景知識等信息發(fā)起攻擊的問題，提出一種面向移動終端的位置隱私保護方法。該方案通過利用k-匿名和本地差分隱私技術(shù)進行用戶位置保護，保證隱私和效用的權(quán)衡。結(jié)合背景知識構(gòu)造匿名集，通過改進的Hilbert曲線對k-匿名集進行分割，使用本地差分隱私算法RAPPOR擾動劃分后的位置集，最后將生成的位置集發(fā)送給位置服務(wù)提供商獲取服務(wù)。在真實數(shù)據(jù)集上與已有的方案從用戶位置保護、位置可用性和時間開銷方面進行對比，實驗結(jié)果顯示，所提方案在確保LBS服務(wù)質(zhì)量的同時，也增強了位置隱私保護的程度。

關(guān)鍵詞：RAPPOR； k-匿名； Hilbert曲線； 位置保護

中圖分類號：TP309.2文獻標志碼：A

文章編號：1001-3695（2022）08-039-2469-05

doi：10.19734/j.issn.1001-3695.2021.12.0698

Location privacy protection through local differential privacy under k-anonymity

Liu Zhenpenga， b， Miao Deweia， Liu Qiannana， Li Ruilina， Li Xiaofeib

（a.School of Cyber Security amp; Computer， b.Information Technology Center， Hebei University， Baoding Hebei 071002， China）

Abstract：Aiming at the problem that attackers use background knowledge and other information to launch attacks in the process of protecting user location privacy， this paper proposed a location privacy protection method for mobile terminals. This solution used k-anonymity and local differential privacy technology to protect the user’s location to ensure the trade-off between privacy and utility. This scheme combined background knowledge to construct anonymity sets， used the improved Hilbert curve to segment the k-anonymous set， used local differential privacy algorithm RAPPOR to perturb the divided location sets， and finally sent the generated location sets to location service providers to obtain services. Comparing this scheme with existing real data set schemes in terms of user location protection， location availability and time overhead， the experimental results show that the proposed scheme not only ensures the quality of LBS service， but also enhances the degree of location privacy protection.

Key words：RAPPOR; k-anonymity; Hilbert curve; location protection

0引言

互聯(lián)網(wǎng)技術(shù)、衛(wèi)星定位技術(shù)和移動設(shè)備高速發(fā)展，基于地理位置的服務(wù)（location-based service，LBS）受到廣泛應(yīng)用［1，2］。用戶在享受位置服務(wù)帶來的便捷的同時，LBS所帶來的用戶位置隱私泄露問題也造成了極大的困擾。惡意位置服務(wù)提供商（location service provider，LSP）通過用戶位置獲取用戶的敏感信息，嚴重侵害了用戶的隱私。因此，位置隱私保護是用戶隱私保護研究中的熱點問題［3］。

在位置隱私保護研究中，基于匿名的k-匿名技術(shù)被廣泛應(yīng)用，該技術(shù)最早由Sweeney［4］提出，其核心思想為使用屬性泛化使單個數(shù)據(jù)與其他k-1個數(shù)據(jù)無法區(qū)分。Gruteser等人［5］首次將k-匿名技術(shù)作為位置隱私保護手段，通過四叉樹搜索構(gòu)造k-匿名位置模型，保證匿名區(qū)域不小于一定值。但該方法增加了時間開銷，容易造成匿名位置過剩，且匿名的k值是一樣的，無法滿足用戶的個性化選擇。為解決生成匿名位置過剩問題，Kido等人［6］使用隨機策略生成k-匿名集，降低了通信成本，但其沒有考慮一些不合理的虛假位置，降低了安全性和服務(wù)質(zhì)量。Zhu等人［7］在Kido的基礎(chǔ)上添加位置緩存機制，設(shè)計了MobileCache系統(tǒng)，通過減少查詢次數(shù)降低了資源開銷，提高了資源利用率。葉阿勇等人［8］通過考慮服務(wù)相似性生成匿名區(qū)，提升了服務(wù)質(zhì)量，但沒有考慮背景知識對隱私保護的影響。Yin等人［9］將k-匿名方法與假名方法相結(jié)合，通過k的最大值和最小值選擇相應(yīng)的匿名方法，改進了k-匿名位置保護方法。Jin等人［10］設(shè)計了一種基于信任的位置隱藏機制，通過在匿名區(qū)域中添加k-1個可信用戶，保證每個用戶都能達到其所需的匿名級別，但該機制需要依賴集中式匿名服務(wù)器。Ling等人［11］為解決不可信匿名服務(wù)器的問題，構(gòu)造了一種基于偏移網(wǎng)格的分布式位置隱私保護機制。通過歷史查詢概率將位置區(qū)域劃分為位置網(wǎng)格，選擇k-1個網(wǎng)格坐標構(gòu)成匿名集，使不可信匿名服務(wù)器難以獲取用戶真實信息。Zhang等人［12］結(jié)合k-匿名思想，利用不規(guī)則多邊形生成算法生成多邊形匿名區(qū)域，通過設(shè)置密度參數(shù)實現(xiàn)空間匿名性，構(gòu)造虛擬位置。閆光輝等人［13］通過服務(wù)相似性構(gòu)造相似地圖，從相似地圖中選取與用戶真實位置查詢結(jié)果相似的興趣點，并結(jié)合背景知識生成熵最大的匿名集，隨機選取匿名集中的一個位置來完成查詢服務(wù)，在保證用戶隱私安全的同時盡可能提高服務(wù)質(zhì)量。楊洋等人［14］設(shè)計了一種基于歷史查詢概率的k-匿名集選取算法，從地理分布和零查詢兩個方面提升了位置隱私的安全性，但其在構(gòu)建匿名集時需要進行離散處理，增加了匿名集的生成時間。

差分隱私（differential privacy，DP）最早由Dwork［15］于2006年提出，通過嚴謹?shù)臄?shù)學證明，可以保證用戶隱私不受攻擊者所知的背景知識攻擊以及某個數(shù)據(jù)變化的影響。袁健等人［16］設(shè)計了一種Laplace機制和匿名組相結(jié)合的LBS軌跡保護算法，對LBS用戶的真實位置進行多輪加噪生成匿名組，用匿名組來獲取LBS服務(wù)，解決了差分隱私實現(xiàn)軌跡隱私保護時產(chǎn)生的隱私預算過度依賴問題，增強了軌跡隱私保護效果。Wang等人［17］提出了一種基于差分隱私擾動的位置保護方法，利用Hilbert曲線將位置映射到一維空間中，通過Laplace噪聲對位置信息進行擾動，將擾動后的位置信息發(fā)送給服務(wù)商來實現(xiàn)位置保護。Zhang等人［18］采用基于最大—最小距離的多中心聚類算法，生成多組候選虛擬對象，選擇最優(yōu)虛擬候選集實現(xiàn)k-匿名。Zhang等人［19］提出了基于差分隱私的位置隱私保護方案，該方案包括均值算法和匿名算法，通過Laplace機制保護用戶的位置隱私，利用指數(shù)機制保護用戶的查詢隱私。

通過差分隱私保護敏感信息需要依賴可信第三方（fully-trusted third party，TTP）數(shù)據(jù)收集器，但在真實環(huán)境中第三方的安全性往往不能得到保證。因此，有學者提出了本地差分隱私（local differential privacy，LDP）概念［20～22］，用戶可以在本地對敏感數(shù)據(jù)進行處理，從而避免不可信第三方的泄露問題。Wang等人［23］提出了一種基于LDP的位置連續(xù)上傳保護方案，使用Hilbert曲線根據(jù)區(qū)域內(nèi)用戶位置數(shù)量動態(tài)劃分子區(qū)域，通過本地差分隱私對位置進行擾動，將擾動后的位置上傳到服務(wù)器，但其數(shù)據(jù)可用性降低。Wang等人［24］讓參與者根據(jù)當前位置的個人隱私需求，選擇兩種不同的本地差分隱私擾動方法，即RAPPOR和k-RR。對參與者的位置進行區(qū)域分割，用選擇的擾動方法對位置區(qū)域進行擾動，將擾動后的位置發(fā)送到數(shù)據(jù)收集服務(wù)器用于數(shù)據(jù)分析。

針對上述方法中的問題，本文結(jié)合k-匿名和本地差分隱私技術(shù)，提出一種無須TTP且能夠抵御背景知識攻擊的本地差分隱私擾動方案，在保證性能的同時降低了攻擊者獲取用戶信息的概率，進一步提高了用戶位置隱私安全性。

1相關(guān)概念

1.1背景知識

背景知識指用戶在特定位置發(fā)送位置服務(wù)請求的概率。由于實際生活中，人們在不同位置獲取LBS服務(wù)的概率是不同的，所以攻擊者可能通過此類信息推斷匿名用戶的真實位置等敏感屬性。將某個地區(qū)劃分為N×N個位置區(qū)域，每個區(qū)域loci被訪問的概率pi為該區(qū)域的查詢次數(shù)mi與整個地區(qū)查詢次數(shù)M的比值，記為

pi=miM（1）

其中：i=1，2，…，N2，且∑N2i=1pi=1。

1.2位置熵

在不考慮背景知識的前提下，k-匿名保護下用戶真實位置被識別的概率為1/k。設(shè)qi為loci是真實位置的概率，則

qi=pi∑kj=1pj（2）

其中：i=1，2， …，k，且∑ki=1qi=1。

位置熵可以用來預估匿名位置集的隱私保護強度。熵值越大，位置集越無序，隱私保護程度就越高。公式如下：

H=-∑ki=1qi·lb qi（3）

由式（3）可知，當所有qi都為相等的概率值1/k時，位置熵H最大。

1.3Hilbert曲線

Hilbert曲線用于將s維空間Rs映射到一維空間R，表示為H：Rs→R。如果點p∈Rs，則H（p）∈R；也就是說，H（p）是p對應(yīng)的H值。對于點集{p1，p2，…，pn}，H{p1，p2，…，pn}={H（p1），H（p2），…，H（pn）}。Hilbert曲線的編碼規(guī)則如圖1所示。

1.4位置本地差分隱私

存在n個位置，每個位置對應(yīng)一條記錄。給定一個隱私算法N及其定義域Def（N）和值域Ran（N），若任意兩條位置記錄t和t′（t，t′∈Def（N））都滿足相同的輸出結(jié)果t*（t*∈Ran（N）），且滿足以下不等式，則算法N滿足ε-本地化差分隱私。

P（N（t）=t*）≤eεP（N（t′）=t*）（4）

由此可知，本地差分隱私通過控制算法N輸出相似的結(jié)果，使攻擊者無法區(qū)分哪一條數(shù)據(jù)為用戶的真實數(shù)據(jù)。

2位置隱私保護方案

2.1系統(tǒng)結(jié)構(gòu)

在基于可信第三方的模型中，用戶發(fā)起多次請求時，TTP容易變成影響系統(tǒng)效率的阻礙，并且，TTP本身容易受到攻擊，一旦TTP被攻破，用戶的全部隱私信息都會泄露。因此本文所采用的方案不使用TTP，主要由本地用戶和LSP兩部分構(gòu)成，如圖2所示。本地用戶通過無線設(shè)備獲取自身位置信息，并在本地運行隱私保護方案，避免使用不可信第三方造成的安全隱患。將擾動后的位置查詢發(fā)送到LSP，由LSP提供查詢結(jié)果返回給本地用戶，通過位置處理算法對查詢結(jié)果進行處理，將用戶所需的數(shù)據(jù)展現(xiàn)給用戶。

2.2k-匿名位置集生成

在k-匿名集生成過程中，首先根據(jù)用戶歷史查詢記錄獲取用戶在城市興趣點中提交查詢請求的概率，將興趣點的概率按大小排序生成概率表T，將T存入本地便于用戶之后的查詢，對T定期更新防止其數(shù)據(jù)落后。針對攻擊者利用背景知識進行攻擊，應(yīng)當確保匿名集的熵盡可能地大，因此將與用戶真實位置Z查詢概率最接近的點添加到匿名候選區(qū)Lc中。由文獻［13］可知，Lc中的熵隨著位置數(shù)的增加而增多，當位置數(shù)達到2k-2時接近最大熵，且不再明顯增大。位置數(shù)的數(shù)量直接影響了計算開銷，為了權(quán)衡效率和隱私保護性，將Lc中的位置數(shù)量設(shè)為2k-2。為了保證匿名集中所選位置具有較好的效用，在Lc生成過程中，以用戶真實位置為中心，根據(jù)歐幾里德距離選擇最近的興趣點。生成Lc的算法如下：

算法1匿名候選區(qū)Lc生成算法

輸入：T、Z、k。

輸出：Lc。

a）從T中獲取Z的查詢概率Zp；

b）獲取與Zp差值不超過ρ的興趣點，存入臨時位置集R中；

c）根據(jù)dis（ri，Z）=（xr－xZ）2+（yr－yZ）2計算R中各個位置ri到Z的歐幾里德距離Si；

d）堆排序法取Si最小的前2k-2個興趣點，存入Lc；

e）結(jié)束。

如圖3所示，通過查詢表T獲取地圖中興趣點概率后與Z比較，可得興趣點L1、L2、L3、L4、L5與Z概率差值不超過ρ=0.01，計算選中的興趣點與Z的歐幾里德距離Si={1，2，3，4，5}。設(shè)k=2，比較Si后得Lc={L2，L3}。設(shè)臨時位置集R中含有n個位置點，算法1的空間復雜度為O（n）。使用堆排序?qū)中位置點到Z的距離進行排序，時間復雜度為O（nlog n）。

2.3IHC劃分興趣點

在生成的Lc中隨機取k-1個位置與用戶真實位置組成k-匿名集L。在生成L的過程中，應(yīng)當盡可能地使所取位置點分散，保證匿名區(qū)域的范圍，將各個興趣點之間的歐幾里德距離之和作為衡量離散度的標準，通過多次隨機分配，選取位置點最分散的匿名集。這時攻擊者從L中得到用戶真實位置的概率接近1/k。由于本文選擇匿名位置的標準之一是與真實位置的歐幾里德距離所產(chǎn)生的匿名位置會以真實位置為中心，這不利于保護真實位置。為了進一步降低攻擊者獲取真實位置的概率，使用改進的Hilbert曲線（improved hilbert curve，IHC）對位置進行劃分，將劃分后的地圖通過RAPPOR進行擾動。

Hilbert曲線能夠?qū)⒌乩砦恢脧亩S空間映射到一維空間上，能夠保證在空間上相鄰的點投射到一維空間后也相鄰，減少了數(shù)據(jù)處理時間，提高了數(shù)據(jù)處理效率。然而Hilbert曲線無法反映興趣點的密集度分布，通常興趣點密集的位置應(yīng)當使用更細的粒度劃分。IHC的構(gòu)建如下：將L中距離Z最遠的點作為邊界R，使所有位置點包含在N×N的地圖空間中。當區(qū)域內(nèi)的興趣點數(shù)大于閾值σ=1時，將該區(qū)域遞歸地劃分成四個大小相同的正方形子區(qū)域。圖4（a）為位置點劃分后的區(qū)域分布，保證了位置點的密度分布。將劃分后的IHC存儲到四叉樹中，存儲方式如圖4（b）所示，興趣點數(shù)量為k，文件的存儲開銷為Ｏ（k），計算各個興趣點IHC值的時間復雜度為Ｏ（k）。與Hilbert曲線相比，IHC劃分可以節(jié)省存儲空間，提升計算效率。

2.4基于本地差分隱私的RAPPOR擾動

RAPPOR［22］能夠?qū)⒔K端用戶眾包數(shù)據(jù)進行匿名，提供了高效的隱私和效用，且不依賴可信第三方。對于映射到Hilbert曲線上的匿名候選位置，通過RAPPOR可實現(xiàn)隨機擾動，獲得強大的隱私保護。設(shè)A={a1，a2，…，an}為地圖劃分后的區(qū)域ID，n為劃分后的區(qū)域總數(shù)。對于第i個區(qū)域，如果存在選中的興趣點，ai設(shè)置為1；否則ai設(shè)置為0。設(shè)R為n位數(shù)組，Rj表示R中第j位的值，當aj為1時，R對應(yīng)的位設(shè)為1，其他位設(shè)為0，如式（5）所示。

Rj=1ifaj=10otherwise （5）

接下來是擾動從式（5）中獲取的R。R中每個位進行隨機響應(yīng)擾動，如式（6）所示。

P（R′j=x）=0.5f x=10.5fx=01－fx=Rj（6）

其中：f（f∈［0，1］）為控制隱私級別的概率參數(shù)，越接近1的值擁有更強的隱私保證。在RAPPOR中，產(chǎn)生的R′被稱為永久隨機響應(yīng)。

然后，將另一個擾動施加到R′的每一位，得到瞬時隨機響應(yīng)，表示為U，如式（7）所示。

P（Uj=1）=qifR′j=1pifR′j=0 （7）

生成的U在RAPPOR中稱為瞬時隨機響應(yīng)，其第k位設(shè)置為1的概率受參數(shù)q（或p）和Rk影響。根據(jù)RAPPOR，上述隨機編碼方法滿足ε-差分隱私。

初始被選中區(qū)域經(jīng)過擾動后仍被選中的概率為

q*=P（Ui=1|Ri=1）=12f（p+q）+（1－f）q（8）

初始未被選中區(qū)域擾動后被選中的概率為

p*=P（Ui=1|Ri=0）=12f（p+q）+（1－f）p（9）

ε=k ln（q*（1－p*）p*（1－q*））（10）

RAPPOR擾動后，通過IHC解碼獲取地理位置集R，使用R進行查詢即可保證用戶位置隱私。k-匿名集經(jīng)過擾動后，用戶真實位置可能在擾動中丟失，當真實位置不在R中時，對于LBS服務(wù)器返回的匿名集的查詢結(jié)果，獲取與用戶真實位置歐幾里德距離最近的n個位置點的查詢結(jié)果，對所獲取的位置信息取并集，作為用戶的查詢信息。位置并集算法如算法2所示。

算法2位置并集獲取算法

輸入：R={lt，t=1，2，…，r}。

輸出：結(jié)果集T。

a）設(shè)T為空；

b）對于R中所有位置點，計算與用戶真實位置的歐幾里德距離；

c）堆排序取與用戶位置距離最小的前n個位置；

d）選取一個位置，將其查詢結(jié)果的興趣點存入T；

e）依次查詢n個位置的查詢結(jié)果，與T求并集后存入T；

f）返回T。

圖5為位置集R中興趣點的查詢結(jié)果。位置集R={L1，L2，L3，L4，L5}為擾動后選取到的五個興趣點，n取3，選取歐幾里德距離最小的前三個位置點為L2、L4、L5，其查詢結(jié)果為L2={a，b，e，f}，L4={e，f，g}，L5={c，d}，則取并集后用戶獲得的查詢信息為T={a，b，c，d，e，f，g}。設(shè)R中含有r個位置點，則堆排序的時間復雜度為O（rlog r），設(shè)每個位置含有m個查詢結(jié)果，生成查詢結(jié)果T的時間復雜度為O（nmlog n），因此算法2的時間復雜度為max（O（rlog r），O（nmlog n））。

3實驗與性能評估

3.1實驗環(huán)境與方法

采用舊金山數(shù)據(jù)集［25］驗證所設(shè)計方案的性能。該數(shù)據(jù)集包含174 956個興趣點。如圖6所示，x和y分別表示經(jīng)緯度轉(zhuǎn)換成的直角坐標。使用Python3.6編程實現(xiàn)，操作系統(tǒng)為Windows 10家庭版，計算機CPU型號為Intel i7，內(nèi)存容量為64 GB。

通過LBS服務(wù)器可以獲取用戶歷史查詢記錄。由文獻［26］可知，當無法獲取查詢記錄時，可以通過地圖上的興趣點數(shù)代替用戶查詢記錄。本實驗使用舊金山數(shù)據(jù)集的興趣點作為用戶查詢記錄。將地圖分割為100×100相同大小的位置單元，計算每個位置單元歷史查詢概率作為先驗概率，在每個位置單元中隨機選擇一個興趣點。興趣點的查詢概率為相應(yīng)位置單元的歷史查詢概率，用戶所在位置單元的興趣點為其真實位置點。

3.2安全性分析

從匿名集的熵和攻擊算法識別概率方面進行安全性分析，并將本文方案與其他方案進行比較。其中每組數(shù)據(jù)取100次實驗的平均值，k的取值為2～30。

3.2.1攻擊方法分析

對于LBS服務(wù)，主要有背景攻擊、概率攻擊和語義攻擊。對于背景攻擊，位置隱私通常通過消除背景信息和用戶當前位置之間的聯(lián)系來保護。

概率攻擊指攻擊者通過已知信息篩選出不合理的位置點，如河流、沙漠等，從而提高發(fā)現(xiàn)用戶真實位置的概率。這些位置點與用戶真實位置沒有直接關(guān)聯(lián)，但是通過過濾k-匿名集中一些虛假位置點，使匿名集不滿足k-匿名要求，降低隱私保護水平，起到了輔助攻擊的效果。通常情況下，對于概率攻擊，可以在獲取查詢用戶的歷史查詢記錄后，將查詢概率高的位置作為虛假位置點，迷惑攻擊者。本文將真實興趣點作為虛假位置，選擇與用戶真實位置查詢概率相同的位置點構(gòu)成候選區(qū)集合，有效避免了概率攻擊的發(fā)生。

語義攻擊的形式很多，其中位置同質(zhì)攻擊是語義攻擊中一種常見的攻擊手段。位置同質(zhì)攻擊是當匿名位置和用戶真實位置間的距離過于接近時，即使達到了k-匿名要求，但是匿名區(qū)域太小，攻擊者可以通過位置聚類等方法進一步縮小匿名區(qū)域，從而增大獲取用戶真實位置的概率。本文方案選擇位置分散度最大的位置集合作為匿名集，降低了攻擊者利用位置同質(zhì)攻擊獲取真實位置的概率。

3.2.2位置熵

為了更好地驗證本文方案的性能，使用文獻［13，14］和最優(yōu)選擇進行對比。由式（3）可知，k不變時位置熵的大小受匿名集中興趣點的查詢概率影響，查詢概率之間差值越小，熵越大，當匿名集中所有位置查詢概率都相等時，所生成匿名集的位置熵最大，本文將這種情況定義為最優(yōu)選擇。每個方案實驗結(jié)果如圖7所示。

由圖7可以看到，生成k-匿名集的位置熵隨著k的增大而增大，即匿名集的安全性增強。其中最優(yōu)選擇法的熵值最大，文獻［13，14］在生成匿名集的過程中充分考慮了興趣點的查詢概率，選取與用戶位置查詢概率相近的興趣點構(gòu)成匿名集，因此所選位置的熵值與最優(yōu)選擇相近，分別比最優(yōu)選擇平均低0.5%和3%。因為本文方法在設(shè)計中考慮了攻擊者可知的背景信息，盡可能地保證了k-匿名集中的位置點查詢概率相同。本文在算法1中引入了差值參數(shù)ρ，通過減小ρ選取概率最近的興趣點構(gòu)造匿名集，生成的匿名集的熵值與最優(yōu)選擇法最接近，僅比其平均低0.3%，所以本文方法生成的匿名集具有很高的隱私保護度。

3.2.3攻擊算法識別用戶位置概率

當攻擊者獲取用戶所發(fā)送匿名集R后，結(jié)合背景信息對用戶位置發(fā)起攻擊，通過文獻［14］中所用攻擊算法推斷用戶的真實位置。攻擊者獲取用戶發(fā)送位置集后，結(jié)合邊信息推斷用戶位置分布概率，確定用戶真實位置。圖8為攻擊算法推斷文獻［13，14，17］和本文方案在不同隱私度k下匿名集位置分布的概率。式（6）中f的取值決定初始擾動的程度，f取1時為完全隨機響應(yīng)，取0時為無擾動，為了保證隱私和效用的平衡，取f為0.5。式（7）中，q、p決定查詢位置集的擾動程度以及位置集中的興趣點數(shù)量，p+q值越大，查詢集中位置點越多，p+q=1可保證擾動前后興趣點數(shù)目基本不變，通過分析查詢結(jié)果的效用，q、p分別取0.75、0.25。通過實驗得算法2中n取值為k/2時，生成的查詢結(jié)果與真實位置查詢結(jié)果基本相同，且效率最高，因此本文中n取值為k/2。

由圖8可知，本文方案所生成的匿名集中用戶真實位置被識別的概率要低于其他三種方案，相比于文獻［13，14］，本文方案添加了RAPPOR擾動，使用戶真實位置出現(xiàn)不存在于匿名集的情況，增加了匿名集的隨機性。文獻［17］選取混淆位置時未考慮背景知識信息，通過背景知識可縮小用戶位置范圍。本文方案匿名區(qū)域隨著k值的增加而增大，降低了攻擊者通過語義攻擊等方法獲取用戶位置的概率，有效提升了用戶位置保護效果。

3.3性能分析

算法在保證用戶位置隱私安全性的同時應(yīng)當充分考慮其性能效用，圖9表示文獻［13，14，17］和本文方案查詢位置服務(wù)可用性比較。由圖9可以看出，隨著k值增大，服務(wù)可用性降低，本文方法生成匿名集的同時能夠更好地保證查詢結(jié)果的可用性，這是因為本文的匿名集中存在包含用戶真實位置和不包含真實位置兩種情況。當包含真實位置時，位置可用性為最優(yōu)；當不包含用戶真實位置時，通過算法2獲取用戶真實位置附近的查詢結(jié)果集，可以保證查詢結(jié)果的可用性。相同情況下本文方法比文獻［13，14，17］分別平均高11.95%、5.92%和29.51%。

圖10為文獻［13，14，17］和本文方案的時間開銷。通過對比可知，隨著k值的增加，算法執(zhí)行時間逐漸增多。文獻［14］構(gòu)造匿名集的同時需要對位置進行離散選擇，因此其運行時間比其他方法略長。本文方法由于添加了擾動，導致其時間略高于文獻［13］。

4結(jié)束語

對于位置服務(wù)中存在的用戶位置隱私保護的問題，本文對現(xiàn)有位置隱私保護方法進行研究，提出基于本地差分隱私的匿名保護方案，對k-匿名集中的候選位置進行擾動，降低了用戶真實位置泄露的概率。通過安全性和可用性分析，證明了本文方案對于用戶隱私和效用起到了很好的權(quán)衡，性能得到了明顯提升。

本文方案在使用匿名集進行查詢訪問時，存在查詢結(jié)果利用率低的問題。在接下來的工作中，將通過使用本地緩存的方式提高查詢資源利用率，降低用戶和LBS服務(wù)器交互的次數(shù)，提升用戶位置隱私保護程度。

參考文獻：

［1］Dilay P， Udai P R. Towards privacy-preserving dummy generation in location-based services ［J］. Procedia Computer Science， 2020， 171： 1323-1326.

［2］Seo Y D， Cho Y S. Point of interest recommendations based on the anchoring effect in location-based social network services ［J］. Expert Systems with Applications， 2021， 164： article ID 114018.

［3］張青云， 張興， 李萬杰， 等. 基于LBS系統(tǒng)的位置軌跡隱私保護技術(shù)綜述 ［J］. 計算機應(yīng)用研究， 2020， 37（12）： 3534-3544. （Zhang Qingyun， Zhang Xing， Li Wanjie， et al. Overview of location trajectory privacy protection technology based on LBS system ［J］. Application Research of Computers， 2020， 37（12）： 3534-3544.）

［4］Sweeney L. k-anonymity： a model for protecting privacy ［J］. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2002， 10（5）： 557-570.

［5］Gruteser M， Grunwald D. Anonymous usage of location-based ser-vices through spatial and temporal cloaking ［C］// Proc of the 1st International Conference on Mobile Systems， Applications and Services. New York： ACM Press， 2003： 31-42.

［6］Kido H， Yanagisawa Y， Satoh T. An anonymous communication technique using dummies for location-based services ［C］// Proc of International Conference on Pervasive Services. Piscataway， NJ： IEEE Press， 2005： 88-97.

［7］Zhu Xiaoyan， Chi Haotian， Niu Ben， et al. MobiCache： when k-anonymity meets cache ［C］// Proc of IEEE Global Communications Conference. Piscataway， NJ： IEEE Press， 2013： 820-825.

［8］葉阿勇， 李亞成， 馬建峰， 等. 基于服務(wù)相似性的k-匿名位置隱私保護方法 ［J］. 通信學報， 2014， 35（11）： 162-169. （Ye Ayong， Li Yacheng， Ma Jianfeng. et al. k-anonymous location privacy protection method based on service similarity ［J］. Journal on Communications， 2014， 35（11）： 162-169.）

［9］Yin Chunyong， Xi Jinwen， Sun Ruxia. Location privacy protection based on improved K-value method in augmented reality on mobile devices ［J］. Mobile Information Systems， 2017， 12： 1-7.

［10］Jin Lei， Li Chao， Palanisamy B， et al. k-trustee： location injection attack-resilient anonymization for location privacy ［J］. Computers amp; Security， 2018， 78（2）： 212-230.

［11］Ling Jie， Xu Junyi. Decentralized location privacy protection method of offset grid ［C］// Proc of the 3rd International Conference on Mechatronics Engineering and Information Technology. ［S.l.］：Atlantis Press， 2019： 113-120.

［12］Zhang Yongbing， Zhang Qiuyu， Yan Yan， et al. A k-anonymous location privacy protection method of polygon based on density distribution ［J］. International Journal of Network Security， 2021， 23（1）： 57-66.

［13］閆光輝， 劉婷， 張學軍， 等. 抵御背景知識推理攻擊的服務(wù)相似性位置k-匿名隱私保護方法 ［J］. 西安交通大學學報， 2020， 54（1）： 8-18. （Yan Guanghui， Liu Ting， Zhang Xuejun， et al. Ser-vice similarity location k-anonymous privacy protection method resisting background knowledge reasoning attack ［J］. Journal of Xi’an Jiaotong University， 2020， 54（1）： 8-18.）

［14］楊洋， 胡曉輝， 杜永文. 基于歷史查詢概率的k-匿名啞元選取算法 ［J］. 計算機工程，2022，48（2）：147-155. （Yang Yang， Hu Xiaohui， Du Yongwen. k-anonymous dummy selection algorithm based on historical query probability ［J］. Computer Engineering，2022，48（2）：147-155.）

［15］Dwork C. Differential privacy ［C］// Proc of International Colloquium on Automata， Languages， and Programming. Berlin： Springer， 2006： 1-12.

［16］袁健， 王迪， 高喜龍， 等. 基于差分隱私的匿名組LBS軌跡隱私保護模型 ［J］. 小型微型計算機系統(tǒng)， 2019， 40（2）： 341-347. （Yuan Jian， Wang Di， Gao Xilong， et al. An anonymous group LBS trajectory privacy protection model based on differential privacy ［J］. Journal of Chinese Computer Systems， 2019， 40（2）： 341-347.）

［17］Wang Jie， Wang Feng， Li Hongtao. Differential privacy location protection scheme based on Hilbert curve ［J］. Security and Communication Networks， 2021， 2021（1）： article ID 5574415.

［18］Zhang Yongbing， Zhang Qiuyu， Li Zongyi， et al. A k-anonymous location privacy protection method of dummy based on geographical semantics ［J］. International Journal of Network Security， 2019， 21（6）： 937-946.

［19］Zhang Qingyun， Zhang Xing， Wang Mingyue， et al. DPLQ： location-based service privacy protection scheme based on differential privacy ［J］. IET Information Security， 2021， 15（6）： 442-456.

［20］Duchi J C， Jordan M I， Wainwright M J. Local privacy and statistical minimax rates ［C］// Proc of the 54th IEEE Annual Symposium on Foundations of Computer Science. Piscataway， NJ： IEEE Press， 2013： 429-438.

［21］Fanti G， Pihur V， Erlingsson ú. Building a RAPPOR with the unknown： privacy-preserving learning of associations and data dictionaries ［J］. Proc on Privacy Enhancing Technologies， 2016， 2016（3）： 41-61.

［22］Erlingsson ú， Pihur V， Korolova A. RAPPOR： randomize aggregatable privacy-preserving ordinal response ［C］// Proc of ACM SIGSAC Conference on Computer and Communications Security. New York： ACM Press， 2014： 1054-1067.

［23］Wang Xiongjian， Yang Weidong. Protection method of continuous location uploading based on local differential privacy ［C］// Proc of International Conference on Networking and Network Applications. Piscataway， NJ： IEEE Press， 2020： 157-161.

［24］Wang Jian， Wang Yanli， Zhao Guosheng， et al. Location protection method for mobile crowd sensing based on local differential privacy preference ［J］. Peer-to-Peer Networking and Applications， 2019， 12（5）： 1097-1109.

［25］Brinkhoff T. A framework for generating network-based moving objects ［J］. GeoInformatica， 2002， 6（2）： 153-180.

［26］Pingley A， Zhang Nan， Fu Xinwen， et al. Protection of query privacy for continuous location based services ［C］// Proc of IEEE INFOCOM. Piscataway， NJ： IEEE Press， 2011： 1710-1718.

收稿日期：2021-12-13；修回日期：2022-02-02基金項目：河北省自然科學基金資助項目（F2019201427）；教育部\"云數(shù)融合科教創(chuàng)新\"基金資助項目（2017A20004）

作者簡介：劉振鵬（1966-），男，河北保定人，教授，博導，博士，主要研究方向為網(wǎng)絡(luò)信息安全、隱私保護等；苗德威（1998-），男，河北邯鄲人，碩士研究生，主要研究方向為信息安全、位置隱私保護；劉倩楠（1999-），女，陜西渭南人，碩士研究生，主要研究方向為區(qū)塊鏈、隱私保護；李瑞林（1996-），男，河南周口人，碩士研究生，主要研究方向為隱私保護、入侵檢測；李小菲（1979-），女（通信作者），河北保定人，工程師，碩士，主要研究方向為網(wǎng)絡(luò)信息安全、隱私保護（lixiaofei@hbu.edu.cn）.