基于隱私信息檢索的位置隱私保護方法

李宗義

摘要：隨著移動通信技術和GPS技術的發展，位置服務得到了大力發展和廣泛應用。但隨之而來的位置隱私泄露問題，越來越引起人們的廣泛關注。為了提高位置隱私保護效果，本文分析了目前主要采用的幾種位置隱私保護方法，并對基于隱私信息檢索的位置隱私保護方法做了深入研究，最后探索了位置隱私保護的進一步研究方向。

Abstract： With the development of mobile communication and GPS technology， LBS was vigorously developed and widely applied. However， the issue of location privacy leakage follows， which attract more and more attention. In order to improve the effect of location privacy protection， several main methods of location privacy protection are analyzed， and the location privacy protection method based on privacy information retrieval is studied deeply in this paper. Finally， the further research direction of location privacy protection is explored.

關鍵詞：基于位置的服務；位置隱私保護；假位置；k-匿名；隱私信息檢索；數據加密

Key words： location-based service （LBS）；location privacy protection； dummy；k-anonymous；privacy information retrieval （PIR）；data encryption

中圖分類號：TP392 文獻標識碼：A 文章編號：1006-4311（2018）30-0234-02

0 引言

隨著信息技術和數字化技術的發展，人們開始步入大數據時代。作為大數據的重要分支，位置大數據在人們的日常生活中得到快速普及和廣泛使用。當前，由于移動設備大多具備GPS精確定位功能，位置服務（LBS）成為人們生活中必不可少的服務之一。LBS的主要應用包括GPS導航（如Tom Tom）、興趣點檢索（如Around Me）、地圖類應用（如Google Maps）、位置感知社會網絡（如Foursquare）和優惠券或折扣提供（如Group On）等。瑞典市場研究公司Berg Insight發布的最新報告預測，全球LBS市場規模將以22.5%的復合年增長率（CAGR）從2014年的103億歐元，增加至2020年的348億歐元。另據前瞻數據庫統計，2016年12月百度宣布，百度地圖每日位置服務突破720億次，每日為用戶提供導航里程數達2億公里，從最初的導航工具逐步發展成為“基于大數據的人工智能出行平臺”。

然而，當LBS服務給人們提供便利的同時，人們的位置隱私信息也隨之泄露，給人們的生命財產安全帶來威脅。因為用戶需要獲取LBS服務時，需要報告他們的當前位置信息，而位置數據隱含著許多用戶的敏感信息，如家庭住址、健康問題、宗教信仰、工作單位等。一旦這些私人信息被泄露，會嚴重威脅到用戶各方面的隱私安全[1]。例如，通過分析位置數據，能推測出用戶過去、現在和將來的位置，以及個人的行蹤；甚至能判斷出用戶的家庭住址、上班地點和工作場所等。因此，如何對用戶的位置隱私進行保護變得越來越迫切，成為工業界和學術界廣泛關注的熱點問題。

1 位置隱私保護體系結構

按照體系結構劃分，位置隱私保護方法主要分為兩類：集中式結構[2]和分布式結構[3]。在集中式結構中，由查詢用戶直接向LBS服務器發起查詢請求，隱私保護技術由移動客戶端完成，或者借助中心匿名服務器（Fully-Trusted Third Party，TTP）實現位置隱私保護。在含有TTP的集中式結構中，當用戶需要位置服務時，不直接向LBS服務器發送查詢請求，而是先將查詢請求提交給TTP，TTP對用戶信息模糊處理后，將查詢請求提交給LBS服務器進行查詢，如圖1所示。在分布式體系結構中，用戶通過近鄰查詢得到相鄰用戶，組建協作用戶組，組內所有用戶具有不可區分性，從而使LBS服務器無法區分真實用戶，如圖2所示。

2 常見的位置隱私保護方法

2.1 k-匿名

位置隱私保護所使用的最主要方法是匿名的方法，以k-匿名[4]最為常見。k-匿名方法最早用在關系數據庫中，對數據庫中的關鍵屬性值進行泛化與模糊化處理，使得k條記錄中的任意一條無法單獨從中區分出來。位置隱私保護方法中k-匿名的實現主要采用空間區域匿名和假位置匿名。空間區域匿名通過對k用戶所在范圍構造匿名區域實現匿名化，假位置匿名通過在當前用戶所在區域添加假位置實現匿名化。該方法能較好的實現位置隱私保護，但對匿名區域和k值的大小有一定的要求。

