楊松濤，馬春光

（1.哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001；2.佳木斯大學(xué)信息電子技術(shù)學(xué)院，黑龍江佳木斯154007）

隨機(jī)匿名的位置隱私保護(hù)方法

楊松濤1，2，馬春光1

（1.哈爾濱工程大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001；2.佳木斯大學(xué)信息電子技術(shù)學(xué)院，黑龍江佳木斯154007）

基于空間匿名區(qū)域的研究方法容易受到多查詢攻擊和推理攻擊，從而帶來隱私暴露問題。為了保證基于位置服務(wù)中的隱私安全，基于k?匿名思想，構(gòu)建了隨機(jī)k?隱藏集以滿足位置k?匿名性和位置l?多樣性。隨機(jī)k?隱藏集是由離散的位置點組成，并且彼此之間的網(wǎng)格距離大于閾值s。利用私有信息檢索協(xié)議保證了查詢結(jié)果在檢索過程中的隱私性，實現(xiàn)了服務(wù)提供者在無法知道用戶精確查詢結(jié)果的前提下為用戶提供基于位置的服務(wù)。仿真實驗驗證了算法的安全性和有效性。

無線網(wǎng)絡(luò)；移動通信；隱私保護(hù)；基于位置服務(wù)；位置k?匿名；私有信息檢索；隨機(jī)匿名

Hilbert Cloak（HC）［4］考慮用戶分布的不均勻性對k?匿名的影響，提出了互易性概念。HC方法中使用連續(xù)的網(wǎng)格構(gòu)建盡可能小的ASR來保證隱私，但是有以下缺點：1）沒有考慮位置l?多樣性問題，即多個用戶可能出現(xiàn)在同一語義位置范圍內(nèi)［5］；2）沒有考慮用戶的移動性，即僅適用于快照查詢，易受到連續(xù)查詢攻擊［6?7］；3）互易性屬性僅能保證查詢隱私，但是無法保障位置隱私和軌跡隱私［8］。

LBS系統(tǒng)在現(xiàn)實應(yīng)用中，快照查詢和連續(xù)查詢經(jīng)常交叉進(jìn)行，增加了隱私保護(hù)的復(fù)雜性。攻擊者也會相互勾結(jié)，導(dǎo)致用戶的地理數(shù)據(jù)和社會化數(shù)據(jù)相互關(guān)聯(lián)，同時攻擊者通常具有大量的背景知識，先進(jìn)的數(shù)據(jù)挖掘技術(shù)和強(qiáng)大的關(guān)聯(lián)攻擊造成了一些時空匿名技術(shù)方案的失效。最近研究將PIR理論引入LBS隱私保護(hù)領(lǐng)域。相對于其他隱私保護(hù)方法而言，基于PIR理論的隱私保護(hù)方法［9?11］有不揭露任何空間信息和抗關(guān)聯(lián)攻擊這2個優(yōu)點。

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

考慮到移動用戶與LBS服務(wù)器之間的通信帶寬非常有限，例如：3G上行速度為64～128 k，下行速度為2 M。如果傳輸大的結(jié)果集，需要花費較高的響應(yīng)時間，不能滿足LBS的實時性，因此，本文采用3層中心服務(wù)器結(jié)構(gòu)。該結(jié)構(gòu)（圖1）包括3個部分，即移動客戶端（mobile client，MC）、位置隱藏服務(wù)器（location cloak server，LCs）和LBS服務(wù)器（LBS server，LBSs）。MC與LCs之間使用安全通道傳輸數(shù)據(jù)（如SSL），LCs隱藏了查詢發(fā)出者的身份標(biāo)識、IP地址和位置信息。

圖1所示的系統(tǒng)結(jié)構(gòu)中，敵手攻擊遵循Honest?but?Curious模型，即LBSs在嚴(yán)格執(zhí)行協(xié)議和算法的前提下，同時使用收集到的位置信息和背景知識推斷用戶的敏感信息，甚至LBSs可能出賣用戶的敏感信息給不友好的第3方。

圖1 系統(tǒng)結(jié)構(gòu)Fig.1 System architecture

