裴媛媛，石潤華，仲 紅，張 順

（1.安徽大學(xué)計算智能與信號處理教育部重點實驗室，合肥 230039；2.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥 230601）

面向位置服務(wù)的用戶隱私保護

裴媛媛1，2，石潤華1，2，仲 紅1，2，張 順1，2

（1.安徽大學(xué)計算智能與信號處理教育部重點實驗室，合肥 230039；2.安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院，合肥 230601）

傳感器技術(shù)和移動通信設(shè)備的發(fā)展使位置服務(wù)（LBS）得到廣泛應(yīng)用。與此同時，在服務(wù)過程中所產(chǎn)生的隱私問題也成為關(guān)注的焦點。為此，針對LBS位置隱私的保護問題，構(gòu)造一個用戶協(xié)作的分布式模型，并設(shè)計一種新的隱私保護方案。在構(gòu)建匿名區(qū)時，使用貝葉斯Nash均衡思想以及安全多方求和技術(shù)以保證用戶信息的隱私。在處理查詢結(jié)果時，引入Voronoi圖的方法以提高查詢效率。分析結(jié)果表明，該方案考慮了用戶節(jié)點自私和不可信的情況，并且簡化了查詢過程，在保護隱私的同時可提高服務(wù)的整體性能。

位置隱私；用戶協(xié)作；貝葉斯Nash均衡；安全多方求和；Voronoi圖

DO I：10.3969/j.issn.1000-3428.2015.10.005

1 概述

隨著無線通信和移動技術(shù)的飛速發(fā)展，位置服務(wù)（Location-based Service，LBS）應(yīng)運而生。LBS就是將移動設(shè)備（如智能手機、平板電腦等）的位置和其他信息整合起來，為用戶提供增值服務(wù)［1］，其主要的應(yīng)用背景有：緊急救援服務(wù)，如“查詢離我最近的醫(yī)院”；信息娛樂服務(wù)，如“查詢離我最近的 KTV”；交通導(dǎo)航服務(wù)，如“根據(jù)行駛道路的擁擠狀況選擇最優(yōu)路徑”；廣告分發(fā)服務(wù)，如“向某超市餐館外100 m的用戶發(fā)送電子優(yōu)惠券”。顯而易見，這些服務(wù)能給人們的生活帶來便利，但人們在享受高品質(zhì)服務(wù)的同時，也可能泄露了部分個人隱私。例如，攻擊者通過竊聽，獲取用戶的位置和查詢內(nèi)容推斷出用戶的身份，進而獲得更多的用戶隱私信息。換言之，人們的隱私和安全受到了威脅。一般地，服務(wù)質(zhì)量和隱

私保護程度是一對矛盾體，提供精確位置可享受高質(zhì)量的服務(wù)，而隱私保護又要求不能暴露確定位置。因此，如何在這兩點之間達到一個平衡，是多數(shù)研究者所要思考的問題。除此之外，文獻［1］還列出了在研究位置隱私保護過程中面臨的其他挑戰(zhàn)，也都是在設(shè)計方案時需要考慮的。

近年來，關(guān)于位置隱私保護的研究最經(jīng)典的模型當(dāng)屬k-匿名模型，多數(shù)研究也是基于此基礎(chǔ)之上，且采用中心服務(wù)器結(jié)構(gòu)。該結(jié)構(gòu)就是在用戶和服務(wù)提供商之間加入了一個可信第三方，即可信匿名服務(wù)器，用于將用戶精確的位置模糊處理，產(chǎn)生一個保護用戶位置的區(qū)域。

中心服務(wù)器結(jié)構(gòu)降低了客戶端的負擔(dān)，但其缺點也很明顯：（1）位置匿名服務(wù)器可能成為系統(tǒng)處理上的瓶頸；（2）當(dāng)位置匿名服務(wù)器變得不可信時，將會導(dǎo)致極為嚴(yán)重的后果。為此，本文提出一個無可信第三方，通過用戶之間協(xié)作完成的分布式位置隱私保護方案。

