位置隱私保護是為了防止用戶的歷史位置以及現在的位置被不法分子或不可信的機構在未經用戶允許的情況下獲取，也是為了阻止不法分子或不可信的機構根據用戶位置信息，結合相應的背景知識推測出用戶的其他個人隱私情況，如用戶的家庭住址、工作場所、工作內容、個人的身體狀況和生活習慣等。下面介紹幾種常用的位置隱私保護技術。

　　一、基于干擾的位置隱私保護技術

　　基于干擾的隱私保護技術主要使用虛假信息和冗余信息來干擾攻擊者對查詢用戶信息的竊取。根據查詢用戶信息（身份信息和位置信息）的不同，基于干擾的隱私保護技術大致可以分為假名技術和假位置技術兩種。

　　（ 1 ） 假名技術

　　假名是基于干擾的位置隱私保護技術中干擾身份信息的技術之一。用戶使用假名來隱藏真實的身份信息，如用戶小張所處的位置是（X,Y），要查詢他附近的KTV，用戶小張的查詢請求包括：小張，位置（X,Y），“離我最近的KTV”。當攻擊者截獲了這個請求后，可以很輕易地識別出用戶的所有信息。而采用假名技術，用戶小張使用假名小李，他的查詢請求就變成了：小李，位置（X,Y），“離我最近的KTV”。這樣攻擊者就認為處于位置（X,Y）的人是小李，用戶成功地隱藏了自己的真實身份。

　　假名技術通過分配給用戶一個不可追蹤的標志符來隱藏用戶的真實身份，用戶使用該標志符代替自己的身份信息進行查詢。在假名技術中，用戶需要有一系列的假名，而且為了獲得更高的安全性，用戶不能長時間使用同一個假名。假名技術通常使用獨立結構和集中式結構，當在獨立結構中使用時，用戶何時何地更換假名只能通過自己的計算和推測來確定，這樣就可能在同一時刻有兩個名字相同的用戶定位在不同地點，令服務器和攻擊者很輕易地知道用戶使用了假名。而在集中式結構中使用時，用戶把更換假名的權利交給匿名服務器，匿名服務器通過周圍環境和其他用戶的信息，能夠更好地完成假名的使用。

　　為了使攻擊者無法通過追蹤用戶的歷史位置信息和生活習慣將假名與真實用戶相關聯，假名也需要以一定的頻率定期交換。通常使用假名技術時需要在空間中定義若干混合區（Mix Zone），用戶可在混合區內進行假名交換，但是不能發送位置信息。

　　如圖1所示，進入混合區前的假名組合為（user1 user2 user3），在混合區內進行假名交換，將會產生6種可能的假名組合。由于用戶在進入混合區前后的假名不同，并且用戶的名字為假名的可能性會隨著進入混合區的用戶數目成指數增長，因此，在混合區模式下，攻擊者很難通過追蹤的方式將用戶與假名關聯，進而即可起到位置隱私保護的效果。

　　圖1  混合區內的假名交換

　　混合區的大小設置與空間部署是假名技術的關鍵所在，因為在混合區內要求不能提交位置信息，所以混合區過大會將導致服務質量下降，混合區過小會將導致同一時刻區內的用戶較少，進行假名交換的效率較低。當混合區內只有一個用戶時，將不會發生假名更換，從而增大了被攻擊的可能性。

　　（ 2 ） 假位置技術

　　假位置技術是在用戶提交查詢信息中，使用虛假位置或者加入冗余位置信息對用戶的位置信息進行干擾。假位置技術按照對位置信息的處理結果可分為孤立點假位置和地址集兩種。

　　孤立點假位置是指用戶向SP提交當前位置時，不發送自己的真實位置，而是用一個真實位置附近的虛假位置代替。例如，用戶小張所在的位置是（X,Y），要查詢他附近離他最近的KTV，用戶小張發送的查詢請求并不是：小張，位置（X,Y），“離我最近的KTV”，而是會采用虛假位置（M,N）代替真實位置，此時他的查詢請求就變成了：小張，位置（M,N），“離我最近的KTV”。這樣，攻擊者就會認為處于位置（M,N）處的人是小張，用戶小張也就成功地隱藏了自己的真實位置。

