用于保護位置隱私的鄰近檢測算法

張一帆,尹樹祥

(復旦大學計算機科學技術學院,上海200433)

用于保護位置隱私的鄰近檢測算法

張一帆,尹樹祥

(復旦大學計算機科學技術學院,上海200433)

現有保護位置隱私的鄰近檢測算法通常根據網格大小對用戶位置進行量化計算,會降低算法結果的準確性。針對該問題,提出2種準確安全的鄰近檢測算法。用戶將自己的位置分成網格內坐標以及網格編號兩部分,并將其分別加密后發送給服務器,服務器利用加密后的網格內坐標在整個地圖中篩選出所有滿足查詢的網格,用戶根據服務器的返回結果判斷用戶之間是否鄰近。實驗結果表明,算法1速度快,傳輸信息少,算法2更加安全,但計算和通信開銷較大,并且需查詢與被查詢用戶同時在線。用戶可根據對服務器的信任程度、查詢性能和應用場景需求進行算法選擇。

基于位置的服務;隱私保護;安全;加密;鄰近檢測;位置隱私

1 概述

隨著擁有定位功能的移動設備(主要是智能手機)的普及,基于位置的服務已經廣泛應用于交通、物流、醫療、生活等領域中[1]。用戶可以通過共享當前的位置信息來享用各種服務。鄰近檢測是一種典型的服務:當2個朋友間的距離在某個范圍內時,應用會發出通知提醒用戶。

現有基于位置的服務要求用戶共享他們的確切位置,這使得用戶隱私保護問題成為阻礙市場發展的一個重要因素。如果這些服務不能提供一定程度的隱私保護,用戶可能不共享他們的位置,這樣用戶也無法從這些基于位置的服務中獲得便利。然而,保護位置隱私與享受服務之間存在矛盾:位置信息越精確,服務質量越高,隱私度越低[2]。

針對鄰近檢測問題,國內外學者提出了一些方法[3-4],使得朋友之間可以無需將確切位置暴露給服務提供商以及對方的條件下,即可判斷對方是否在自己附近。文獻[5]先運用保持距離不變的映射函數對用戶位置加密,再計算加密后位置間的距離。然而,文獻[6]指出這種保持距離不變的映射函數不安全,攻擊者可以輕易破解映射函數。更多的學者傾向于采用基于網格的方法?；诰W格的方法通常將整個地圖劃分為許多網格,用戶將自己所處的網格編號進行加密,服務器通過比較用戶所在的網格是否相同來判斷他們是否鄰近。文獻[7]將整個地圖劃分成互相重疊的六邊形網格,然后通過比較用戶所處的3個網格中是否有相同的網格來判斷用戶是否鄰近。但是此類方法不夠靈活,用戶只能采用預先設定的距離進行查詢。文獻[8]采用多層次的網格,并提出鄰近區域的概念,使得用戶可以任意指定查找范圍而不僅局限于他們之間的空間距離。但是該方法同樣存在以下問題:多層次的網格使得用戶需要經過多次通信協議才能得到檢測結果,增加算法的整體運行時間。另外,文獻[9]采用剪枝和精煉的方法,但難以保證計算結果的準確性。

為解決上述問題,本文提出2種保護用戶隱私同時能夠得到準確檢測結果的鄰近檢測算法。先將地圖劃分成網格,再將用戶的位置分成網格內的坐標以及網格編號兩部分,這樣使得服務器在不知道用戶確切位置的情況下也能夠準確判斷用戶間是否鄰近。

2 問題描述

2.1 系統模型

本文考慮針對2個不同實體的鄰近檢測服務:擁有可定位和網絡通信的移動設備的用戶可以確定自己的位置并連接到服務器;服務提供商接收用戶發來的請求與位置信息,判斷用戶之間是否鄰近,并進行相應的通知。

問題定義:用戶A與用戶B是朋友;用戶B周期性地將自己的位置加密后發送給服務器;用戶A將查詢請求以及自己的位置信息發送給服務器;服務器根據用戶A與用戶B的位置信息進行計算。當用戶A與用戶B之間的距離小于用戶A設定的閾值R時,用戶A將收到通知。

2.2 設計目標

在理想模型下,算法應該滿足以下條件:

(1)不對稱性:用戶A了解用戶B是否在附近,而用戶B不知道任何信息;

(2)距離閾值:閾值R由每個用戶設定且不統一;

(3)安全性:用戶A只知道用戶B是否在其附近,而用戶B和服務器不知道任何信息;

(4)準確性:判斷結果盡量準確,如果存在誤差,則控制在一定范圍內,并且用戶可以決定該范圍的大小;

(5)性能:由于應用運行在資源有限的移動設備上,需要考慮到算法在計算和通信上的開銷。

