張少波 劉 琴 王國軍

?

基于網(wǎng)格標識匹配的位置隱私保護方法

張少波①③劉 琴②王國軍*①④

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

在基于位置的服務中，基于可信第三方模型是當前位置隱私保護中的主要模型，但該模型存在一定的隱私泄露風險。該文提出一種基于網(wǎng)格標識匹配(GIM)的位置隱私保護方法，用戶首先將查詢區(qū)域劃分為網(wǎng)格，并結合保序?qū)ΨQ加密和K匿名技術，在匿名器形成K匿名，然后利用網(wǎng)格標識匹配返回查詢結果給用戶。在查詢的過程中，匿名器并不知道用戶的具體位置，加強了該模型中用戶位置的隱私保護。同時中間匿名器僅進行簡單的比較和匹配，有效緩解了匿名器的性能瓶頸問題。安全分析表明該方法能有效保護用戶的位置隱私；并且通過實驗驗證該方法能有效減小匿名器的處理時間開銷。

位置隱私；網(wǎng)格標識匹配；保序?qū)ΨQ加密；K匿名

1 引言

隨著無線通信技術、智能終端設備和定位技術的發(fā)展，基于位置的服務(Location Based Service, LBS)發(fā)展迅速并獲得廣泛關注[1,2]。在LBS中，用戶通過帶有定位功能的設備可以獲得當前位置，并向位置服務器發(fā)送查詢，以獲取用戶位置附近的興趣點(Points Of Interests, POIs)，例如尋找距離當前位置最近的賓館、影院和加油站等，然而人們在享用LBS帶來便利的同時，也面臨著敏感信息泄露的風險[3]。根據(jù)用戶發(fā)送的LBS查詢，攻擊者可能分析出特定用戶的敏感信息，如家庭住址、生活習慣、健康狀況以及社會關系等[4]。同時位置服務提供商(Location Services Provider, LSP)也可能將用戶的隱私信息泄露給第三方，這將給用戶帶來嚴重的安全隱私風險。因此，目前基于位置服務的位置隱私保護問題已引起學者的廣泛關注，并迫切需要解決。

為減少隱私泄露的風險，國內(nèi)外已提出一些位置隱私保護方法，采用的基本結構主要分為兩類[5]：基于點對點的結構和基于可信第三方(Fully- Trusted Third Party, TTP)的中心服務器結構。在基于點對點的結構中，用戶之間通過協(xié)作的方式形成K匿名域[6,7]或使用混淆的方式[8]向LBS發(fā)送查詢，使LSP不知道用戶的精確位置。在基于可信第三方的中心服務器結構中，引入了一個可信匿名器，作為移動用戶和LSP之間的中間體。該結構中用戶首先將查詢請求發(fā)送給匿名器，然后匿名器將用戶的服務請求按用戶的隱私需求形成一個包括個用戶的匿名域，并將它發(fā)送給LSP進行查詢，得到查詢結果集后再返回給匿名器，最后可信匿名器根據(jù)用戶需求對候選結果集進行求精，并將精確結果返回給用戶。但基于可信第三方的中心服務器結構存在兩個問題：(1)匿名器知道用戶的精確位置，如果它被攻擊者攻破，將會帶來嚴重的安全威脅。(2) 匿名器承擔著匿名、求精等繁重的計算任務，容易成為該結構中的性能瓶頸。

針對TTP結構存在的兩個缺陷，文獻[12]提出通過自定義動態(tài)網(wǎng)格系統(tǒng)，使中間第三方不知道用戶的具體位置，達到保護用戶位置隱私的目的。但如果用戶指定的查詢區(qū)域只有一個用戶，LBS服務器就會很容易指出真實的用戶，暴露用戶的位置隱私。針對該方法存在的缺陷，本文提出基于網(wǎng)格標識匹配(Grid Identifier Matching, GIM)的位置隱私保護方法，結合保序?qū)ΨQ加密(Order-Preserving Symmetric Encryption, OPSE)和K匿名技術，用戶首先對查詢面積進行網(wǎng)格劃分，并將能確定各用戶查詢區(qū)域的坐標用保序?qū)ΨQ加密算法加密，然后發(fā)送到中間匿名器形成K匿名域，匿名器并不知道用戶的具體位置，且它不需要完全可信，加強了對用戶位置的隱私保護。同時在查詢的過程中，中間匿名器僅進行簡單的比較和匹配，有效緩解了匿名器的性能瓶頸問題。

2 系統(tǒng)模型和相關定義

2.1 系統(tǒng)模型

