Universally optimal privacy mechanisms for minimax agents
Published 6 June 2010
Mangesh Gupte, Mukund Sundararajan
Citations75
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
This paper shows that for every fixed count query, the geometric mechanism is universally optimal for all minimax information consumers, and makes it possible to release query results, when information consumers are at different levels of privacy, in a collusion-resistant manner.
Abstract
A scheme that publishes aggregate information about sensitive data must resolve the trade-off between utility to information consumers and privacy of the database participants. Differential privacy [5] is a well-established definition of privacy--this is a universal guarantee against all attackers, whatever their side-information or intent. Can we have a similar universal guarantee for utility?
Keywords
Computer ScienceSocial Sciences
International Journal of Uncertainty Fuzziness and Knowledge-Based Systemsk-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
8,492 Citations2002Latanya Sweeney
The solution provided in this paper includes a formal protection model named k-anonymity and a set of accompanying policies for deployment and examines re-identification attacks that can be realized on releases that adhere to k- anonymity unless accompanying policies are respected.
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.
The Economic JournalRegret Theory: An Alternative Theory of Rational Choice Under Uncertainty
4,049 Citations1982Graham Loomes, Robert Sugden
Lecture notes in computer scienceDifferential Privacy: A Survey of Results
3,295 Citations2008Cynthia Dwork
This survey recalls the definition of differential privacy and two basic techniques for achieving it, and shows some interesting applications of these techniques, presenting algorithms for three specific tasks and three general results on differentially private learning.
Proceedings - IEEE Symposium on Security and Privacy/Proceedings of the ... IEEE Symposium on Security and PrivacyRobust De-anonymization of Large Sparse Datasets
2,298 Citations2008Arvind Narayanan, Vitaly Shmatikov
This work applies the de-anonymization methodology to the Netflix Prize dataset, which contains anonymous movie ratings of 500,000 subscribers of Netflix, the world's largest online movie rental service, and demonstrates that an adversary who knows only a little bit about an individual subscriber can easily identify this subscriber's record in the dataset.
Towards Sharp Inapproximability For Any 2-CSP
1,358 Citations2007Per Austrin
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).
Smooth sensitivity and sampling in private data analysis
986 Citations2007Kobbi Nissim, Sofya Raskhodnikova +1 more
This is the first formal analysis of the effect of instance-based noise in the context of data privacy, and shows how to do this efficiently for several different functions, including the median and the cost of the minimum spanning tree.
RePEc: Research Papers in EconomicsMicroeconomic Theory
690 Citations1995Mas-Colell, Andreu 1944-, Whinston, Michael D. 1959- +1 more
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.
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.
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.
IEEE Signal Processing MagazineCollusion-resistant fingerprinting for multimedia
216 Citations2004Min Wu, Wade Trappe +2 more
The geometry of differential privacy
95 Citations2013Aleksandar Nikolov, Kunal Talwar +1 more
The connection between the hereditary discrepancy and the privacy mechanism enables the first polylogarithmic approximation to the hereditary discrepancies of a matrix A to be derived.
Proceedings of the VLDB EndowmentOptimal random perturbation at multiple privacy levels
61 Citations2009Xiaokui Xiao, Yufei Tao +1 more
The proposed technique is both space economical and computationally efficient, and produces a new anonymized version in O (n + log m) expected time, where n is the cardinality of the original dataset, and m the number of versions released previously.
Boosting the Accuracy of Differentially-Private Queries Through Consistency
23 Citations2009Michael Hay, Vibhor Rastogi +2 more
This work shows that it is possible to significantly improve accuracy for a general class of histogram queries, and carefully chooses a set of queries to evaluate, and then exploits consistency constraints that should hold over the noisy output.