2 研究進展

在位置隱私保護中有3種常見的設(shè)計思想：k-匿名，混合區(qū)，虛擬節(jié)點。

（1）k-匿名：使用包含 k個節(jié)點的一塊區(qū)域來代替某一具體位置發(fā)送給服務(wù)提供者，以使得攻擊者沒有辦法確定用戶的真實位置。文獻［2］提出k-匿名的概念，使用到關(guān)系數(shù)據(jù)庫的數(shù)據(jù)隱私保護中。文獻［3］將 k-匿名的概念應(yīng)用到位置隱私上來，提出位置k-匿名。文獻［4］提出個性化 k-匿名算法，針對不同應(yīng)用背景的隱私需求，但它只簡單介紹個性化位置 k-匿名的基本概念和設(shè)計的基本思想。所以，文獻［5］繼續(xù)完善，提出一套完整的體系結(jié)構(gòu)。文獻［6］使用博弈論的方法獲取 k-匿名，解決了節(jié)點密度低時如何保證達到 k-匿名的問題。

（2）混合區(qū)：指定一個區(qū)域作為混合區(qū)，在進入該區(qū)域內(nèi)所有節(jié)點同時改變自己的假名，之后，監(jiān)聽者則不能再繼續(xù)跟蹤下去，因為它沒有辦法確定新舊假名之間的映射。關(guān)于這方面的研究最初是文獻［7-8］提出混合區(qū)的結(jié)構(gòu)，并使用熵的概念來分析其隱私性。文獻［9］提出了一個時空數(shù)據(jù)的 k-匿名模型，它將混合區(qū)思想與k-匿名結(jié)合起來，對前面的混合區(qū)模型進行完善，但它們都沒考慮實際的道路網(wǎng)絡(luò)分布情況。文獻［10］提出基于道路網(wǎng)絡(luò)的一個混合區(qū)方案，它將混合區(qū)由理論矩形變化到道路網(wǎng)絡(luò)并加入了多種影響因素。文獻［11］提出流量感知多混合區(qū)的放置算法，考慮了道路流量分布不均勻情況下，在何處安放混合區(qū)，以使其效益達到最大的問題。文獻［12］提出分布式混合區(qū)算法，它是從用戶角度出發(fā)，根據(jù)博弈論的思想，決定是否加入某混合區(qū)，使自已利益最大化。

（3）虛擬節(jié)點：指產(chǎn)生假的位置信息，代替真實位置發(fā)送給LBS，或者與真實位置一起發(fā)送過去，達到混淆的目的。文獻［13］提出虛擬節(jié)點的匿名技術(shù)，但它沒有具體考慮虛擬節(jié)點移動軌跡的限制。文獻［14］使用虛擬節(jié)點保護移動軌跡，解決了上面的問題，且提出了 2種生成虛擬軌跡的方案。2010年，文獻［15］把虛擬節(jié)點應(yīng)用到一個混合匿名系統(tǒng)中，這樣減少了用戶操作并提高系統(tǒng)性能。文獻［16］提出一個關(guān)于隱私保護的混合算法，在模糊區(qū)域產(chǎn)生過程中加入虛擬節(jié)點以達到k-匿名。目前多數(shù)關(guān)于虛擬節(jié)點的方法，是與 k-匿名或混合區(qū)的思想結(jié)合起來，以達到更為滿意的位置隱私保護的效果。

另外，還有基于PIR的位置隱私保護算法，如文獻［17-18］，通過對查詢進行加密以及數(shù)據(jù)庫記錄置亂等方式進行。但由于其加解密過程中產(chǎn)生的計算和通信代價都很大，因此進一步的研究并不多。

