PaperlayerView exact revision on arXiv

Source-linked AI summary

Differential Privacy as a Mutual Information Constraint

Paul Cuff, Lanqing Yu

arXiv:1608.03677v1cs.ITcs.CR

TL;DR

Differential privacy protects individual database entries while answering aggregate queries, but its guarantee embodies a strong-adversary assumption that can be overlooked. The paper defines privacy through conditional mutual information maximized over database distributions and shows that MI-DP lies between ε-DP and (ε,δ)-DP. This formulation clarifies the guarantee and supports direct analysis of privacy properties, while retaining its limitation under correlated entries.

  • Problem

    Differential privacy’s strong-adversary assumption and distinction between conditional and unconditional information can be overlooked when interpreting its privacy guarantee.

  • Method

    The paper formulates differential privacy using conditional mutual information, maximized over all database distributions, and compares MI-DP with standard privacy definitions.

  • Results

    MI-DP is weaker than ε-DP but stronger than (ε,δ)-DP, with equivalence to (ε,δ)-DP when the query domain or range is finite.

  • Takeaways & Limitations

    Mutual information provides a simpler, more intuitive privacy definition whose well-understood properties make several differential-privacy results easier to verify.

  • Takeaways & Limitations

    Under correlated database entries, MI-DP does not bound unconditional mutual information and can leave privacy vulnerable to weaker adversaries.

Abstract

from arXiv · show

Differential privacy is a precise mathematical constraint meant to ensure privacy of individual pieces of information in a database even while queries are being answered about the aggregate. Intuitively, one must come to terms with what differential privacy does and does not guarantee. For example, the definition prevents a strong adversary who knows all but one entry in the database from further inferring about the last one. This strong adversary assumption can be overlooked, resulting in misinterpretation of the privacy guarantee of differential privacy. Herein we give an equivalent definition of privacy using mutual information that makes plain some of the subtleties of differential privacy. The mutual-information differential privacy is in fact sandwiched between $ε$-differential privacy and $(ε,δ)$-differential privacy in terms of its strength. In contrast to previous works using unconditional mutual information, differential privacy is fundamentally related to conditional mutual information, accompanied by a maximization over the database distribution. The conceptual advantage of using mutual information, aside from yielding a simpler and more intuitive definition of differential privacy, is that its properties are well understood. Several properties of differential privacy are easily verified for the mutual information alternative, such as composition theorems.

1. INTRODUCTION

The paper recasts differential privacy as a mutual-information constraint to clarify its assumptions and establish its relationship to standard privacy definitions. MI-DP uses conditional mutual information maximized over database distributions, is weaker than ε-DP but stronger than (ε,δ)-DP, and inherits the strong-adversary limitation.

  • Motivation: Differential privacy answers aggregate queries while protecting individual database entries through a precise mathematical framework.It replaces informal rules such as refusing averages over fewer than k entries.
  • Contribution: The paper casts differential privacy as mutual-information differential privacy and establishes an equivalence with standard (ε,δ)-DP.The contribution is presented as a connection and equivalence rather than only an upper bound.
  • Main result: MI-DP is weaker than ε-DP but stronger than (ε,δ)-DP, with equivalence to (ε,δ)-DP when the query domain or range is finite.ε-DP implies ε-MI-DP, while ε-MI-DP implies (ε′,δ)-DP with parameters vanishing as ε goes to zero.
  • Interpretation: The mutual-information formulation makes the strong-adversary assumption explicit by conditioning on all database entries except one.The assumption protects an individual even when an adversary knows everyone else’s responses.
  • Limitations: Correlations among database entries can let weaker adversaries compromise privacy, and MI-DP does not bound unconditional mutual information in that setting.This limitation is shared by MI-DP because it is equivalent in the relevant privacy sense.
  • Definition: MI-DP uses conditional rather than unconditional mutual information and maximizes over all database distributions.This preserves the mechanism-level, prior-independent nature of differential privacy.

2. PRELIMINARIES

The preliminaries formalize neighboring databases, statistical indistinguishability, privacy-parameter orderings, and related divergence-based metrics. They connect these metrics to inference and establish strictness and parameter relationships used later.

  • Notation and neighbors: A database is modeled as X^n=(X_1,…,X_n), with X_-i denoting all entries except X_i, and the mechanism output represented by Y.Neighboring instances differ in exactly one entry, equivalently at Hamming distance one.
  • Statistical indistinguishability: Differential privacy uses statistical indistinguishability of output distributions on neighboring databases, formalized through (ε,δ)-closeness.The standard ε-DP and (δ)-DP forms set δ or ε to zero, respectively.
  • Metric orderings: The privacy-metric ordering is strict: the reverse implications do not hold, even with cardinality bounds.The stated properties are tight or tight up to a multiplicative constant where indicated.
  • Inference connections: Total variation, Kullback–Leibler divergence, and likelihood-ratio closeness have direct interpretations in hypothesis testing and Bayesian inference.Total variation determines binary testing error, KL divergence governs asymptotic testing error, and (ε,0)-closeness bounds changes in log posterior odds.
  • Parameter trade-offs: Property 3 gives the tightest possible trade-off between ε and δ for (ε,δ)-closeness, with the resulting δ′ greater than δ.The text also states that a larger δ cannot imply a smaller one for finite ε and ε′.
  • Additional metrics: KL-DP is introduced as an additional privacy metric based on Kullback–Leibler divergence, alongside a formal definition of stronger privacy metrics.The paper uses these definitions to compare privacy guarantees through parameter mappings.