3 鄰近檢測算法

在現有基于網格的算法中通常存在一些區域,系統不能準確判斷用戶的鄰近關系,造成這個不確定區域的原因在于,用戶通過網格將自己的位置信息隱藏起來,但與此同時也模糊了自己的位置,使得系統不能準確進行判斷。為此,本文提出2種能夠得到準確檢測結果的異步鄰近檢測算法(算法1)和同步鄰近檢測算法(算法2)。

3.1 異步鄰近檢測算法

3.1.1 異步鄰近檢測算法描述

將地圖劃分成邊長為a的網格,將用戶U在網格內的坐標記為Lx(U),Ly(U),網格在水平方向和垂直方向的坐標記為Gx(U),Gy(U)。

假設用戶A與用戶B是好友,并且共享一個密鑰k。同時,他們各自維護一個初始值為零的計數器ctr。

用戶B增加計數器ctr,并且通過密鑰k和計數器ctr生成隨機數(r1,r2,r3,k1,k2,k3,k4)←F(k,ctr),然后計算:

用戶A向服務器詢問用戶B的計數器數值。如果服務器返回值是用戶A曾經使用的,那么查詢中止。用戶A用密鑰k和計數器ctr生成隨機數,然后用相同方法加密自己的位置信息,并將加密后的信息與距離閾值R′←r1·R一起發送給服務器。

服務器收到用戶A的請求后,找到與用戶A具有相同計數器值ctr的用戶B的位置信息,然后計算所有滿足(L″x(A)-L″x(B)+na)2+(L″y(A)-L″y(B)+ma)2≤R′2的(n,m)值,其中,n,m是整數,服務器得到一系列(n,m)值。這里需要注意的是只有那些在邊界處的(n,m)值才需被記錄。服務器通過用戶的網格坐標信息判斷他們的相對位置,并為每一對(n,m)值計算:

其中,x表示不小于x的最小整數;h(·)是一個保持順序的哈希函數。最后,服務器將{(μx,μy)}列表作為結果發送給用戶A。

用戶A收到服務器的結果后,判斷是否有(μx,μy)滿足。如果有這樣的(μx,μy)存在,那么用戶A認為用戶B與自己鄰近。

3.1.2 異步鄰近檢測算法分析

算法分析具體如下:

(1)性能

在算法1中采用異步的方法,因此在查詢過程中,無需向用戶B詢問其位置信息。同時,通過(n,m)列表對所有滿足條件的網格進行壓縮,減少了算法通信開銷。在整個算法運行過程中,只需要進行簡單的加法、乘法運算以及哈希函數的映射,使得算法能夠快速運行。

(2)安全性

在整個算法運行過程中,用戶B不知道任何信息;服務器知道用戶A與用戶B加密后的位置信息。雖然服務器能夠通過比較的值,并進一步知道用戶A與用戶B的相對位置(比如用戶A在用戶B的西南方)。但是服務器并不能通過這些信息進一步了解用戶所在的區域以及他們的確切位置,因此,算法仍然是安全的。

由于用戶A可能通過移動并利用三角法則來確定用戶B的位置,因此允許用戶B用一個參數來保護確切位置。當用戶B在發送位置信息時,在一個預先設定的范圍內生成一個隨機數d,并發送d′=r1d作為距離參數。當服務器收到用戶A加密了的位置信息和距離閾值后,計算R″=R′+d′,并作為查詢范圍。由于用戶A不知道隨機數d的值,因此不能確定用戶B的確切位置。需要注意的是增加這樣該參數可能會導致檢測結果不準確,但是這個不確定的區域大小僅隨著該參數改變,與網格大小無關。

3.2 同步鄰近檢測算法

在算法1中,用戶將他們的相對位置暴露給服務器。如果假定服務器在得知用戶A的加密網格坐標后,可以計算與A相鄰的網格坐標的加密信息,那么可以使服務器計算所有滿足查詢的網格坐標的密文,然后運用安全相等測試[10-13],讓用戶A來判斷用戶B是否落在這些網格內。這樣服務器就不能知道任何信息(包括用戶的相對位置),但計算開銷會有所增加。

3.2.1 同步鄰近檢測算法描述

假設G是一個p階的循環群,其中,p是質數;g是G的一個生成元。

用戶A在Zp中選擇一個隨機數x,并計算h←gx,這樣可以生成私鑰{x},公鑰{g,h}。

與算法1一樣,用戶B增加計數器ctr,生成隨機數,計算并發送自己加密后網格內的坐標信息。

用戶A查詢計數器ctr,同樣加密自己網格內的坐標,并計算作為自己加密后的網格信息:

3.2.2 同步鄰近檢測算法分析

算法分析具體如下:

(1)鄰居數量

在該算法中,服務器不再知道用戶A與用戶B的相對位置。但是,由于服務器和客戶端都需要計算和傳輸所有滿足查詢的網格加密后的信息,計算開銷與通信開銷都有所增加。這些額外開銷取決于鄰居數量,因此,一個合適的網格大小非常重要。

(2)安全性

盡管在該算法中,服務器不知道任何信息,但是客戶端知道鄰居數量。為防止這個可能的安全隱患,服務器可以在計算用戶A的鄰居加密信息時增加一些虛假信息。如果給定一個距離閾值,那么鄰居的最大數量N可以確定。因此,如果服務器每次都傳輸N個網格信息給用戶B,其中包括一些虛假的信息,那么用戶B就不知道鄰居的真正數量。

本文提出2種新的鄰近檢測算法,將用戶的位置分為網格內坐標以及網格編號兩部分,通過讓服務器根據用戶的網格內坐標,在地圖上篩選出所有滿足查詢的網格,再進一步對這些網格進行比較,得到準確的檢測結果。

本文提出的2種算法:算法1運行速度快,傳輸信息少,但是會將用戶的相對位置暴露給服務器;算法2更加安全,但是計算和通信開銷有所增加,并且要求用戶同時在線才能進行查詢。對于用戶如何選擇使用哪種算法,取決于用戶對于服務器的信賴程度,以及對算法性能與功能上的需求。

4 實驗結果與分析

由于該算法部分運行在移動終端上,計算開銷與網絡通信開銷顯得異常重要。為測試算法性能,對于不同的參數設置,分別對計算開銷和網絡通信開銷進行實驗。實驗中地圖大小是50 000×50 000, 1個單位代表1m。用戶位置由算法隨機生成。實驗運行在四核1.70 GHz處理器、4 GB內存,運行64位Windows7操作系統的計算機上。算法2采用PBC(Pairing-Based Cryptography)庫來實現加密算法,其中,p是160位的質數;g是512位的整數。實驗結果均為100次計算后的平均值。

4.1 通信開銷

在算法1中,通信開銷主要在于服務器返回的(μx,μy)列表。對于不同的網格大小以及查詢半徑,服務器返回的列表大小如圖1所示。隨著查詢半徑的增加,服務器返回列表的大小也隨之增加。原因在于增大查詢半徑會使得更多的網格處于查詢范圍內,即滿足條件的(n,m)值增加,返回列表也由此更大。同時可以看到,網格大小也對返回列表有影響。這是由于網格越大,在查詢范圍中的網格數量會相應減小。

圖1 算法1中服務器返回列表大小

網格大小同樣會影響安全性。如果網格太大,會使得用戶處于少量網格中,那么用戶A就有可能通過返回列表的數量來推測用戶B的位置。

在算法2中,通信開銷取決于滿足條件的網格數量,通過在不同參數情況下測試這些網格數量,得到結果如圖2所示?？梢钥闯?由于在通信中需要列舉出所有滿足查詢的網格,而不是像算法1中只需要列舉出那些處于邊界處的網格,因此算法2的通信開銷遠遠大于算法1;同時,網格大小越小、查詢半徑越大時,網格的數量會有指數級的增長。

圖2 算法2中滿足查詢的網格數量

4.2 計算開銷

由于算法1僅需要一些加法和乘法運算以及哈希函數的映射,運行時間較少,因此在此只討論算法2。在實驗中,通過改變各查詢半徑以及網格大小,對算法2的計算開銷進行評估。

圖3和圖4分別是查詢半徑R=100 m與R= 200 m時,在不同網格大小下服務器、用戶A以及用戶B各自的計算開銷。

圖3 查詢半徑R=100 m時算法2的計算開銷

圖4 查詢半徑R=200 m時算法2的計算開銷

可以看出,網格越小,查詢半徑越大,那么滿足條件的網格就越多,計算開銷也越大。另外,用戶A的計算開銷大于服務器和用戶B,這是因為用戶A需要對每個服務器返回的候選網格進行運算并判斷用戶B是否與自己鄰近。

5 結束語

本文提出2種準確安全的鄰近檢測算法。將地圖事先劃分成網格后,通過將用戶的位置分成網格內的坐標以及網格編號兩部分,分別對兩部分信息進行加密,使得用戶在不將自己位置暴露給其他用戶和服務器的情況下,準確判斷其他用戶是否在自己附近。通過實驗比較2種算法在不同網格大小以及查詢半徑下的通信以及計算開銷,結果表明,2種算法均能保護用戶隱私,同時得到準確的檢測結果。今后將從鄰近區域的角度出發,進一步研究在非歐式距離以及指定查詢區域情況下的鄰近檢測問題。