2.2 時空模糊

在時間或空間范圍內，將用戶的當前位置模糊化在某一空間或時間區域內，使敵手無法得知用戶的真實位置。如采用哈希函數、歸一化方法、Hilber曲線等方法實現時空轉換。該方法因使用時空轉換操作，造成所發布的數據不夠準確等問題。

2.3 假名

假名是用一個標識，而不是真實的名字進行發布信息。基本原理是：在集中式結構模式下，將LBS的查詢中的用戶名u，采用直接刪除，或者用假名代替的方法，斷開了用戶身份和位置查詢之間的聯系，實現了位置隱私保護。但在服務器上存儲的數據（如用戶名、用戶身份、時空信息等）依然是相互關聯的，敵手通過關聯信息識別，能夠獲得隱私信息。

2.4 加密

在用戶發起查詢之前，先對查詢信息進行加密，使不可信第三方無法獲得用戶的查詢信息。通常情況下，加密方法與其他方法結合使用，以實現更好的位置隱私保護效果。

以上方法盡管能在一定條件下實現位置隱私保護，但在隱私需求級別較高的情境中，依然存在位置隱私泄露的風險。而基于隱私信息檢索（PIR）的方法憑借其高強度的隱私保護質量，能實現完美的隱私保護效果。

3 基于隱私信息檢索的方法

云服務器的出現，使數據外包模式應運而生。在該模式中，用戶在云服務器中檢索位置數據記錄時，不會暴露數據項信息，可以較隱秘地對不可信服務器上的任意數進行檢索[5]。

基于PIR的隱私保護方法描述為：假定數據庫是一個由n位二進制數組成的字符串S，如圖3所示。當用戶對字符串S中的第i位查詢字符Si進行查詢時，如果直接進行查詢，肯定會將Si值的相關信息泄露，造成隱私泄露的嚴重后果。為了保護數據隱私，用戶不能直接發起查詢，而在查詢之前，先使用加密機制對查詢i進行加密得到E（i），而后將加密的E（i）發送給位置服務器進行查詢。LBS服務器收到查詢請求E（i）后，進行查詢數據庫操作，并將查詢得到的結果q（S，E（i））返回給用戶。當用戶收到查詢結果q（S，E（i））后，應用解密操作進行解密，得到最終的查詢結果。

基于PIR的位置數據隱私保護方法在滿足位置服務正常進行的前提下，能夠實現高質量的隱私保護效果，不會泄露任何用戶的位置信息。但是，該方法查詢效率較低，會降低位置服務質量。因此，還需要對該方法進行改進。主要思路有：①采用信息緩存的方法，將查詢頻率相對較高的熱點位置存放在緩存中，當用戶進行查詢時，先訪問緩存，當緩存中沒有所要查詢的信息時，才向LBS服務器發起查詢請求；②通過建立樹型等索引結構，提高查詢效率；③改進加密方法，降低加解密運算的時間開銷。

4 結語

近年來，位置隱私保護逐漸成為信息安全領域的一個研究熱點。本文針對目前廣泛采用的位置隱私保護方法中存在的問題，通過對比分析，對基于隱私信息檢索的位置隱私保護方法進行了深入探討。隨著云計算技術的發展和普及，可搜索加密的位置隱私保護技術將成為未來的主要研究方向。

參考文獻：

[1]張學軍，桂小林，伍忠東.位置服務隱私保護研究綜述.軟件學報，2015，26（9）：2373-2395.

[2]周長利，馬春光，楊松濤.路網環境下保護LBS位置隱私的連續KNN查詢方法[J].計算機研究與發展，2015，52（11）：2628-2644.

[3]黃毅，霍崢，孟小峰.CoPrivacy：一種用戶協作無匿名區域的位置隱私保護方法[J].計算機學報，2011，34（10）：1976-1985.

[4]Latanyasweeney. k-Anonymity： A model for protecting privacy[J]. International Journal of Uncertainty Fuzziness and Knowledge-Based Systems， 2012， 10（05）：557-570.

[5]Chor B， Goldreich O， Kushilevitz E， Sudan M. Private information retrieval. Journal of the ACM， 1998，45（6）：965-981.