隨機匿名的位置隱私保護方法

楊松濤，馬春光

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

隨機匿名的位置隱私保護方法

楊松濤1，2，馬春光1

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

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

無線網絡；移動通信；隱私保護；基于位置服務；位置k?匿名；私有信息檢索；隨機匿名

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

LBS系統在現實應用中，快照查詢和連續查詢經常交叉進行，增加了隱私保護的復雜性。攻擊者也會相互勾結，導致用戶的地理數據和社會化數據相互關聯，同時攻擊者通常具有大量的背景知識，先進的數據挖掘技術和強大的關聯攻擊造成了一些時空匿名技術方案的失效。最近研究將PIR理論引入LBS隱私保護領域。相對于其他隱私保護方法而言，基于PIR理論的隱私保護方法［9?11］有不揭露任何空間信息和抗關聯攻擊這2個優點。

1 系統結構

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

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

圖1 系統結構Fig.1 System architecture

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

依照圖1所示的系統結構，本文確定了4個基本假設如下：

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

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

假設3 用戶的分布是有規律的，但是分布密度是不均勻的，這是符合現實世界情況的，城市中心地帶用戶分布密集，而郊區用戶數量較少；

假設4 LCs使用的匿名算法是公開的。

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

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

2 隨機位置隱藏

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

式中：u代表用戶身份的假名；l代表用戶的當前位置坐標；t代表當前查詢時間；c代表用戶的查詢內容；s代表用戶要求的網格距離；k代表用戶要求的匿名度。

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

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

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

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

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

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

LCs通過執行kRCS算法來實現查詢用戶的位置隱藏。具體過程如下：

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

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

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

4）提取參數t、c，與S（k，s）和新生成的kRCS的標識符共同構成kRCS；

5）LCs發送kRCS給LBSs，用于檢索服務。

圖3 4×4空間分區樣例Fig.3 4×4 space partitioning example

3 私有檢索

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

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

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

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

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

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

3）依據歐拉準則，LCs分別計算

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

4 分析與驗證

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

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

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

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

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

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

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

5 結束語

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

［1］周傲英，楊彬，金澈清，等.基于位置的服務_架構與進展［J］.計算機學報，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中連續查詢攻擊算法及匿名性度量［J］.軟件學報，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］霍崢，孟小峰.軌跡隱私保護技術研究［J］.計算機學報，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.網絡出版時間：2015?01?09.

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

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

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

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

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

馬春光（1974?），男，教授，博士生導師.