崔煒榮，杜承烈

(1.西北工業(yè)大學(xué) 計算機學(xué)院，西安 710072； 2.安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000)

移動社交網(wǎng)絡(luò)中可保護隱私的快速鄰近檢測方法

崔煒榮1,2*，杜承烈1

(1.西北工業(yè)大學(xué) 計算機學(xué)院，西安 710072； 2.安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000)

(*通信作者電子郵箱sealrong@163.com)

針對鄰近檢測中的用戶隱私保護問題，提出了一種可保護隱私的快速鄰近檢測方法。該方法用網(wǎng)格劃分地圖。在鄰近檢測的過程中：首先，用戶的鄰近區(qū)域被轉(zhuǎn)化為其周邊網(wǎng)格的集合；然后，利用隱私交集運算(PSI)計算用戶鄰近區(qū)域的交集以達到保護隱私的目的;最后，依據(jù)交集是否為空進行鄰近判定。分析和實驗結(jié)果表明，與現(xiàn)有的基于私密相等性檢測以及基于坐標(biāo)變換的方法相比，所提方法解決了鄰近檢測中隱私保護的公平性問題，能夠較好地防范勾結(jié)攻擊，并且具備較高的計算效率。

移動社交網(wǎng)絡(luò)；基于地理位置的服務(wù)；鄰近檢測；隱私交集運算

0 引言

隨著智能手機的普及和移動社交網(wǎng)絡(luò)(Mobile Social Network, MSN)的興起，基于地理位置的服務(wù)(Location Based Service, LBS)已經(jīng)成為人們生活中不可或缺的部分。LBS不僅為人們的生活帶來了巨大的便利，也為人與人之間的交互創(chuàng)造了新的時空聯(lián)系。LBS一般分為兩種類型:一種可以幫助用戶找到其鄰近區(qū)域內(nèi)感興趣的場所(Point of Interest, POI)，比如商店或酒店等;另一種可以使得用戶能夠感知其鄰近區(qū)域內(nèi)的滿足一定條件的其他用戶。本文關(guān)注的問題主要針對第二種類型，即鄰近檢測(Proximity Testing, PT)。

考慮以下一種典型的鄰近檢測的場景。用戶A和用戶B為好友，他們互相設(shè)置了關(guān)注，希望當(dāng)他們彼此鄰近時能夠感知對方的存在和方位。為了實現(xiàn)以上功能，最直接的方式是使得A和B通過服務(wù)器共享彼此的地理位置信息，并通過計算他們之間的距離來判斷是否鄰近。然而，這種簡單的解決方法沒有考慮用戶隱私保護問題。對于使用LBS的用戶，將自己的精確地理位置信息暴露給服務(wù)提供商或其他用戶會面臨較大的隱私泄露風(fēng)險，甚至可能對用戶的財產(chǎn)和人身安全造成威脅[1]。

針對如上所述的隱私安全風(fēng)險，為了可以讓用戶在不暴露地理位置信息的條件下實現(xiàn)鄰近檢測，一些可保護隱私的PT(Private PT, PPT)方法已經(jīng)被提出[2-6]。總體而言，這些方法所遵循的思路是相似的。首選將地圖劃分成某種類型的網(wǎng)格，將用戶的位置表示為其地理坐標(biāo)所落入的網(wǎng)格單元。用戶的鄰近區(qū)域由圍繞在其周圍的一定形狀范圍內(nèi)的網(wǎng)格單元組成。其次，將鄰近檢測轉(zhuǎn)化為子集查詢問題，即檢測用戶B所在的網(wǎng)格單元是否落入到用戶A的鄰近區(qū)域內(nèi)。參與比較的網(wǎng)格單元都被進行了某種形式的加密，從而能夠在一定程度上保護用戶的隱私。

現(xiàn)有的可保護隱私的鄰近檢測方法的局限性在于：1)為了實現(xiàn)隱私保護，用戶之間需要提前共享密鑰。然而，在用戶和用戶之間，用戶和服務(wù)器之間有可能勾結(jié)的假設(shè)下，這種方式無法有效地保護隱私信息。2)大部分的方案都是非對稱的，即只有查詢的發(fā)起方能夠獲知鄰近檢測的結(jié)果。從實用性角度上看，這是不公平的。為了實現(xiàn)公平，當(dāng)A感知到B在鄰近區(qū)域的同時，B也應(yīng)該能夠感知到A在其鄰近區(qū)域。3)當(dāng)用戶處于移動狀態(tài)時，用戶的鄰近區(qū)域往往隨著用戶的位置變化要重新計算，這會引起較高的計算開銷。

