Source-linked AI summary
On the `Semantics' of Differential Privacy: A Bayesian Formulation
Shiva Prasad Kasiviswanathan, Adam Smith
TL;DR
The paper addresses how to formulate differential privacy's claimed protection against adversaries with arbitrary side information. It models the adversary Bayesianly and shows that both pure and (ε, δ)-differential privacy satisfy the resulting formulation, with parameter guidance for the relaxed definition.
Problem
The paper asks how privacy guarantees should be stated when adversaries possess arbitrary external information and notes that stronger conclusions about excluding a person's data altogether are impossible in that setting.
Method
The paper formulates semantic privacy in terms of a Bayesian adversary and analyzes pure and relaxed differential privacy using probability-distribution distance properties and related games.
Results
Both pure and relaxed differential privacy provide meaningful guarantees against arbitrary side information; for (ε, δ)-privacy, δ should be smaller than about ε^2/n.
Takeaways & Limitations
Relaxed differential privacy can be used with the same kind of semantic assurances as pure differential privacy when its parameters are set appropriately.
Takeaways & Limitations
A statistical-difference-based relaxation can satisfy its formal requirement while revealing an individual's data in the clear and failing semantic privacy.
Abstract
from arXiv · showhide
Differential privacy is a definition of "privacy'" for algorithms that analyze and publish information about statistical databases. It is often claimed that differential privacy provides guarantees against adversaries with arbitrary side information. In this paper, we provide a precise formulation of these guarantees in terms of the inferences drawn by a Bayesian adversary. We show that this formulation is satisfied by both "vanilla" differential privacy as well as a relaxation known as (epsilon,delta)-differential privacy. Our formulation follows the ideas originally due to Dwork and McSherry [Dwork 2006]. This paper is, to our knowledge, the first place such a formulation appears explicitly. The analysis of the relaxed definition is new to this paper, and provides some concrete guidance for setting parameters when using (epsilon,delta)-differential privacy.
1 Introduction
The paper frames arbitrary side information as a central challenge for privacy guarantees and gives a precise Bayesian formulation of differential privacy's semantic meaning. It establishes that both pure and relaxed differential privacy can support such guarantees, with parameter guidance for the relaxed definition.
- Motivation: Arbitrary side information from sources such as the web, public records, and domain knowledge complicates privacy reasoning.Secure composition is therefore important for modularly designing schemes that remain private alongside independent releases and external knowledge.
- Approach: The paper gives a Bayesian formulation of pure differential privacy that explicitly models an adversary's side information.The formulation concerns the inferences drawn by a Bayesian adversary.
- Results: The paper proves that several relaxed differential privacy definitions imply the Bayesian formulation.The proof is non-trivial and relies on continuity properties of Bayes' rule with respect to distance measures on probability distributions.
- Results: (ε, δ)-differential privacy provides meaningful guarantees when δ, the additive error parameter, is smaller than about ε^2/n.Here n is the size of the data set.
2 Semantics of Differential Privacy
The paper formalizes privacy against arbitrary external knowledge by modeling an adversary’s beliefs and posterior inferences, then relates this semantic formulation to differential privacy. It proves two-way implications for pure and relaxed definitions, while identifying parameter conditions and limitations of alternative metrics.
- Bayesian formulation: Arbitrary external knowledge is modeled as a prior distribution over databases, with conclusions represented by the Bayesian posterior after observing a transcript.The framework treats side information as a belief distribution and updates it using Bayes’ rule.
- Bayesian formulation: The semantic privacy test compares posterior beliefs when the adversary interacts with the original database and when one individual’s data is replaced by a default value.The construction uses Game 0 for the actual interaction and Game i for the scenario excluding person i’s data.
- Pure differential privacy: Pure differential privacy and semantic privacy are essentially equivalent, with ε-differential privacy implying (e^ε −1)-semantic privacy and ε/2-semantic privacy implying 3ε-differential privacy for ε ≤0.45.These bounds establish the paper’s formal connection between the standard and Bayesian formulations.
- Relaxed differential privacy: The relaxed formulation allows bad transcripts with probability δ, extending the Bayesian framework to (ε, δ)-differential privacy.The paper defines (ε, δ)-semantic privacy probabilistically over transcripts and relates it to the relaxed differential privacy definition.
- Relaxed differential privacy: If δ < (1 −e^-ε)^2/n, then (ε, δ)-differential privacy implies (ε′, δ′)-semantic privacy; conversely, (ε, δ)-semantic privacy implies (3ε, 2δ)-differential privacy when ε ≤0.45.The main theorem supplies parameter conditions for the relaxed two-way relationship.
- Limits of alternative metrics: The equivalence depends on the multiplicative metric: analogous implications need not hold for statistical difference or mutual information.A uniformly sampled individual’s data can satisfy those alternative requirements while failing semantic privacy for reasonable parameters.
3 Proofs of Main Results
The paper proves that differential privacy can be formulated as Bayesian semantic privacy, and extends the connection to (ε,δ)-differential privacy using indistinguishability and a conditioning lemma.
- Indistinguishability: The proof framework defines (ε,δ)-indistinguishability through two-sided probability bounds over every measurable set.This measure underlies the relaxed differential-privacy results.
- Indistinguishability: The indistinguishability lemmas relate point-wise and ordinary indistinguishability and support postprocessing over jointly distributed variables.These properties are used to transfer guarantees between algorithms and belief distributions.
- Pure differential privacy: ε/2-differential privacy implies (e^ε−1)-semantic privacy, while ε/2-semantic privacy implies 3ε-differential privacy for ε≤0.45.The proof compares posterior distributions under the original and modified databases, then converts their closeness into indistinguishability.
- Relaxed differential privacy: The Conditioning Lemma converts indistinguishability of joint pairs into conditional indistinguishability with 3ε and controlled failure probability.It is the main tool for extending the Bayesian argument to relaxed differential privacy.
- Relaxed differential privacy: (ε,δ)-differential privacy implies (ε′,δ′)-semantic privacy under a small-δ condition, while (ε,δ)-semantic privacy implies (3ε,2δ)-differential privacy when ε≤0.45.The proof applies the conditioning result to the original and leave-one-out mechanisms and then bounds the exceptional transcript probability.
4 Further Discussion
The paper shows that selected relaxations retain semantic guarantees against side information and develops local-sensitivity and high-probability privacy consequences.
- Relaxations: Some relaxations of differential privacy still provide meaningful guarantees against arbitrary side information, although this fails for all possible relaxations.The result depends on using the specific relaxations analyzed in the paper.
- High-probability guarantees: The same techniques analyze mechanisms that satisfy indistinguishability for most neighboring database pairs rather than every pair.The failure set is required to occur only with small probability.
- Local semantic privacy: The paper weakens semantic privacy so that it holds for specific belief distributions rather than universally.The resulting definition is local semantic privacy for a belief distribution.
- Local semantic privacy: If neighboring outputs are (ε,δ)-indistinguishable on a high-probability set of databases, the algorithm satisfies local semantic privacy with adjusted parameters.The set E contains databases whose outputs are indistinguishable from all neighbors, and the belief distribution assigns it probability at least 1−δ1.
- Local sensitivity: For local sensitivity, Laplacian noise is combined with the theorem to obtain a local semantic-privacy guarantee under a belief distribution concentrated on low-sensitivity databases.The event E is defined by LS_f(x)≤s, and the belief assigns E probability at least 1−δ1.
A Proof of Lemma 3.3
The lemma proofs derive probability and statistical-distance consequences from (ε,δ)-indistinguishability by isolating bad events and applying symmetry.
- Part 1: The proof defines a bad set where point probabilities differ by more than multiplicative factors e^ε and e^-ε, then bounds its probability by δ.Outside this set, the desired multiplicative comparison holds.
- Part 2: A two-sided indistinguishability argument bounds the probability of outcomes violating an e^2ε ratio by a quantity proportional to δ.The proof treats the upper and lower violation sets symmetrically.
- Part 3: Indistinguishability is preserved for paired random variables when the same input distribution is processed by two indistinguishable algorithms.The argument evaluates arbitrary subsets of the joint output space.
- Part 4: When indistinguishability fails on an input subset of probability δ1, the resulting joint distributions remain indistinguishable with additive error δ+δ1.This accounts explicitly for the probability of exceptional inputs.
- Part 5: The statistical difference between indistinguishable random variables is at most ε̄+δ, where ε̄=e^ε−1.The proof applies the defining inequality to every subset.
B Another View of Semantic Privacy
The paper examines a stronger, reality-oblivious formulation of semantic privacy and shows that (ε, δ)-differential privacy cannot generally guarantee it for arbitrary beliefs. A counterexample demonstrates exponentially separated posterior distributions when the adversary’s beliefs differ greatly from the real database.
- Reality-oblivious semantic privacy: The alternative reality-oblivious definition requires semantic privacy for every belief distribution and database, except with probability δ over transcripts.It quantifies over arbitrary beliefs b on D^n, databases x, and individuals.
- Main result: (ε, δ)-differential privacy does not imply reality-oblivious (ε′, δ′)-semantic privacy for any reasonable parameter values.The paper presents this as a theorem about the stronger definition.
- Counterexample: The counterexample uses a uniform prior over {(0^n), (1, 0^{n−1})} while the real database is (1^n), producing sharply different posterior updates.The construction examines a mechanism intended to reveal a function of the database.
- Counterexample: The resulting posterior distributions are exponentially far apart: one becomes highly biased toward (1, 0^{n−1}), while the other remains uniform.This establishes the failure of any reasonable reality-oblivious semantic-privacy guarantee in the example.
- Interpretation: The authors attribute the large posterior change to adversaries whose beliefs are very different from the real database, rather than to a privacy violation by the mechanism itself.The limitation concerns the mismatch between the adversary’s belief distribution and reality.