[1] 唐科萍,許方恒,沈才棵.基于位置服務的研究綜述[J].計算機應用研究,2012,29(12):4432-4436.

[2] 潘 曉,肖 珍,孟小峰.位置隱私研究綜述[J].計算機科學與探索,2007,1(3):268-281.

[3] Nielsen J D,Pagter J I,StausholmM B.Location PrivacyViaActivelySecurePrivateProximity Testing[C]//Proceedings of 2012 IEEE International ConferenceonPervasiveComputingandCommunications Workshops.Lugano,Italy:IEEE Press, 2012:19-23.

[4] Narayanan A,Thiagarajan N,Lakhani M,et al.Location Privacy via Private Proximity Testing[C]//Proceedings of NDSS’11.[S.l.]:IEEE Press,2011.

[5] Ruppel P,Treu G,Küpper A,et al.Anonymous User Tracking for Location-based Community Services[C]// Proceedings of the 2nd International Conference on LocationandContext-awareness.Berlin,Germany: Springer-Verlag,2006:116-133.

[6] Liu K,Giannella C,Kargupta H.An Attacker’s View of Distance Preserving Maps for Privacy Preserving Data Mining[C]//Proceedingsofthe10thEuropean Conference on Principle and Practice of Knowledge Discovery inDatabases.Berlin,Germany:Springer-Verlag,2006:297-308.

[7] Siksnys L,Thomsen J R,Saltenis S,et al.Private and Flexible Proximity Detection in Mobile Social Networks[C]//Proceedings of the11th International Conference on Mobile Data Management.Washington D.C., USA:IEEE Computer Society,2010:23-26.

[8] Mascetti S,Bettini C,Freni D,et al.Privacy-aware Proximity Based Services[C]//Proceedings of the10th International Conference on Mobile Data Management: Systems,Services and Middleware.Washington D.C., USA:IEEE Computer Society,2009:31-40.

[9] Saldamli G,Chow R,Jin H,et al.Private Proximity Testing With an Untrusted Server[C]//Proceedings of the 6th ACM Conference on Security and Privacy in Wireless and Mobile Networks.New York,USA:ACM Press,2013:113-118.

[10] Montreuil A,PatarinJ.TheMarriageProposals Problem:Fair and Efficient Solution for Two-party Computations[C]//Proceedings of the 5th International Conference on Cryptology in India.Berlin,Germany: Springer-Verlag,2004:33-47.

[11] Fagin R,Naor M,Winkler P.Comparing Information Without Leaking It[J].Communications of the ACM, 1996,39(5):77-85.

[12] Lipmaa H.Verifiable Homomorphic Oblivious Transfer andPrivateEqualityTest[C]//Proceedingsof ASIACRYPT’03.Berlin,Germany:Springer-Verlag, 2003:416-433.

[13] Naor M,Pinkas B.Oblivious Transfer and Polynomial Evaluation[C]//Proceedings of the 31st Annual ACM Symposium on Theory of Computing.New York,USA: ACM Press,1999:245-254.

編輯 陸燕菲

Proximity Testing Algorithms for Preserving Location Privacy

ZHANG Yifan,YIN Shuxiang
(School of Computer Science,Fudan University,Shanghai 200433,China)

Existing privacy preserving proximity testing algorithms usually quantize user’s location according to grid size,which makes these algorithms have low accuracy.Aiming at this problem,this paper proposes two accurate and secure proximity testing algorithms.A user transforms location to two parts,the coordinates inside the grid and the grid index,and sends them both after encryption.Then the server computes all possible grids which satisfy the query according to the encrypted coordinates.The user judges whether the two users are in proximity according to the response from the server.Experimental result shows algorithm1runs fast and sends fewer messages,algorithm 2 is more secure,but it needs more computation and communication cost,and both users are required to be online.User can choose the more proper algorithm based on his trust in the server,the query performance,and the scenario.

location-based service;privacy preserving;security;encryption;proximity testing;location privacy

張一帆,尹樹祥.用于保護位置隱私的鄰近檢測算法[J].計算機工程,2015,41(2):52-56.

英文引用格式:Zhang Yifan,Yin Shuxiang.Proximity Testing Algorithms for Preserving Location Privacy[J].Computer Engineering,2015,41(2):52-56.

1000-3428(2015)02-0052-05

:A

:TP311

10.3969/j.issn.1000-3428.2015.02.011

張一帆(1989-),男,碩士研究生,主研方向:云數據管理,隱私保護;尹樹祥,碩士研究生。

2014-03-06

:2014-04-08E-mail:zhangyifan31@hotmail.com