針對以上不足，本文提出了一種基于隱私交集運算(Private Set Intersection, PSI)的可保護隱私的鄰近檢測方法。與有的方法相似的是，該方法也將用戶的位置及用戶的鄰近區(qū)域表示為網(wǎng)格；與已有的方法不同的是，該方法將用戶的鄰近區(qū)域表示為以用戶所在網(wǎng)格單元為中心的九宮格，同時將鄰近檢測問題規(guī)約為隱私交集運算問題。通過采用文獻[8]所設(shè)計的基于同態(tài)加密的快速安全交集計算方法，本文方法可以實現(xiàn)高效準(zhǔn)確的鄰近檢測。

1 相關(guān)工作

隨著LBS的普及，如何保護個人地理位置隱私逐漸成為研究的熱點。目前，大多數(shù)此類文獻主要研究當(dāng)用戶向服務(wù)器提交POI查詢時如何保護查詢者的位置隱私。其所使用方法可以分為3類：假名(pseudonym)[2-3]、空間模糊(spatial cloaking)[4-6]和加密[7-8]。然而，上述的方法并不能直接應(yīng)用于鄰近檢測場景中。目前，有關(guān)實現(xiàn)可保護用戶隱私的鄰近檢測的文獻相對較少，現(xiàn)有的方法[9-14]總體思路是類似的，即通過判斷被查詢的用戶的位置是否落入查詢者的鄰近范圍內(nèi)來進行鄰近檢測，其主要區(qū)別在于鄰近區(qū)域的表示方法以及信息隱藏的方式。在文獻[9]所提出的方案中，地圖被劃分成多級別的正方形網(wǎng)格，不同的級別代表不同的網(wǎng)格粒度。用戶的鄰近區(qū)域由用戶指定的包含其所在網(wǎng)格單元的任意形狀區(qū)域所覆蓋的網(wǎng)格單元的集合表示。將B用戶所在的網(wǎng)格單元是否被包含在A用戶的指定區(qū)域內(nèi)作為鄰近檢測的判據(jù)。該方法基于客戶機/服務(wù)器(Client/Server, C/S)架構(gòu)，為了保護用戶位置隱私，其假設(shè)用戶之間共享密鑰，表示用戶位置及鄰近區(qū)域的網(wǎng)格均被進行安全哈希變換后上傳至服務(wù)器，由服務(wù)器進行比較運算。該方法的局限在于無法抵御服務(wù)器和用戶的勾結(jié)，且只適用于用戶靜態(tài)情形下的檢測。

文獻[10]將鄰近檢測歸約可保護隱私的相等測試(Private Equality Testing, PET)計算。這種方法的計算由參與比較的用戶完成，第三方服務(wù)器只起到消息傳送的作用。為了判斷用戶B是否與A鄰近，需要利用PET運算判斷B的位置網(wǎng)格單元是否與A的網(wǎng)格單元相等。這種方法雖然能夠防范服務(wù)器和用戶的勾結(jié)，但其檢測精度較低。此外，當(dāng)用戶的鄰近區(qū)域包含多個網(wǎng)格時，基于PET的檢測方法會使得檢測雙方面臨較大的計算開銷。

文獻[11]提出利用安全多方計算(Secure Multiparty Computation, SMC)來實現(xiàn)鄰近檢測。這種方法改進了文獻[3]所提出的方案，將地圖劃分為正方形網(wǎng)格。用以用戶為中心的一定半徑的圓所覆蓋的網(wǎng)格單元近似用戶的鄰近區(qū)域。若用戶B所在的網(wǎng)格單元落入A的鄰近區(qū)域，則判定B與A鄰近。但這種方法需要用戶之間共享密鑰，所以無法防范勾結(jié)攻擊，也不能適用于用戶動態(tài)變化的場景。

