基于位置服務中單向哈希法隱私保護研究

劉林武+張弛

摘 要：基于位置的服務（LBS）正在被越來越多的移動用戶使用，用戶的身份信息和位置信息也將暴露給服務提供商，從而可能導致用戶的隱私被侵犯。提出了單向哈希方法，避免將用戶的個人信息直接暴露給服務提供商；使用一種匿名方法，由匿名器將用戶的真實位置信息和故意添加的虛假位置信息一齊發(fā)送給服務提供商，從而使服務提供商無法得知用戶的真實位置，保護了用戶的位置隱私。

關鍵詞：隱私保護；LBS；哈希函數(shù)

中圖分類號：TP391.4 文獻標志碼：A

Research on the Method of Privacy Preserving

in location-based Service by One-way Hash

LIU Lin-wu，ZHANG Chi

（College of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，Nanjing，Jiangsu 211106，China）

Abstract：Location based services （LBS） are being used by more and more mobile users，and the users identity and location information will also be exposed to the service provider，which may lead to user privacy violations.The one-way hash method is used to avoid the users identity information being directly exposed to the service provider；With an anonymous method，the anonymizer sends the users real location information and the deliberately-added false location information together to the service provider，so that service provider cannot know the true position and the users location privacy is protected.

Key words：privacy preserving；LBS；hash function

0 引 言

隨著移動互聯(lián)網(wǎng)的快速發(fā)展，越來越多基于位置的服務開始出現(xiàn)，極大地方便了人們的生產(chǎn)生活。比如，基于位置服務的車輛調度管理系統(tǒng)[1]。又如，可以應用百度地圖搜索附近的銀行、飯店、醫(yī)院；使用滴滴打車軟件，可以搜索并召喚附近的出租車。用戶首先通過GPS[2]等定位手段獲得自己的精確位置信息，然后把位置信息發(fā)送給服務提供商，服務提供商根據(jù)用戶的位置提供相應的服務。但是，一旦用戶將位置信息提交給服務提供商后，他將不能刪除或修改該位置信息，如果服務提供商是不可信任的，或者數(shù)據(jù)庫遭到非法入侵，用戶的隱私也將暴露。設想這樣的一個情形，用戶A需要搜索附近的治療乙肝的醫(yī)院，出于某種原因，他不愿意別人知道自己得了乙肝。如果僅僅保護用戶A的姓名不泄露，卻對他的位置信息不保密，那么攻擊者也有可能獲得用戶A的身份。假如A使用假ID在自己郊外的家中搜索附近的肝病醫(yī)院，攻擊者獲得A的位置信息后，在電子地圖上（例如百度地圖或者谷歌地圖）搜索該位置信息，就可以定位到A的住宅，再通過其它手段，就可以獲得A的身份信息。因此，為了在使用基于位置的服務時能保護用戶的隱私，需要隱藏用戶的位置信息，但服務提供商為了提供服務，又必須知道用戶的位置信息。所以，需要尋找一種既然使用服務又能保護用戶位置隱私的方法。

另外，某些LBS需要用戶提供大量的個人背景信息，如姓名，郵箱號，家庭地址，電話號碼等[3]。實際上，用戶并不想這些個人信息被服務提供商收集。因此，為了保護隱私，用戶希望防止自己的個人信息和用戶請求對應起來[4]。

密碼學方法也可以用來保護用戶的隱私[5]。當對用戶請求使用同態(tài)加密后，服務提供商無法從用戶請求中獲取任何有用的知識。但高昂的計算成本和通信開銷使得這種方法不太實用。

私人信息檢索法（private information retrieval）[6-7]可以使用戶向數(shù)據(jù)庫提交請求時不必泄露真實請求，這種方法可以很好地保護用戶的隱私。但是該方法需要較高的計算開銷，對服務器的計算能力有較高的要求。

1 基于位置的服務的匿名訪問

1.1 基于位置的服務

為了使用基于位置的服務（LBS），用戶需要首先使用GPS等手段對自己進行定位，然后將位置信息發(fā)送給服務提供商。服務提供商根據(jù)該位置信息返回相應的結果。假如在地圖上有某個用戶和多家醫(yī)院如圖1所示。圖中黑色圓點表示用戶，十字形標志表示醫(yī)院。

假設用戶需要搜索離自己最近的醫(yī)院，如圖2所示，該過程分為四步：

第一步：將自己的位置信息（通過GPS獲得）和請求“離自己最近的醫(yī)院”發(fā)送到服務提供商。

第二步：服務提供商在將該位置信息和請求提交到后臺數(shù)據(jù)庫。

第三步：后臺數(shù)據(jù)庫經(jīng)過比對用戶位置和以前存儲的醫(yī)院位置信息，找到離用戶最近的醫(yī)院4，并將醫(yī)院4的信息提交給服務提供商。

服務提供商在收集到用戶的位置信息后，可以推測出下列信息：

1.用戶在特定時間段內經(jīng)常出現(xiàn)在什么地方。endprint

