Universally utility-maximizing privacy mechanisms

By Arpita Ghosh, Tim Roughgarden, Mukund Sundararajan. 2008

595 citations recorded by the source corpus.

A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. Privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same whether or not a given database row is included or excluded. The goal of this paper is strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a loss function). Our main result is: for each fixed count query and differential privacy level, there is a geometric mechanism M* -- a discrete variant of the simple and well-studied Laplace mechanism -- that is simultaneously expected loss-minimizing for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: 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. More precisely, for every user u there is an optimal mechanism Mu for it that factors into a user-independent part (the geometric mechanism M*) followed by user-specific post-processing that can be delegated to the user itself. The first part of our proof of this result characterizes the optimal differentially private mechanism for a fixed but arbitrary user in terms of a certain basic feasible solution to a linear program with constraints that encode differential privacy. The second part shows that all of the relevant vertices of this polytope (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.

Subfields: Artificial Intelligence, Computer Science Applications, Privacy & Security

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 Computer Science Applications

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “with a low ε / high privacy level) [12, 330, 181, 356, 188].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, methodology): “A common choice of D is the Discrete Laplace distribution with parameter ε, which yields an (ε, 0)-DP protocol for binary summation with an asymptotically tight MSE of O(1/ε(2)); this is known to be optimal in the central DP model (Ghosh et al., 2012).”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “The concept of differential pri vacy has been developed in two different contexts: the global privacy context (for instance, when institutions release statisti cs of groups of people) [3], and the local privacy context when individuals disclose their personal data [4].”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, methodology): “Geometric mechanism requires drawing two r.v., one from Poisson and one from gamma distributions, which makes it slower than most DLPA mechanisms.”
Extremal Mechanisms for Local Differential Privacy (2014, background): “showed that the geometric noise adding mechanism is optimal (under a Bayesian setting) for monotone utility functions under count queries (sensitivity one) [17].”
The Composition Theorem for Differential Privacy (2013, methodology): “For count queries with sensitivity one, the geometric noise adding mechanism is known to be universally optimal in a general cost minimization framework (Bayesian setting in Ghosh et al. (2012) and worst-case setting in Geng & Viswanath (2012)).”
Privacy Aware Learning (2012, neutral): “[2013], and Ghosh et al. [2009]).”
Distributed Private Data Analysis: On Simultaneously Solving How and What (2008, background): “It has been demonstrated that differentially private analyses exist for a variety of tasks including the approximation of numerical functions (by adding carefully chosen random noise that conceals any single individual’s contribution) [11, 2, 22, 17], non-numerical analyses [20], datamining [2, 22],”
On the geometry of differential privacy (2009, background): “For the case of d = 1, Ghosh, Roughgarden and Sundararajan [GRS09] show that adding Laplace noise is in fact optimal in a very general decision-theoretic framework, for any symmetric decreasing loss function.”
A Statistical Framework for Differential Privacy (2008, methodology): “After submitting the first draft of this paper, new work has appeared on differential privacy that is also statistical in nature, namely, Ghosh, Roughgarden, and Sundararajan (2009), Dwork and Lei (2009), Dwork et al. (2009), Feldman et al. (2009).”
Interactive privacy via the median mechanism (2009, background): “Among all α -diﬀerentially private mechanisms, this one (or rather, a discretized analog of it) maximizes user utility in a strong sense [GRS09].”
The Power of Linear Reconstruction Attacks (2012, background): “This is already perhaps surprising, since many of the above releases (likeM -estimators) are obtained by solving highly nonlinear formulations.”
Differentially private data aggregation with optimal utility (2014, methodology): “To this end, Ghosh et al. [28] proposed the discrete Laplace mechanism (also called geometric mechanism).”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, methodology): “Therefore, we add noises sampled from symmetric geometric distributions [12].”
An Adaptive Mechanism for Accurate Query Answering under Differential Privacy (2012, unknown): “For a single numerical query, the addition of appropriatelyscaled discrete Laplace noise satisfies -differential privacy and has been proven optimally accurate [11].”
Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message (2021, methodology): “We also include the Discrete Laplace mechanism (Ghosh et al., 2012) in our plots for comparison, although it is not directly implementable in the shufﬂe model.”