與以上方法不同，文獻[12]提出了一種新的鄰近區(qū)域的表示方法。該方法允許用戶將鄰近區(qū)域指定為任意凸多邊形。如果B的位置落入A的鄰近區(qū)域且A的位置也在B的鄰近區(qū)域則判定A與B相鄰。這種方法是一種對稱的鄰近檢測，但其依然需要用戶之間事先共享秘密。相對于網(wǎng)格表示法，該方法雖然能夠提供更加靈活的鄰近區(qū)域表示和較為準(zhǔn)確的判斷結(jié)果，但其鄰近檢測的計算過程相對復(fù)雜，擴展性較低。

2 同態(tài)加密與隱私交集運算

本文所提出的方法基于文獻[15]所提出的隱私交集運算算法。該算法利用同態(tài)加密的性質(zhì)可實現(xiàn)如下功能：假如A有集合Sa，B有集合Sb，經(jīng)過隱私交集運算，B無法得知任何有關(guān)Sa的信息，而A除了知道Sa∩Sb外也不能得知Sb中的其他成員信息。為了便于理解，本章將簡單介紹所使用的同態(tài)加密和隱私交集運算原理。

2.1 同態(tài)加密

E(m1,r1)·E(m2,r2)=E(m1+m2,r1r2) modn2

E(m1,r1)m2=E(m1m2,r1m2) modn2

Pailliers Cryptosystem是一種概率加密體系，隨機數(shù)r1和r2只被用來對加密內(nèi)容進行隨機化處理，其本身并不會影響加密和解密的結(jié)果。所以，為了方便描述，在下文中用E(m)代表E(m,r)。以上的同態(tài)性質(zhì)可以簡化為：

E(m1)·E(m2)=E(m1+m2)

E(m1)m2=E(m1m2)

2.2 隱私交集運算

文獻[15]提出了一種基于PailliersCryptosystem的高效隱私交集運算協(xié)議。在該協(xié)議中，客戶端首先根據(jù)自己的集合X定義一個多項式P(y)：

其中，xk為客戶端集合X所包含的元素。也就是說，X中的每一個元素都是P(y)的一個根。之后，客戶端利用Pailliers Cryptosystem的加密算法對P的每個系數(shù)au進行加密，并將密文傳送給服務(wù)器端。當(dāng)服務(wù)器端收到密文后，基于同態(tài)加密的性質(zhì)，服務(wù)器可將自己集合Y中的元素代入到多項式P中，即計算E(r(P(yi)+yi)。其中：yi為Y中的元素，r為隨機數(shù)。隨后，服務(wù)器端將計算的結(jié)果返回給客戶端，客戶端進行解密操作。顯然，若解密的結(jié)果在客戶端集合中，則其對應(yīng)的yi被包含在集合X∩Y中。該協(xié)議的詳細(xì)過程將在第4章中進行描述。

3 系統(tǒng)模型及問題定義

3.1 系統(tǒng)模型及安全性假設(shè)

本文所針對的系統(tǒng)模型由用戶A、用戶B及服務(wù)器S組成。其中：A的角色為檢測的發(fā)起者，B的角色為響應(yīng)者，S為消息的傳遞者。鄰近檢測采用分布式的方式，即由A和B之間的交互完成。服務(wù)器不參與計算，只負(fù)責(zé)傳遞A和B之間的消息。

本文假設(shè)：1)模型中的角色都是誠實并好奇的(HonestButCurious,HBC)。也就是說，用戶A和用戶B都嚴(yán)格遵循協(xié)議的規(guī)則，同時也試圖通過收到的信息獲取盡可能多的對方隱私信息。2)存在被動攻擊者。即攻擊者能夠監(jiān)聽A與B之間所有的消息往來，并試圖通過這些消息獲取A和B的地理位置信息。但攻擊者不會進行諸如篡改，注入等主動攻擊。3)A和B的地理位置信息及鄰近區(qū)域信息都是真實可信的。

3.2 問題定義

令A(yù)的位置為loca，其鄰近區(qū)域為Ra；B的位置為locb，其鄰近區(qū)域為Rb。本文采用的鄰近檢測的判據(jù)為：locb∈Ra且loca∈Rb。具體而言，A將檢測B是否處于自己的鄰近區(qū)域內(nèi)。如果B處于A的鄰近區(qū)域，則A一定處于B的鄰近區(qū)域，此時檢測通過，A和B將獲得鄰近提醒并獲取彼此的位置。為了在此過程中保護用戶隱私，需要滿足以下需求：

