Composition attacks and auxiliary information in data privacy

By Srivatsava Ranjit Ganta, Shiva Prasad Kasiviswanathan, Adam D. Smith. 2008

437 citations recorded by the source corpus.

Privacy is an increasingly important aspect of data publishing. Reasoning about privacy, however, is fraught with pitfalls. One of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. This paper explores how one can reason about privacy in the face of rich, realistic sources of auxiliary information. Specifically, we investigate the effectiveness of current anonymization schemes in preserving privacy when multiple organizations independently release anonymized data about overlapping populations. 1. We investigate composition attacks, in which an adversary uses independent anonymized releases to breach privacy. We explain why recently proposed models of limited auxiliary information fail to capture composition attacks. Our experiments demonstrate that even a simple instance of a composition attack can breach privacy in practice, for a large class of currently proposed techniques. The class includes k-anonymity and several recent variants. 2. On a more positive note, certain randomization-based notions of privacy (such as differential privacy) provably resist composition attacks and, in fact, the use of arbitrary side information.This resistance enables "stand-alone" design of anonymization schemes, without the need for explicitly keeping track of other releases. We provide a precise formulation of this property, and prove that an important class of relaxations of differential privacy also satisfy the property. This significantly enlarges the class of protocols known to enable modular design.

Subfields: Artificial Intelligence, Sociology and Political Science, 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 Sociology and Political Science

In Privacy & Security

Citations in the corpus

Prochlo: Strong Privacy for Analytics in the Crowd (2017, methodology): “To illustrate, consider the app/API example from § 2.1 (see § 5 for detailed use cases).”
Privacy in Pharmacogenetics: An End-to-End Case Study of Personalized Warfarin Dosing (2014, neutral): “However, others have motivated or designed DP mechanisms with the goal of ensuring the privacy of patients’ diseases [15], features on users’ social network profiles [33], and website visits in network traces [38]— all of which relate to attribute privacy.”
Signal Processing and Machine Learning with Differential Privacy (2013, background): “This defini tion has many features: it is resistant to attacks to which other privacy models are susceptible [2], it bounds the privacy risk to each individual, and it degrades gracefully as an individual's data is used in multiple computations.”
Privacy Aware Learning (2012, background): “Indeed, differential privacy protects against side information and many adversarial attacks that break previous de.nitions of privacy, such as k-anonymity [Ganta et al. 2008].”
Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples (2016, background): “…databases D(L,R), D′(L,R) are dependent neighboring databases, if the modification of a tuple value in database D(L,R) (e.g., the change from Di in D(L,R) to D′i) causes change in atmost L − 1 other tuple values in D′(L,R) due to the probabilistic dependence relationship R between the data tuples.”
Learning privately from multiparty data (2016, background): “, 2006; Dwork, 2006) has addressed several weaknesses of k-anonymity (Ganta et al., 2008), and gained popularity as a quantifiable measure of privacy risk.”
Minimax Optimal Procedures for Locally Private Estimation (2016, methodology): “…that are problematic for other formalisms, have been used to make the case for differential privacy within the computer science literature; see, for example, the articles Evfimievski, Gehrke, and Srikant (2003); Dwork et al. (2006); Barak et al. (2007); Ganta, Kasiviswanathan, and Smith (2008).”
Differential privacy via wavelet transforms (2009, methodology): “For each dataset, we create a set of 40000 random rangecount queries, such that the number of predicates in each query is uniformly distributed in [1, 4].”
Discovering frequent patterns in sensitive data (2010, background): “This implies that no matter what the adversary knows ahead of time, he learns the same thing about Alice whether or not her data is actually included in the data set x [10, 13].”
Near-Optimal Algorithms for Differentially-Private Principal Components (2012, methodology): “urvey with more references. Many of these models have been shown to be susceptible to composition attacks, which are attacks in which the adversary exploits prior knowledge to reidentify individuals [Ganta et al., 2008]. An alternative line of privacy-preserving data-mining work [Zhan and Matwin, 20”
Differential Privacy for Statistics: What we Know and What we Want to Learn (2010, neutral): “See [19] [31] for discussion.”
A Practical Differentially Private Random Decision Tree Classifier (2009, background): “[18]), provides its privacy guarantees even in the presence of arbitrary auxiliary information.”
Towards an axiomatization of statistical privacy and utility (2010, background): “In other cases, subtle implicit assumptions created weaknesses that could be exploited to breach privacy [25, 41, 22, 27].”
Pufferfish (2014, methodology): “P uffer F ish( S , pairs ) satisﬁes the axioms of convexity and transformation invariance.”
Convergence Rates for Differentially Private Statistical Estimation (2012, background): “It has been shown to have strong semantic guarantees (Dwork et al., 2006b) and is resistant to many attacks (Ganta et al., 2008) that succeed against some other deﬁnitions of privacy.”
Testing the Lipschitz Property over Product Distributions with Applications to Data Privacy (2013, background): “With known attacks (e.g. [15]) on k - anonymity and (cid:2) -diversity, privacy community has pretty much converged to theoretically sound notions of privacy like differential privacy.”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, background): “[11], it is mentioned that Dwork and McSherry proposed semantic privacy which measures how the posterior distribution on”