Abstract: 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.

Key words: Mobile Social Network (MSN), Location-Based Service (LBS), proximity testing, Private Set Intersection (PSI)

摘要： 针对邻近检测中的用户隐私保护问题，提出了一种可保护隐私的快速邻近检测方法。该方法用网格划分地图。在邻近检测的过程中：首先，用户的邻近区域被转化为其周边网格的集合；然后，利用隐私交集运算（PSI）计算用户邻近区域的交集以达到保护隐私的目的；最后，依据交集是否为空进行邻近判定。分析和实验结果表明，与现有的基于私密相等性检测以及基于坐标变换的方法相比，所提方法解决了邻近检测中隐私保护的公平性问题，能够较好地防范勾结攻击，并且具备较高的计算效率。

关键词: 移动社交网络, 基于地理位置的服务, 邻近检测, 隐私交集运算