Computer Science – Cryptography and Security
Scientific paper
2010-08-02
Computer Science
Cryptography and Security
Scientific paper
The notion of a universally utility-maximizing privacy mechanism was recently introduced by Ghosh, Roughgarden, and Sundararajan [STOC 2009]. These are mechanisms that guarantee optimal utility to a large class of information consumers, simultaneously, while preserving Differential Privacy [Dwork, McSherry, Nissim, and Smith, TCC 2006]. Ghosh et al. have demonstrated, quite surprisingly, a case where such a universally-optimal differentially-private mechanisms exists, when the information consumers are Bayesian. This result was recently extended by Gupte and Sundararajan [PODS 2010] to risk-averse consumers. Both positive results deal with mechanisms (approximately) computing a single count query (i.e., the number of individuals satisfying a specific property in a given population), and the starting point of our work is a trial at extending these results to similar settings, such as sum queries with non-binary individual values, histograms, and two (or more) count queries. We show, however, that universally-optimal mechanisms do not exist for all these queries, both for Bayesian and risk-averse consumers. For the Bayesian case, we go further, and give a characterization of those functions that admit universally-optimal mechanisms, showing that a universally-optimal mechanism exists, essentially, only for a (single) count query. At the heart of our proof is a representation of a query function $f$ by its privacy constraint graph $G_f$ whose edges correspond to values resulting by applying $f$ to neighboring databases.
Brenner Hai
Nissim Kobbi
No associations
LandOfFree
Impossibility of Differentially Private Universally Optimal Mechanisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Impossibility of Differentially Private Universally Optimal Mechanisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Impossibility of Differentially Private Universally Optimal Mechanisms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-52643