移动社交网络中可保护隐私的快速邻近检测方法

崔炜荣，杜承烈

(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