如圖1所示為基于GIM的位置隱私保護模型圖，系統(tǒng)主要由用戶、匿名器和LBS服務器3類實體組成，具體工作過程為：(1)用戶發(fā)送查詢時，首先指定一個查詢面積進行網(wǎng)格劃分，并尋找用戶附近個其它用戶，各用戶按查詢范圍在網(wǎng)格結構上確定各自的查詢區(qū)域，然后用OPSE對各確定網(wǎng)格查詢區(qū)域的坐標進行加密，發(fā)送給匿名器；同時用戶將自己指定的查詢區(qū)域內(nèi)的網(wǎng)格單元標識進行Hash并加密發(fā)送給匿名器；(2)匿名器比較用OPSE加密后的坐標大小，并根據(jù)比較結果形成包含個用戶查詢區(qū)域的匿名域，然后將該匿名域發(fā)送給LSB服務器進行查詢；(3)LBS服務器查詢匿名域內(nèi)的POIs，并將各POIs的位置以及對應的網(wǎng)格單元標識進行Hash并加密后返回給匿名器；(4)匿名器將各POIs位置所在的加密網(wǎng)格單元標識與用戶需要查詢區(qū)域的加密網(wǎng)格單元標識進行匹配，如果相等，則將該網(wǎng)格單元標識對應的POIs發(fā)送給用戶。該方法的優(yōu)點是匿名器并不知道用戶的精確位置，同時它只進行簡單的比較和匹配操作，加強了對用戶位置的隱私保護，同時也有效緩解了匿名器的性能瓶頸問題。

圖1 基于GIM的位置隱私保護模型

2.2 保序加密

2.3 安全模型

在位置隱私保護的研究方面，目前比較典型的攻擊模型主要分為兩種[16]：強攻擊者攻擊模型和弱攻擊者攻擊模型。

(1)強攻擊者攻擊模型： 在強攻擊者攻擊模型中，攻擊者能監(jiān)視整個系統(tǒng)中特定用戶的行為記錄，本方法中的匿名器和LSP都可能成為潛在的強攻擊者。因為LBS服務器管理所有用戶的LBS查詢數(shù)據(jù)，LSP因利益關系，可能會泄露LBS服務器中敏感信息給第三方。匿名器在用戶和LBS服務器之間進行匿名和轉(zhuǎn)發(fā)信息，也可能會對用戶進行行為分析，并造成信息泄露。

(2)弱攻擊者攻擊模型： 在弱攻擊者攻擊模型中，攻擊者具有很少關于用戶的背景知識，攻擊者通過使用背景知識或其它攻擊手段，試圖知道其它用戶更多的個人信息。本方法中，攻擊者可能試圖竊聽用戶與LBS服務器之間的通信信道，分析傳輸過程中的數(shù)據(jù)，甚至篡改查詢結果發(fā)送給用戶進行攻擊。

3 基于網(wǎng)格標識匹配的位置隱私保護方法

3.1 用戶加密查詢

本文假定用戶的查詢是范圍查詢，例如在市區(qū)環(huán)境下用戶查詢自己周圍1 km范圍內(nèi)的餐館、酒店或電影院等。用戶在發(fā)送查詢前，首先通過帶有定位功能的設備獲得自己的當前位置，然后根據(jù)自己的查詢半徑，指定一個包含用戶查詢范圍的方形查詢面積。該查詢面積可由左下角坐標和右上角坐標確定，再將該查詢面積劃分為大小相等的網(wǎng)格。因此，用戶指定的查詢面積網(wǎng)格結構可表示為

(2)

(4)

(5)

為使匿名器形成K匿名，用戶根據(jù)K近鄰算法[17]尋找到用戶附近興趣點相同的個其它用戶，它們都是可信的。然后每個用戶在網(wǎng)格結構上分別形成半徑為的圓形查詢范圍，并分別確定自己的查詢區(qū)域。

(7)

(9)

3.2 位置坐標比較

(11)

3.3 服務器查詢

LBS服務器收到匿名器轉(zhuǎn)發(fā)的查詢請求消息后，首先使用LBS服務器私鑰解密中的。然后根據(jù)中,和恢復用戶指定的查詢面積網(wǎng)格結構，并獲得用戶需要查詢的興趣點以及對稱加密密鑰集。同時LBS服務器用OPSE中的解密算法以及密鑰，解密查詢區(qū)域中的兩個坐標，可以在網(wǎng)格結構上確定K匿名域。最后LBS服務器根據(jù)查詢匿名域的POIs，共得到個POIs。如果第個POI的位置為，則它所在的網(wǎng)格單元標識為。