2.用戶的行為模式，也即用戶在特定時間段內的移動路線和頻率。

3.用戶經(jīng)常去某些地方的頻次，比如商場，夜總會，醫(yī)院。

而這些信息事關用戶的隱私，一般是用戶不愿意泄露的。因此，用戶在使用LBS的時候希望將自己的位置信息隱藏。

1.2 K級空間匿名方法

為了保護用戶的個人位置信息，需要為用戶提供空間匿名度。與上文中用戶將自己的位置信息直接發(fā)送給服務提供商不同的是，K級空間匿名方法將用戶的真實位置信息La和其它k-1個虛假的位置信息混合在一起，得到一組位置信息L={l1，l2，...lk-1，la}，一齊發(fā)送給服務提供商。這樣，服務提供商無法知道哪個位置才是真正的用戶位置，猜測出用戶的位置信息的概率為1/k。K值越大，猜中的概率就越低。服務提供商在得到這k個位置信息后，在數(shù)據(jù)庫搜索，得到k個結果R={r1，r2，...rk-1，ra}。然后將這K個結果返回給用戶。用戶在這K個結果中很容易找到于位置la對應的結果ra。然而，隨著K的值增大，服務器的搜索時間也將增加，用戶得到返回結果的等待時間也將延長，因此，需要根據(jù)用戶所需的匿名程度和等待時間選擇恰當?shù)腒值。但由用戶直接產(chǎn)生虛假位置，將增加用戶設備的負擔，降低用戶體驗，而且，如果一個用戶產(chǎn)生大量的虛假位置發(fā)送給服務提供商，服務提供商會懷疑自己受到了攻擊從而拒絕服務[8]。

2 單向哈希函數(shù)與匿名器

2.1 單向哈希函數(shù)

單向哈希函數(shù)，也稱做“消息摘要”，是一種廣泛應用的加密方法，相當于對要發(fā)送的消息添加了“指紋”。一般地，在非安全信道上傳輸信息時，為了檢測在傳輸過程中信息是否被篡改，可以用哈希函數(shù)來確認信息的完整性[9]。本文將單向哈希函數(shù)用于用戶訪問服務時的認證過程。借助哈希函數(shù)，得到用戶個人信息（或稱之為用戶憑證）的“消息摘要”（也即指紋）。通過該指紋，可以精準地唯一地確定用戶身份。假設C為用戶張三的一個屬性集，C中包含四條信息：{姓名，用戶ID，郵箱號，年齡}。那么可知張三的屬性集C為C={張三，1688，zhangsan@test.com，31}。使用單向哈希函數(shù)H，對C中的屬性進行哈希運算，可得一個消息摘要，也即張三的電子指紋fa。fa為一個固定長度的比特串，可用作張三的身份憑證，但無法通過fa逆向計算出C的內容，從而保護了張三的個人信息。

2.2 匿名器

為了讓用戶在使用基于位置的服務時用戶隱私能保護，需要一個匿名器。該匿名器的作用相當于一個居于用戶和服務提供商之間的可信任第三方。用戶在匿名器上進行認證，而不是在服務提供商上進行認證。認證通過后，匿名器將來自用戶的位置信息和服務請求進行處理并轉發(fā)給服務提供商，使得服務提供商無法得知用戶的隱私信息。

3 匿名訪問LBS的框架

隨著用戶的隱私保護意識越來越強，有時候用戶并不信任服務提供商，他們在使用LBS時并不想透露個人信息。但是，為了使用某些服務，必須對用戶進行認證，合法的用戶才可以使用服務，這就意味著用戶必須提供出個人信息以及身份憑證。為了解決這個問題，提出了一個匿名訪問框架。該框架由用戶、匿名器、服務提供商組成。如圖3所示：

圖3 匿名訪問LBS框架

假設在用戶發(fā)送服務請求之前，匿名器和服務提供商之間已經(jīng)建立了可信任連接（比如可信任的SSH連接）。該框架的工作流程如下：

1.用戶向匿名器發(fā)送一個數(shù)據(jù)包，如圖4所示，該數(shù)據(jù)包里有用戶的ID號，指紋fa，服務請求request，服務ID等。

2.匿名器根據(jù)服務ID號確定服務提供商，然后向服務提供商請求所有注冊了該服務的用戶的ID號，假設所有用戶ID的起始范圍為[M，N]，顯然，張三的ID號在[M，N]范圍內。

3.服務提供商返回所有用戶ID。

4.匿名器在[M，N]中隨機選擇k個ID號，當然，張三的ID號必須被選中。但服務提供商不知道哪個ID是張三的，也就不知道誰在請求服務。然后，匿名器請求服務提供商提供這K個ID號對應的指紋。

5.服務提供商向匿名器返回指紋集F。匿名器在收到F后，將fa與F中的元素逐一比對。假設f5和fa相等，那么說明張三的指紋之前已經(jīng)存儲在服務提供商的數(shù)據(jù)庫中，說明張三是合法用戶，認證通過。如果fa與F中的所有元素都不相同，說明張三的指紋沒有存儲在服務提供商的數(shù)據(jù)庫中，也即張三是非法用戶，認證沒能通過。