定義1 可信與半可信主體。設(shè)LBS系統(tǒng)中參與主體的集合為S＝｛S1，S2，…，Sm｝，算法集合為A＝｛A1，A2，…，An｝，協(xié)議集合為P＝｛P1，P2，…，Pk｝，任意Si（i＝1，2，…，m）嚴(yán)格執(zhí)行算法Aj（j＝1，2，…，n）或協(xié)議Pt（t＝1，2，…，k）。如果Si（i＝1，2，…，m）不會保留協(xié)議執(zhí)行的中間過程并推導(dǎo)其他主體的隱私信息，則Si是可信主體，否則是半可信主體。

依照圖1所示的系統(tǒng)結(jié)構(gòu)，本文確定了4個基本假設(shè)如下：

假設(shè)1 LCs和MC是完全可信的。LBSs是半可信的，為用戶提供服務(wù)，但是有可能直接或間接泄露用戶的隱私信息；

假設(shè)2 敵手可以從公共數(shù)據(jù)庫（例如：電話黃頁，家庭住址等）獲得一些先驗知識。同時，敵手具備統(tǒng)計分析和推理能力，可以利用匿名信息和先驗知識形成后驗知識；

假設(shè)3 用戶的分布是有規(guī)律的，但是分布密度是不均勻的，這是符合現(xiàn)實世界情況的，城市中心地帶用戶分布密集，而郊區(qū)用戶數(shù)量較少；

假設(shè)4 LCs使用的匿名算法是公開的。

一個查詢請求處理過程如圖2所示。

圖2 查詢處理過程Fig.2 Query processing

2 隨機(jī)位置隱藏

定義2 （k，s）受限查詢Q（k，s），Q（k，s）以6元組形式表示，形式化表示為

式中：u代表用戶身份的假名；l代表用戶的當(dāng)前位置坐標(biāo)；t代表當(dāng)前查詢時間；c代表用戶的查詢內(nèi)容；s代表用戶要求的網(wǎng)格距離；k代表用戶要求的匿名度。

如果位置集合滿足Q（k，s）中的k、s要求，則稱該位置集合為（k，s）受限位置集合，記為S（k，s）。

定義3 隨機(jī)k?隱藏集（kRCS）。kRCS可以形式化表示為

式中：SID代表kRCS的標(biāo)識符；S（k，s）＝｛l1，l2，…，lk｝，li（i＝1，2，…，k）代表用戶ui的當(dāng)前位置。

定義4 網(wǎng)格距離（D）。用戶之間的網(wǎng)格距離可以形式化表示為

式中：ni、nj分別代表用戶ui、uj的當(dāng)前位置ui.l、uj.l所在網(wǎng)格的序號。

為了方便計算，本文將平面空間劃分為網(wǎng)格圖形式，為每個網(wǎng)格賦予一個序號。以圖3為例，在4×4的網(wǎng)格圖上隨機(jī)分布了20個移動用戶。u1～u20是周期性地向LCs更新位置信息的移動用戶，假設(shè)用戶u3發(fā)出k＝5，s＝2的查詢，則kRCS＝｛SID，（u3.l，u9.l，u12.l，u15.l，u10.l），c，t｝，kRCS算法形成的S（k，s）不是唯一的，這樣有利于增強(qiáng)抗LBSs推理攻擊的能力。

LCs通過執(zhí)行kRCS算法來實現(xiàn)查詢用戶的位置隱藏。具體過程如下：

1）LCs接收到查詢請求Q（k，s），提取參數(shù)l、s和k，構(gòu)建kRCS。初始狀態(tài)下位置集合S（k，s）為空集，LCs將l加入S（k，s）；

2）從每個網(wǎng)格內(nèi)選取一個當(dāng)前用戶的位置并將其加入集合T，要求T中任意2個元素之間的D必須大于s；

3）判斷T中元素個數(shù)是否滿足用戶要求的k值，如果滿足要求，則隨機(jī)選擇k-1個元素加入S（k，s），擾亂S（k，s）中元素的順序，否則位置隱藏失??；