1)只有滿足鄰近檢測的判據(jù)，A和B才能獲知對方的位置信息；否則，A和B無法通過鄰近檢測獲知彼此的位置信息。

2) 滿足對稱性需求，即如果locb∈Ra且loca∈Rb，則A和B將同時獲得鄰近提醒。

3) 無論是服務(wù)器還是攻擊者，都無法從A和B之間傳遞的消息中獲取有關(guān)A和B的位置信息。

4 鄰近檢測協(xié)議設(shè)計

4.1 基本思路

位置及鄰近區(qū)域表示：令D為鄰近檢測的區(qū)域，將D劃分為正方形網(wǎng)格系統(tǒng)，每個網(wǎng)格單元的邊長為k。每個網(wǎng)格單元具有唯一的標(biāo)識c∈N。將用戶的地理位置locu由其所落入的網(wǎng)格單元的標(biāo)識表示，用戶u的鄰近區(qū)域Ru由以其所落入的網(wǎng)格單元為中心的九宮格表示。如圖1所示，則Ru={cu,1,cu,2,…,cu,9},locu=cu,5。

圖1 位置及鄰近區(qū)域表示

鄰近判據(jù)：令用戶A的位置為loca，其鄰近區(qū)域為Ra，用戶B的位置為locb，其鄰近區(qū)域為Rb，則本方法判斷A與B互相鄰近的判據(jù)為locb∈Ra且loca∈Rb。 圖2描述了滿足鄰近判據(jù)的三種情況。第一種情況(圖2(b))，B的位置與A的鄰近區(qū)域的角格重合，即locb=ca,1， 或locb=ca,3，或locb=ca,7或locb=ca,9。第二種情況(圖2(c))，B的位置與A的鄰近區(qū)域的邊中格重合，即locb=ca,2，或locb=ca,4，或locb=ca,6，或locb=ca,8。第三種情況(圖2(d))，B的位置與A的位置重合，即locb=loca。以上每種情況，當(dāng)B落入A的鄰近區(qū)域時，A也位于B的鄰近區(qū)域，所以滿足鄰近判據(jù)。

圖2 鄰近判斷

4.2 協(xié)議設(shè)計

本節(jié)描述所設(shè)計的鄰近檢測協(xié)議的詳細(xì)步驟，流程示見圖3,詳細(xì)的算法步驟如下。

圖3 協(xié)議流程

輸入 檢測區(qū)域D，loca，Ra，locb，Rb；

輸出 判斷A和B是否相互鄰近以及彼此的相對位置。

步驟1 A按序進行以下計算。

1)A生成Paillier密鑰對PUa和PRa。PUa為用作加密的公鑰，PRa為用作解密的私鑰。

2)A根據(jù)Ra定義多項式Pa(y)，該多項式的根為Ra中的元素，即：

3)A使用同態(tài)加密算法以PUa為密鑰加密Pa(y)的10個系數(shù)，生成加密系數(shù)向量：

Pa=[EPUa(a0),EPUa(a1),…,EPUa(a9)]。

隨后A 將PUa及Pa經(jīng)服務(wù)器S發(fā)送給B。

步驟2 B收到PUa及Pa后，按序進行如下計算。

1)B生成Paillier密鑰對PUb和PRb。

2)B根據(jù)Rb定義多項式Pb(y)，該多項式的根為Rb中的元素，即：

3)B使用同態(tài)加密算法以PUb為密鑰加密Pb(y)的10個系數(shù)，生成加密系數(shù)向量:

Pb=[EPUb(b0),EPUb(b1),…,EPUb(b9)]

4)B利用同態(tài)性質(zhì)將自己的位置網(wǎng)格單元ID即locb代入EPUa(Pa(y))進行計算。具體而言，B計算：

隨后，B生成隨機數(shù)rb，利用同態(tài)性質(zhì)計算EPUa(rbPa(locb)+locb)，并將其連同PUb、Pb一起發(fā)送給服務(wù)器。

步驟3 服務(wù)器收到B回復(fù)的信息后，將EPUa(rbPa(locb)+locb)緩存，將PUb、Pb發(fā)送給A。

步驟4 A收到Pb及PUb后按序完成如下操作。