　　地址集則是在發送真實位置的同時，加入了冗余的虛假位置信息形成的。將用戶真實的位置隱藏在地址集中，通過干擾攻擊者對用戶真實位置的判斷，達到保護用戶位置信息的目的。例如，用戶小張所在的位置是（X,Y），要查詢附近離他最近的KTV，這次用戶小張發送的查詢請求中，由一個包含真實位置（X,Y）的集合代替用戶所在的位置。因此，他的查詢請求就變成了：小張，地址集{（X,Y），（X,Y），（X1,Y1），（X2,Y2），（X3,Y3），…}，“離我最近的KTV”。這樣就可以使攻擊者很難從地址集中尋找到用戶的真實位置。但地址集的選擇非常重要，地址數量過少可能會達不到要求的匿名度，而地址數量過多則會增加網絡傳輸的負載。采用隨機方式生成假位置的算法，能夠保證多次查詢中生成的假位置帶有軌跡性。

　　（ 3 ） 啞元位置技術

　　啞元位置技術也是一種假位置技術，通過添加假位置的方式同樣可以實現k-匿名。啞元位置技術要求在查詢過程中，除真實位置外還須加入額外的若干個假位置信息。服務器不僅響應真實位置的請求，還響應假位置的請求，以使攻擊者無法從中區分出哪個是用戶的真實位置。

　　假設用戶的初始查詢信息為（user_id locreal），locreal為用戶的當前位置，那么使用假位置技術后用戶的查詢信息將變為

　　q*=（user_id,locreal,dummy_loc1,dummy_loc2），其中dummy_loc1和dummy_loc2為生成的假位置。

　　啞元位置技術的關鍵在于如何生成無法被區分的假位置信息，若假位置出現在湖泊或人煙稀少的大山中，則攻擊者可以對其進行排除。假位置可以直接由客戶端產生（但客戶端通常缺少全局的環境上下文等信息），也可以由可信第三方服務器產生。

　　二、 基于泛化的位置隱私保護技術

　　泛化技術是指將用戶所在的位置模糊成一個包含用戶位置的區域，最常用的基于泛化的位置隱私保護技術就是k-匿名技術。k-匿名是指在泛化形成的區域中，包含查詢用戶及其他k-1個用戶。SP不能把查詢用戶的位置與區域中其他用戶的位置區分開來。因此，匿名區域的形成是決定k-匿名技術好壞的重要因素，常用集中式結構和P2P結構來實現。

　　k-匿名技術要求發布的數據中包含k個不可區分的標志符，使特定個體被發現的概率為1/k。在位置隱私保護中，k-匿名通常要求生成一組包含k個用戶的查詢集，隨后用戶即可使用查詢集所構成的一個共同的匿名區域。圖2展示了用戶User1、User2和User3所構成的匿名區域（（Xl，Yl），（Xr，Yr））。

　　圖2  混合區內的假名交換

　　k-匿名技術中通常要求的若干參數介紹如下。

　　① 匿名度k：定義匿名集中的用戶數量。匿名度k的大小決定了位置隱私保護的程度，更大的k值意味著匿名集包含更多的用戶，這會使攻擊者更難進行區分。

　　② 最小匿名區域Amin：定義要求k個用戶位置組成空間的最小值。當用戶分布較密集時將導致組成的匿名區域過小，即使攻擊者無法準確地從匿名集中區分用戶，匿名區域也可能將用戶的位置暴露給攻擊者。

　　③ 最大延遲時間Tmax：定義用戶可接受的最長匿名等待時間。

　　k-匿名技術在某些場景下仍可能導致用戶的隱私信息暴露。例如，當匿名集中用戶的位置經緯度信息都可以映射到某一具體的物理場所（如醫院）時。對此，增強的l-多樣性、t-closeness等技術被提出，要求匿名集中用戶的位置要相隔得足夠遠以致不會處于同一物理場所內。

　　k-匿名技術可以通過匿名服務器來完成匿名集的收集與查詢的發送，也可以通過分布式點對點的技術由若干客戶端組成對等網絡來完成。

　　（ 1 ） 集中式k-匿名

