移動社交網絡中基于代理轉發機制的軌跡隱私保護方法

張少波 Md Zakirul Alam Bhuiyan 劉 琴 王國軍

?

移動社交網絡中基于代理轉發機制的軌跡隱私保護方法

張少波①④Md Zakirul Alam Bhuiyan②劉 琴③王國軍*①⑤

①(中南大學信息科學與工程學院 長沙 410083)②(天普大學計算機與信息科學系 費城 PA19122)③(湖南大學信息科學與工程學院 長沙 410082)④(湖南科技大學計算機科學與工程學院 湘潭 411201)⑤(廣州大學計算機科學與教育軟件學院 廣州 510006)

K匿名技術是當前軌跡隱私保護的主流方法，但該方法也存在隱私泄露的風險。該文提出一種在移動社交網絡中基于代理轉發機制(BAFM)的軌跡隱私保護方法。該方法利用安全多方計算和內積安全計算進行隱私加密匹配，通過可信服務器在移動社交網絡中找最匹配的用戶做代理，然后由代理轉發用戶的請求到服務器進行查詢，隱藏用戶的真實軌跡與位置服務器的聯系，有效保護用戶的軌跡隱私。安全分析表明該方法能有效保護用戶的軌跡隱私；同時，通過實驗驗證該方法相對K匿名更高效，能減小服務器的查詢和通信開銷。

移動社交網絡；軌跡隱私保護；安全多方計算；內積安全計算

1 引言

隨著無線通信技術和具有定位功能的個人智能終端設備的發展，基于位置的服務(Location- Based Service, LBS)發展迅速并獲得廣泛關注[1]。用戶通過LBS可以獲得用戶位置附近的興趣點(Points Of Interests, POIs)，然而人們在享用LBS服務帶來便利的同時，也面臨著敏感信息泄露的風險。例如：根據用戶連續的LBS查詢，攻擊者可以分析出用戶的敏感軌跡特征，如工作及家庭地址、個人生活習慣等。因此，目前基于位置服務的軌跡隱私保護問題已引起學術界和工業界的廣泛關注，并迫切需要解決。為減少軌跡隱私泄露的風險，國內外學者已提出一些軌跡隱私保護方法，主要可分為3類[2]：假軌跡方法、抑制法和泛化法。假軌跡方法通過為真實軌跡產生一些假軌跡來減少真實軌跡暴露的風險[3,4]，該方法簡單并具有較小的計算開銷，但數據存儲容量大。抑制方法使軌跡上的敏感位置或頻繁訪問的位置不發布到LBS服務器[5,6]，該方法容易實現，但會丟失信息。泛化法就是泛化軌跡上的樣本點到相關的匿名域，使用戶的位置不能被精確地確定，該方法能確保數據的正確性，但有很高的計算開銷。

2 系統模型和相關定義

2.1 系統模型

基于代理轉發機制的軌跡隱私保護模型如圖1所示。移動過程中服務用戶需要LBS時，首先以當前位置為中心形成一個MSN，該MSN覆蓋范圍內的用戶分別將個人的屬性信息發送到可信計算服務器，然后利用基于安全多方計算和內積安全計算進行隱私匹配，找到MSN中與服務用戶指定屬性最匹配的用戶做代理。通過代理在服務用戶和LBS服務器之間進行信息轉發，使LBS服務器無法獲得服務用戶的真實身份信息，該方法能以較低的計算和通信開銷保護用戶的軌跡隱私，并讓用戶獲取精確的查詢結果。該模型主要由4類實體組成：服務用戶、最匹配用戶、LBS服務器以及可信計算服務器。

圖1 BAFM軌跡隱私保護模型

服務用戶 攜帶具有全球定位、計算存儲和無線通信功能的智能終端用戶，它能將不同時刻的請求信息連續發送到服務器進行查詢。

最匹配用戶 在MSN中最滿足服務用戶特定屬性條件的用戶，它的主要功能是在服務用戶和LBS服務器之間轉發查詢請求信息和查詢結果。