(13)

(14)

(16)

(17)

3.4 網(wǎng)格標識匹配

3.5 用戶求精結果

4 安全性分析

本節(jié)主要分析GIM位置隱私保護模型分別抵制強攻擊者和弱攻擊者的攻擊，本模型中將LSP和匿名器作為強攻擊者，竊聽者為弱攻擊者。具體分析如下。

4.1抵制LSP的攻擊

挑戰(zhàn)：LSP管理所有用戶的查詢數(shù)據(jù)，LSP作為強攻擊者想從這些數(shù)據(jù)中推斷出一些用戶敏感信息，從而揭露用戶的精確位置。如果LSP可以確定地知道查詢內(nèi)容所對應用戶的精確位置，那么LSP將贏得這個游戲。

定理1 GIM位置隱私保護方法能抵制LSP的推斷攻擊。

證明 本方案中，用戶發(fā)送的查詢經(jīng)匿名器轉(zhuǎn)發(fā)給LSP的查詢請求為,中包括匿名域，興趣點類型，密鑰集以及網(wǎng)格結構，從這些信息中，LSP不能獲得用戶的精確位置。因為在查詢過程中，LBS服務器根據(jù),查詢中的每個網(wǎng)格的POIs，然后返回給匿名器，而LSP僅知道該用戶的，但它并不能與具體的用戶關聯(lián)。而且該匿名區(qū)域至少包括個用戶，LSP能猜到是某個用戶的概率最多只有。因此，LSP通過這些數(shù)據(jù)不能得到用戶的精確位置。

證畢

4.2 抵制匿名器的攻擊

挑戰(zhàn)：匿名器在用戶和LBS服務器之間，負責對用戶進行K匿名，同時對查詢請求、查詢結果等信息的進行轉(zhuǎn)發(fā)，它作為強攻擊者想從這些數(shù)據(jù)中能推斷出一些用戶的敏感信息，從而揭露用戶的精確位置。如果匿名器可以確定地知道查詢內(nèi)容所對應用戶的精確位置，那么匿名器將贏得這個游戲。

定理2 GIM位置隱私保護方法能抵制匿名器的推斷攻擊。

證畢

4.3 抵制竊聽者的攻擊

挑戰(zhàn)：弱攻擊者通過偵聽不安全的無線信道，試圖從這些數(shù)據(jù)中能推斷出一些用戶的敏感信息，從而揭露用戶的精確位置，甚至攻擊者有意篡改用戶的查詢結果。如果弱攻擊者知道用戶的精確位置或能成功篡改用戶的查詢結果，那么弱攻擊者將贏得這個游戲。

村級診所作為新型農(nóng)村合作醫(yī)療的前沿陣地，鄉(xiāng)村醫(yī)生直接決定著新農(nóng)合供給的質(zhì)量，這就要求當?shù)卣畬嵤┓e極的鄉(xiāng)村醫(yī)生隊伍建設政策，其中包括提高鄉(xiāng)村醫(yī)生專業(yè)素質(zhì)，堅持持證上崗原則；不斷引進專業(yè)院校大學生來到村級診所工作，制定一系列的鼓勵政策；提升鄉(xiāng)村醫(yī)生的工作環(huán)境，提高其工資待遇水平；加強醫(yī)療設備的供給，保障最基本的醫(yī)療衛(wèi)生服務等。

定理3 GIM位置隱私保護方法能抵制偵聽者的攻擊。

證明 在用戶發(fā)送給LBS服務器的查詢請求消息,中，,,和都是通過對稱加密,和非對稱加密進行加密的，攻擊者沒有密鑰，不能解密這些參數(shù)，從而得不到有用的信息。在用戶查詢結果返回給用戶的,中，中網(wǎng)格單元標識的哈希值加密后的,POIs的位置加密后的以及完整性驗證函數(shù)都是通過對稱加密函數(shù)進行加密的，同樣攻擊者得不到密鑰，也得不到有用的信息。如果攻擊者在結果返回的過程中，試圖篡改POIs的位置，或加入一些假POIs的位置發(fā)送給用戶，使用戶得到錯誤的查詢結果。GIM方案在LBS服務器端引入消息完整性驗證機制，，用戶得到POIs的位置后，先用驗證值是否相等，如果不相等，則說明該查詢結果的完整性被破壞，用戶丟棄該查詢結果并進行重新查詢。因此，弱攻擊者既不能得到用戶的精確位置，也不能破壞查詢結果的完整性。

證畢

5 實驗及結果分析

