基于SpaceTwist的混合式LBS隱私保護方案

職鳴奕 楊明

摘要：基于位置的信息服務（Location Based Services，LBS）在給個人生活帶來極大便利的同時，也帶來了個人隱私泄露的危險。本文對現有位置隱私保護方案進行梳理，提出一種混合式LBS隱私保護方案。該方法采用混合式系統結構，基于SpaceTwist方案的位置隱私保護算法，以六邊形匿名區域中心作為錨點進行K-匿名增量近鄰查詢，根據用戶需求在位置隱私保護度和查詢結果準確性之間做到有效調節，從而對查詢用戶進行個性化的隱私保護。

關鍵詞：LBS;隱私保護;混合式系統結構;SpaceTwist方案;增量查詢

中圖分類號：TP3? ? ? ?文獻標識碼：A

文章編號：1009-3044（2021）26-0025-03

開放科學（資源服務）標識碼（OSID）：

基于位置的信息服務（Location Based Services，以下簡稱LBS）是LBS服務提供商根據用戶的空間位置，通過移動通信運營商向用戶提供的與位置相關的信息資源和增值服務。LBS最初應用于軍事領域，現已廣泛應用于緊急救援、商業、醫療、工業、物流等民生領域[1]。其典型應用包括：緊急救援服務（美國的“911”，中國的“119”），導航服務（高德地圖、百度地圖），商場、酒店、餐廳等周邊信息查詢服務（美團，口碑，大眾點評），定位服務（菜鳥物流，京東物流），廣告促銷，個人安全服務，位置計費等。LBS的廣泛應用給人們的生活帶來了極大的便利，但是，由此產生的位置大數據也帶來了個人隱私泄露的危害，主要包括：位置隱私（家庭住址、工作單位、訪問地址等）和查詢隱私（興趣愛好，健康狀況，運動模式等）。位置隱私和查詢隱私二者密切相關，位置隱私的泄露，可能導致用戶被定位跟蹤，進而獲取用戶的查詢隱私;另一方面，攻擊者根據歷史數據來匹配查詢隱私，將查詢隱私和位置隱私聯系起來，從而獲得個人隱私信息。因此，LBS隱私保護是位置服務中非常重要的問題。

LBS隱私保護技術仍面臨一些挑戰：①用戶的位置信息是關聯的。攻擊者知道用戶的當前位置和運動模式，可推斷出預計到達的位置;②位置服務的及時性，面對海量的數據，連續的服務請求能進行高效率的處理;③隱私保護度、查詢結果的準確性和開銷三者之間是矛盾的。目前，國內外學者進行了大量的研究，提出各種隱私保護方案，本文將其分為3類：政策法、扭曲法、加密法三種。與政策法、加密法相比，扭曲法能更好地保留用戶信息，無須可信第三方以及額外的硬件，因此在LBS隱私保護中得到廣泛應用。

1 研究現狀綜述與分析

1.1? LBS隱私保護技術[1-2]

本文將LBS隱私保護技術分為3類：基于政策法的LBS隱私保護技術、基于扭曲法的LBS隱私保護技術以及基于加密法的LBS隱私保護技術。

1.1.1 基于政策法的LBS隱私保護技術

基于政策法的LBS隱私保護技術，顧名思義就是政府或組織發布隱私管理規定或協議，通過限制LBS服務提供商對用戶信息的不正當使用，從而達到保護用戶隱私的目的。政策法實現簡單，技術難度低，但隱私保護效果無法衡量，無法保證LBS服務提供商的完全可信，即使其聲稱不會對用戶數據進行不正當使用，但仍然無法保證用戶的隱私安全。

1.1.2 基于扭曲法的LBS隱私保護技術

基于扭曲法的LBS隱私保護技術，這一技術通過讓用戶提交對時間、空間、服務屬性適當增加、修改等操作后的查詢內容，來避免攻擊者獲取用戶的真實信息。采用的技術主要有：隨機化（增加隨機噪點）、空間模糊化（將查詢位置模糊為一片區域）、時間模糊化（增加時間域的不確定性）。扭曲法能在隱私保護度和服務質量之間做到較好的平衡，但是容易受到完全背景攻擊。需要在滿足用戶最低服務質量的前提下，提高隱私保護度，以降低用戶隱私泄漏的危險。

1.1.3 基于加密法的LBS隱私保護技術

基于加密法的LBS隱私保護技術，是指利用加密算法對查詢內容進行加密并發送發給LBS服務提供商，LBS服務提供商在不解密查詢內容的情況下，直接進行位置服務查詢處理。加密法能滿足較高的隱私需求和完全的服務質量，但是查詢過程中需要額外的硬件和計算，查詢過程中花費的代價很大，導致效率低下，而高效率的查詢又會導致暴露查詢數據之間的關系。

1.2 LBS隱私保護技術分析比較

表1從隱私保護度、服務質量和開銷三個方面分析比較了現有的隱私保護技術。表2從優缺點和代表技術做了進一步分析。

由此可以看出，當用戶對隱私保護度不高且對服務質量要求較高時，政策法更適合。當用戶對隱私保護度很高，可以考慮加密法，這時的代價較高。其余情況可以考慮扭曲法，需要在隱私保護度、服務質量和開銷之間取得平衡。需要注意的是，不同的LBS隱私保護技術基于不同的隱私保護需求，單一的方案并不能完美解決所有問題。

2 混合式LBS隱私保護方案

2.1 系統結構

本方案采用混合式系統結構[3]，由集中式結構和分布式結構結合而成，具體組成如圖1所示：

用戶在發起LBS查詢前，通過隱私保護通信協議構建所在區域的匿名組。若組內有效用戶連接數量滿足該用戶匿名需求，則將該匿名區域中心位置發送給LBS服務提供商進行LBS查詢，并將查詢結果返回給用戶，由客戶端本身對結果進行篩選;若組內有效用戶連接數量不滿足該用戶匿名需求，則用戶將實際位置發送給匿名服務器，由匿名服務器實現匿名、查詢以及求精處理。具體的時序交互方式如圖2所示：

2.2 隱私保護算法

基于SpaceTwist方案的LBS隱私保護算法（如圖3所示），用隨機生成的錨點q代替用戶的真實位置q進行LBS查詢。查詢過程中，以q為中心的供應空間不斷增大，以q為中心的需求空間不斷縮小，直到需求空間完全被供應區間覆蓋停止檢索，并將查詢結果返回給用戶[4-5]。該方案不需要額外引入第三方可信匿名服務器，但是采用隨機生成錨點的方法，導致錨點位置在現實生活中可能不合理，提高錨點生成速率和合理性，能夠很好地提高LBS隱私保護度和服務質量。