Perturb and optimize users’ location privacy using geo-indistinguishability and location semantics

Yan Yan, Fei Xu, Adnan Mahmood, Zhuoyue Dong, Quan Z. ShengScientific 2022 · DOI

TL;DR

This paper introduces a novel method to protect user location privacy in Location-Based Services (LBS) by combining "geo-indistinguishability" with "location semantics." The approach generates a perturbed location that is both privacy-preserving and semantically optimized, aiming to minimize service quality loss and prevent attackers from inferring sensitive information from location patterns.

What Problem Does This Paper Address?

Location-Based Services (LBS) offer immense convenience by leveraging user location data for services like navigation and information retrieval. However, this reliance on precise location information poses a significant privacy risk. While existing methods like location perturbation can mask a user's exact whereabouts, they often fail to account for the "semantic meaning" of locations (e.g., home, work, hospital). Attackers can exploit this semantic information, even from perturbed locations, to infer sensitive details about a user's life, habits, and health. This paper addresses the challenge of enhancing location privacy by not only perturbing locations but also optimizing these perturbed locations based on their semantic context and temporal relevance, thereby mitigating semantic inference attacks.

Methods

The proposed solution involves a three-stage algorithm:

  1. Perturbation Area Generation (Geo-indistinguishability): This stage uses the planar Laplace mechanism to generate a perturbed location area that satisfies geo-indistinguishability. This means that within a certain radius, an attacker cannot reliably distinguish between the user's real location and the perturbed one. The size of this area is controlled by a privacy parameter ($\epsilon$).
  2. Perturbation Area Optimization (Location Semantics): This stage refines the generated perturbation area by considering location semantics and temporal characteristics. It filters out locations that are too sparse (low user count, reducing anonymity) or too semantically similar to the user's real location. This step aims to reduce the likelihood of attackers inferring privacy from semantic patterns.
  3. Optimal Selection (Linear Programming): The final stage uses linear programming to select the optimal perturbed location from the optimized area. The objective is to minimize the loss of LBS service quality, ensuring that the chosen perturbed location still allows for useful service delivery while maintaining privacy.

Datasets

The experimental evaluation utilized a real-world dataset containing over 573,000 check-in records from Tokyo, Japan, collected between April 12, 2012, and February 16, 2013. This dataset included GPS coordinates, timestamps, and location semantics, allowing for the study of spatio-temporal regularities. The paper also mentions using Google Maps for geo-information and POI data for visualization.

Key Insights and Ideas

  • Semantics Matter: The paper strongly emphasizes that simply perturbing a location isn't enough; the meaning of that location is crucial for privacy. Attackers can exploit semantic correlations to infer information even if the exact coordinates are hidden.
  • Balancing Privacy and Utility: The core challenge is to achieve strong privacy without rendering LBS unusable. The proposed method explicitly optimizes for minimal service quality loss, a critical factor for practical adoption.
  • Temporal Dynamics: Recognizing that location semantics and user activity vary significantly throughout the day and week is key. The method incorporates this temporal aspect to create more robust privacy protections.
  • Geo-indistinguishability as a Foundation: Using geo-indistinguishability as the initial step provides a strong theoretical basis for privacy, ensuring that perturbed locations are inherently difficult to distinguish from real ones within a defined radius.

Key Results

  • Reduced Perturbation Distance: The proposed method achieved approximately a 37% reduction in perturbation distance compared to state-of-the-art methods.
  • Lower Semantic Similarity: The generated perturbed locations exhibited considerably lower semantic similarity with the user's real location, indicating improved resistance to semantic inference attacks.
  • Improved Query Accuracy: The method improved region counting query accuracy by around 40%.
  • Robustness Across Times: The proposed algorithm demonstrated consistent performance across different times of day (3 AM, 12 PM, 6 PM), indicating its temporal robustness.

Limitations and Future Work

  • Continuous Queries: The current method is primarily designed for single LBS requests or can be adapted for discrete queries. Future work could focus on developing continuous policies for privacy budget allocation and perturbation schemes for users with spatiotemporal correlated location needs.
  • Richer Semantic Information: The study utilized a specific set of location semantics. Future research could explore incorporating more diverse semantic information, such as visit durations, travel distances, and relationships between locations, to further enhance privacy.
  • Statistical Errors in Aggregation: While LDP offers strong user-side privacy, it can lead to more statistical errors for aggregators compared to centralized DP. The authors suggest exploring combinations with shuffled models to address this.

Summary updated

Abstract

Location-based services (LBS) are capable of providing location-based information retrieval, traffic navigation, entertainment services, emergency rescues, and several similar services primarily on the premise of the geographic location of users or mobile devices. However, in the process of introducing a new user experience, it is also easy to expose users' specific location which can result in more private information leakage. Hence, the protection of location privacy remains one of the critical issues of the location-based services. Moreover, the areas where humans work and live have different location semantics and sensitivities according to their different social functions. Although the privacy protection of a user's real location can be achieved by the perturbation algorithm, the attackers may employ the semantics information of the perturbed location to infer a user's real location semantics in an attempt to spy on a user's privacy to certain extent. In order to mitigate the above semantics inference attack, and further improve the quality of the location-based services, this paper hereby proposes a user side location perturbation and optimization algorithm based on geo-indistinguishability and location semantics. The perturbation area satisfying geo-indistinguishability is thus generated according to the planar Laplace mechanism and optimized by combining the semantics information and time characteristics of the location. The optimum perturbed location that is able to satisfy the minimum loss of location-based service quality is selected via a linear programming method, and can be employed to replace the real location of the user so as to prevent the leakage of the privacy. Experimental comparison of the actual road network and location semantics dataset manifests that the proposed method reduces approximately 37% perturbation distance in contrast to the other state-of-the-art methods, maintains considerably lower similarity of location semantics, and improves region counting query accuracy by a margin of around 40%.
BibTeX
@inproceedings{yan2022perturb,
  author = {Yan Yan and Fei Xu and Adnan Mahmood and Zhuoyue Dong and Quan Z. Sheng},
  title = {{Perturb and optimize users’ location privacy using geo-indistinguishability and location semantics}},
  booktitle = {Scientific},
  year = {2022},
  doi = {10.1038/s41598-022-24893-0},
}
Figure