Service-Splitting-Based Privacy Protection Mechanism for Proximity Detection Supporting High Utility

Proximity detection is one of the most popular location-based applications in social networks when users intend to find their nearby friends. However, the existing proximity detection has access to precise and real-time location information of users, raising serious privacy concerns for millions of users. A number of privacy-preserving models have taken shape over the past decade, but they almost universally rely on syntactic privacy models such as $k$ -anonymity and location perturbation, which are proved to waver in the balance of privacy and availability requirements. To solve this problem, we introduce a novel location privacy-preserving mechanism for proximity detection to support user-defined range queries while guaranteeing a certain level of privacy. It divides the proximity detection service into two independent subservices and ensures that each subservice provider can only access part of the user’s location information, which is encoded by Geohash and divided into two parts (i.e., prefix and suffix). By adjusting the length of location encoding, we can make a good trade-off between accuracy and system overhead. The privacy requirements of users are not implicated in the quality of service, and it achieves the balance of privacy and utility. The analysis results through an extensive simulation indicate that our scheme successfully ensures that neither each server in the system nor an external attacker can obtain the real location of the user. Moreover, it demonstrates the effectiveness of the proposed scheme.