3. MAIN RESULT

The paper establishes an equivalence between differential privacy and a mutual-information constraint, clarifying the role of conditional mutual information and distribution maximization. The main theorem orders mutual-information privacy between classical privacy notions, with bounds and tightness characterized through binary reductions and cardinality conditions.

  • 3.1 Equivalence: The work's emphasis is the equivalence of mutual-information differential privacy with classical differential privacy.
  • 3.1 Equivalence: The implication from (ε,δ)-DP to MI-DP depends on a bound on the cardinality of database entries or query responses.
  • 3.1 Equivalence: Mutual-information differential privacy requires conditional mutual information together with maximization over all database distributions.
  • 3.1 Equivalence: The main ordering places ε-DP above KL-DP, MI-DP, and (δ)-DP, while reverse implications in the strict orderings do not hold.
  • 3.3 Proof of Theorem 1: For ε ∈ [0, ln 2], the tightest stated implication uses δ′ = 1 − 2h−1(ln 2 − ε); for ε > ln 2, the resulting (1)-DP guarantee is vacuous.
  • 3.3 Proof of Theorem 1: The proof reduces arbitrary neighboring databases and measurable outputs to binary-input, binary-output mechanisms, whose characterization is shown to be tight.
  • 3.3 Proof of Theorem 1: The complete parameter trade-off requires δ′ to exceed an ε-dependent positive threshold, with ε′ diverging as δ′ approaches that threshold.

4. PROPERTIES OF DIFF. PRIVACY

MI-DP makes privacy properties easier to analyze through mutual information, exposing the strong-adversary conditioning and yielding composition results. The section also shows that correlated responses can invalidate the usual independent-query guarantee, while disjoint partial queries preserve privacy.

  • Strong adversary assumption: MI-DP explicitly bounds information leakage about one entry conditioned on the remainder of the database.This makes the strong adversary assumption visible in the privacy definition.
  • Evidence of participation: When database entries are independent, ε-MI-DP protects evidence of participation through the corresponding unconditional information bound.Correlations remove this general protection, as shown by the maximally correlated database example.
  • Composition: For conditionally independent queries, the combined MI-DP parameter increases by at most the sum of the individual parameters.The result is described as tight and follows from mutual-information chain-rule arguments.
  • Composition: Reusing noise across query responses provides no analogous composition guarantee.The paper illustrates this with correlated outputs whose combination reveals the protected database entry.
  • Partial queries: Disjoint partial queries that are conditionally independent each satisfy the same aggregate MI-DP parameter as their individual mechanisms.Each response depends on a disjoint subset of database entries.

5. A DISCREPANCY

The section identifies a discrepancy between entry-level and group-level information guarantees. MI-DP controls conditional leakage for individual entries but need not bound leakage about correlated groups without cardinality constraints.

  • Group guarantees: MI-DP lacks the standard differential-privacy property that scales guarantees to changes in multiple database entries.Even ε-MI-DP may leave I(XI; Y |XIc) unbounded for a subset of k entries.
  • Unbounded group leakage: Without constraints on continuous database entries, the mutual information I(X1, X2; Y ) can be unbounded.The example sets X2 = X1, making the entries perfectly correlated.
  • Privacy and utility: The section interprets MI-DP’s failure to impose a group-information bound as a potential utility advantage.The comparison concerns a crude utility bound that can be detrimental when n is not large.
  • Bounded domains: With cardinality bounds on database entries or outputs, MI-DP does provide an upper bound on information leaked from a group.The paper derives this bound for any subset I of size k.

6. VARIATIONS OF DIFF. PRIVACY

The paper adapts MI-DP to several differential-privacy variants, including personalized, free-lunch, Bayesian, and adversarial privacy. These adaptations reveal different trade-offs involving priors, correlations, strength, and utility.

  • Variant definitions: MI-DP can be adapted to correspond to multiple proposed variations of differential privacy.The section treats personalized, free-lunch, Bayesian, and adversarial privacy.
  • Free-lunch privacy: Free-lunch MI-DP bounds information between arbitrary disjoint index sets, making it stronger but potentially utility-poor.Its output information is bounded by ε regardless of distribution and prior knowledge.
  • Bayesian privacy: Bayesian differential privacy addresses correlated databases by assuming a prior distribution and protecting against adversaries with varying background knowledge.Maximizing the MI-DP condition over database distributions removes the Bayesian prior assumption and strengthens the notion.
  • Adversarial privacy: Adversarial privacy assumes a database prior, avoids neighboring-instance restrictions, and imposes an asymmetric certainty constraint.The paper notes that this constraint implies a mutual-information bound but is not fully captured by the MI-DP variant.