6.匿名器向用戶和服務器發(fā)送認證結果。

也就是說，匿名器作為可信任的第三方，在本框架中替代服務提供商，基于用戶的指紋對用戶的身份憑證進行認證，可以避免泄露用戶的個人信息的細節(jié)。

當認證通過后，用戶可開始使用LBS。與前文不同的是，這里由匿名器代替用戶的移動設備來產(chǎn)生虛假位置信息，這樣可以降低用戶端移動設備的軟硬件要求，減輕用戶端移動設備負擔，使用戶端移動設備運行流暢，改善用戶體驗。而且，由于服務提供商對匿名器是完全信任的，即使匿名器發(fā)送大量服務請求，也不會識以為受到了攻擊而拒絕服務。如圖5所示，步驟如下：

1.服務請求者向匿名器發(fā)送服務請求包，請求包里包括（用戶ID，位置信息la，服務ID，其它信息）

2.匿名器尋找請求者附近的離請求者最近的其它k-1個用戶，將這k-1個用戶的位置作為干擾項，得到匿名化后的位置信息L={l1，l2，...lk-1，la}。

3.匿名器將服務請求包中的用戶ID用“anonymous ID”代替，這樣服務請求包變?yōu)椋╝nonymous ID，L，服務ID，其它信息）。這樣，服務提供商只知道是匿名器在請求服務，而不知道是哪個用戶在請求服務，也不知道到底有多少用戶在請求服務。由于服務提供商是信任匿名器的，因此它會響應匿名器發(fā)送的服務請求。endprint

4.匿名器將服務請求包發(fā)送到服務提供商。服務提供商根據(jù)這k個位置數(shù)據(jù)l1，l2，...lk-1，la進行搜索計算，返回結果R={r1，r2，...rk-1，ra}，匿名器根據(jù)請求者的真實位置信息，過濾掉干擾項，將結果ra返回給用戶。

在用戶訪問服務的過程中，服務提供商都無法得知用戶的真實位置，從而保護了用戶的隱私。

4 結束語

本文提出的方法借助單向哈希函數(shù)和匿名器，在認證過程中保護了用戶的隱私，防止用戶個人信息被泄露。同時，在使用服務的過程，采用K級空間匿名法，對用戶的位置進行模糊化處理，防止用戶位置信息被泄露。這樣，在整個過程中，用戶都保持了很好的匿名性。將來，需要考慮如何使虛假位置的移動軌跡接近于用戶真實位置的移動軌跡，防止攻擊者利用軌跡追蹤確認用戶身份，而且要考慮如何量化評價位置信息的匿名度。

參考文獻

[1] 胡卉卉，宋丹.基于位置的服務在車聯(lián)網(wǎng)系統(tǒng)中的應用[J].計算技術與自動化，2013，32（4）：92-95.

[2] GETTING I.The global positioning system[J].In IEEE Spectrum，1993，30（12）：36-47.

[3] KOTZANIKOLAOU P，MAGKOS E，PETRAKOS N，et al.Fair Anonymous Authentication for Location Based Services[M]// Data Privacy Management and Autonomous Spontaneous Security.Springer Berlin Heidelberg，2013：1-14.

[4] NONJUR M，AHAMED S I，HASAN C S.ELALPS： A Framework to Eliminate Location Anonymizer from Location Privacy Systems[C]// IEEE International Computer Software and Applications Conference，COMPSAC 2009，Seattle，Washington，Usa，20-24 July.DBLP，2009：11-20.

[5] GAHI Y，GUENNOUN M，GUENNOUN Z，et al.Privacy Preserving Scheme for Location-Based Services[J].Journal of Information Security，2012，03（2）：105-112.

[6] OLUMOFIN F，TYSOWSKI P K，GOLDBERG I，et al.Achieving Efficient Query Privacy for Location Based Services[C]// Privacy Enhancing Technologies，International Symposium，PETS 2010，Berlin，Germany，July 21-23，2010.Proceedings.DBLP，2010：93-110.

[7] KHOSHGOZARAN A，SHAHABI C.Private Information Retrieval Techniques for Enabling Location Privacy in Location-Based Services[M]// Privacy in Location-Based Applications.Springer-Verlag，2009：59.

[8] CHOW C Y.A peer-to-peer spatial cloaking algorithm for anonymous location-based service[C]// ACM International Symposium on Geographic Information Systems，Acm-Gis 2006，November 10-11，2006，Arlington，Virginia，Usa，Proceedings.DBLP，2006：171-178.

[9] RAGAB A H M，ISMAIL N A，ALLAH O S F.An efficient message digest algorithm （MD） for data security[C]// IEEE Region 10 International Conference on Electrical and Electronic Technology.IEEE Xplore，2001，1：191-197.endprint