本節(jié)主要通過實驗驗證GIM方案在相關參數(shù)變化下，用戶每次查詢時，對平均計算時間和平均通信開銷的影響；同時在匿名器的平均計算時間以及平均通信開銷上，與TTP[10], ELPP[5]方法進行仿真實驗比較。實驗采用由Brinkhoff移動對象生成器[18]，并利用德國奧爾登堡市交通網(wǎng)絡圖作為輸入生成10000個移動用戶，如圖2所示。實驗隨機選取某時刻的移動對象Tom作為實驗對象，Tom尋找到鄰近的其它2和3個用戶的位置分布情況如圖3所示。實驗參數(shù)設置如表1所示。實驗的硬件環(huán)境為：Intel(R)Core(TM)i5-4590CPU@3.30 GHz3.30 GHz, 4.00 GB內(nèi)存，操作系統(tǒng)為Microsoft Windows 7，采用MyEclipse開發(fā)平臺，以Java編程語言實現(xiàn)。

圖2 生成10000個移動用戶???????????????? 圖3移動用戶Tom找到的鄰近用戶

表1實驗參數(shù)設置

5.1 參數(shù)變化對GIM性能的影響

圖4 網(wǎng)格單元粒度及查詢范圍半徑變化對性能的影響

圖5 網(wǎng)格單元粒度及匿名度變化對性能的影響

5.2 匿名器性能對比

圖6 匿名器性能對比

由圖6(b)可知，在匿名器通信開銷上，TTP和ELPP相對于GIM有一定優(yōu)勢。因為在用戶發(fā)送查詢請求消息給匿名器的過程中，TTP中發(fā)送的是用戶的精確位置，ELPP中發(fā)送的是經(jīng)過轉(zhuǎn)換的位置信息，而GIM方法發(fā)送的是個能確定用戶指定查詢區(qū)域的坐標加密集、加密網(wǎng)格單元標識集和用戶端生成的對稱密鑰集等信息。同時在匿名器返回結果消息給用戶的過程中，TTP和ELPP方法中匿名器返回的是精確結果，而GIM方法返回的候選結果集，在用戶端需耗費一定的開銷對結果集求精。因此，在匿名器的通信開銷上，GIM方法有一定的劣勢，但它能更好保護用戶的位置隱私。

6 結束語

基于位置服務的快速發(fā)展，位置隱私問題已成為當前隱私保護方向的一個研究熱點。針對TTP結構模型存在的缺陷，本文提出一種基于網(wǎng)格標識匹配的位置隱私保護方法。該方法利用網(wǎng)格思想，結合保序?qū)ΨQ加密和K匿名技術，加強用戶的位置隱私保護，且匿名器不清楚用戶的具體位置。安全分析表明該方法能抵制LSP、匿名器和竊聽者的隱私攻擊。同時通過實驗驗證該方法在匿名器上具有較低的查詢計算開銷，有效緩解了匿名器的性能瓶頸問題。當然該方法也有待改進的地方，例如查詢結果集的求精和尋找其它個用戶由用戶端完成，增加了用戶端的計算開銷，因此在下一步工作中，我們嘗試在匿名器上通過用戶歷史記錄形成K匿名，在適當增加匿名器開銷的情況下，減少用戶端的開銷。

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

[2] YU Rong, KANG Jiawen, HUANG Xumin,MixGroup: accumulative pseudonym exchanging for location privacy enhancement in vehicular social networks[J]., 2016, 13(1): 93-105. doi: 10.1109/TDSC.2015.2399291.

[3] NIU Ben, LI Qinghua, ZHU Xiaoyan,Enhancing privacy through caching in location-based services[C]. 2015 IEEE Conference on Computer Communication(INFOCOM), Hong Kong, China, 2015: 1017-1025. doi: 10.1109/ INFOCOM.2015.7218474

[4] 張學軍, 桂小林, 伍忠東. 位置服務隱私保護研究綜述[J]. 軟件學報, 2015, 26(9): 2373-2395. doi: 10.13328/j.cnki.jos. 004857.

ZHANG Xuejun, GUI Xiaolin, and WU Zhongdong. Privacy preservation for location-based services: a survey[J]., 2015, 26(9): 2373-2395. doi: 10.13328/j.cnki.jos. 004857.

[5] PENG Tao, LIU Qin, and WANG Guojun. Enhanced location privacy preserving scheme in location-based services [J]., 2014: 1-12. doi: 10.1109/JSYST. 2014.2354235.

[6] SHOKRI R, THEODORAKOPOULOS G, PAPADIMITRATOS P,Hiding in the mobile crowd: location privacy through collaboration[J]., 2014, 11(3): 266-279. doi: 10.1109/TDSC.2013.57.

