崔炜荣，杜承烈

(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)。

考虑以下一种典型的邻近检测的场景。……