移動社交網絡中可保護隱私的快速鄰近檢測方法

崔煒榮，杜承烈

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

移動社交網絡中可保護隱私的快速鄰近檢測方法

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

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

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

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

移動社交網絡；基于地理位置的服務；鄰近檢測；隱私交集運算

0 引言

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

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

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

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

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

1 相關工作

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

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

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

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

2 同態加密與隱私交集運算

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

2.1 同態加密

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

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

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

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

E(m1)m2=E(m1m2)

2.2 隱私交集運算

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

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

3 系統模型及問題定義

3.1 系統模型及安全性假設

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

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

3.2 問題定義

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

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

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

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

4 鄰近檢測協議設計

4.1 基本思路

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

圖1 位置及鄰近區域表示

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

圖2 鄰近判斷

4.2 協議設計

本節描述所設計的鄰近檢測協議的詳細步驟，流程示見圖3,詳細的算法步驟如下。

圖3 協議流程

輸入 檢測區域D，loca，Ra，locb，Rb；

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

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

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

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

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

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

隨后A 將PUa及Pa經服務器S發送給B。

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

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

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

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

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

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

隨后，B生成隨機數rb，利用同態性質計算EPUa(rbPa(locb)+locb)，并將其連同PUb、Pb一起發送給服務器。

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

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

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

隨后，A生成隨機數ra，利用同態性質計算EPUb(raPb(loca)+loca)，并將其發送給服務器S。

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

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

正確性 以用戶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且為隨機數。在這里，rb主要起到對加密內容隨機化的作用，以防范暴力破解。

5 安全性分析

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

5.1 對用戶位置隱私的保護

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

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

5.2 公平性保障

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

5.3 防范勾結攻擊

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

6 性能評估

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

6.1 多項式生成效率

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

圖4 多項式生成效率

6.2PSI計算效率

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

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

圖5 PSI計算效率

6.3 協議執行效率

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

圖6 靜止場景下協議計算效率

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

圖7 移動場景下協議計算效率

7 結語

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

)

[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—)，男，陜西漢中人，講師，博士研究生，主要研究方向：網絡安全，隱私保護； 杜承烈(1970—)，男，陜西西安人，教授，博士，CCF高級會員，主要研究方向：網絡信息安全、實時分布式計算、移動與嵌入式計算。

1001- 9081(2017)06- 1657- 06

10.11772/j.issn.1001- 9081.2017.06.1657

TP393.08

A