　　典型的集中式k-匿名是間隔匿名。間隔匿名算法的基本思想為：匿名服務器構建一個四叉樹的數據結構，將平面空間遞歸地用十字分成4個面積相等的正方形區間，直到所得到的最小正方形區間的面積為系統要求的允許用戶所采用的最小匿名區面積為止，每個正方形區間對應四叉樹中的一個節點。系統中的用戶每隔一定的時間就將自己的位置坐標上報給匿名服務器，匿名服務器更新并統計每個節點對應區間內的用戶數量。當用戶U進行匿名查詢時，匿名器會通過檢索四叉樹為用戶U生成一個匿名區ASR，間隔匿名算法從包含用戶U的四叉樹的葉子節點開始向四叉樹根的方向搜索，直至找到包含不少于K個用戶（包括用戶U）的節點，進而即可將該節點所對應的區域作為用戶U的一個匿名區。如圖3所示，如果用戶U1發起K=2的匿名查詢，則間隔匿名算法將首先搜索到象限區間[（0,0），（4,4）]，其中包含不少于兩個用戶，然后，向根的方向上升一級搜索到象限區間[（0,0），（2,2）]，該象限區間包含3個用戶，大于要求的兩個，算法停止搜索，并將該區間作為用戶U1的匿名區。由于該算法所得到的匿名區所包含的用戶數量可能遠大于K，因此其會加大LBS服務器的查詢處理負擔和網絡流量負荷。

　　圖3  k-匿名實例

　　Casper匿名算法與間隔匿名算法類似，但不同于間隔匿名算法的是：Casper采用Hash表來識別和訪問四叉樹的葉子節點，同時當搜索節點用戶數小于K時，首先會對其相鄰的兩個兄弟節點進行搜索，如果該節點與其相鄰的兩個兄弟節點合并后的總用戶數大于K，則將它們合并，并作為匿名區，否則，再對其父節點進行搜索。Casper生成的匿名區面積相比于間隔匿名算法生成的要小，這會減少網絡的負載。

　　Hilbert匿名算法的基本思想是通過Hilbert空間填充曲線將用戶的二維坐標位置轉換成一維Hilbert值進行匿名，按照曲線通過的順序對用戶進行編號，此編號即為用戶的Hilbert值，并把相鄰的k個用戶放入同一個桶中。匿名集就是包含請求服務的用戶所在桶內的所有用戶。計算出匿名集的最小綁定矩形并將其作為匿名區。若兩個用戶在二維空間中相鄰，那么映射到一維空間的Hilbert值也有較大的概率會相鄰。Hilbert匿名算法可以滿足絕對匿名。如圖4所示，用戶U1的匿名度為3，他和他的相鄰用戶U3和U4共同組成了匿名區域。

　　圖4  Hilbert匿名實例

　　（ 2 ） P2P結構下的k-匿名

　　基于P2P結構的k-匿名查詢算法的基本思想是：假設所有的節點都是可信的。每個用戶都有兩個獨立的無線網絡，一個網絡用于與LBS通信，另一個網絡用于P2P通信，并且系統中的用戶都是安全可信的。一個完整的查詢過程包括以下3步。

　　① 對等點查詢。移動用戶需要通過單跳或多跳網絡查找不少于k-1個對等點鄰居。

　　② 生成匿名區。移動用戶與他所查找到的k-1個鄰居形成一個組，將他準確地隱藏到一個覆蓋整個組內所有用戶的區域（即匿名區）中。如果生成的ASR面積小于用戶所要求的最小匿名區面積Amin，那么就需要擴大這個匿名區ASR到最小匿名面積Amin。

　　③ 選擇代理并查詢。為了防止攻擊者通過移動蜂窩定位技術進行攻擊，移動用戶需要在所形成的組內隨機找一個對等點鄰居并將其作為代理。通過專門用于P2P通信的網絡，將生成的匿名區和查詢的參數內容告訴代理，由代理通過另一個網絡與LBS服務器聯系，發送查詢參數和匿名區，并接收候選集，然后代理通過專門用于P2P的網絡將候選集傳回查詢用戶。最后查詢用戶對返回的候選集進行過濾，得到查詢結果。

　　三、基于模糊法的位置隱私保護技術

　　位置混淆技術的核心思想在于通過降低位置精度來提高隱私保護程度。一種模糊法可將坐標替換為語義位置，即利用帶有語義的地標或者參照物代替基于坐標的位置信息，實現模糊化。也有用圓形區域代替用戶真實位置的模糊法技術，此時，將用戶的初始位置本身視為一個圓形區域（而不是坐標點），并提出3種模糊方法：放大、平移和縮小。利用這3種方法中的一種或兩種的組合，可生成一個滿足用戶隱私度量的圓形區域。

　　例如，可以將由用戶位置的經緯度坐標轉換而來的包含該位置的圓形或矩形區域作為用戶的位置進行提交。當提交查詢時，我們使用圓形區域C1替換用戶的真實位置（X,Y）。