上述3種主要思想在已有研究中都存在一些問題。如混合區(qū)中每個用戶假名的變換、保存狀態(tài)信息以及通知應(yīng)用服務(wù)器新用戶的到達等，需要花費不少代價，而且可能導(dǎo)致服務(wù)質(zhì)量的下降。單個節(jié)點產(chǎn)生虛擬節(jié)點，利用假位置查詢，則隱私性不高。k-匿名的使用大多需要借助可信第三方。因此，本文在k-匿名方法的基礎(chǔ)上，通過用戶協(xié)作的方式，并以虛擬節(jié)點為輔助，彌補了上述設(shè)計思想中的不足，并且使隱私匿名度得到提高。

3 本文方案

本文提出的方案是基于分布式結(jié)構(gòu)，包括客戶端和服務(wù)提供商兩部分。具體如圖1所示，不同于原先的獨立式結(jié)構(gòu)，它考慮了全局信息，通過用戶之間的協(xié)作來完成，主要涉及三方面內(nèi)容：（1）如何找到滿足用戶匿名需求的節(jié)點數(shù)；（2）怎樣求取多個節(jié)點的密度中心作為錨點；（3）怎樣才能方便地獲得用戶的查詢結(jié)果候選集以及最后篩選出精確解。

圖1 分布式用戶查詢服務(wù)模型

（1）用戶模型：對于用戶來說，需要保證攻擊者是沒有辦法把他的位置以及查詢結(jié)果與其標(biāo)識符具體的對應(yīng)起來。本文通過選取一個錨點，以此隱藏用戶真實的位置信息。進而，所有用戶的查詢內(nèi)容都與錨點的坐標(biāo)位置對應(yīng)起來。例如，假設(shè)用戶U1，U2，…，Un，各點真實位置坐標(biāo)分別為（χ1，y1），（χ2，y2），…，（χn，yn），其中所有用戶協(xié)作選取的錨點U0坐標(biāo)為（χ0，y0）。假定原查詢請求分別為：U1：（（χ1，y1），Initial-Q1），U2：（（χ2，y2），Initial-Q2），…，Un：（（χn，yn），Initial-Qn）。則有了錨點 U0后實際查詢請求分別為：U1：（（χ0，y0），Q1），U2：（（χ0，y0），Q2），…，Un：（（χ0，y0），Qn）。其中Qi定義如下：

定義1 查詢Qi定義為：Qi=｛（χ0，y0），t，reqi，mi｝，其中，（χ0，y0）表示查詢輸入的位置信息，在本文方案中指的是錨點坐標(biāo)；t表示提出查詢的時刻；reqi表示第i個用戶請求查詢的內(nèi)容；mi表示查詢處理過程中返回的候選集內(nèi)節(jié)點個數(shù)，mi的值越大，返回的節(jié)點個數(shù)越多，也越有利于用戶找到最優(yōu)的結(jié)果，但處理效率會降低，這由用戶具體權(quán)衡。

定義2 關(guān)于匿名區(qū)k-AR的表示如下：k-AR=｛gid，k，anchor｝，其中，gid表示匿名組的編號；k表示匿名區(qū)內(nèi)用戶節(jié)點的個數(shù)；anchor表示匿名區(qū)的錨點，是通過求取區(qū)域的密度中心獲得的，每個用戶都可使用該位置提出服務(wù)請求。

（2）攻擊者模型：攻擊者可以在網(wǎng)絡(luò)中竊聽到節(jié)點的查詢內(nèi)容和返回的查詢結(jié)果，但不可以篡改。然后再根據(jù)事先獲取的一些知識，以一定的概率推理出某個查詢對應(yīng)的用戶隱私信息。

3.1 查詢預(yù)處理

假定用戶U1作為算法的發(fā)起者，發(fā)出尋找用戶節(jié)點共同構(gòu)建匿名組的請求Discoνer，如算法1所示。U1首先生成新的組編號 gid，發(fā)送廣播消息＜gid，h＞，h初始設(shè)為一個最大值，表示路由轉(zhuǎn)發(fā)的最大跳數(shù)。之后，等待鄰居節(jié)點的響應(yīng)＜res，Ui＞，把發(fā)回響應(yīng)消息的用戶節(jié)點 Ui加入集合 S中且跳數(shù)更改為h-1，繼而判斷或者h=0時，查找用戶節(jié)點的步驟完成，否則利用其相鄰節(jié)點進行下一跳的廣播。

