基于多匿名器的軌跡隱私保護方法

張少波 王國軍 劉 琴 劉建勛

1(湖南科技大學計算機科學與工程學院 湖南湘潭 411201)2(廣州大學計算機科學與教育軟件學院 廣州 510006)3 (湖南大學信息科學與工程學院 長沙 410082) (shaobozhang@hnust.edu.cn)

近年來，全球定位技術和無線通信技術的飛速發展以及移動智能終端設備的快速普及，使得基于位置服務(location-based service, LBS)的移動社交網絡APP(如Foursquare，Twitter，Loopt)得到廣泛關注和使用，人們通過這些APP可以發現最近的電影院、超市和醫院等，它們正在改變著信息時代人們的生活[1-2].在LBS應用中，用戶需要將自己當前位置、查詢內容等信息發送到LBS服務器查詢，以獲得預期的查詢結果.然而人們在享受LBS帶來全新體驗和生活便利的同時，也面臨著個人敏感信息可能被泄露的風險[3-4].攻擊者根據用戶連續發送的LBS查詢，可以追蹤到用戶的日常行為軌跡，并可能分析出特定用戶的敏感信息，如生活習慣、工作地址以及社會關系等，這將給用戶個人隱私帶來極大的安全隱患[5].因此，如何對位置服務中的用戶軌跡進行隱私保護，已成為當前迫切需要解決的問題.

為減少基于位置服務中的軌跡隱私泄露，學者們已提出一些軌跡隱私保護方法，它們主要采用基于點對點(peer to peer, P2P)的結構和基于可信第三方(fully-trusted third party, TTP)的中心服務器結構[6].P2P結構中用戶之間相互可信，且它們相互協作形成匿名域后再向位置服務提供商(location service provider， LSP)發送查詢請求.文獻[7]首次提出了一種用戶協作的點對點匿名算法，移動用戶通過單跳或者多跳路由尋找其他K-1個近鄰用戶，形成一個包括K個用戶的匿名域[8-9]，再發送到LSP查詢，但在尋找近鄰用戶時會產生較大開銷.為減少開銷，文獻[10]提出了一種基于緩存的用戶合作隱私保護方法，移動用戶先在合作用戶緩存中查找查詢內容，當找不到時才通過協作的方式向LSP發出查詢.總體而言，在點對點結構中移動用戶發送查詢前需要進行一定的匿名或變換處理，這將會對移動終端產生較大的計算開銷，同時它不能避免惡意用戶的攻擊.

在TTP結構中，通過在用戶和LSP之間引入一個中間體即匿名器，負責對用戶位置進行匿名和用戶查詢結果求精[11].文獻[12]最先提出了通過第三方可信服務器實現匿名功能的TTP結構，以達到對用戶位置隱私的目的.文獻[13]提出了一種移動軌跡查詢點的時間混淆技術，該方法基于TTP結構，并根據用戶的隱私屬性和周圍條件形成匿名域，同時在查詢點時間上進行混淆，攻擊者不能重新構造用戶的移動軌跡.文獻[14]在TTP結構中基于虛假位置提出一種路網環境下的連續查詢方法，使用路網交叉點代替真實用戶查詢位置，以獲取用戶查詢結果.文獻[15]在連續LBS查詢過程中，提出了一種防止位置注入攻擊的K匿名隱私保護方案，它結合用戶的移動模式建立基于可信的K匿名機制來防止用戶使用假位置，使攻擊者能識別真實用戶的概率為1/K.總體而言，這些基于TTP結構的方法存在2個問題：1)匿名器知道所有用戶的精確位置和查詢內容，如果匿名器被攻破，這將會帶來嚴重的安全威脅.2)用戶的查詢請求和結果返回都必須經過匿名器，它承擔著匿名、求精等繁重的計算任務，容易成為該結構中的性能瓶頸，同時也存在著中心點失效風險.

