Protecting Locations with Differential Privacy under Temporal Correlations

Abstract

Concerns on location privacy frequently arise with the rapid development of GPS enabled devices and location-based applications. While spatial transformation techniques such as location perturbation or generalization have been studied extensively, most techniques rely on syntactic privacy models without rigorous privacy guarantee. Many of them only consider static scenarios or perturb the location at single timestamps without considering temporal correlations of a moving user's locations, and hence are vulnerable to various inference attacks. While differential privacy has been accepted as a standard for privacy protection, applying differential privacy in location based applications presents new challenges, as the protection needs to be enforced on the fly for a single user and needs to incorporate temporal correlations between a user's locations. In this paper, we propose a systematic solution to preserve location privacy with rigorous privacy guarantee. First, we propose a new definition, "$\delta$-location set" based differential privacy, to account for the temporal correlations in location data. Second, we show that the well known ${\ell }_1$-norm sensitivity fails to capture the geometric sensitivity in multidimensional space and propose a new notion, sensitivity hull, based on which the error of differential privacy is bounded. Third, to obtain the optimal utility we present a planar isotropic mechanism (PIM) for location perturbation, which is the first mechanism achieving the lower bound of differential privacy. Experiments on real-world datasets also demonstrate that PIM significantly outperforms baseline approaches in data utility.

Final version Nov-04-2015

References in corpus (2)

• Understanding individual human mobility patterns
• Blowfish Privacy: Tuning Privacy-Utility Trade-offs using Policies

Cited by in corpus (32)

• The Long Road to Computational Location Privacy: A Survey
• Quantifying Differential Privacy under Temporal Correlations
• Quantifying Differential Privacy in Continuous Data Release under Temporal Correlations
• LDPTrace: Locally Differentially Private Trajectory Synthesis
• Comparative Study of Differentially Private Data Synthesis Methods
• PriSTE: From Location Privacy to Spatiotemporal Event Privacy
• Protecting Spatiotemporal Event Privacy in Continuous Location-Based Services
• Impact of Prior Knowledge and Data Correlation on Privacy Leakage: A Unified Analysis
• Differential Privacy Techniques for Cyber Physical Systems: A Survey
• Privacy-preserving Travel Time Prediction with Uncertainty Using GPS Trace Data
• Privacy-Preserving Synthetic Location Data in the Real World
• Differentially Private Publication of Location Entropy
• On (The Lack Of) Location Privacy in Crowdsourcing Applications
• DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy
• ON-OFF Privacy Against Correlation Over Time
• Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms
• Composition Properties of Bayesian Differential Privacy
• PGLP: Customizable and Rigorous Location Privacy through Policy Graph
• Correlated Data in Differential Privacy: Definition and Analysis
• Geo-Graph-Indistinguishability: Location Privacy on Road Networks Based on Differential Privacy
• Is Geo-Indistinguishability What You Are Looking for?
• PANDA: Policy-aware Location Privacy for Epidemic Surveillance
• CONNA: Addressing Name Disambiguation on The Fly
• Detecting Anomalous LAN Activities under Differential Privacy
• Location Trace Privacy Under Conditional Priors
• Adaptive Statistical Learning with Bayesian Differential Privacy
• Utility-efficient Differentially Private K-means Clustering based on Cluster Merging
• Location histogram privacy by sensitive location hiding and target histogram avoidance/resemblance (extended version)
• Protecting Geolocation Privacy of Photo Collections
• Designing a Location Trace Anonymization Contest
• Protect Edge Privacy in Path Publishing with Differential Privacy
• Relations among different privacy notions