With the pervasiveness of location-aware mobile terminals and the popularity of social applications, location-based social networking service (LBSNS) has brought great convenience to people’s life. Meanwhile, proximity detection, which makes LBSNS more flexible, has aroused widespread concern. However, the prosperity of LBSNS still faces many severe challenges on account of users’ location privacy and data security. In this paper, we propose two efficient and privacy-preserving proximity detection schemes, named AGRQ-P and AGRQ-C, for location-based social applications. With proposed schemes, a user can choose any area on the map, and query whether her/his friends are within the region without divulging the query information to both social application servers and other users, meanwhile, the accurate locations of her/his friends are also confidential for the servers and the query user. Specifically, with algorithms based on ciphertext of geometric range query, users’ query and location information is blurred into chipertext in client, thus no one but the user knows her/his own sensitive information. Detailed security analysis shows that various security threats can be defended. In addition, the proposed schemes are implemented in an IM APP with a real LBS dataset, and extensive simulation results over smart phones further demonstrate that AGRQ-P and AGRQ-C are highly efficient and can be implemented effectively.
Proximity detection with geometric range query
Conceptual architecture of proximity detection.
Orientation of point p and polygon vertexes.
The evaluation demo for AGRQ-P and AGRQ-C
Computation complexity and communication overhead of AGRQ-P
(a) Computation cost of QU vs EPDCP.
(b) Computation cost of UF vs EPDCP.
(c) Communication overhead vs EPDCP.
Computation complexity and communication overhead of AGRQ-C
(a) Computation cost of QU vs CRQP.
(b) Computation cost of UF vs CRQP.
(c) Communication overhead vs CRQP.