New Efficient Attacks on Statistical Disclosure Control Mechanisms

By Cynthia Dwork, Sergey Yekhanin. 2008

135 citations recorded by the source corpus.

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

Citations in the corpus

Tight Lower Bounds for Differentially Private Selection (2017, background): “Another line of work proves lower bounds in differential privacy via reconstruction attacks [13], [32], [33], [34], [35], [36], [37].”
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning (2009, background): “A sequence of prior negative results have shown that any mechanism providing overly accurate responses cannot be private (Dinur and Nissim, 2003; Dwork et al., 2007; Dwork and Yekhanin, 2008).”
On the geometry of differential privacy (2009, positive): “These results were strengthened by Dwork, McSherry and Talwar [DMT07], and by Dwork and Yekhanin [DY08].”
Fingerprinting codes and the price of approximate differential privacy (2013, methodology): “The result will follow from three lower bounds: the Ω̃( √ d) lower bound for 1-way marginals and the Ω(VC (Q)) bound that we have already discussed, and a lower bound of Ω(1/α(2)) that is a simple variant of the seminal reconstruction attack of Dinur and Nissim [12], and related attacks such as [15,”
A Simple and Practical Algorithm for Differentially Private Data Release (2010, background): “deed, there is a lower bound of Ω( √ n log |Q|) on the error of any algorithm avoiding what is called “blatant nonprivacy” [4, 11, 7].”
Understanding the Sparse Vector Technique for Differential Privacy (2016, background): “Some well-known lower-bo und results [3, 5, 6, 10] suggest that “one cannot answer a linear , in the database size, number of queries with small noise while pres erving privacy” [7].”
The Power of Linear Reconstruction Attacks (2012, methodology): “Specifically, we consider a setting in which the same statistic (either1 or 2 above) is released about how the sensitive attribute relates to all subsets of sizek (out of a total ofd) nonsensitive boolean attributes.”
Private and Continual Release of Statistics (2010, background): “However, previous work has shown that such statistical disclosures can expose sensitive information about an individual user [3, 11].”
On the complexity of differentially private data release: efficient algorithms and hardness results (2009, background): “There has been a series of negative results concerning privacy, roughly saying that there is a class of queries with the property that it is blatantly non-private (allowing almost full reconstruction) if “too many” queries receive “overly accurate” responses [5, 7, 9].”
The Complexity of Differential Privacy (2017, background): “which again can be shown to be Ω( √ n) for a random n× n matrix Q, as well as for some explicit constructions [37].”
A Multiplicative Weights Mechanism for Privacy-Preserving Data Analysis (2010, background): “than the database size) with “overly accurate” responses (smaller error than the sampling error1) leads to blatant privacy violations [3], [6], [11].”
Private coresets (2009, background): “INTRODUCTION The notion of Differential privacy [18] has emerged in a recent line of work on private data analysis that seeks a rigorous treatment of privacy and its consequences (see [15, 22, 20, 7, 18, 17, 16, 40, 19, 37, 5, 41, 8, 6, 21, 35]).”