針對LBS中TTP結構存在的缺陷，本文提出一種基于多匿名器的軌跡隱私保護方法 (trajectory privacy-preserving method based on multi-anonymizer, TPMA)，通過在用戶和LSP之間部署多個匿名器，在連續查詢過程中，用戶分別隨機選擇不同的匿名器進行匿名.攻擊者從單個匿名器不能推斷出用戶的真實軌跡.并且用戶每次查詢前，通過動態假名機制選擇不同的用戶假名，即使多個匿名器進行共謀，也不能獲得真實用戶的軌跡. 同時該方法結合Shamir門限方案，將用戶的查詢內容分成n份額子信息，并且這些子信息被隨機發送給n個匿名器進行處理后再轉發給LSP，單匿名器也不能推斷出用戶查詢內容，該TPMA方法中某個匿名器的失效并不影響系統的運行，單個匿名器也不會承擔用戶連續查詢過程中的所有匿名處理，有效解決TTP結構中匿名器單點失效風險和性能瓶頸問題.

1 系統模型和相關定義

1.1 系統模型

TPMA軌跡隱私保護模型如圖1所示，它主要由4類實體組成：用戶、認證中心(certificate authority, CA)、多匿名器和LSP.

Fig. 1 The TPMA model圖1 TPMA模型

1) 用戶.指攜帶有移動智能終端的用戶，且該智能終端具有定位、通信、計算和存儲功能，它能將用戶的查詢請求發送給LSP查詢.同時它具有一些基本的處理功能，如產生密鑰，對信息進行轉換、劃分和聚合等.

2) 認證中心.它是一個可信實體，主要負責用戶和LSP的注冊.本方案中它也具有發布用戶假名和證書的功能，用戶在每次查詢時能隨機選擇不同的假名，使攻擊者在匿名器中不能識別真實的用戶軌跡和查詢內容.

3) 多匿名器.它是介于用戶與LSP之間的實體，主要功能是形成K匿名區域，以保證用戶在LBS服務器中的位置隱私.TPMA中多匿名器也具有轉發用戶信息功能.

4) LSP.它是一個服務提供者，擁有不同應用的LBS服務器，并能及時存儲和更新應用服務數據，為用戶提供各種數據服務.在該模型中，LBS服務器能恢復出用戶需要查詢的內容，然后在數據庫搜索用戶的POIs，并將查詢結果集分成w份經多匿名器返回給用戶.

TPMA工作過程如下：1)用戶首先向CA進行注冊或認證，并獲得一些假名和證書，同時用Shamir門限將查詢內容分成n份額子信息.2)用戶取假名，并將這n份額子信息隨機發送給n個不同匿名器，然后由其中一個匿名器負責對用戶位置匿名后，再轉發查詢請求給LSP.3)LSP只要收到t份子信息，就能恢復用戶的查詢內容，并在LBS服務器數據庫中查詢匿名區域內的興趣點(point of interests, POIs).4)LSP獲得查詢結果后，將其分成w個子候選結果集，然后從系統中隨機選擇w個匿名器，并將子候選結果集經這些匿名器轉發給用戶.5)用戶收到w個子候選結果集后，經求精得到精確結果.

該方法的優點是攻擊者從單個匿名器并不能獲得用戶的軌跡和查詢內容，加強了對用戶的隱私保護，同時也有效解決TTP結構中單匿名器的性能瓶頸問題和單點失效風險.

1.2 Shamir門限方案

設t,n是正整數，且t≤n.如果將一個秘密S分解為n份子秘密{S1,S2,…,Sn}，然后將其分別給n個參與者{P1,P2,…,Pn}各分發1份子秘密Si(1≤i≤n).若要得到秘密S，則最少需要t個參與者{P1,P2,…,Pt}一起使用t份秘密Si聚合，而少于t個參與者則不能計算出秘密S，那么稱該方案為(t,n)門限方案，其中t為門限值.

Shamir門限方案是基于Lagrange插值公式實現[16]，通過構造t-1次多項式，共享秘密S為該多項式的常數項，每份秘密滿足該多項式的一個坐標點(xi,F(xi))，生成的多項式為

F(x)=(S+m1x+m2x2+…+
mt-1xt-1) modq.

(1)

Shamir門限方案滿足3個條件：

1) 式(1)中m1,m2,…,mt-1是隨機整數，且t是不大于n的整數.

2) 分發者選擇一個有限域GF(p)且p為大素數.對于每個在有限域內選定的xi(i=1,2,…,n)，能計算出一個唯一的F(xi)，并將其解(xi,F(xi))作為一個秘密份額，由n個參與者{P1,P2,…,Pn}分別持有.