4）提取參數(shù)t、c，與S（k，s）和新生成的kRCS的標(biāo)識符共同構(gòu)成kRCS；

5）LCs發(fā)送kRCS給LBSs，用于檢索服務(wù)。

圖3 4×4空間分區(qū)樣例Fig.3 4×4 space partitioning example

3 私有檢索

定義5 候選結(jié)果集（CS），LBSs對S（k，s）中的每一個位置元素進(jìn)行最近鄰查詢或k?最近鄰查詢，查詢結(jié)果集合為CS，形式化為

式中：ri是S（k，s）中第i個位置的查詢結(jié)果，ri以m位的字符串表示。

本文方法中，k值的大小會影響CS的尺寸，k值較大，CS也較大。LCs對CS求精的方式會增加LCs的計算負(fù)擔(dān)和LCs與LBSs之間的通信負(fù)載。同時，候選結(jié)果集是LBSs推斷用戶位置和身份的重要依據(jù)。因此，本文采用PIR檢索技術(shù)，服務(wù)器無法確定用戶u對第i條記錄感興趣。為了便于PIR檢索，CS以m×k位矩陣表示，即MR＝［r1，r2，…，rk］。MR的第i（i＝1，2，…，k）行數(shù)據(jù)構(gòu)成新的t×t位矩陣Mi，則MR＝［M1，M2，…，Mm］T。類似于可計算PIR協(xié)議中秘密檢索1位數(shù)據(jù)的方法，分別檢索m個矩陣中的數(shù)據(jù)，從而將可計算PIR協(xié)議從秘密檢索1位數(shù)據(jù)擴(kuò)展為秘密檢索m位數(shù)據(jù)。PIR檢索過程如下：

1）LCs隨機(jī)選取k位自然數(shù)N，且N＝q1q2，q1，其中q2是k／2位素數(shù)，產(chǎn)生查詢信息y＝［y1，y2，…，yt］，yb屬于二次非剩余集（QNR），yi屬于二次剩余集（QR），且b≠j，并將y發(fā)送給LBSs；

2）LBSs分別計算M1，M2，…，Mm，

式中：r代表行號，并將Zi＝｛zi［1］，…，zi［t］｝，i＝（1，…，m）發(fā)送給LCs；

3）依據(jù)歐拉準(zhǔn)則，LCs分別計算

如果式（3）為“真”，則zi［r］∈QR，Mi［r，b］＝0，否則，zi［r］∈QNR，Mi［r，b］＝1。

4 分析與驗證

LBS系統(tǒng)中，服務(wù)質(zhì)量和隱私保護(hù)不存在合作的可能，存在的研究工作都基于“零和博弈”的觀點。同時，查詢樣例和查詢結(jié)果集合是攻擊者推斷用戶位置隱私的直接依據(jù)。本文從3個角度分析提出的隨機(jī)匿名方法的抗攻擊能力和服務(wù)質(zhì)量。

1）時空匿名角度。本文提出的隨機(jī)匿名方法中，生成kRCS的集合覆蓋了整個服務(wù)區(qū)域，S（k，s）內(nèi)的元素是離散的和隨機(jī)的，同時滿足了位置k?匿名性和位置l?多樣性。用戶可以提高k值和s值以實現(xiàn)擴(kuò)大匿名區(qū)域范圍，增強(qiáng)隱私度。由于方案中不采用ASR方式，進(jìn)而不會遭受連續(xù)多查詢攻擊和推理攻擊。

2）查詢結(jié)果角度?？捎嬎鉖IR協(xié)議的安全性基于二次剩余假設(shè)，如果N是2個素數(shù)的乘積，即N＝q1q2，q1、q2是大素數(shù)，那么計算模N的平方根等價于對N進(jìn)行因子分解，區(qū)分二次剩余和二次非剩余的概率很小。LBSs根據(jù)kRCS檢索到的CS駐留在LBSs的緩存內(nèi)。在LCs與LBSs之間執(zhí)行PIR協(xié)議過程中，LCs從CS中秘密獲得查詢用戶需要的服務(wù)信息，攻擊者關(guān)聯(lián)查詢用戶位置和查詢內(nèi)容的概率為1／k。所以，本文方法不會遭受關(guān)聯(lián)攻擊。

