Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples

By Changchang Liu, Supriyo Chakraborty, Prateek Mittal. 2016

213 citations recorded by the source corpus.

Differential privacy (DP) is a widely accepted mathematical framework for protecting data privacy. Simply stated, it guarantees that the distribution of query results changes only slightly due to the modification of any one tuple in the database. This allows protection, even against powerful adversaries, who know the entire database except one tuple. For providing this guarantee, differential privacy mechanisms assume independence of tuples in the database – a vulnerable assumption that can lead to degradation in expected privacy levels especially when applied to real-world datasets that manifest natural dependence owing to various social, behavioral, and genetic relationships between users. In this paper, we make several contributions that not only demonstrate the feasibility of exploiting the above vulnerability but also provide steps towards mitigating it. First, we present an inference attack, using real datasets, where an adversary leverages the probabilistic dependence between tuples to extract users’ sensitive information from differentially private query results (violating the DP guarantees). Second, we introduce the notion of dependent differential privacy (DDP) that accounts for the dependence that exists between tuples and propose a dependent perturbation mechanism (DPM) to achieve the privacy guarantees in DDP. Finally, using a combination of theoretical analysis and extensive experiments involving different classes of queries (e.g., machine learning queries, graph queries) issued over multiple large-scale real-world datasets, we show that our DPM consistently outperforms state-of-the-art approaches in managing the privacy-utility tradeoffs for dependent data.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Electrical and Electronic Engineering

In Privacy & Security

Citations in the corpus

Deep Models Under the GAN: Information Leakage from Collaborative Deep Learning (2017, background): “At NDSS’16, it was shown in [46] that DP is not effective in real-life scenarios where data such as social data,”
$\textsf{LoPub}$ : High-Dimensional Crowdsourced Data Publication With Local Differential Privacy (2016, background): “However, the correlations and sparsity in high-dimensional data are not well considered, which will cause low scalability and utility for highdimensional data [25], [35].”
Adaptive Laplace Mechanism: Differential Privacy Preservation in Deep Learning (2017, background): “, data collection [19], spatiotemporal correlations [20, 21], data streams [22], stochastic gradient descents [23], recommendation [7], regression [6], online learning [24], publishing contingency tables [25], and spectral graph analysis [26].”
Differentially-Private Multi-Party Sketching for Large-Scale Statistics (2020, background): “[48] has pointed out that dierential privacy guarantees may be insufcient when data in the database is correlated as in the case when the same or closely related users may appear in multiple organizations’ data sets.”
DEEProtect: Enabling Inference-based Access Control on Mobile Sensing Applications (2017, methodology): “, among the three dimensions of accelerometer in Case Study 1) according to [53]; 2) training customized models specific to each individual user that installs DEEProtect in phone; and 3) training models based on a larger amount of users’ data as in [30].”