[7] CHOW C Y, MOKBEL M F, and LIU X. Spatial cloaking for anonymous location-based services in mobile peer-to-peer environments[J]., 2011, 15(2): 351-380. doi: 10.1007/s10707-009-0099-y.

[8] ARDAGNA C A, CREMONINI M, VIMERCATI S D C,An obfuscation-based approach for protecting location privacy[J].,2011, 8(1): 13-27. doi: 10.1109/TDSC.2009.25.

[9] 彭志宇, 李善平. 移動環(huán)境下LBS位置隱私保護[J]. 電子與信息學報, 2011, 33(5): 1211-1216. doi: 10.3724/SP.J.1146. 2010.01050.

PENG Zhiyu and LI Shanping. Protecting location privacy in location-based services in mobile environments[J].&2011, 33(5): 1211-1216. doi: 10.3724/SP.J.1146. 2010.01050.

[10] GEDIK B and LIU L. Protecting location privacy with personalized k-anonymous: architecture and algorithms[J]., 2008, 7(1): 1-18. doi: 10.1109/TMC.2007.1062.

[11] 周長利, 馬春光, 楊松濤. 路網(wǎng)環(huán)境下保護LBS位置隱私的連續(xù)KNN查詢方法[J]. 計算機研究與發(fā)展, 2015, 52(11): 2628-2644. doi: 10.7544/issn1000-1239.2015.20140523.

ZHOU Changli, Ma Chunguang, and YANG Songtao. Location privacy-preserving method for LBS continuous KNN query in road networks[J]., 2015, 52(11): 2628-2644. doi: 10.7544/ issn1000-1239.2015.20140523.

[12] SCHLEGEL R, CHOW C Y, HUANG Q,User-defined privacy grid system for continuous location-based services[J]., 2015, 14(10): 2158-2172. doi: 10.1109/TMC.2015.2388488.

[13] AGRAWAL R, KIERNAN J, SRIKANT R,Order preserving encryption for numeric data[C]. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France, 2004: 563-574.

[14] POPA R A, LI F H, and ZELDOVICH N. An ideal-security protocol for order-preserving encoding[C]. 2013 IEEE Symposium on Security and Privacy (SP), Berkeley, California, 2013: 463-477. doi: 10.1109/SP.2013.38.

[15] AHMADIAN M, PAYA A, and MARINESCU D C. Security of applications involving multiple organizations and order preserving encryption in hybrid cloudenvironments[C]. 2014 IEEE International Parallel & Distributed Processing Symposium Workshops (IPDPSW), Phoenix, Azerbaijan, 2014: 894-903. doi: 10.1109/IPDPSW.2014.102.

[16] 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.

[17] MCNAMES J. A fast nearest-neighbor algorithm based on a principal axis search tree[J].2001, 23(9): 964-976. doi: 10.1109/34.955110.

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

The Method of Location Privacy Protection Based on Grid Identifier Matching

ZHANG Shaobo①③LIU Qin②WANG Guojun①④

①(School of Information Science and Engineering, Central South University, Changsha 410083, China)②(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 model based on fully-trusted third party is a major model for location privacy protection in location-based services, but the model has some risk of exposing privacy. In this paper, a location privacy protection method based on Grid Identifier Matching (GIM) is proposed. In this method the user first divides the query area into grid and combines the order-preserving symmetric encryption and K-anonymity mechanism. Then, the K-anonymity paradigm is formed in anonymizer. Finally, the query results are returned to users by utilizing GIM. In the query process, the anonymizer dose not have any knowlegdge about a user’s real location, which can enhance the user’s location privacy. Meanwhile, the anonymizer only does simple comparison and matching operations, which relieves effectively is performance bottleneck of the anonymizer. Security analysis shows that the proposed approach can effectively protect the user’s location privacy. Experimental evaluations show that the proposed approach can decrease processing time overhead of the anonymizer.

Location privacy; Grid Identifier Matching (GIM); Order-preserving symmetric encryption; K- anonymity

TP393

A

1009-5896(2016)09-2173-07

10.11999/JEIT160350

2016-04-12；

2016-07-18；

2016-08-09

國家自然科學基金(61472451, 61272151, 61402161)，中南大學中央高?；究蒲袠I(yè)務費專項資金(2016zzts058)

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

王國軍 csgjwang@csu.edu.cn

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

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

王國軍： 男，1970年生，教授，博士生導師，研究方向為系統(tǒng)安全、隱私保護、可信計算和大數(shù)據(jù)安全.