3）服務(wù)質(zhì)量角度。匿名時間、匿名成功率、服務(wù)時間和通信量是影響服務(wù)質(zhì)量的4個基本要素。kRCS算法的匿名時間和匿名成功率主要取決于網(wǎng)格劃分的精細(xì)度和k值。網(wǎng)格越密，匿名時間越長，匿名成功率越高。k值越大，匿名時間越長，匿名成功率越低。kRCS算法比較簡單，在線性復(fù)雜度的時間內(nèi)即可完成位置匿名。通常情況下，網(wǎng)格數(shù)量和移動用戶數(shù)量遠(yuǎn)遠(yuǎn)大于用戶的隱私要求。因此，在本文方法中，匿名成功率不是關(guān)注的主要問題。服務(wù)時間包括PIR檢索時間和LBSs查詢時間。PIR檢索時間必然延長了總的服務(wù)響應(yīng)時間，也可以在有限多項式時間內(nèi)完成。但是，PIR協(xié)議帶來了高度的隱私性，符合服務(wù)質(zhì)量與隱私之間均衡的理念。LBSs查詢采用簡單的單點最近鄰查詢技術(shù)，優(yōu)于范圍查詢方法，簡化了LBS服務(wù)器的查詢處理過程。LCs與LBSs之間的通信量取決于CS的尺寸和k值。

圖4為隨機(jī)匿名方法與基于ASR的方法比較。如圖4（a）所示，隨著匿名度k值的增加，kRCS、HC［4］和PG［5］的匿名區(qū)域的覆蓋面積均變大，kRCS匿名算法產(chǎn)生的用戶覆蓋面積變化明顯。而且kRCS的匿名覆蓋面積遠(yuǎn)大于其他二者。kRCS匿名算法以構(gòu)建隨機(jī)匿名集的方式實現(xiàn)匿名，在不降低匿名度的情況下，覆蓋面積變大增加了匿名的安全性。如圖4（b）所示，kRCS、HC和PG在平均匿名時間上沒有太大的差異，k值與匿名時間成正比關(guān)系。如圖4（c）所示，隨著用戶數(shù)量N值的增加，因為更容易實現(xiàn)匿名，HC和PG的覆蓋面積變小，kRCS的覆蓋面積變化不明顯。

圖4 隨機(jī)匿名方法與基于ASR的方法比較Fig.4 The comparison of k?RCS and ASR?based methods

圖5 為POIs對查詢效率的影響結(jié)果。如圖5（a）所示，隨著興趣點POIs數(shù)量和k值的增加，平均查詢時間增長。如圖5（b）所示，k值越大，候選結(jié)果集越大，則kRCS和ASR?based方法查詢處理時間越長，PIR? based［9］方法不受k值的影響，kRCS的平均檢索時間在k＜30時優(yōu)于PIR?based方法。如圖5（c）所示，隨著POIs數(shù)量增加，ASR?based方法的候選結(jié)果集變大，kRCS的候選結(jié)果集不受POIs數(shù)量的影響，PIR?based方法的候選結(jié)果集雖然不受k的影響，但是受到POIs數(shù)量的影響。

5 結(jié)束語