3) 只有等于或多于t個參與者將所持有的秘密份額聚合，才能恢復出秘密，少于t個參與者{P1,P2,…,Pt}所持有的秘密份額，則不能恢復出秘密S.

1.3 安全模型

目前，在LBS位置隱私保護研究中，具有代表性的攻擊模型分為強攻擊者攻擊模型和弱攻擊者攻擊模型[17].

1) 強攻擊者攻擊模型

在強攻擊者模型中，攻擊者可以監視系統中特定用戶的行為記錄，它試圖從當前獲得的信息中推斷出用戶的其他信息[18].TPMA模型中將LSP、匿名器視為強攻擊者.LSP憑借自己對LBS數據庫的擁有權，它可能會因利益關系，將數據庫中的用戶個人敏感信息泄露給第三方而引起的隱私風險.在匿名器對用戶查詢請求和查詢結果進行轉發過程中，它可能對這些信息進行分析，造成用戶敏感信息的泄露.

2) 弱攻擊者攻擊模型

在弱攻擊者模型中，攻擊者擁有很少的用戶個人信息，它試圖使用背景知識或其他一些攻擊手段進行攻擊，以期待獲得用戶的敏感信息.TPMA模型中，弱攻擊者通過竊聽用戶查詢過程中的通信信道，試圖分析出特定用戶的敏感信息.

2 TPMA軌跡隱私保護方法

本節將分別從用戶查詢請求、匿名器匿名、服務器查詢和用戶獲得結果4個主要步驟介紹TPMA方法的具體實現過程.

2.1 用戶查詢請求

2.1.1 門限分割機制

用戶發出查詢前，先將查詢內容和用戶產生的密鑰使用Shamir門限進行分割.分割時，用戶根據具體的語言環境，選擇合適的編碼方式(如Unicode，ANSI，ASCII等)將用戶需要查詢內容q中的字符信息轉換為數值，然后采用Shamir門限方案將查詢內容q、用戶隨機產生密鑰k分別分割為n份數值信息，其具體實現為：

1) 在GF(p)內，可以任意選擇t-1個元素mi(i=1,2,…,t-1)構成t-1階多項式

(2)

其中,p是一個大素數且p>S,秘密S=F(0).用戶可以生成n個子秘密：

(3)

其中，j=1,2,…,n.

2) 將用戶查詢內容q和密鑰k分別作為式(3)中的S，并在有限域GF(p)內隨機選定n個非零且互不相同的元素qi，ki(i=1,2,…,n)分別代入式(3)中的變量xj得到F(xj)，即為F(qi)和F(ki)，由此可計算得到n份子查詢內容和子密鑰，分別為{(q1,F(q1)),(q2,F(q2)),…,(qn,F(qn))},{(k1,F(k1)),(k2,F(k2)),…,(kn,F(kn))}.同時分別令Qi=(qi,F(qi))，Ki=(ki,F(ki))，則n份子查詢內容和子密鑰分別可表示為{Q1,Q2,…,Qn}，{K1,K2,…,Kn}.

3) 得到分割后的n份子信息{(Q1,K1),(Q2,K2),…,(Qn,Kn)}.

2.1.2 動態假名機制

在連續查詢過程中，用戶通過不斷變換假名，使用不同假名向不同匿名器發出轉發查詢請求，使攻擊者不能從單匿名器獲得用戶真實身份，同樣不能獲得用戶的真實軌跡.用戶動態假名機制實現過程如下：

2.1.3 隨機映射機制

假定系統中有編號為1,2,…,N的N個匿名器(A1,A2,…,AN)，用戶通過隨機映射機制將子信息{(Q1,K1),(Q2,K2),…,(Qn,Kn)}(N≥n)分別分配到隨機選定的n個匿名器進行處理.本文通過構造一個映射表Table，以各子信息為變量構造一個散列函數H(·)并將其取模，以獲得映射到編號為l的匿名器.

Al=H(Qj+Kj) modN，

(4)

其中，1≤j≤n,1≤l≤N.

當存在不同子信息映射到相同匿名器時，將會產生沖突.本文對有沖突的匿名器編號進行計算：

Al=(H(Qj+Kj)+v) modN，

(5)

其中，1≤v≤N-1.先取v=1，如果獲得的匿名器編號還有沖突，依次增加v的值，令v=v+1，直到解決沖突為止.由此構造一個映射表，將各子信息分別映射到不同的匿名器.