　　此外，還可以采用基于物理場所語義的位置混淆技術，該技術會提交用戶所在的場所而不是用戶的具體坐標。例如，使用在西安交通大學校園內的語義地點“圖書館”替換我的具體坐標；也可以使用“興慶公園”內的黑點位置所示用戶，發起查詢“最近加油站”的位置服務。

　　混淆技術的關鍵在于如何生成混淆空間。用戶總是在混淆區域的中間位置，或混淆區域中大部分區域是用戶無法到達的河流等場所，亦或混淆區域內人口相對稀疏，這些都會增加攻擊者發現用戶真實位置的可能性。

　　大多數模糊法技術無須額外信息輔助，即可在用戶端直接實現，因此它們多使用獨立結構。

　　與泛化法不同，多數模糊法技術沒有能力對LBS返回的結果進行處理，往往會產生比較粗糙的LBS結果。例如，使用圖5中興慶公園模糊化用戶請求“最近加油站”時，事實上S1是最近的加油站，當將C1作為其模糊區域時能夠尋找到正確結果；但當將隱私程度更高的C2作為模糊區域時，SP將把S2作為結果返回。所以，雖然C2的半徑大于C1的半徑，這使得隱私程度提高，但此時SP沒有最好地滿足用戶需求。模糊法技術應解決如何在“保證LBS服務質量”和“滿足用戶隱私需求”之間尋求平衡的問題。解決該問題的一種方式是在SP和用戶之間采用迭代詢問的方法，不斷征求用戶是否同意降低其隱私度量，在有限次迭代中盡可能地提高服務質量。

　　圖5  基于模糊法的隱私保護技術

　　四、基于加密的位置隱私保護技術

　　在基于位置的服務中，基于加密的位置隱私保護技術將用戶的位置、興趣點加密后，即會在密文空間內進行檢索或者計算，而SP則無法獲得用戶的位置以及查詢的具體內容。兩種典型的基于加密的位置隱私保護技術分別是基于隱私信息檢索（Private Information Retrieval，PIR）的位置隱私保護技術和基于同態加密的位置隱私保護技術。

　　（ 1 ） 基于隱私信息檢索（PIR）的位置隱私保護技術

　　PIR是客戶端和服務器通信的安全協議，能夠保證客戶端在向服務器發起數據庫查詢時，客戶端的私有信息不被泄露給服務器的條件下完成查詢并返回查詢結果。例如，服務器S擁有一個不可信任的數據庫DB，用戶U想要查詢數據庫DB[i]中的內容，PIR可以保證用戶能以一種高效的通信方式獲取到DB[i]，同時又不讓服務器知道i的值。

　　在基于PIR的位置隱私保護技術中，服務器無法知道移動用戶的位置以及要查詢的具體對象，從而防止了服務器獲取用戶的位置信息以及根據用戶查詢的對象來確定用戶的興趣點并推斷出用戶的隱私信息。其加密思想如圖6所示：用戶想要獲得SP服務器數據庫中位置i處的內容，用戶自己將查詢請求加密得到Q（i），并將其發送給SP，SP在不知道i的情況下找到X，將結果進行加密R（X,Q（i））并返回給用戶，用戶可以輕易地計算出Xi。包括SP在內的攻擊者都無法通過解析得到i，因此無法獲得查詢用戶的位置信息和查詢內容。

　　圖6  PIR方案

　　PIR可以保證用戶的請求、信息的檢索以及結果的返回都是安全可靠的。但是，PIR要求SP存儲整個區域的興趣點和地圖信息，這使存儲空間和檢索效率受到了極大挑戰。如何設計出更合適的存儲結構及檢索方式是PIR要繼續研究的重點。

　　（ 2 ） 基于同態加密的位置隱私保護技術

　　同態加密是一種支持密文計算的加密技術。對同態加密后的數據進行計算等處理，處理的過程不會泄露任何原始內容，處理后的數據用密鑰進行解密，得到的結果與沒有進行加密時的處理結果相同。基于同態加密的位置隱私保護最常用的場景是鄰近用戶相對距離的計算，它能夠實現在不知道雙方確切位置的情況下，計算出雙方間的距離，如微信的“搖一搖”功能。Paillier同態加密是基于加密隱私保護技術常用的同態加密算法，最為典型的有Louis協議和Lester協議。Louis協議允許用戶A計算其與用戶B的距離，Lester協議規定只有當用戶A和用戶B之間的距離在用戶B設置的范圍內時，才允許用戶A計算兩者之間的距離。