1)A利用同態(tài)性質(zhì)將自己的位置網(wǎng)格單元ID即loca代入EPUb(Pb(y))進行計算。具體而言，A計算：

隨后，A生成隨機數(shù)ra，利用同態(tài)性質(zhì)計算EPUb(raPb(loca)+loca)，并將其發(fā)送給服務(wù)器S。

步驟5 服務(wù)器收到EPUb(raPb(loca)+loca)后，檢查緩存，若EPUa(rbPa(locb)+locb)存在，則將其發(fā)送給A，并將EPUb(raPb(loca)+loca)發(fā)送給B。

步驟6 A和B收到服務(wù)器返回的信息后，各自進行如下計算：

正確性 以用戶A為例，若locb∈Ra，則locb為Pa(y)的根，即Pa(locb)=0,rbPa(locb)+locb=locb，由此，DPRa(EPUa(rbPa(locb)+locb))∈Ra；否則DPRa(EPUa(rbPa

(locb)+locb))?Ra且為隨機數(shù)。在這里，rb主要起到對加密內(nèi)容隨機化的作用，以防范暴力破解。

5 安全性分析

本章針對4.2節(jié)所提出的隱私保護需求，分析所提出的鄰近檢測方法的安全性。需要注意的是，本文方法的安全性保障建立在PallierCryptosystem是語義安全的假設(shè)基礎(chǔ)上[11 ]。

5.1 對用戶位置隱私的保護

首先，由于假設(shè)PallierCryptosystem是語義安全的，B無法利用所收到的來自A的加密多項式系數(shù)向量Pa恢復(fù)Pa(y)，從而得知A的鄰近區(qū)域信息。同理，A 也無法利用Pb推測出B的鄰近區(qū)域信息。其次，當(dāng)A收到B傳回的EPUa(rbPa(locb)+locb)時，只有當(dāng)locb∈Ra時，A能夠通過解密得知locb的值。否則，解密結(jié)果對于A來說只是無意義的隨機數(shù)。同理，當(dāng)B收到A傳來的EPUb(raPb(loca)+loca)，只有l(wèi)oca∈Rb時，B才可以得知loca的值，否則解密結(jié)果對B來說也是無意義的隨機數(shù)。通過以上分析可知，對于本文的鄰近檢測算法，只有當(dāng)A和B的位置滿足鄰近判據(jù)時，他們才能得知彼此的位置，否則他們無法獲得有關(guān)對方位置的任何信息。此外，由于PallierCryptosystem是概率加密體系，因此無論是服務(wù)器還是竊聽者，都無法從得到的A與B之間的加密信息獲取有關(guān)密鑰和明文的任何信息，從而可以保證通信的安全性。最后，由于用戶的精確位置被替換為其所落入的網(wǎng)格單元，實現(xiàn)了用戶位置信息的模糊化，在某種程度上也保護了用戶位置隱私。

零多項式攻擊：值得注意的是，假設(shè)用戶A不再是誠實可信的，A可以定義一個零多項式Pe，即Pe的所有系數(shù)均為零。在這種情況下，由于每一個cb,i均為Pe的根，基于此事實，A可以在即便是和B沒有相互鄰近的情況下獲知locb。為了防范這種攻擊，本文采用文獻[19]所提出的方法，即設(shè)多項式最高次項的系數(shù)為1，且該系數(shù)由對方加密生成。舉例而言，A只需要將[EPUa(a0),EPUa(a0),…,EPUa(a8)]傳給B， B已知a9=1，則B可以利用A的公鑰計算EPUa(1)，之后再進行多項式估值。同理，B也依照此方法處理加密系數(shù)。

5.2 公平性保障