LBS服務器 它是一個服務提供者，擁有服務數據庫能為用戶提供各種數據服務。LBS服務器收到查詢請求后，在數據庫搜索服務用戶指定的POIs，并將它返回給服務用戶。

可信計算服務器 它是建立在可信計算平臺上的服務提供者，具有較強的計算能力，為用戶提供各種計算服務。本模型中，可信計算服務器主要提供安全多方計算和內積安全計算，以高效計算得到最匹配值。

2.2相關定義

(2)

定義3 安全多方計算協議 假設有個參與者，它們通過密碼學協議共同計算某個給定的函數，其中函數是一個概率函數，分別為參與者的秘密輸入，協議結束后，分別得到。協議要求每個參與者除了知道之外，不能得到任何信息。

2.3 安全模型

對隱私模型進行攻擊時，攻擊者的背景知識非常關鍵。根據已有的研究[12,13]，該隱私方法安全模型可分為：弱攻擊者攻擊模型和強攻擊者攻擊模型。

(1)弱攻擊者攻擊模型：在弱攻擊者攻擊模型中，攻擊者具有很少關于用戶的背景知識。通常攻擊者通過偵聽不安全的無線信道，試圖得到一些信息，從中推斷出用戶的敏感信息，如用戶的敏感位置、真實身份和興趣愛好等。本文方法中，攻擊者試圖竊聽服務用戶與LBS服務器之間的通信信道，分析代理轉發的信息進行攻擊。

(2)強攻擊者攻擊模型：在強攻擊者攻擊模型中，攻擊者能監視整個系統中特定用戶的行為記錄。本方法中的LBS服務器和代理可能成為潛在的強攻擊者。LBS服務器管理所有用戶的LBS查詢數據，服務提供商因利益關系，可能會泄露LBS服務器中敏感信息給第三方。代理在服務用戶和LBS服務器之間轉發信息，也可能會泄露轉發的信息或對信息進行用戶行為分析。

3 基于代理轉發機制的軌跡隱私保護方法

MSN中基于代理轉發機制的軌跡隱私保護方法，主要分為查找代理、代理轉發和服務器查詢3個過程，相關的符號描述如表1所示。

表1 BAFM隱私保護方法中的符號描述

3.1 查找代理

在查找最匹配用戶做代理的過程中，利用安全多方計算和內積安全計算進行隱私匹配，以確保用戶之間屬性信息的隱私[14,15]。MSN中的用戶都能獲得當前的位置和運動方向，因此服務用戶匹配過程中可定義兩個屬性：距離()和角度差()。表示服務用戶和被匹配用戶之間的距離，,為MSN覆蓋范圍的半徑；表示服務用戶和被匹配用戶之間的運動方向角度差，。假設,是移動對象2維平面的位置坐標，在時間內能獲得兩個不同的權重矢量和，則,之間的角度差為

(6)

服務用戶加密過程如表2所示。

表2服務用戶加密過程

在匹配用戶計算過程中，服務用戶首先對自身屬性矩陣加密，如算法1所示。通過計算得到加密矩陣，以隱藏個人信息，再發送給可信計算服務器。同時個被匹配用戶將自身的屬性矩陣進行轉置得到，并輸入到可信計算服務器。然后可信計算服務器對被匹配用戶()與服務用戶進行匹配值計算，得到匹配值，計算過程如算法2所示。通過該算法可信計算服務器可得到個匹配值,值越大表示越匹配。因此服務用戶選擇值最大的被匹配用戶做為代理。

用戶匹配值計算過程如表3所示。

表3用戶匹配值計算

3.2 代理轉發

(9)

3.3 服務器查詢

(11)

4 安全性分析

