Abstract: Existing privacy preserving proximity testing algorithms usually quantize user’s location according to grid size,which makes these algorithms have low accuracy. Aiming at this problem,this paper proposes two accurate and secure proximity testing algorithms. A user transforms location to two parts,the coordinates inside the grid and the grid index,and sends them both after encryption. Then the server computes all possible grids which satisfy the query according to the encrypted coordinates. The user judges whether the two users are in proximity according to the response from the server. Experimental result shows algorithm 1 runs fast and sends fewer messages,algorithm 2 is more secure,but it needs more computation and communication cost,and both users are required to be online. User can choose the more proper algorithm based on his trust in the server,the query performance,and the scenario.

Key words: location-based service, privacy preserving, security, encryption, proximity testing, location privacy

摘要： 现有保护位置隐私的邻近检测算法通常根据网格大小对用户位置进行量化计算,会降低算法结果的准确性。针对该问题,提出2 种准确安全的邻近检测算法。用户将自己的位置分成网格内坐标以及网格编号两部分,并将其分别加密后发送给服务器,服务器利用加密后的网格内坐标在整个地图中筛选出所有满足查询的网格,用户根据服务器的返回结果判断用户之间是否邻近。实验结果表明,算法1 速度快,传输信息少,算法2 更加安全, 但计算和通信开销较大,并且需查询与被查询用户同时在线。用户可根据对服务器的信任程度、查询性能和应用场景需求进行算法选择。

关键词: 基于位置的服务, 隐私保护, 安全, 加密, 邻近检测, 位置隐私

CLC Number: 

• TP311