現(xiàn)有的可保護隱私的鄰近檢測方法一般都忽視了用戶之間的公平性，即只有協(xié)議的發(fā)起者可以獲知鄰近檢測的結(jié)果，而協(xié)議的響應(yīng)者無法得知?；诂F(xiàn)實考慮，這種不對稱的檢測方法只保護了協(xié)議發(fā)起者的隱私，并未保護響應(yīng)者的隱私。因此，合理的方法應(yīng)充分考慮用戶的公平性，即滿足A在發(fā)現(xiàn)B鄰近并獲知B的位置的同時，B也應(yīng)該發(fā)現(xiàn)A并獲知A的位置。在本文所設(shè)計的方法中，鄰近檢測是雙向的。A和B要各自進行相同的檢測計算，其獲得的結(jié)論也是一致的。此外，第三方服務(wù)器不僅是信息的傳遞者，也起到了協(xié)調(diào)和同步的作用。由協(xié)議的步驟3和步驟5可知，只有當(dāng)EPUa(rbPa(locb)+locb)和EPUb(raPb(loca)+loca)都提交給服務(wù)器后，服務(wù)器才進行轉(zhuǎn)發(fā)。也就是說，若A能感知到B位于其鄰近區(qū)域以及大致的位置，則B也能同時感知到A位于其鄰近區(qū)域及大致的位置。以上分析說明，本文的方法可以保證用戶之間的公平性。

5.3 防范勾結(jié)攻擊

在本文中，勾結(jié)指協(xié)議的響應(yīng)者向服務(wù)器透漏部分或全部信息，從而暴露協(xié)議發(fā)起者的隱私。為了便于討論和比較，本文討論兩種情景下的勾結(jié)攻擊。情景1：A和B尚未鄰近。情景2：A和B相互鄰近。若使用文獻[9-11]中設(shè)計的方案，由于A和B之間預(yù)先共享密鑰。B可以將該密鑰透漏給服務(wù)器，從而使得服務(wù)器獲得A的位置和鄰近區(qū)域。這樣，無論是在情景1還是情景2，A的位置隱私都有可能暴露給服務(wù)器。采用本文的方案，在情景1中，A和B之間的鄰近檢測并沒有使得B獲知A的位置信息，同時也因為所有的信息均由A的私鑰加密，所以服務(wù)器無法通過B獲知A的位置隱私。在情景2時，B能夠獲知A的位置，因此仍然可以向服務(wù)器告知A的位置信息。值得注意的是，為了實現(xiàn)公平性，在情景2下的勾結(jié)攻擊是無法避免的。

6 性能評估

為了評估協(xié)議的執(zhí)行效率，本文構(gòu)建了協(xié)議原型并進行了一系列仿真測試。仿真測試所用的計算機配置為IntelCOREi5 2.30GHz處理器、2GBRAM、Ubuntu14.04OS及Python3.4.3。協(xié)議所使用的PSI計算基于Python的PHE1.2.2庫實現(xiàn)。首先，本文測試了協(xié)議中所使用的關(guān)鍵技術(shù)(多項式生成及PSI計算)的執(zhí)行效率；之后，分別在靜止和移動兩種場景下測試了協(xié)議執(zhí)行的整體效率并和現(xiàn)有方法進行了對比。

6.1 多項式生成效率

在本協(xié)議中，多項式的系數(shù)由基于插值的算法生成。為了評估該算法的效率，本文測試了多項式系數(shù)生成的時間開銷隨著集合元素增加的變化情況，測試結(jié)果如圖4所示。測試結(jié)果表明，多項式生成的時間開銷隨集合的元素的增加成線性增長。本協(xié)議中，用戶鄰近區(qū)域集合中的元素個數(shù)固定為9，生成所需9次多項式的時間約為0.06ms。

圖4 多項式生成效率

6.2PSI計算效率

作為協(xié)議的核心算法，PSI的執(zhí)行效率決定了協(xié)議是否高效可行。為此，本文測試了在不同的安全參數(shù)(密鑰長度)配置下，本文所使用的PSI的計算時間隨著用戶集合大小增加的變化情況。

測試結(jié)果如圖5所示。測試結(jié)果說明：1)PSI的執(zhí)行時間隨著用戶集合中元素數(shù)量的增加線性增長。2)同態(tài)加密的密鑰長度對PSI的執(zhí)行效率影響較大。密鑰長度越大，其安全性越強，同時效率越低。權(quán)衡安全性和效率，本文的協(xié)議原型使用的密鑰長度為256b,其單向PSI的時間花費約為1.74ms。

圖5 PSI計算效率

6.3 協(xié)議執(zhí)行效率