抵制強攻擊者攻擊 當LBS服務器成為強攻擊者時，BAFM方法中的服務用戶以代理在LBS服務器進行查詢，LBS服務器記錄的是與代理相關的行為信息。同時在服務用戶移動的過程中，找到的代理是動態變化的，且代理之間沒有關聯性。因此，LBS服務器不能通過任意的代理身份識別出用戶的真實身份。當代理成為強攻擊者時，代理轉發的,是使用非對稱加密和對稱加密加密的，代理沒有密鑰或，它將不能解密轉發的信息與，因此，代理不可能通過轉發的信息泄露服務用戶的軌跡隱私。由上述可知，BAFM方法能有效抵制強攻擊者的攻擊。

抵制弱攻擊者攻擊 當攻擊者竊聽服務用戶與代理之間的消息和時，攻擊者只能從,得到服務用戶的身份，因為其它信息通過非對稱加密和對稱加密進行了加密，攻擊者沒有私鑰和密鑰，不能解密獲得有效信息。當攻擊者竊聽代理與LBS服務器之間的信息和時，同樣攻擊者從,中只能得到代理身份。即使攻擊者同時得到和，它也不能與具體的查詢信息相關聯，因此該方法能有效抵制弱攻擊者的攻擊，攻擊者不能識別出用戶的軌跡。

5 實驗及結果分析

實驗主要從查找最匹配用戶和服務器查詢兩方面分析該方法的性能，并與匿名算法進行仿真實驗比較。實驗采用的數據集是由Brinkhoff軌跡生成器[16]生成，實驗利用德國奧爾登堡市交通網絡圖(區域為23.57 km26.92 km)作為輸入，生成1000條移動軌跡。查詢對象集數據是隨機分布的，實驗隨機選取移動對象Tom的移動軌跡作為實驗對象，Tom在不同時刻移動的軌跡如圖2所示。實驗參數設置如表4所示。實驗的硬件環境為：Intel(R) Core(TM) i5-4590 CPU @3.30 GHz 3.30 GHz, 4.00 GB內存，操作系統為Microsoft Windows 7，采用MyEclipse 開發平臺，以Java編程語言實現。

圖2 移動對象Tom的移動軌跡

表4 實驗參數設置

5.1 尋找最匹配用戶

圖3 值變化下的時間開銷 ? ? ? ? ? ? 圖4 值變化下的通信開銷

5.2 在LBS服務器查詢時的性能對比

在POIs=500且其它參數不變的情況下，將BAFM方法與文獻[17]，文獻[18]中Iclique, L2P2匿名方法進行比較，對比3種方法隨值變化對LBS服務器性能的影響。由圖7，圖8可知，在LBS服務器處理時間和通信開銷上，Iclique, L2P2匿名方法隨著值的增大而增大，而BAFM方法基本保持不變。這是因為值越大，Iclique, L2P2匿名方法形成的匿名域就越大，LBS服務器需要查詢的POIs就越多，所需的處理時間和通信開銷就越多。BAFM方法發送到服務器查詢的位置是精確的，因此查詢時間和通信開銷不會隨著值的增大而增大。

圖7 值變化下的時間開銷對比? ? ? ? ? ? 圖8 值變化下的通信開銷對比

6 結束語

基于位置服務的快速發展，位置隱私問題已成為當前隱私保護方向的一個研究熱點。本文提出一種基于MSN代理轉發機制的軌跡隱私保護方法，通過代理轉發信息到LBS服務器查詢，隱藏用戶真實軌跡和LBS服務器的關聯，保證用戶的軌跡隱私。該方法利用安全多方計算和內積計算進行隱私匹配，在MSN中找到最匹配的用戶做代理，在保證用戶之間隱私的情況下，提高查詢最匹配用戶的效率。安全分析表明該方法能抵制弱敵手和強敵手攻擊模型的隱私攻擊。同時，通過對比實驗驗證該方法在服務器具有較低的計算和通信開銷。當然該方法還有待改進的地方，例如，在MSN中代理轉發查詢信息時，只是假定用戶遵守相互轉發機制，因此在下一步工作中，我們嘗試使用轉發激勵機制，激發MSN中的用戶相互轉發信息。

