本節書摘來自華章出版社《位置大資料隐私管理》一 書中的第1章，第1.5節，作者潘曉、霍 峥、孟小峰，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
傳統的lbs隐私保護技術可以歸納為3類：基于資料失真的位置隐私保護方法、基于抑制釋出的位置隐私保護方法以及基于資料加密的位置隐私保護方法。不同的位置隐私保護技術基于不同的隐私保護需求以及實作原理，在實際應用中各有優缺點。
基于資料失真的方法，顧名思義是指通過讓使用者送出不真實的查詢内容來避免攻擊者獲得使用者的真實資訊。對于一些隐私保護需求不嚴格的使用者，該技術假設使用者在某時刻的位置資訊隻與目前時刻攻擊者收集到的資料有關，滿足直覺上的隐私需求，提供較高效的隐私保護算法和較快的服務響應。采取的技術主要包括随機化、空間模糊化和時間模糊化3種形式。這3類技術的共同點是一般假設在移動使用者和伺服器之間存在一個可信任的第三方伺服器，該伺服器可以将使用者的位置資料或查詢内容轉換成接近但不真實的資訊，然後再送出給伺服器。同時，将伺服器傳回的針對模糊資料的查詢結果轉化成使用者需要的結果。
随機化是在原始位置資料中加入随機噪聲。可信第三方伺服器在接收到使用者的準确位置後，将噪聲和準确位置都發送給服務提供商。在服務提供商傳回候選結果集後，可信第三方根據使用者的真實位置對候選結果集過濾求精，傳回真實的查詢結果給相應使用者。文獻[15]中首次提出了随機化方法，在每一時刻，根據上一時刻的位置按照随機的速度和随機的方向進行移動，并将獲得的随機位置點加入到原始資料中進行釋出。然而，這些随機位置點組成的曆史資料的移動特征與真實移動對象的特征具有很大差别，甚至送出的位置可能是一些實際上不可達的位置，是以很容易被攻擊者區分。為此，文獻[31]中在産生随機位置資料的時候加入了路網、移動速度等移動特征的限制條件。在文獻[15]和[31]中假設物體在不停地移動，文獻[17]中考慮到移動對象不會不停地移動，根據移動對象的周圍環境等因素讓移動對象随機産生停頓，以進一步防止攻擊者區分這些噪聲。
空間模糊化通過在一定程度上降低釋出位置資料的精度以滿足使用者隐私需求，具體來講，即将使用者送出的位置精度從一個點模糊到一個區域，以緻攻擊者無法獲得某個使用者清晰的位置。圖1-2是某一時刻标号為a～e的6個移動使用者在空間中的位置。根據四分樹（quad-tree）劃分技術[13]，空間被劃分成若幹區域，使用者希望每次釋出的位置資料不要準确到區域中隻有一個使用者。于是，使用者a(b, c)在釋出自己的位置時，可以釋出左下角陰影區域作為自己的位置；使用者d(e, f)可以釋出右上角陰影區域作為自己的位置。假設每個移動對象均向服務提供商發送自己所在的陰影區域來請求近鄰查詢，服務提供商需要計算包含陰影區域中任何一點的最近鄰的區域，傳回其中包含的全部使用者。例如，對于包含右上角陰影區域的近鄰查詢，伺服器隻需要傳回陰影區域和黑色區域包含的全部使用者，發起查詢的使用者就可以自行計算出自己的近鄰。
時間模糊化通過增加位置資料時間域的不确定性，以減少位置資料的精度。圖1-3例舉了一個簡單的時間模糊例子。圖1-3a是兩個移動物體在路網上運動的示意圖。物體1的移動軌迹用黑色表示，物體2的移動軌迹用灰色表示。沒有經過時間模糊時，它們要送出的位置資訊如圖1-3b第1、2行所示，其中a、b和c表示物體1的位置。假設使用者希望t2時刻在黑色框内的使用者不唯一，則經過時間模糊後的位置資料如圖1-3b第3、4行所示。在t2時刻，黑色框内物體1和物體2同時在位置c出現，達到了使用者的隐私要求。時間模糊化的隐私保護方法易于操作且實際應用通常不需要很大程度的資料改變量，是以它被廣泛應用在lbs隐私保護中。考慮到移動對象在某些敏感位置和時間域上展現一定的特征，例如，在交通路口當紅色交通信号燈亮時，附近的移動對象會在較長時間内沒有位置變化。通過對位置資料的時間域進行模糊，能夠避免攻擊者察覺到使用者處于交通路口這一事件的發生[28]。同時，當滿足使用者隐私要求的區域不存在時，使用時間模糊化可以實作使用者的隐私需求[7,29,25]。
1.5.1節中介紹的方法隻考慮目前時刻的位置是否會暴露使用者的敏感位置，然而，使用者的隐私資訊可能會由于位置資料在時間和空間上的關聯而洩露。事實上，有研究表明使用者在未經保護的情況下送出查詢時，位置資料在時間和空間上的關系可以通過多種模型來刻畫。目前主要使用隐馬爾可夫模型[5]或一般化圖模型[13]來刻畫使用者的位置資料在時間和空間上的關系。
2012年，文獻[11]中提出了基于隐馬爾可夫模型的機率推測抑制法。該方法針對lbs應用中使用者連續地向伺服器發送位置資訊的場景，假設攻擊者具有足夠的背景知識，并對使用者送出的每個位置資料推測使用者隐私。該工作提出了maskit系統，幫助使用者判斷送出目前位置資料是否違反使用者隐私要求。對于違反隐私要求的位置資訊采取機率性的抑制釋出政策，以此來保證攻擊者無法以較高的後驗機率推測出使用者處于哪個敏感位置。
圖1-4是将使用者移動模式用隐馬爾可夫模型模組化的示意圖。使用者從每天的起始位置開始移動，以後的各個時刻會根據上一時刻使用者位置的不同，轉移到各個其他位置，其中有些位置是敏感位置（在圖中用淺色陰影表示）。轉移的機率由模型建立時形成的參數确定。攻擊者推測使用者處于敏感位置的先驗機率是0.2，假設無論使用者處于敏感位置或非敏感位置都以0.5的機率釋出位置，則當攻擊者接收到抑制釋出的位置資訊時，根據貝葉斯公式，攻擊者推測使用者處于敏感位置的後驗機率為：
隐馬爾可夫模型認為使用者釋出的位置資料隻與其目前所處的位置有關。這樣的假設有利于模型的高效建立，但對使用者在某時刻處于某位置的機率計算并不十分準确。考慮到曆史資料也會暗示使用者目前位置是否敏感，是以曆史資料也對目前位置是否能夠安全釋出具有很大影響。總之，目前時刻所處的位置和之前的曆史資料均對是否釋出位置資料有影響，且影響基于位置服務的可用性。為此，文獻[11]中提出了兩種不同的抑制方法，這兩種方法針對各自的使用者群體具有各自适宜的服務可用性。
第一種抑制方法：設反映對各個位置的釋出機率的向量p=( p1，…，pn)，其中pi表示使用者處于第i個位置時以pi的機率釋出。方法一從p=(0，…，0)開始（即完全不釋出位置資訊）。利用mondfrian和algpr等貪心優化方法，逐漸調整各個位置的釋出機率。釋出機率向量确定後，根據給定的移動軌迹，利用貝葉斯公式和隐馬爾可夫模型分别計算使用者屬于敏感位置的後驗機率和先驗機率。根據後驗機率與先驗機率之差，判斷p是否滿足隐私需求，不斷調整p中各個元素的值直至收斂。在實際運作中，系統按照收斂後的釋出機率向量在各個位置上釋出使用者的位置資訊。
第二種抑制方法：根據使用者曆史位置資料計算使用者目前處于敏感位置的先驗機率；然後通過考慮未來所有可能的位置釋出，計算釋出目前位置以後使用者在各個時刻處于各個敏感位置的後驗機率；與第一種方法類似，根據後驗機率與先驗機率之差，判斷釋出目前位置是否違反隐私需求，進而線上決定是否釋出該位置。文獻[11]将“考慮未來所有可能的位置釋出”這樣一項時間複雜度極高的任務，簡化成了多項式時間内可完成的任務。
一方面，基于抑制的隐私保護方法送出了使用者的若幹真實查詢，當攻擊者具有使用者的背景知識時，攻擊者可以根據使用者釋出的位置直接得到使用者所在的位置；另一方面，基于抑制的方法犧牲了lbs應用的可用性，使用者在查詢被抑制時無法得到服務。
1.5.1節和1.5.2節介紹的隐私保護技術通過釋出失真位置資料和抑制釋出位置資料的方法，達到了對位置大資料隐私保護的目的。然而，這兩類方法無法滿足具有較高隐私需求使用者的要求。基于資料加密的方法是指利用加密算法将使用者的查詢内容（包括位置屬性、敏感語義屬性等）進行加密處理後發送給服務提供商。服務提供商根據接收到的資料在不解密的情況下直接進行查詢處理。服務提供商傳回給用戶端的查詢結果需要使用者根據自己的密鑰進行解密，并獲得最終的查詢結果。在這個過程中，服務提供商因為沒有密鑰，無法得知使用者的具體查詢内容，甚至對傳回給用戶端的查詢結果的含義也無法掌握。
最早基于資料加密的方法是通過利用空間填充曲線轉換資料空間實作的。khoshgoz-aran等人提出了利用hilbert曲線将表示位置資訊的二維坐标從二維空間轉換到一維空間，利用一維空間的鄰近性來解決近鄰查詢等空間查詢問題[18,20]。當使用者提出查詢請求的時候，将查詢位置的二維坐标轉換成一維的hilbert值并發送給服務提供商。服務提供商根據在一維空間的值查詢出滿足條件的對象傳回給使用者。在此過程中，服務提供商隻能傳回給使用者近似解。同時，該方法因空間填充曲線的局部性和距離維護性會導緻潛在的隐私洩露風險。
第二類是利用同态加密等加密工具結合資料庫索引技術來防止空間查詢處理過程中的隐私洩露。文獻[37]提出了基于查詢隐私保護的層次型索引結構，可支援多種查詢類型。該方法從查詢隐私和資料隐私兩個方面進行設計，然而該方法依然存在查詢關鍵字的洩露風險。因為送出使用者的每個查詢後，在伺服器端按照算法執行的過程會形成一個通路模式（如通路伺服器資料庫的次數、單次通路的資料量大小等）。通路模式的不同給攻擊者帶來了推測隐私的機會。以圖1-5為例，當使用者提出的查詢位于興趣位置點（point of interest，poi）分布稀疏和密集的兩種情況下，需要的資料頁通路數量肯定是不同的。攻擊者可根據目前查詢的通路模式推測出查詢是位于poi分布稀疏的區域，還是位于poi分布密集的區域，由此會導緻隐私洩露。第一類和第二類方法均不能阻止攻擊者通過通路模式對使用者的查詢内容進行推測。
第三類是基于私有資訊檢索（private information retrieval，pir）技術的隐私保護方法。pir理論最早被應用于通路網絡中的外包資料，使用者可以檢索一個不可信伺服器上的任意資料項，而不暴露使用者檢索的資料項資訊[4]。當使用者送出查詢資料庫中索引為i的資料塊時，pir技術可以在伺服器不知道使用者的查詢内容（i）的前提下為使用者傳回其查詢的資料塊。基于pir的隐私保護技術大緻可以分為3類：基于資訊論的pir技術、基于計算能力的pir技術以及基于硬體的pir技術。其中後兩種被研究者普遍應用于最短路徑計算[22]以及近鄰查詢[12,10,26]計算。
位置資料隐私保護技術需要在保護使用者位置隐私的同時兼顧服務可用性以及開銷。一般從以下3個方面度量位置隐私保護技術的性能：
1）服務的可用性，指釋出位置資訊的準确度和及時性，反映通過隐私保護技術處理後使用者獲得的基于位置資料的服務品質。
2）隐私保護程度，通常由隐私保護技術的披露風險來反映。通常，服務的可用性與隐私保護程度之間具有一個權衡，提高隐私保護程度有時會降低服務的可用性。
3）開銷，包括預計算和運作時發生的存儲和計算代價。存儲代價主要發生在預計算時，該代價在現有技術中通常可以接受，并在選擇隐私保護技術時被忽略。運作時的計算代價根據位置大資料隐私保護技術的特點，一般利用cpu計算時間以及檔案塊通路次數的時間複雜度進行度量。
每類位置資料隐私保護技術都有不同的特點。表1-3從隐私保護度、運作時開銷、預計算開銷和資料缺失4個方面分析比較了現有的各種隐私保護技術。從表1-3可以看出，不同方法的适用範圍、性能表現等不盡相同。當對位置資料的隐私程度要求較高且對計算開銷要求較高時，基于抑制釋出的位置大資料隐私保護技術更适合。當關注位置資訊的完美隐私保護時，則可以考慮基于資料加密的位置大資料隐私保護技術，這時計算量以及響應時間上的代價較高。基于資料失真的位置隐私保護技術能夠以較低的計算開銷實作對一般隐私需求的保護。表1-4從技術層面對各種方法的優點、缺點以及代表性技術作了進一步的對比顯示。