7. RÉNYI ENTROPY GENERALIZATION

The paper generalizes the mutual-information analysis using Rényi information measures. It establishes upper bounds for α-mutual information under ε-DP and notes equivalences among several Rényi-information definitions after maximizing over database distributions.

  • Generalization: α-mutual information generalizes mutual information using Rényi information measures, with Shannon mutual information recovered at α = 1.The paper adopts Sibson’s proposal and describes the associated conditional Rényi divergence.
  • Upper bound: ε-DP implies an upper bound on α-mutual information for every α ≥0, database index i, and remainder assignment x−i.The bound is stated in Lemma 4 and proved by fixing the remainder event.
  • Shannon specialization: For α = 1, the α-mutual-information bound reduces to the Shannon mutual-information bound I(Xi; Y |U) ≤ ε.This specializes the general result to the paper’s MI-DP quantity.
  • Equivalence: After maximizing over database distributions, three discussed notions of α-mutual information are equivalent.The equivalence holds for α > 0.

A. PROOF OF PROPERTY 1

The proof uses convexity to reduce the maximization of relative entropy to endpoint-supported distributions, then identifies a symmetric binary extremizer. It also compares the resulting bound with prior small-ε estimates.

  • Convexity of f(x) = x ln x implies that the maximizing distribution places all mass at the endpoints of the allowed support interval.
  • Computing E[Z ln Z] for this endpoint-supported distribution yields the desired result.
  • The extremum is achieved by a symmetric pair of binary distributions, for which D(P∥Q) = D(Q∥P).
  • Prior bounds show that (ε, 0)-closeness implies roughly ε^2 nats of Kullback-Leibler divergence for small ε, within a factor of two.

B. PROOF OF PROPERTY 3

The proof establishes the relaxed closeness property by treating the two likelihood inequalities symmetrically and applying bounds to an event and its complement. Algebraic rearrangement completes the argument.

  • The proof begins by assuming P and Q are (ε, δ)-close and aims to show that they are (ε′, δ′)-close for every event A.
  • By symmetry, it suffices to establish only inequality (83).
  • One inequality is obtained directly from (5), while the other applies (6) to the complement A^c.
  • Substituting P(A^c) = 1 − P(A) and Q(A^c) = 1 − Q(A), then rearranging, produces the needed bound.
  • The final case split uses (88) or (89), depending on the relation between ε and ε′, to establish (85).

C. PROOF OF LEMMA 2

The proof reduces the capacity–total-variation trade-off to binary channels and then uses symmetrization and convexity to identify binary symmetric channels as extremal. The resulting capacity formula is inverted and relaxed using entropy bounds.

  • The argument reduces the claim to randomized mechanisms with binary input and binary output.This reduction is stated as sufficient for the proof.
  • For a one-entry database, ε-MI-DP is expressed through a bound on the channel capacity of PY|X.
  • A binary channel is parametrized by two parameters, then paired with a complementary channel and symmetrized by convex combination.
  • The original, complementary, and symmetrized channels have the same total variation between conditional output distributions.
  • Convexity makes the binary symmetric channel lower-capacity than its paired channels, so it is extremal with respect to capacity and total variation.Every binary channel therefore has a binary symmetric channel with the same capacity and at least as large total variation.
  • The proof applies the binary symmetric channel capacity formula, inverts it, and obtains a relaxed bound using the second-order Taylor expansion of binary entropy.An alternative argument derives the looser bound from the information-ball geometry and Pinsker’s inequality.

D. PROOF OF LEMMA 3

The proof bounds conditional mutual information under differential privacy by fixing the other database entries and analyzing the resulting pair of conditional distributions. It uses separate finite-alphabet arguments and a continuity bound for conditional entropy.

  • Two proof arguments handle finite database-entry alphabets and finite query-response alphabets, respectively.
  • Because conditional mutual information averages over X−i, the proof fixes x−i arbitrarily and analyzes the induced pair (X̃, Ỹ).
  • Databases that differ only in entry i are neighbors, allowing the differential-privacy assumption to control the corresponding conditional output distributions.
  • When |Y| is finite, the constructed response variable satisfies |Ỹ| = |Y|, and mutual information is decomposed as I(X̃; Ỹ) = H(Ỹ) − H(Ỹ | X̃).
  • A continuity lemma bounds conditional-entropy differences for distributions on U × V when |U| is finite.The proof obtains the lemma through a common-distribution construction based on total variation and bounds the resulting non-negative terms.
  • The final argument applies the continuity lemma to the constructed distributions and combines it with the preceding bounds.
Loading 1608.03677v1…