Achieve Efficient and Privacy-Preserving Proximity Detection Scheme for Social Applications

This paper proposes an efficient scheme, named CPSS, to perform privacy-preserving proximity detection based on chiphertext of convex polygon spatial search. We consider a scenario where users have to submit their location and search information to the social application server for accessing proximity detection service of location-based social applications (LBSAs). With proximity detection, users can choose any polygon area on the map and search whether their friends are within the select region. Since the location and search information of users are sensitive, submitting these data over plaintext to the social application server raises privacy concerns. Hence, we propose a novel method, with which users can access proximity detection without divulging their search and location information. Specifically, the data of a user is blurred into chipertext in client, thus no one can obtain the sensitive information except the user herself/himself. We prove that the scheme can defend various security threats and validate our scheme using a real LBS dataset. Also, we show that our proposed CPSS is highly efficient in terms of computation complexity and communication overhead.