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 locationbased 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.

Introduction

IN recent years, location-based service (LBS), a general service for mobile devices [1]–[۴], has been applied to many areas such as social applications, financial services, transportation, tourism, healthcare, automation and so on [5]. With the development of social applications, location-based social networking service (LBSNS) has attracted considerable interest. Meanwhile, as a high level location based function, proximity detection allows users to choose specified geometric range (such as triangles, circles, rectangles) on the map and query which friends of her/his are in the region, as shown in Fig.1. Proximity detection with geometric range query has been one of the most popular features of LBSNS [6]–[۸]. However, the flourish of the LBSNS system still faces severe challenges due to the sensitivity of users’ location information [9]–[۱۵]. Once users’ sensitive information is compromised, it may lead to computer-assisted crime (harassment, car theft, kidnapping, etc.). Therefore, when users use social applications (such as Wechat, Facebook, Twitter and so on) for location query, they cannot obtain other users’ accurate location information, and their sensitive query information cannot be leaked either. Nevertheless, most LBSNSs rely on the fact that users provide accurate location for service providers, and then service providers provide LBSNS for them. Thus, how to provide accurate LBSNS query results without divulging users’ sensitive information to both social application servers and other users has become a hot spot of LBS research. In order to protect the sensitive information of users and solve problems mentioned above, many security techniques have been proposed, such as k − anonymity model [16], [17], spatial cloaking techniques [18]–[۲۰] and traditional homomorphic encryption techniques [21]–[۲۴].