Regionalized location obfuscation mechanism with personalized privacy levels

Shun Zhang, Benfei Duan, Zhili Chen, Hong ZhongarXiv 2021 · DOI · OpenReview

TL;DR

This paper introduces DPIVE, a novel location obfuscation technique that enhances user privacy in location-based services by regionalizing privacy protection. It addresses limitations in prior methods by offering personalized privacy levels and improving data utility, especially for users in less dense or "skewed" locations.

What Problem Does This Paper Address?

Location-based services (LBS) are increasingly popular, but they raise significant privacy concerns as user location data is continuously collected. Existing privacy-preserving methods often struggle to balance strong privacy guarantees with acceptable data utility, particularly for users in less common locations. Specifically, the PIVE framework, while attempting to combine geo-indistinguishability and expected inference error, suffers from theoretical issues related to overlapping privacy regions and inconsistent sensitivity, leading to compromised privacy. This paper aims to correct these issues by proposing a regionalized approach that allows for personalized privacy settings and ensures more robust protection.

Methods

The core of the proposed solution, DPIVE, operates in two phases:

  • Phase I: Regionalization and Partitioning (DPIVE's Algorithm F): Instead of adaptive, potentially overlapping regions, DPIVE partitions the entire discrete location space into disjoint Protection Location Sets (PLSs). This is achieved using a novel QK-means clustering algorithm, which is an adaptation of the k-means algorithm designed for 2D space. QK-means aims to create compact PLSs with small average diameters, satisfying privacy requirements (specifically, a user-defined lower bound on expected inference error, $E_m$). This approach ensures that locations within the same PLS share the same sensitivity, addressing a key flaw in PIVE.
  • Phase II: Differential Privacy Mechanism (DPIVE's Mechanism K): Once the disjoint PLSs are determined, an exponential mechanism is employed to generate pseudo-locations. This mechanism uses the diameter of each PLS as its sensitivity, ensuring differential privacy within each PLS. The paper also introduces PDPIVE, an extension that allows users to personalize their privacy budget ($\epsilon$) for each location, further enhancing fine-grained control.

Datasets

The proposed methods were evaluated using two real-world datasets:

  • GeoLife: This dataset represents a relatively dense distribution of locations.
  • Gowalla: This dataset features a sparser distribution of locations.

The paper also mentions using a grid size of 1km x 1km for processing these datasets.

Key Insights and Ideas

  • Regionalization as Personalization: The paper argues that personalization in location privacy is best achieved through regionalization, where different areas can have tailored privacy settings.
  • Disjoint PLSs are Crucial: Overlapping or adaptive PLSs, as seen in PIVE, create theoretical vulnerabilities. DPIVE's approach of creating disjoint PLSs is key to its improved privacy guarantees.
  • QK-means for Efficient Partitioning: The QK-means algorithm offers a more effective way to partition 2D location data into PLSs compared to methods like Hilbert curves, leading to smaller average PLS diameters and better utility.
  • Personalized Privacy Budgets: Allowing users to set individual privacy budgets for different locations (PDPIVE) significantly improves data utility without compromising privacy requirements.
  • Robustness for Skewed Locations: DPIVE demonstrates superior performance in protecting users in isolated or less dense areas, which are often challenging for other privacy mechanisms.

Key Results

  • Improved Privacy and Utility: DPIVE achieves a better balance between privacy protection and data utility compared to previous methods like EM, Joint, and Opt-Geo.
  • Reduced Quality Loss: The QK-means partitioning method in DPIVE reduces quality loss by up to 21.8% and 35.5% on GeoLife and Gowalla datasets, respectively, compared to Hilbert curve-based methods.
  • Enhanced Protection for Isolated Regions: DPIVE significantly reduces the attack success probability in isolated regions, with attack success rates below 20% compared to much higher rates for other schemes.
  • Personalization Benefits: PDPIVE reduces quality loss by 4.1%-4.9% on GeoLife and 9.1%-11.8% on Gowalla compared to baseline DPIVE schemes.
  • Application Performance: In spatial crowdsourcing scenarios, DPIVE shows improved availability (lower WTD) compared to Joint, while still providing strong privacy guarantees.

Limitations and Future Work

  • Computational Complexity: The paper notes that for large-scale domain scenarios, higher computational complexity and communication requirements may arise.
  • Future Work: The authors suggest exploring differential location privacy problems in large-scale domain scenarios, which will involve addressing higher computational complexity and various communication environment requirements.

Summary updated

Abstract

The popularity of cyber-physical systems is fueling the rapid growth of location-based services. This poses the risk of location privacy disclosure. Effective privacy preservation is foremost for various mobile applications. Recently, geo-indistinguishability and expected inference error are proposed for limiting location leakages. In this paper, we argue that personalization means regionalization for geo-indistinguishability, and we propose a regionalized location obfuscation mechanism called DPIVE with personalized utility sensitivities. This substantially corrects the differential and distortion privacy problem of PIVE framework proposed by Yu et al. on NDSS 2017. We develop DPIVE with two phases. In Phase I, we determine disjoint sets by partitioning all possible positions such that different locations in the same set share the Protection Location Set (PLS). In Phase II, we construct a probability distribution matrix in which the rows corresponding to the same PLS have their own sensitivity of utility (PLS diameter). Moreover, by designing QK-means algorithm for more search space in 2-D space, we improve DPIVE with refined location partition and present fine-grained personalization, enabling each location to have its own privacy level endowed with a customized privacy budget. Experiments with two public datasets demonstrate that our mechanisms have the superior performance, typically on skewed locations.
BibTeX
@misc{zhang2021regionalized,
  author = {Shun Zhang and Benfei Duan and Zhili Chen and Hong Zhong},
  title = {{Regionalized location obfuscation mechanism with personalized privacy levels}},
  year = {2021},
  eprint = {2102.00654},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2102.00654},
}
Figure