Dependence Makes You Vulnerable: Differential Privacy Under Dependent Tuples

Changchang Liu, Supriyo Chakraborty, Prateek Mittal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

120 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publication23rd Annual Network and Distributed System Security Symposium, NDSS 2016
PublisherThe Internet Society
ISBN (Electronic)189156241X, 9781891562419
DOIs
StatePublished - 2016
Event23rd Annual Network and Distributed System Security Symposium, NDSS 2016 - San Diego, United States
Duration: Feb 21 2016Feb 24 2016

Publication series

Name23rd Annual Network and Distributed System Security Symposium, NDSS 2016

Conference

Conference23rd Annual Network and Distributed System Security Symposium, NDSS 2016
Country/TerritoryUnited States
CitySan Diego
Period2/21/162/24/16

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality

Fingerprint

Dive into the research topics of 'Dependence Makes You Vulnerable: Differential Privacy Under Dependent Tuples'. Together they form a unique fingerprint.

Cite this