位置k?匿名和位置模糊是典型的隱私保護(hù)技術(shù)，分別保護(hù)查詢隱私和位置隱私。但是，以往研究方法中主要是以匿名框的形式掩蓋用戶的真實位置，匿名框的相交和重疊會帶來多查詢攻擊和推理攻擊。本文提出一種隨機(jī)匿名的位置隱私保護(hù)方法，采用3層匿名器結(jié)構(gòu)和k?匿名技術(shù)，不產(chǎn)生匿名框，以離散匿名集的形式同樣可以達(dá)到位置k?匿名和位置模糊的效果。設(shè)計了kRCS匿名算法，該算法使用離散點的位置構(gòu)成位置隱藏集合，實現(xiàn)了k?匿名集合中用戶的離散性和隨機(jī)性，在保證查詢用戶匿名度的前提下，提高了匿名區(qū)域的覆蓋面積，同時并不犧牲用戶的服務(wù)質(zhì)量，能夠滿足位置k?匿名、位置l?多樣性，達(dá)到了位置隱私和查詢隱私的雙重保護(hù)目標(biāo)，提高了隱私安全性和匿名效率。采用了PIR協(xié)議，對LBSs查詢候選結(jié)果集進(jìn)行秘密檢索，保證了查詢結(jié)果的隱匿性。采用簡單的單點最近鄰查詢技術(shù)簡化了LBSs的查詢處理過程。實驗驗證了該方法隱私安全強(qiáng)度高于基于匿名框的方法，計算效率高于基于PIR的匿名方法。

［1］周傲英，楊彬，金澈清，等.基于位置的服務(wù)_架構(gòu)與進(jìn)展［J］.計算機(jī)學(xué)報，2011，34（7）：1156?1171.ZHOU Aoying，YANG Bin，JIN Cheqing，et al.Location?based services：architecture and progress［J］.Journal of Computers，2011，34（7）：1156?1171.

［2］SHIN K G，JU X，CHEN Z，et al.Privacy protection for us?ers of location?based services［J］.IEEE Wireless Communi?cations，2012，19（1）：30?39.

［3］BENISCH M，KELLEY P G，SADEH N，et al.Capturing location?privacy preferences：quantifying accuracy and user?burden tradeoffs［J］.Personal and Ubiquitous Computing，2011，15（7）：679?694.

［4］KALNIS P，GHINITA G，MOURATIDIS K，et al.Preven?ting location?based identity inference in anonymous spatial queries［J］.IEEE Transactions on Knowledge and Data Engi?neering，2007，19（12）：1719?1733.

［5］BAMBA B，LIU L，PESTI P，et al.Supporting anonymous location queries in mobile environments with privacy grid［C］／／Proceedings of the 17th International Conference on World Wide Web.Beijing，China，2008：237?246.

［6］林欣，李善平，楊朝暉.LBS中連續(xù)查詢攻擊算法及匿名性度量［J］.軟件學(xué)報，2009，20（4）：1058?1068.LIN Xin，LI Shanping，YANG Zhaohui.Attacking algo?rithms against continuous queries in LBS and anonymity measurement［J］.Journal of Software，2009，20（4）：1058?1068.

［7］NUSSBAUM D，OMRAN M T，SACK J.Techniques to pro?tect privacy against inference attacks in location based serv?ices［C］／／Proceedings of the 3rd ACM SIGSPATIAL Inter?national Workshop on Geo?Streaming.New York，USA，2012：58?67.

［8］霍崢，孟小峰.軌跡隱私保護(hù)技術(shù)研究［J］.計算機(jī)學(xué)報，2011（10）：1820?1830.HUO Zheng，MENG Xiaofeng.A survey of trajectory priva?cy?preserving techniques［J］.Journal of Computers，2011（10）：1820?1830.

［9］GHINITA G，KALNIS P，KHOSHGOZARAN A，et al.Pri?vate queries in location based services：anonymizers are not necessary［C］／／Proceedings of the 2008 ACM SIGMOD In?ternational Conference on Management of Data.Vancouver，Canada，2008：121?132.

［10］KHOSHGOZARAN A，SHAHABI C，SHIRANI H.Loca?tion privacy：going beyond k?anonymity，cloaking and ano?nymizers［J］.Knowledge and Information Systems，2011，26（3）：435?465.

［11］WANG S，CHEN C，TING I，et al.Multi?layer partition for query location anonymization［C］／／Proceedings of the 2012 IEEE International Conference on Systems，Man，and Cybernetics.Seoul，Korea，2012：378?383.

Random anonymity method for location privacy protection

YANG Songtao1，2，MA Chunguang1
（1.College of Computer Science＆Technology，Harbin Engineering University，Harbin 150001，China；2.Colleges of Information＆Electronic Technology，Jiamusi University，Jiamusi 154007，China）

