張一帆,尹樹祥

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

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

張一帆,尹樹祥

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

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

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

1 概述

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

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

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

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

2 問題描述

2.1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

3 鄰近檢測(cè)算法

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

3.1 異步鄰近檢測(cè)算法

3.1.1 異步鄰近檢測(cè)算法描述

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

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

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

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

服務(wù)器收到用戶A的請(qǐng)求后,找到與用戶A具有相同計(jì)數(shù)器值ctr的用戶B的位置信息,然后計(jì)算所有滿足(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)信息判斷他們的相對(duì)位置,并為每一對(duì)(n,m)值計(jì)算:

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

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

3.1.2 異步鄰近檢測(cè)算法分析

算法分析具體如下:

(1)性能

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

(2)安全性

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

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

3.2 同步鄰近檢測(cè)算法

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

3.2.1 同步鄰近檢測(cè)算法描述

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

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

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

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

3.2.2 同步鄰近檢測(cè)算法分析

算法分析具體如下:

(1)鄰居數(shù)量

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

(2)安全性

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 通信開銷

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

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

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

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

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

4.2 計(jì)算開銷

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

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

圖3 查詢半徑R=100 m時(shí)算法2的計(jì)算開銷

圖4 查詢半徑R=200 m時(shí)算法2的計(jì)算開銷

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

5 結(jié)束語(yǔ)

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

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

[2] 潘 曉,肖 珍,孟小峰.位置隱私研究綜述[J].計(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ù)位置隱私的鄰近檢測(cè)算法[J].計(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