為了評估本協(xié)議的執(zhí)行效率，本文分別在靜止和移動的場景下進行了相關(guān)測試。首先，測試了靜止場景下(A和B位置固定)，在相同輸入條件下，使用本文方法及現(xiàn)有的其他典型方法實現(xiàn)對稱鄰近檢測所花費的時間。這些方法包括私密相等性測試(PrivateEqualityTest,PET)[9]、快速私密相等性測試(FastPET,FPET)[10]以及坐標(biāo)轉(zhuǎn)換比較(ShiftAndCompare,SAC)[11]。測試結(jié)果如圖6所示.

圖6 靜止場景下協(xié)議計算效率

為了測試移動場景下本協(xié)議的執(zhí)行效率，本文利用了TomasBrinkoff路網(wǎng)數(shù)據(jù)生成器[20]所生成的數(shù)據(jù)集。利用該生成器，生成了200組在Olderburg市區(qū)(面積為23.57km×26.92km)交通路網(wǎng)內(nèi)的用戶軌跡。每組包含兩個由起始遠(yuǎn)離到最終相鄰的隨機用戶軌跡，每個用戶的移動速度設(shè)置為60km/h，軌跡采樣時間戳間隔設(shè)置為1min，網(wǎng)格單元大小設(shè)置為1km×1km。對于每組軌跡，分別利用本文提出的方法和PET、FPET、SAC進行動態(tài)鄰近檢測。具體而言，假設(shè)A和B位于同一組，則從用戶A的軌跡起始時刻，每到達一個時間戳，A都向B發(fā)送請求進行鄰近檢測，直至檢測到鄰近為止。記錄了相關(guān)的時間開銷，實驗結(jié)果如圖7所示。其中，平均運行時間指的是給定的方法對于每個輸入軌跡組進行動態(tài)檢測的平均時間開銷。通過圖6～7所示的實驗結(jié)果表明，與PET、FPET、SAC相比，本文方法具有更高的執(zhí)行效率。

圖7 移動場景下協(xié)議計算效率

7 結(jié)語

針對移動社交網(wǎng)絡(luò)中進行鄰近檢測時的位置隱私保護問題，本文提出了一種基于PSI的鄰近檢測方法。該方法可以使得用戶在不暴露個人位置信息的情況下快速感知附近的朋友。與PET、FPET、SAC相比，本文方法充分考慮了隱私保護的公平性，因此更加貼合實際場景中的用戶隱私保護需求。此外，對協(xié)議的仿真測試表明，所提方法在保證隱私安全性的同時也具備較高的執(zhí)行效率，具有較強的實用性。今后，將針對如何提高本文所提出方法的鄰近檢測精確度和效率展開進一步研究。

)

[1]LIMY,ZHUHJ,GAOZY,etal.Allyourlocationarebelongtous:breakingmobilesocialnetworksforautomateduserlocationtracking[C]//Proceedingsofthe15thACMInternationalSymposiumonMobileAdHocNetworkingandComputing.NewYork:ACM, 2014: 43-52.

[2]BERESFORDAR,STAJANOF.Locationprivacyinpervasivecomputing[J].IEEEPervasiveComputing, 2003, 2(1): 46-55.

[3]MYLESG,FRIDAYA,DAVIESN.Preservingprivacyinenvironmentswithlocation-basedapplications[J].IEEEPervasiveComputing, 2003, 2(1): 56-64.

[4]GEDIKB,LIUL.Protectinglocationprivacywithpersonalizedk-anonymity: architecture and algorithms [J]. IEEE Transactions on Mobile Computing, 2008, 7(1): 1-18.

[5] GRUTESTER M, GRUNWALD D. Anonymous usage of location-based services through spatial and temporal cloaking [C]// MobiSys’03: Proceedings of the 1st International Conference on Mobile Systems, Applications and Services. New York: ACM, 2003: 31-42.

[6] XU J L, TANG X Y, HU H B, et al. Privacy-conscious location-based queries in mobile environments [J]. IEEE Transactions on Parallel and Distributed Systems, 2010, 21(3): 313-326.

[7] HU H B, XU J L, CHEN Q, et al. Authenticating location-based services without compromising location privacy [C]// SIGMOD’12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 301-312.

[8] YIU M L, JENSEN C S, HUANG X G, et al. SpaceTwist: managing the trade-offs among location privacy, query performance, and query accuracy in mobile services [C]// ICDE’08: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2008: 366-375.

