Impossibility of Differentially Private Universally Optimal Mechanisms

By Hai Brenner, Kobbi Nissim. 2010

94 citations recorded by the source corpus.

The notion of {\em a universally utility-maximizing privacy mechanism} was recently introduced by Ghosh, Rough garden, and Sundararajan~[STOC 2009]. These are mechanisms that guarantee optimal utility to a large class of information consumers, {\em simultaneously}, while preserving {\em Differential Privacy} [Dwork, McSherry, Nissim, and Smith, TCC 2006]. Ghosh, Rough garden and Sundararajan 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 {\em 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 {\em privacy constraint graph} $G_f$ whose edges correspond to values resulting by applying $f$ to neighboring databases.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

In Computational Theory and Mathematics

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “A recent work by Awan and Slavkovic [AS18] gives a universally optimal test when the domain size is two, however Brenner and Nissim [BN14] shows that such universally optimal tests cannot exist when the domain has more than two elements.”
Universally utility-maximizing privacy mechanisms (2008, background): “Dinur and Nissim [7] 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 resul”
The Optimal Noise-Adding Mechanism in Differential Privacy (2012, methodology): “Brenner and Nissim [7] show that for general query functions, no universally optimal differential privacy mechanisms exist.”
The Staircase Mechanism in Differential Privacy (2015, background): “[48] K. Nissim, S. Raskhodnikova, and A. Smith, “Smooth sensitivity and sampling in private data analysis,” in Proc.”
Privacy-Preserving Data Exploration in Genome-Wide Association Studies (2013, background): “[10] and Brenner and Nissim [3] investigate the problem of finding truly optimal mechanisms.”
Differentially private multi-party computation (2014, background): “While such universal mechanisms do not exist in terms of maximizing average accuracy [5], recent work [17, 18] construct a class of mechanisms (termed as “staircase” mechanisms) that are universally optimal in terms of maximizing worst-case accuracy for any cost metric that is monotonic in the error”
Selling privacy at auction (2010, background): “There is a natural tradeoﬀ between the privacy parameter ǫ and the accuracy of privacy-preserving estimates (which is well-understood in the case of single statistics, see [GRS09, BN10]).”
Secure Multi-party Differential Privacy (2015, background): “Formulating utility maximization under differential privacy as linear programs has been previously studied in [32, 20, 6, 23], under the standard client-server model where there is a single data publisher and a single data analyst.”
Broadening the Scope of Differential Privacy Using Metrics (2013, background): “The second [8] says that for any other kind of query no universally optimal mechanism exists.”