[1] LU Rongxing, LIN Xiaodong, LIANG Xiaohui,A dynamic privacy preserving key management scheme for location-based services in vanets[J]., 2012, 13(1): 127-139.doi: 10.1109/TITS.2011.2164068.

[2] 霍崢, 孟小峰, 黃毅. PrivateCheckIn:一種移動社交網絡中的軌跡隱私保護方法[J]. 計算機學報, 2013, 36(4): 716-726.doi: 10.3724/SP.J.1016.2013.00716.

HUO Zheng, MENG Xiaofeng, and HUANG Yi. PrivateCheckIn: Trajectory privacy-preserving for check-in services in MSNS[J]., 2013, 36(4): 716-726.doi: 10.3724/SP.J.1016.2013.00716.

[3] LEI P R, PENG W C, SU I J,Dummy-based schemes for protecting movement trajectories[J]., 2012, 28(2): 335-350.

[4] YOU T H, PENG W C, and LEE W C. Protecting moving trajectories with dummies[C]. Proceedings of the 8th International Conference on Mobile Data Management, Mannheim, Germany, 2007: 278-282. doi: 10.1109/MDM. 2007.58.

[5] TERROVITIS M and MAMOULIS N. Privacy preservation in the publication of trajectories[C]. Proceedings of the 9th International Conference on Mobile Data Management, Beijing, 2008: 65-72. doi: 10.1109/MDM. 2008.29.

[6] 趙婧, 張淵, 李興華, 等.基于軌跡頻率抑制的軌跡隱私保護方法[J]. 計算機學報, 2014, 37(10): 2096-2106. doi: 10.3724/ SP.J.1016.2014.02096.

ZHAO Jing, ZHANG Yuan, LI Xinghua,A trajectory privacy protection approach via trajectory frequency suppression[J].2014, 37(10): 2096-2106. doi: 10.3724/SP.J.1016.2014.02096.

[7] HWANG R H, HSUEH Y L, and CHUNG H W. A novel time-obfuscated algorithm for trajectory privacy protection[J]., 2014, 7(2): 126-139. doi: 10.1109/TSC.2013.55.

[8] 朱懷杰, 王佳英, 王斌, 等. 障礙空間中保持位置隱私的最近鄰查詢方法[J]. 計算機研究與發展, 2014, 51(1): 115-125. doi: 10.7544/issn1000-1239.2014.20130694.

ZHU Huaijie, WANG Jiaying, WANG Bin,Location privacy preserving obstructed nearest neighbor queries[J]., 2014, 51(1): 115-125. doi: 10.7544/issn1000-1239.2014.20130694.

[9] 楊靜, 張冰, 張健沛, 等. 基于圖劃分的個性化軌跡隱私保護方法[J]. 通信學報, 2015, 36(3): 1-11. doi: 10.11959/j.issn. 1000-436x.2015053.

YANG Jing, ZHANG Bing, ZHANG Jianpei,Personalized trajectory privacy preserving method based on graph partition[J]., 2015, 36(3): 1-11. doi: 10.11959/j.issn.1000-436x.2015053.

[10] 王超, 楊靜, 張健沛. 基于軌跡位置形狀相似性的隱私保護算法[J]. 通信學報, 2015, 36(2): 144-157. doi: 10.11959/j.issn. 1000-436x.2015043.

WANG Chao, YANG Jing, and ZHANG Jianpei. Privacy preserving algorithm based on trajectory location and shape similarity[J]., 2015, 36(2): 144-157. doi: 10.11959/j.issn.1000-436x.2015043.

[11] XU T and CAI Y. Exploring historical location data for anonymity preservation in location-based services[C]. Proceedings of the 27th International Conference on Computer Communications(INFOCOM 2008), Toronto, Canada, 2008: 547-555. doi: 10.1109/INFOCOM.2008.103.