初始基于信息熵理論將匿名性進行量化，如式（1）所示：

建立博弈模型，經(jīng)過一系列的統(tǒng)計和推理，得到如式（2）中所示的策略選擇：

其中，si表示節(jié)點Ui選擇的策略；｛C，D｝為供選擇的集合，C是合作，即生成剩下的個節(jié)點；D是拒絕，即不產(chǎn)生任何虛擬節(jié)點；Gi（C）表示節(jié)點Ui選擇合作所獲取的利益；Gi（D）表示節(jié)點Ui選擇拒絕所獲取的利益，詳細求解見式（3）和式（4）。

其中，dj（θj）表示每一節(jié)點在θj情形下選擇D的可能性；ηj表示節(jié)點選擇D的期望值。

算法1查詢預(yù)處理

3.2 錨點計算

在一般k-匿名算法中，用一個區(qū)域坐標(biāo)代替某一點位置坐標(biāo)發(fā)送給服務(wù)提供商用于查詢。而在本文中用區(qū)域的錨點來替代。這樣，不僅達到了 k-匿名的效果，而且降低了通信代價。在計算錨點時，使用如下公式：

其中，（χ0，y0）是所求錨點的坐標(biāo)；（χi，yi）為用戶節(jié)點Ui的坐標(biāo)。

由式（5）很容易求取錨點的坐標(biāo)，但為保護用戶隱私，本文引入了安全多方計算技術(shù)，設(shè)計了算法2。這樣就可以在不知道每個點的準(zhǔn)確坐標(biāo)情況下，求取所有節(jié)點坐標(biāo)之和，繼而得到筆者想要的結(jié)果，并且很好地抵御了攻擊者竊取位置信息的威脅。

算法2計算錨點

圖2 錨點計算過程

假定有6個用戶參與錨點計算，根據(jù)安全多方求和策略，這些用戶秘密選擇的計算次序為 U1-U3-U4-U2-U6-U5，每個用戶分別對應(yīng)計算一次，當(dāng)U5計算完成返回結(jié)果給U1，進而 U1便可得到錨點的坐標(biāo)。

3.3 查詢處理

前面匿名的過程已處理完畢，而如何用錨點坐標(biāo)去查詢用戶所想要的結(jié)果仍很關(guān)鍵。本文采用了 Voronoi圖的方法，該方法更加清晰簡便。Voronoi圖的作用在于當(dāng)平面中有N個查詢結(jié)果（對應(yīng)查詢空間內(nèi)的 N點），對于每個點 Pi，可以很容易找到平面內(nèi)距離點 Pi比距離其他點更近的區(qū)域。據(jù)此可以利用它作為查找最優(yōu)結(jié)果的工具?？赏ㄟ^對查詢返回結(jié)果構(gòu)造一個Voronoi圖，具體如圖3所示。圖中圓點表示對應(yīng)查詢的多個結(jié)果，菱形表示錨點U0。

圖3 基于Voronoi圖的查詢結(jié)果

當(dāng)返回候選結(jié)果時，選擇錨點所在區(qū)域的生成點以及周邊相鄰的結(jié)果作為候選集合發(fā)送回去。而對于每個用戶節(jié)點收到候選結(jié)果時，使用同樣的方法，判斷節(jié)點具體落在哪個區(qū)域內(nèi)，就可找到想要的結(jié)果。例如，圖中五角星表示一用戶節(jié)點 Ui，明顯可以看出，它要查詢的精確結(jié)果就是 Pi。在該查詢處理部分考慮了2種方法，具體如算法3所示（對于查詢服務(wù)器來說，Ui是未知的，而所有 Pi是已知的）。

算法3查詢結(jié)果處理

