用于保護(hù)位置隱私的鄰近檢測算法

張一帆,尹樹祥

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院,上海200433)

用于保護(hù)位置隱私的鄰近檢測算法

張一帆,尹樹祥

(復(fù)旦大學(xué)計算機(jī)科學(xué)技術(shù)學(xué)院,上海200433)

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

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

1 概述

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

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

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

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

2 問題描述

2.1 系統(tǒng)模型

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

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

2.2 設(shè)計目標(biāo)

在理想模型下,算法應(yīng)該滿足以下條件:

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

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

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

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

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

3 鄰近檢測算法

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

3.1 異步鄰近檢測算法

3.1.1 異步鄰近檢測算法描述

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

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

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

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

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

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

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

3.1.2 異步鄰近檢測算法分析

算法分析具體如下:

(1)性能

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

(2)安全性

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

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

3.2 同步鄰近檢測算法

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

3.2.1 同步鄰近檢測算法描述

假設(shè)G是一個p階的循環(huán)群,其中,p是質(zhì)數(shù);g是G的一個生成元。

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

與算法1一樣,用戶B增加計數(shù)器ctr,生成隨機(jī)數(shù),計算并發(fā)送自己加密后網(wǎng)格內(nèi)的坐標(biāo)信息。

用戶A查詢計數(shù)器ctr,同樣加密自己網(wǎng)格內(nèi)的坐標(biāo),并計算作為自己加密后的網(wǎng)格信息:

3.2.2 同步鄰近檢測算法分析

算法分析具體如下:

(1)鄰居數(shù)量

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

(2)安全性

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

本文提出2種新的鄰近檢測算法,將用戶的位置分為網(wǎng)格內(nèi)坐標(biāo)以及網(wǎng)格編號兩部分,通過讓服務(wù)器根據(jù)用戶的網(wǎng)格內(nèi)坐標(biāo),在地圖上篩選出所有滿足查詢的網(wǎng)格,再進(jìn)一步對這些網(wǎng)格進(jìn)行比較,得到準(zhǔn)確的檢測結(jié)果。

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

4 實驗結(jié)果與分析

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

4.1 通信開銷

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

圖1 算法1中服務(wù)器返回列表大小

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

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

圖2 算法2中滿足查詢的網(wǎng)格數(shù)量

4.2 計算開銷

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

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

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

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

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

5 結(jié)束語

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

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

[2] 潘 曉,肖 珍,孟小峰.位置隱私研究綜述[J].計算機(jī)科學(xué)與探索,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

張一帆,尹樹祥.用于保護(hù)位置隱私的鄰近檢測算法[J].計算機(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-),男,碩士研究生,主研方向:云數(shù)據(jù)管理,隱私保護(hù);尹樹祥,碩士研究生。

2014-03-06

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