The Differential Privacy Frontier (Extended Abstract)
Lecture notes in computer sciencePublished 1 January 2009
Cynthia Dwork
Citations136
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The definition of differential privacy is reviewed and a handful of very recent contributions to the differential privacy frontier are surveyed.
Abstract
We review the definition of differential privacy and briefly survey a handful of very recent contributions to the differential privacy frontier.
Keywords
Computer ScienceSocial Sciences
Lecture notes in computer scienceCalibrating Noise to Sensitivity in Private Data Analysis
7,028 Citations2006Cynthia Dwork, Frank McSherry +2 more
Lecture notes in computer scienceDifferential Privacy
5,027 Citations2006Cynthia Dwork
A general impossibility result is given showing that a formalization of Dalenius' goal along the lines of semantic security cannot be achieved, which suggests a new measure, differential privacy, which, intuitively, captures the increased risk to one's privacy incurred by participating in a database.
TechnometricsRobust Statistics: The Approach Based on Influence Functions
3,793 Citations1987David Ruppert, Frank R. Hampel +3 more
This paper presents a meta-modelling framework for estimating the values of Covariance Matrices and Multivariate Location using one-Dimensional and Multidimensional Estimators.
Towards Sharp Inapproximability For Any 2-CSP
1,358 Citations2007Per Austrin
Mechanism Design via Differential Privacy
1,341 Citations2007Frank McSherry, Kunal Talwar
Revealing information while preserving privacy
999 Citations2003Irit Dinur, Kobbi Nissim
A polynomial reconstruction algorithm of data from noisy (perturbed) subset sums of data from noisy (perturbed) subset sums shows that in order to achieve privacy one has to add perturbation of magnitude (Ω√n).
Practical privacy
815 Citations2005Avrim Blum, Cynthia Dwork +2 more
This work considers a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries, and modify the privacy analysis to real-valued functions f and arbitrary row types, greatly improving the bounds on noise required for privacy.
Lecture notes in computer scienceAdvances in Cryptology – CRYPTO 2004
704 Citations2004Matthew Franklin, Franklin, Matthew
Differential privacy and robust statistics
619 Citations2009Cynthia Dwork, Jing Lei
It is shown by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators.
A learning theory approach to non-interactive database privacy
527 Citations2008Avrim Blum, Katrina Ligett +1 more
A new notion of data privacy is introduced, which is called distributional privacy, and it is shown that it is strictly stronger than the prevailing privacy notion, differential privacy.
Privacy, accuracy, and consistency too
485 Citations2007Boaz Barak, Kamalika Chaudhuri +4 more
This paper proposes a solution that provides strong guarantees for all three desiderata simultaneously, including privacy, accuracy, and consistency among the tables of the contingency table, and its techniques are surprisingly efficient.
Lecture notes in computer scienceBeyond Uniformity: Better Security/Efficiency Tradeoffs for Compression Functions
363 Citations2008Martijn Stam
The conjecture that typically collisions can be found in 2(nr+ cri¾? m)/(r+ 1)queries is conjecture, which shows that Rogaway and Steinberger's recent bound of 2(nri½? mi¾?)queries (for c= 0) crucially relies upon a uniformity assumption; a blanket generalization to arbitrary compression functions would be incorrect.
Lecture notes in computer sciencePrivacy-Preserving Datamining on Vertically Partitioned Databases
358 Citations2004Cynthia Dwork, Kobbi Nissim
Under a rigorous definition of breach of privacy, Dinur and Nissim proved that unless the total number of queries is sub-linear in the size of the database, a substantial amount of noise is required to avoid a breach, rendering the database almost useless.
What Can We Learn Privately?
324 Citations2008Shiva Prasad Kasiviswanathan, Homin K. Lee +3 more
Universally utility-maximizing privacy mechanisms
248 Citations2009Arpita Ghosh, Tim Roughgarden +1 more
Every potential user u, no matter what its side information and preferences, derives as much utility from M* as from interacting with a differentially private mechanism Mu that is optimally tailored to u, subject to differential privacy.
Lecture notes in computer scienceComputational Differential Privacy
230 Citations2009Ilya Mironov, Omkant Pandey +2 more
This work extends the dense model theorem of Reingold et al. to demonstrate equivalence between two definitions (indistinguishability- and simulatability-based) of computational differential privacy, and presents a differentially-private protocol for computing the distance between two vectors.
The price of privacy and the limits of LP decoding
219 Citations2007Cynthia Dwork, Frank McSherry +1 more
The principal result is the discovery of a sharp threshhold ρ*∠ 0.239, which says that any privacy mechanism, interactive or non-interactive, providing reasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, is blatantly non-private.
Journal of Privacy and ConfidentialityOn the Difficulties of Disclosure Prevention in Statistical Databases or The Case for Differential Privacy
114 Citations2010Cynthia Dwork, Moni Naor
A general impossibility result is given showing that a natural formalization of Dalenius’ goal cannot be achieved if the database is useful, and a variant of the result threatens the privacy even of someone not in the database.
Private coresets
96 Citations2009Dan Feldman, Amos Fiat +2 more
A link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy are forged, and it is proved that private coresets must have an additive error.
Lecture notes in computer scienceNew Efficient Attacks on Statistical Disclosure Control Mechanisms
95 Citations2008Cynthia Dwork, Sergey Yekhanin
The Dinur-Nissim style results are strong because they demonstrate insecurity of all low-distortion privacy mechanisms, and a more acute attack, requiring only a fixed number of queries for each bit revealed.
FigshareDifferentially Private Approximation Algorithms
21 Citations2018Anupam Gupta, Katrina Ligett +3 more
It is shown that many such problems indeed have good approximation algorithms that preserve differential privacy; this is even in cases where it is impossible to preserve cryptographic definitions of privacy while computing any non-trivial approximation to even the value of an optimal solution, let alone the entire solution.