上述2種方法的優(yōu)缺點如下：（1）從用戶本身要求考慮，mi值越大，返回的解也就越多，這樣有利于用戶挑選出一個較為接近的結(jié)果，但同時服務(wù)效率可能就不高，反之亦然；（2）確定能為用戶找到最精確的結(jié)果，但查詢時間也許會變長。

4 算法分析

本節(jié)主要對本文方案的算法從如下方面來進行分析：

（1）隱私保護度：算法的前2個步驟都保證了隱私度：一是構(gòu)建匿名區(qū)，二是計算錨點。初始時，查找另外k-1個節(jié)點，共同組建匿名區(qū)，并考慮在節(jié)點不足的情況下，使用博弈論的思想產(chǎn)生虛擬節(jié)點予以補充，以滿足k-匿名。之后，計算錨點時，引入安全多方計算技術(shù)保護各節(jié)點隱私，不僅對于外部攻擊者，而且對于內(nèi)部偽裝在用戶間的攻擊者，也同樣能確保安全傳輸，不暴露位置。另外，該算法的安全性可以控制，即在節(jié)點不足時可以生成虛擬節(jié)點補充，而且可以通過生成虛擬節(jié)點距離的遠近，調(diào)控節(jié)點到錨點的平均距離（Δχ，Δy），這樣就可以根據(jù)網(wǎng)絡(luò)環(huán)境的好壞，動態(tài)地保護隱私。

（2）匿名成功率：考慮用戶節(jié)點密度低時，要想找到滿足匿名需求的節(jié)點就會變得很困難。所以，生成虛擬節(jié)點是個不錯的辦法，但虛擬節(jié)點由誰生成是個問題。在考慮節(jié)點自私的情況，引入博弈論的思想，這樣就保證了算法的成功實行，顯然在這種情況下，匿名成功率比其他算法明顯要高。

（3）效率：就整個查詢過程來說，算法 1是節(jié)點搜索構(gòu)建匿名區(qū)的過程，所牽涉到的計算都是輕量級的，計算復(fù)雜度低。算法2是一個高效的安全多方算法，其通信代價及輪次均為 O（n）。在算法 3中，用Voronoi進行查詢處理時，主要分兩步，第1步的V圖已通過離線過程構(gòu)造好，直接定位就可找到返回的候選結(jié)果，所以復(fù)雜度為 O（1），第2步則需根據(jù)返回的候選結(jié)果集合用戶自己構(gòu)造Voronoi圖，復(fù)雜度為O（m lb m），m為返回的候選結(jié)果個數(shù)。所以，查詢處理效率較高。

進一步，將本文方案與其他主流方案進行了詳細比較，其結(jié)果如表1所示。

表1 方案性能比較

由表1可以明顯看出本文方案綜合性能較強：

（1）安全性：表1中第1種方案，需要一個可信的第三方。而當(dāng)?shù)谌阶兊貌豢尚艜r，它的隱私將受到嚴(yán)重威脅。第 2種方案選取一個錨點用于查詢，但它沒有達到k-匿名。第3種方案獲得了 k-匿名，但沒有考慮計算錨點時位置信息的泄露問題。

（2）匿名成功率：這主要針對在用戶節(jié)點密度低的情況下，第 1種方案顯然沒有考慮這種情況，第2種不需生成匿名區(qū)。

（3）公平性：表1中前3種方案都沒有考慮到用戶的公平性問題，針對不同用戶的主觀需求應(yīng)付出不同的代價。可信第三方：只有第1種需要可信第三方。

（4）效率：第1種方案由于需要返回一個結(jié)果集合交給匿名服務(wù)器處理，當(dāng)查詢用戶過多時，效率會很低。第2種和第3種查詢方法一樣，都是使用增量近鄰查詢，能確保找到精確解，需要查詢時先對數(shù)據(jù)庫中查詢結(jié)果按照與錨點的遠近進行排序，之后多次提出查詢，且每次都需構(gòu)造供應(yīng)空間和需求空間進行比較，這些都是在線過程，因而影響了查詢效率。

