An Accurate Approach For Private Proximity Testing

Location-aware devices are becoming more popular. People can enjoy vari-ous location-based services (e.g., Google Map, Find My Friends) by sharing their location information. Proximity testing is an important type of such services:a pair of friends will be informed when they are within a threshold of each other.Location-based services usually require user’s location information while users expect to reveal no information. Existing privacy-preserving proximity testing methods usually quantize user’s location according to grid size, which makes these algorithms have low accuracy. Aiming at this problem, we propose a new scheme in this paper which can protect user’s location privacy and get accurate detection results. A user transforms his location to two parts, the coordinates inside the grid and the grid index, and sends them both to the server after encryption. Then the server computes all possible grids which satisfy the query according to the encrypted coordinates. Finally, the user judges whether he and his friend are in proximity according to the response from the server.We propose three algorithms in this paper:the asynchronous proximity test-ing scheme runs fast and sends fewer messages; the synchronous one is more secure, but it needs more computation and communication cost, and both users are re-quired to be online; the vicinity region testing scheme is more flexible, and it allows users to arbitrarily choose query region. We analyze the performance and security of the algorithms. The experiments show the performance of the proposed algorithms with different parameters.