(6)

用戶向匿名器發送請求消息時，也需要將查詢標識符Q，分別加入到其他n-1個子信息中形成{{Q,(Q2,K2)},{Q,(Q3,K3)},…,{Q,(Qn,Kn)}}.然后，根據隨機映射機制，通過安全信道發送到對應的n-1個不同的匿名器.

2.2 匿名器匿名

(7)

同時其他n-1個匿名器也分別將其余子信息{{Q,(Q2,K2)},{Q,(Q3,K3)},…,{Q,(Qn,Kn)}}轉發給LBS服務器.

2.3 服務器查詢

(8)

(9)

然后，LBS服務器根據用戶的查詢內容q、匿名域region和查詢半徑R查詢用戶需要的興趣點POIs，POIs搜索算法如算法1所示：

算法1. POIs搜索算法.

輸出：POIs.

① LBS服務器根據查詢標識Q、在時間T內聚合多個(qj,kj)(t≤j≤n)，通過恢復Lagrange多項式計算獲得用戶查詢內容q；

③ 在查詢范圍內搜尋所有興趣點；

④ IF興趣點Pi為qTHEN

⑤POIs←Pi；

⑥ ENDIF

該算法的主要開銷是在LBS服務器搜索興趣點的開銷，它的時間復雜度為O(m)[19]，m是興趣點數目.通過算法1可獲得查詢范圍內的興趣點集Re，同時將Re分為w個子集{Re1,Re2,…,Rew}且w≤N，并對它們分別使用對稱加密算法DES和密鑰k進行加密得到Enk(Rei)(1≤i≤w).最后，LBS服務器從N個匿名器中隨機選擇w個對結果集{Re1,Re2,…,Rew}進行轉發，其轉發消息為

(10)

其中，1≤i≤w.

2.4 用戶獲得結果

(11)

其中，1≤i≤w.

3 安全性分析

本節通過分析TPMA方法分別抵制本文1.3節安全模型中提出的強攻擊者攻擊和弱攻擊者攻擊，并將系統中的匿名器、LSP考慮為強攻擊者，竊聽者考慮為弱攻擊者.

3.1 抵制匿名器推斷攻擊

挑戰：多匿名器主要負責對用戶位置進行匿名和用戶查詢信息進行轉發，它們試圖從用戶轉發的信息中推斷出一些個人敏感信息.如果多匿名器可以確定地知道用戶的查詢內容和用戶對應的軌跡，那么它將贏得這個游戲.

定理1. TPMA方法能抵制匿名器的推斷攻擊.

在查詢結果返回給用戶的過程中，w個結果子集Enk(Rei)都使用密鑰k進行了加密，匿名器沒有用戶密鑰k，就不能解密獲得用戶的查詢結果集Re.從以上分析可知，匿名器不能獲得用戶的查詢內容和用戶對應的軌跡.

證畢.

3.2 抵制LSP推斷攻擊

挑戰：LSP擁有對所有LBS數據庫的管理權限，它試圖從數據庫中的用戶查詢數據推斷出關于用戶的個人敏感信息.如果LSP可以成功的猜測出指定用戶的查詢內容或所對應用戶軌跡，那么LSP將贏得這個游戲.

定理2. TPMA方法能抵制LSP的推斷攻擊.

當LSP收到t個子信息{Q,(Qi,Ki)}時，就可以利用Lagrange插值多項式恢復出用戶查詢內容q，并根據q,region,R查詢得到所有興趣點的結果集.在這過程中，LSP也僅知道該用戶需要查詢的內容q，由于使用了假名機制，它并不能與具體的用戶相關聯.因此，通過這些用戶查詢的數據，LSP不能確定用戶軌跡，也猜測不出需要查詢內容所對應的用戶.

證畢.

3.3 抵制竊聽者攻擊

挑戰：弱攻擊者偵聽用戶查詢過程中的通信信道，試圖從獲得的用戶數據分析出指定用戶的軌跡或查詢內容等敏感信息.如果弱攻擊者可以成功地猜測出指定用戶的查詢內容或所對應軌跡，那么弱攻擊者將贏得這個游戲.

定理3. TPMA方法能抵制偵聽者的攻擊.

證畢.

4 實驗及結果分析