5 結(jié)束語

本文采用了分布式的思想，通過用戶之間協(xié)作，并考慮節(jié)點不足情況下，使用貝葉斯Nash均衡算法產(chǎn)生虛擬節(jié)點，以完成 k-匿名區(qū)域的構(gòu)建。匿名區(qū)生成后，計算錨點，用它來代替區(qū)域進行查詢處理。在計算錨點坐標(biāo)值時，引入安全多方求和技術(shù)，避免了各點坐標(biāo)值的泄露。最后，利用Voronoi圖思想進行LBS查詢，與傳統(tǒng)的查詢算法相比，更加便利。分析結(jié)果表明，本文方案達到了k-匿名的效果，保證了隱私，可使服務(wù)質(zhì)量以及整體系統(tǒng)性能得到提升。

未來研究工作將考慮多服務(wù)提供商的情況。此外，目前多數(shù)研究方法都是從客戶端進行處理，因此，下一步將研究從服務(wù)提供者的數(shù)據(jù)庫入手提高安全性和效率。

［1］ 潘 曉，肖 珍，孟小峰.位置隱私研究綜述［J］.計算機科學(xué)與探索，2007，1（3）：268-281.

［2］ Sweeney L.k-anonymity：A Model for Protecting Privacy［J］.International Journal on Uncertainty，F(xiàn)uzziness and Know ledge-based Systems，2002，10（5）：557-570.

［3］ Gruteser M，Grunwald D.Anonymous Usage of Locationbased Services Through Spatial and Temporal Cloaking［C］//Proceedings of the 1st International Con-ference on Mobile Systems，Applications and Services.San Francisco，USA：ACM Press，2003：31-42.

［4］ Gedik B，Liu Ling.A Customizable k-anonymity Model for Protecting Location Privacy［C］//Proceedings of the 1st International Conference on Distributed Computing System s.Columbus，USA：IEEE Com puter Society，2005：620-629.

［5］ Gedik B，Liu Ling.Protecting Location Privacy with Personalized k-anonymity：Architecture and Algorithms［J］.Mobile Computing，2008，7（1）：1-18.

［6］ Liu Xinxin，Liu Kaikai，Guo Linke，et al.A Gametheoretic Approach for Achieving k-anonymity in Location Based Services［C］//Proceedings of INFOCOM’13. Turin，Italy：IEEE Press，2013：2985-2993.

［7］ Beresford A R，Stajano F.Location Privacy in Pervasive Com puting［J］.Pervasive Computing，2003，2（1）：46-55.

［8］ Beresford A R，Stajano F.M ix Zones：User Privacy in Location-aware Services［C］//Proceedings of Pervasive Computing and Communications Workshops.Vienna，Austria：IEEE Press，2004：127-131.

［9］ Zacharouli P，Gkoulalas-Divanis A，Verykios V S.A kanonymity Model for Spatio-temporal Data［C］//Proceedings of ICDEW’07.Washington D.C.，USA：IEEE Press，2007：555-564.

［10］ Palanisamy B，Liu L.Mobimix：Protecting Location Privacy with Mix-zones over Road Networks［C］// Proceedings of ICDE’11.Hannover，Germany：IEEE Press，2011：494-505.

［11］ Liu Xinxin，Zhao Han，Pan Miao，et al.Traffic-aware Multiple Mix Zone Placement for Protecting Location Privacy［C］//Proceedings of INFOCOM’12.Orlando，USA：IEEE Press，2012：972-980.

［12］ Du Suguo，Zhu Haojin，Li Xiaolong，et al.M ix Zone in Motion：Achieving Dynamically Cooperative Location Privacy Protection in Delay-tolerant Networks［J］.IEEE Transactions on Vehicular Technology，2013，62（9）：4565-4575.

［13］ Kido H，Yanagisawa Y，Satoh T.An Anonymous Communication Technique Using Dummies for Locationbased Services［C］//Proceedings of Conference on Pervasive Services.Santorini，Greece：IEEE Press，2005：88-97.