[10] NARAYANAN A, THIAGRARAJAN N, LAKHANI M, et al. Location privacy via private proximity testing [EB/OL]. [2016- 09- 20]. https://www.shiftleft.org/papers/locpriv/locpriv.pdf.

[11] NIELSEN J D, PAGTER J I, STAUSHOLM M B. Location privacy via actively secure private proximity testing [C]// Proceedings of the 2012 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops). Piscataway, NJ: IEEE, 2012: 381-386.

[12] LIN X, HU H B, LI H P, et al. Private proximity detection and monitoring with vicinity regions [C]// MobiDE’13: Proceedings of the 12th International ACM Workshop on Data Engineering for Wireless and Mobile Access. New York : ACM, 2013: 5-12.

[13] SALDAMLI G, CHOW R, JIN H X, et al. Private proximity testing with an untrusted server [C]// WiSec’13: Proceedings of the Sixth ACM Conference on Security and Privacy in Wireless and Mobile Networks. New York: ACM, 2013: 113-118.

[14] JING T, LIN P, LU Y F, et al. FPODG: a flexible and private proximity testing based on ′one degree′ grid [J]. International Journal of Sensor Networks, 2016, 20(3): 199-207.

[15] FREEDMAN M J, NISSIM K, PINKAS B. Efficient private matching and set intersection [C]// Proceedings of the 2004 International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 3027. Berlin: Springer, 2004: 1-19.

[16] OKAMOTO T, UCHIYAMA S. A new public-key cryptosystem as secure as factoring [C]// Proceedings of the 1998 International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 1403. Berlin: Springer, 1998: 308-318.

[17] NACCACHE D, STERN J. A new public key cryptosystem based on higher residues [C]// CCS’98: Proceedings of the 5th ACM Conference on Computer and Communications Security. New York: ACM, 1998: 59-66.

[18] PAILLIER P. Public-key cryptosystems based on composite degree residuosity classes [C]// EUROCRYPT’99: Proceedings of the 1999 17th International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1999: 223-238.

[19] LI R H, WU C K. An unconditionally secure protocol for multi-party set intersection [C]// ACNS’07: Proceedings of the 5th International Conference on Applied Cryptography and Network Security. Berlin: Springer, 2007: 226-236.

[20] BRINKHOFF T. A framework for generating network-based moving objects [J]. GeoInformatica, 2002, 6(2): 153-180.

CUI Weirong, born in 1983, Ph. D. candidate, lecturer. His research interests include network security, privacy preserving.

DU Chenglie, born in 1970, Ph. D., professor. His research interests include network information security, real-time distributed computing, mobile and embedded computing.

Fast proximity testing method with privacy preserving in mobile social network

CUI Weirong1,2*, DU Chenglie1

(1.SchoolofComputerScienceandEngineering,NorthwesternPolytechnicalUniversity,Xi’anShaanxi710072,China; 2.CollegeofElectronicandInformationEngineering,AnkangUniversity,AnkangShaanxi725000,China)

Concerning the problem of protecting user’s location privacy in proximity testing, a new method of achieving fast proximity testing with privacy preserving was proposed. The map was divided with the grid by the proposed method. In the process of proximity testing, firstly, the vicinity region of the user was transformed into a collection of the surrounding grids. Then, the intersection of the users’ vicinity regions was calculated by using the Private Set Intersection (PSI) for privacy preserving. Finally, the proximity determination was made based on whether the intersection was empty. The results of analysis and experiment show that, compared with the existing methods based on private equality testing and the method based on coordinate transformation, the proposed method can solve the fairness issue of privacy preserving in proximity testing, resist the collusion attack between the server and the user, and has a higher computational efficiency.

Mobile Social Network (MSN); Location-Based Service (LBS); proximity testing; Private Set Intersection (PSI)

2016- 11- 14;

2016- 12- 21。

崔煒榮(1983—)，男，陜西漢中人，講師，博士研究生，主要研究方向：網(wǎng)絡(luò)安全，隱私保護； 杜承烈(1970—)，男，陜西西安人，教授，博士，CCF高級會員，主要研究方向：網(wǎng)絡(luò)信息安全、實時分布式計算、移動與嵌入式計算。

1001- 9081(2017)06- 1657- 06

10.11772/j.issn.1001- 9081.2017.06.1657

TP393.08

A