本部分通過實驗驗證用戶連續查詢時，TPMA方案在相關參數變化下對系統平均計算時間與通信開銷的影響，并在匿名器的平均計算時間和通信開銷上與TTP結構中的Gedik方案[12]和Hwang方案[13]進行實驗對比.實驗通過在Brinkhoff移動對象生成器中輸入德國奧爾登堡市交通網絡圖，并生成10 000個移動對象[20].Brinkhoff生成的移動用戶隨機分布，實驗對象隨機選擇一條移動軌跡，匿名器數目N=100.實驗環境為：Intel?CoreTMi5-4590 CPU @3.30 GHz,4.00 GB內存，Microsoft Windows 7 操作系統，在MyEclipse平臺以Java實現.

4.1 參數變化對TPMA性能的影響

Fig. 2 The effect of the number of sub-information and the anonymity圖2 子信息數目及匿名度對性能的影響

本節主要通過改變子信息劃分數目n、查詢半徑R、興趣點數目POIs以及匿名度K，分析對TPMA性能的影響.

如圖2所示為R=1,POIs=10 000時，通過改變子信息劃分數目n和匿名度K值對TPMA性能的影響.由圖2可知系統查詢時間和通信開銷都隨著n的增大而增大，同時K值越大其系統開銷也越大.因為子信息劃分數目n越大，需要更多匿名器處理用戶的子信息，查詢所需的時間和通信量就會增長越快.同時形成的匿名域也會隨著K值的增大而擴大，從而系統需要查詢更大范圍內包含的POIs,相應所需時間和通信開銷就會增多.因此，n或K值越大，系統查詢所需的時間和通信開銷就越大.

如圖3所示為n=50,POIs=10 000時，通過改變查詢半徑R和匿名度K值對TPMA性能的影響.由圖3可知系統查詢時間和通信開銷都隨著R值的增大而增大，同時K值越大其系統開銷也越大.因為R值越大，用戶需要查詢的范圍面積就越大，相應會查詢到更多的POIs，所以需要更多的處理時間和通信開銷.

Fig. 3 The effect of the query range and the anonymity圖3 查詢半徑及匿名度對性能的影響

如圖4所示為n=50，R=1時，通過改變興趣點POIs和匿名度K值對TPMA性能的影響.由圖4可知系統查詢時間和通信開銷都隨著POIs值的增大而增大，同時K值越大系統開銷也越大.因為匿名域中的POIs數目越多，系統需要更多時間來處理POIs，而且也會增加用戶求精的處理時間，因此相應時間開銷也越大.同時匿名域中的POIs數目越多，就會有更多POIs從LBS服務器到匿名器以及從匿名器返回給用戶，所以相應通信開銷也越大.

Fig. 4 The effect of the POIs and the anonymity圖4 POIs及匿名度對性能的影響

4.2 單匿名器性能對比

Fig. 5 The performance comparison of a single anonymizer圖5 單匿名器的性能對比

由圖5可知在單匿名器的時間和通信開銷上，TPMA相對于Gedik，Hwang有明顯優勢.因為TPMA方法是從N個匿名器隨機選擇n個匿名器同時處理用戶的單次查詢，而TTP中僅由一個匿名器處理，所以本文提出的TPMA方法在單個匿名器的平均時間和通信開銷上相對于TTP結構的Gedik，Hwang方法更有優勢，同時也解決了單個匿名器性能瓶頸問題和單點失效風險.

5 總 結

在LBS位置隱私保護中，針對傳統TTP結構存在的隱私風險和性能瓶頸問題，本文提出了一種基于多匿名器的軌跡隱私保護方法，通過在用戶和LSP之間部署多個匿名器，并結合Shamir門限方案和動態假名機制，將分割后的用戶查詢信息經隨機選擇的不同匿名器轉發給LSP，單個匿名器不能獲得用戶的軌跡和查詢內容.安全性分析表明TPMA方法能有效抵制匿名器、LSP和竊聽者的攻擊.實驗結果表明，與TTP結構的相關方案對比，TPMA方法能大大降低單匿名器的平均開銷，并有效解決單個匿名器的性能瓶頸問題.然而由于引入了Shamir門限方案和動態假名機制，增加了系統中用戶端的開銷，因此下一步我們將進一步優化TPMA方法，降低LBS的查詢開銷，提高用戶服務質量.