［14］ You T H，Peng W C，Lee W C.Protecting Moving Trajectories with Dummies［C］//Proceedings of Conference on Mobile Data Management.Mannheim，Germany：IEEE Press，2007：278-282.

［15］ Tran M T，Echizen I，Duong A D.Binomial-mix-based Location Anonymizer System with Global Dummy Generation to Preserve User Location Privacy in Locationbased Services［C］//Proceedings of Conference on Availability，Reliability，and Security.Krakow，Poland：IEEE Press，2010：580-585.

［16］ Miura K，Sato F.A Hybrid Method of User Privacy Protection for Location Based Services［C］//Proceedings of CISIS’13.W ashington D.C.，USA：IEEE Press，2013：434-439.

［17］ Khoshgozaran A，Shirani-Mehr H.SPIRAL：A Scalable Private Inform ation Retrieval Approach to Location Privacy［C］//Proceedings of M obile Data Management Workshops.Washington D.C.，USA：IEEE Press，2008：55-62.

［18］ Mouratidis K.Strong Location Privacy：A Case Study on Shortest Path Queries［C］//Proceedings of ICDEW’13. Brisbane，Australia：IEEE Press，2013：136-143.

［19］ Yiu M L，Jensen C S，Huang Xuegang，et al.Spacetwist：Managing the Trade-offs Among Location Privacy，Query Performance，and Query Accuracy in Mobile Services［C］//Proceedings of ICDEW’08.Cancun，Mexico：IEEE Press，2008：366-375.

［20］ 黃 毅，霍 崢，孟小峰.CoPrivacy：一種用戶協(xié)作無匿名區(qū)域的位置隱私保護方法［J］.計算機學(xué)報，2011，34（10）：1976-1985.

編輯 金胡考

User Privacy Protection for Location-based Service

PEI Yuanyuan1，2，SHI Runhua1，2，ZHONG Hong1，2，ZHANG Shun1，2
（1.Key Laboratory of Intelligent Computing&Signal Processing，Ministry of Education，Anhui University，Hefei 230039，China；2.School of Computer Science and Technology，Anhui University，Hefei 230601，China）

With the development of sensor technology and mobile communication equipments，there appears Locationbased Service（LBS），which is widely used.However，privacy issues，which arise in the enjoyment of the services at the same time，are becoming the focus of research.For privacy protection issues in LBS，this paper proposes a distributed model with users’cooperation and designs a new privacy protection scheme.In this scheme，when constructing the anonymous area，it uses Bayesian Nash equilibrium and secure multiparty summation technologies to ensure the user information privacy.When processing the query results，it introduces the Voronoi map method to increase the query efficiency.Analysis experimental result shows that the proposed scheme gives full consideration to the selfishness and unreliability of users.Hence it not only can provide the protection of user privacy，but also can improve the performance of the services.

location privacy；user collaboration；Bias Nash equilibrium；secure multiparty summation；Voronoi map

裴媛媛，石潤華，仲 紅，等.面向位置服務(wù)的用戶隱私保護［J］.計算機工程，2015，41（10）：20-25.

英文引用格式：Pei Yuanyuan，Shi Runhua，Zhong Hong，et al.User Privacy Protection for Location-based Service［J］. Computer Engineering，2015，41（10）：20-25.

1000-3428（2015）10-0020-06

A

TP309

國家自然科學(xué)基金資助項目（61173187，61173188，11301002）；安徽省自然科學(xué)基金資助項目（11040606M 141，1408085QF107）；安徽大學(xué)博士科研啟動經(jīng)費基金資助項目（33190187）；安徽大學(xué)“信息安全”新專業(yè)基金資助項目（17110099）。

裴媛媛（1991-），女，碩士研究生，主研方向：信息安全；石潤華、仲 紅，教授、博士生導(dǎo)師；張 順，講師、博士。

2014-11-04

2014-12-05E-m ail：992755870@qq.com