The price of privacy and the limits of LP decoding

By Cynthia Dwork, Frank McSherry, Kunal Talwar. 2007

260 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Networks and Communications, Electrical and Electronic Engineering

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Electrical and Electronic Engineering

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].”
Concentrated Differential Privacy (2016, background): “239 fraction of queries leads to blatant non-privacy [DMT07], while noise drawn from a Laplace distribution with standard deviation .”
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).”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, methodology): “However, (to the best of our understanding) these implications of [7, 12] do not imply the lowerbounds we get for local interactive protocols and distributed protocols.”
Robust Traceability from Trace Amounts (2015, background): “These attacks, which immediately give lower bounds on noise needed to avoid blatant non-privacy, have been extended in numerous works [4]–[11].”
A learning theory approach to non-interactive database privacy (2008, background): “Categories and Subject Descriptors F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity General Terms Algorithms, Security, Theory Keywords non-interactive database privacy, learning theory”
Universally utility-maximizing privacy mechanisms (2008, background): “…showed that for a database with n rows, answering O ( n log 2 n ) randomly chosen subset count queries with o ( √ n ) error allows an adversary to reconstruct most of the rows of the database (a blatant privacy breach); see Dwork et al. [11] for a more robust impossibility result of the same type.”
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,”
Lower Bounds in Differential Privacy (2011, methodology): “We note that Hardt and Talwar [HT10] had shown such a separation but that was only when k = O(log n) and δ = n−O(1).”
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.”
Differential Privacy: A Survey of Results (2008, unknown): “Although this can be ameliorated to some extent using Gaussian noise instead of Laplacian, an exciting line of research begun by Dinur and Nissim [13] (see also [17, 20]) shows that this increase is essential.”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, background): “Dwork, McSherry, and Talwar, [22] and Dwork and Yekhanin [30] generalized this attack to only require (α, β)-accuracy for some constant β > 0, and we will make use of this extension (although we do not require computational efficiency, which was a focus of those works).”
The Complexity of Differential Privacy (2017, unknown): “(This is a theorem of Dwork, McSherry, and Talwar [39], and is based on connections to compressed sensing.”