Quantifying Differential Privacy under Temporal Correlations

Abstract

Differential Privacy (DP) has received increased attention as a rigorous privacy framework. Existing studies employ traditional DP mechanisms (e.g., the Laplace mechanism) as primitives, which assume that the data are independent, or that adversaries do not have knowledge of the data correlations. However, continuously generated data in the real world tend to be temporally correlated, and such correlations can be acquired by adversaries. In this paper, we investigate the potential privacy loss of a traditional DP mechanism under temporal correlations in the context of continuous data release. First, we model the temporal correlations using Markov model and analyze the privacy leakage of a DP mechanism when adversaries have knowledge of such temporal correlations. Our analysis reveals that the privacy leakage of a DP mechanism may accumulate and increase over time. We call it temporal privacy leakage. Second, to measure such privacy leakage, we design an efficient algorithm for calculating it in polynomial time. Although the temporal privacy leakage may increase over time, we also show that its supremum may exist in some cases. Third, to bound the privacy loss, we propose mechanisms that convert any existing DP mechanism into one against temporal privacy leakage. Experiments with synthetic data confirm that our approach is efficient and effective.

appears at ICDE 2017

References in corpus (2)

• Protecting Locations with Differential Privacy under Temporal Correlations
• DPCube: Differentially Private Histogram Release through Multidimensional Partitioning

Cited by in corpus (17)

• A Comprehensive Survey on Local Differential Privacy Toward Data Statistics and Analysis
• LDPTrace: Locally Differentially Private Trajectory Synthesis
• Differential Privacy for Eye Tracking with Temporal Correlations
• Real-World Trajectory Sharing with Local Differential Privacy
• Protecting Spatiotemporal Event Privacy in Continuous Location-Based Services
• Impact of Prior Knowledge and Data Correlation on Privacy Leakage: A Unified Analysis
• DP-Sync: Hiding Update Patterns in Secure Outsourced Databases with Differential Privacy
• Improved Differentially Private Decentralized Source Separation for fMRI Data
• Context-aware Data Aggregation with Localized Information Privacy
• Local Information Privacy and Its Application to Privacy-Preserving Data Aggregation
• PGLP: Customizable and Rigorous Location Privacy through Policy Graph
• VideoDP: A Universal Platform for Video Analytics with Differential Privacy
• Differentially Private Online Bayesian Estimation With Adaptive Truncation
• SoK: Chasing Accuracy and Privacy, and Catching Both in Differentially Private Histogram Publication
• Trading Location Data with Bounded Personalized Privacy Loss
• Near-Optimal Privacy-Utility Tradeoff in Genomic Studies Using Selective SNP Hiding
• What Does The Crowd Say About You? Evaluating Aggregation-based Location Privacy