[12] GAO Sheng, MA Jianfeng, SHI Weisong,TrPF: a trajectory privacy-preserving framework for participatory sensing[J]., 2013, 8(6): 874-887. doi: 10.1109/TIFS.2013. 2252618.

[13] NIU Ben, ZHU Xiaoyan, CHI Haotian,3PLUS: privacy-preserving pseudo-location updating system in location-based services[C]. 2013 IEEE Wireless Communications and Networking Conference, Shanghai, China, 2013: 4564-4569. doi: 10.1109/WCNC.2013.6555314.

[14] GENKIN D, ISHAI Y, and POLYCHRONIADOU A. Efficient multi-party computation: from passive to active security via secure SIMD circuits[C]. Proceedings of the 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 721-741. doi: 10.1007/978-3-662-48000-7-35.

[15] ZHU Xiaoyan, LIU Jie, JIANG Shunrong,Efficient weight-based private matching for proximity-based mobile social networks[C]. 2014 IEEE International Conference on Communications, Sydney, Australia, 2014: 4114-4119. doi: 10.1109/ICC.2014.6883965.

[16] BRINKHOFF T. Generating traffic data[J]., 2003, 26(2): 19-25.

[17] PAN Xiao, XU Jianliang, and MENG Xiaofeng. Protecting location privacy against location-dependent attacks in mobile services[J]., 2012, 24(8): 1506-1519. doi: 10.1109/TKDE. 2011.105.

[18] WANG Yu, XU Dingbang, HE Xiao,L2p2: Location-aware location privacy protection for location-based services[C]. Proceedings IEEE INFOCOM, Orlando, Florida USA, 2012: 1996-2004. doi: 10.1109/INFOCOM.2012. 6195577.

The Method of Trajectory Privacy Preserving Based on Agent Forwarding Mechanism in Mobile Social Networks

ZHANG Shaobo①④Md Zakirul Alam Bhuiyan②LIU Qin③WANG Guojun①⑤

①(School of Information Science and Engineering, Central South University, Changsha 410083, China)②(Department of Computer and Information Sciences, Temple University, Philadelphia, PA19122, USA)③(College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China)④(School of Computer Science and Engineering, Hunan University of Science and Technology, Xiangtan 411201, China)⑤(School of Computer Science and Educational Software, Guangzhou University, Guangzhou 510006, China)

The trajectory K-anonymous is the mainstream of the current trajectory privacy protection, but the method has some defects such as privacy leakage. In this paper, a method of trajectory privacy preserving is proposed Based on Agent Forwarding Mechanism (BAFM) in mobile social networks, which uses secure multi-party computation and inner product secure computation to find the best matching user by the trusted server as the agent. The agent forwards the user’s request to the server to query, which hides the correlation between user’s real trajectory and the server in order to achieve user’s trajectory privacy. Security analysis shows that the propose method can effectively protect the user's trajectory privacy. Experiments show that the proposed method is more effective, it reduces the overhead of server’s query and communication.

Mobile social network; Trajectory privacy-preserving;Secure multi-party computation; Inner product secure computation

TP393

A

1009-5896(2016)09-2158-07

10.11999/JEIT151136

2016-02-18；

2016-04-26

國家自然科學基金(61472451, 61272151, 61402161, 61502163)，中南大學中央高校基本科研業務費專項資金(2016zzts058, 2016zzts060)

The National Natural Science Foundation of China (61472451, 61272151, 61402161, 61502163), The Fundamental Research Funds for the Central Universities of Central South University (2016zzts058, 2016zzts060)

王國軍 csgjwang@csu.edu.cn

張少波： 男，1979年生，博士生，講師，研究方向為云安全、隱私保護.

Md Zakirul Alam Bhuiyan： 男，1983年生，博士，助理教授，研究方向為云計算、數據挖掘和隱私保護.

劉 琴： 女，1982年生，博士，助理教授，研究方向為云計算、大數據和隱私保護.

王國軍： 男，1970年生，博士生導師，教授，研究方向為可信計算、大數據安全和隱私保護.