The methods that are based on the anonymous spatial region are vulnerable to multiple queries attacks and inference attacks，which result in the privacy exposure issues.In order to ensure the location?based privacy se?curity，this paper constructed the random k?cloak set to meet requirement of location k?anonymity and location l?di?versity.Random k?cloak set is composed of discrete dots of location，and the grid distance between dots is greater than the threshold value s.Private information retrieval employed in the study guaranteed privacy in retrieval pro?cessing，and achieved the goal that the server provides the location?based service for users on the premise of not knowing user's query results.Simulation experiments verify the security and validity of this method.

wireless networks；mobile communication；privacy protection；location?based services；location k?ano?nymity；private information retrieval；random anonymity

10.3969／j.issn.1006?7043.201311024

http：／／www.cnki.net／kcms／detail／23.1390.U.20150109.1654.019.html

TP393

A

1006?7043（2015）03?0374?05

2013?11?11.網(wǎng)絡(luò)出版時間：2015?01?09.

國家自然科學(xué)基金資助項目（61472097）；黑龍江省教育廳科學(xué)技術(shù)研究基金資助項目（12541788）；佳木斯大學(xué)重點資助項目（Lz2013?010）.

楊松濤（1972?），男，副教授，博士研究生；

馬春光，E?mail：machunguang＠hrbeu.edu.cn.可能匯聚成一點，在稀疏區(qū)域，k?ASR可能很大。

基于位置的服務(wù)（location?based services，LBS）是移動互聯(lián)網(wǎng)中的典型應(yīng)用，包括定位和電子地圖等技術(shù)。在哪里（空間信息）、和誰在一起（社會信息）、附近有什么資源（信息查詢）是LBS系統(tǒng)中最基本的內(nèi)容［1］。為了了解周邊興趣點（points of interest，POIs）信息，用戶必須向LBS服務(wù)器提供位置信息和服務(wù)內(nèi)容。然而，LBS提供者可能主動推理用戶敏感信息并將其出賣給一些商業(yè)機(jī)構(gòu)，導(dǎo)致LBS提供者不可信成為了危及用戶位置隱私的主要原因。目前，LBS隱私保護(hù)是研究的熱點問題，有效地推動了位置隱私保護(hù)的研究［2］。一些研究方法實現(xiàn)了位置隱私，但是個人隱私與服務(wù)質(zhì)量產(chǎn)生新的沖突，換句話說，用戶必須在隱私保護(hù)和精確服務(wù)之間做出權(quán)衡。盡管基于策略的方法對位置數(shù)據(jù)的收集、存儲和使用等方面做出了規(guī)定，但是，執(zhí)行這些政策通常超出了用戶的控制［3］。本文提出了一種隨機(jī)位置隱藏的隱私保護(hù)方法，采用可信匿名器結(jié)構(gòu)和k?匿名技術(shù)，使用隨機(jī)離散匿名集的方式取得更大的覆蓋面積，滿足了位置k?匿名和位置l?多樣性，保證了用戶的位置隱私，但是不會增加計算量和通信負(fù)載。查詢候選結(jié)果集是LBS提供者推斷用戶敏感信息的重要依據(jù)，本文采用可計算私有信息檢索協(xié)議（private information retrieval，PIR）秘密檢索候選結(jié)果集，保證了用戶查詢結(jié)果的隱私性。

位置k?匿名模型中的位置k?匿名強(qiáng)度取決于k值的大小，一般來說，k值越大則用戶的精確位置坐標(biāo)與查詢信息的關(guān)聯(lián)度越小，然而服務(wù)質(zhì)量越差。位置k?匿名混淆了匿名查詢和位置隱私的概念，k?匿名可以切斷查詢內(nèi)容和用戶身份的關(guān)聯(lián)，但是無法保證用戶位置軌跡隱私。k值的大小不依賴于匿名空間區(qū)域（a?nonymous spatial region，ASR），在用戶密集區(qū)域，k?ASR

馬春光（1974?），男，教授，博士生導(dǎo)師.