　　五、位置隱私攻擊模型

　　網絡中的攻擊者是用戶位置隱私最大的威脅來源。攻擊者針對不同的位置隱私保護技術形成了不同的攻擊模型。這些攻擊模型根據攻擊者的行為主要可分為主動攻擊模型和被動攻擊模型。

　　1. 主動攻擊模型

　　攻擊者向受害用戶或LBS服務器發送惡意的信息，從而獲取用戶的位置信息或者干擾用戶使用LBS服務。主要包括偽裝用戶攻擊和信息洪水攻擊。

　　（ 1 ） 偽裝用戶攻擊

　　偽裝用戶攻擊主要針對基于P2P結構的位置隱私保護技術。在P2P結構下，同一網絡中的用戶相互信任。攻擊者可以假扮用戶的好友或其他普通用戶，也可以在該網絡中的用戶的移動設備中植入病毒來控制這些設備。這時攻擊者會主動向受害者用戶提出協助定位申請，由于得到受害用戶的信任，攻擊者可以輕松地獲取用戶精確的位置信息。

　　偽裝用戶攻擊對于基于同態加密的位置隱私保護技術也有很好的攻擊效果。當攻擊者得到受害用戶信任或距離受害用戶的距離在受害用戶設置的限定范圍之內時，攻擊者可以計算得知他與受害者的相對距離。根據三角定位原理，攻擊者在成功取得3次及以上相對距離的時候，經過簡單的計算就可以得知受害用戶的精確位置。

　　目前已有的位置隱私保護算法中還沒有能夠很好地解決偽裝用戶攻擊的方法。

　　（ 2 ） 信息洪水攻擊

　　信息洪水攻擊的原理是拒絕服務。在獨立結構和集中式結構中，攻擊者向LBS服務器發送大量的LBS請求，占用LBS服務器的帶寬和流量，以影響LBS服務器對受害用戶的服務效率。在P2P結構中，由于用戶之間可以發送協助定位申請，因此攻擊者可直接向受害用戶發送大量的協助定位申請，這些申請會像洪水一樣涌向受害用戶，受害用戶不僅需要接受這些信息，還需要對這些信息進行處理和轉發。數量巨大的信息會導致受害用戶的移動網絡阻塞，甚至會導致移動設備崩潰。

　　2. 被動攻擊模型

　　被動攻擊是指攻擊者被動收集受害用戶的信息，并通過收集到的信息來推斷用戶的真實位置。被動攻擊主要包括基于歷史信息的攻擊、基于語義信息的攻擊和基于社交關系的攻擊。

　　（ 1 ） 基于歷史信息的攻擊

　　基于歷史信息的攻擊主要通過收集受害用戶相關的歷史信息，分析用戶對LBS的使用習慣來推測用戶的具體位置。其中歷史信息包括受害用戶之前發起LBS請求的時間、內容、頻率等。例如，如果受害用戶經常在晚上或者周末在不同的地點使用導航到達同一地點，則該地點很可能是受害用戶的家庭住址。同理，如果受害用戶經常在工作日查詢某一地點附近的餐廳，則該地點很可能是用戶的工作地點。

　　（ 2 ） 基于語義信息的攻擊

　　基于語義信息的攻擊者通過分析受害用戶所在位置區域的信息及其周圍環境的語義信息，可縮小用戶所在區域的范圍，增加識別用戶位置的概率。例如，攻擊者截獲了一個受害用戶所在的位置區域信息，經過對該信息進行分析，發現該區域包括一片人工湖、幾棟高層樓房和一個停車場。由此可以推斷用戶位于湖面的概率遠小于位于樓房內和停車場的概率。如果又知道用戶正在使用導航功能查找去往某地的路線，則用戶位于停車場的概率就高于位于樓房內的概率。

　　（ 3 ） 基于社交關系的攻擊

　　基于社交關系的攻擊主要利用了如今發達的社交網絡。首先攻擊者收集受害用戶的社交信息，通過對其社交網絡中的其他用戶進行攻擊以間接地攻擊該受害用戶。如果用戶甲對自己的位置隱私保護非常重視，攻擊者很難直接對用戶甲進行攻擊，而通過社交網絡了解到，用戶甲和用戶乙是同事，則攻擊者就可以對用戶乙實施攻擊，通過獲取用戶乙的工作地點來推斷出用戶甲的工作地點。