Differential Privacy: on the trade-off between Utility and Information Leakage

Mário S. Alvim; Miguel E. Andrés; Konstantinos Chatzikokolakis; Pierpaolo Degano; Catuscia Palamidessi

Source-linked AI summary

Differential Privacy: on the trade-off between Utility and Information Leakage

Mário S. Alvim, Miguel E. Andrés, Konstantinos Chatzikokolakis, Pierpaolo Degano, Catuscia Palamidessi

arXiv:1103.5188v3Mar 27, 2011cs.CRcs.DBcs.IT

TL;DR

The paper asks how differential privacy relates to information leakage and utility in randomized database queries. It models queries as information-theoretic channels, proves tight privacy and utility bounds, and gives a conditional construction of optimal private mechanisms.

Problem
The paper investigates how to characterize information leakage and utility while preserving differential privacy in statistical database queries.
Method
It models randomized queries as channels, uses min-entropy leakage, and analyzes oblivious mechanisms through their query and randomization components.
Results
Differential privacy implies tight bounds on information leakage and utility, and under stated conditions the constructed mechanism maximizes utility while preserving privacy.
Takeaways & Limitations
The framework integrates privacy and utility and provides a way to optimize utility under differential privacy for binary gain functions.
Takeaways & Limitations
The leakage results abstract from attacker side information by proving them for all prior distributions, while optimality of the construction requires structural conditions on the answer space.

Abstract

from arXiv · show

Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities that two adjacent datasets give the same answer is bound by e^epsilon. In the field of information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of Rényi min mutual information, a notion strictly related to the Bayes risk. In this paper, we show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of mutual information. We show that differential privacy implies a bound on the mutual information (but not vice-versa). Furthermore, we show that our bound is tight. Then, we consider the utility of the randomization mechanism, which represents how close the randomized answers are, in average, to the real ones. We show that the notion of differential privacy implies a bound on utility, also tight, and we propose a method that under certain conditions builds an optimal randomization mechanism, i.e. a mechanism which provides the best utility while guaranteeing differential privacy.

1 Introduction

The paper studies differential privacy through quantitative information flow, asking how privacy protection relates to leakage and how utility can be improved without losing privacy.

Differential privacy is motivated as a practical alternative to stronger privacy goals that are impossible or too restrictive for useful databases.
The analysis uses min-entropy to quantify leakage, with attacker side information represented by a prior over databases.
The paper models privacy and utility together to relate differential privacy, information leakage, and reported-answer quality.
The paper proves that ǫ-differential privacy bounds information leakage, with a tight bound holding for all prior distributions.
It also proves a differential-privacy bound on utility and, under certain conditions, constructs mechanisms maximizing utility while preserving privacy.

2 Background

This section introduces differential privacy, information-theoretic channels, Rényi min-entropy, and leakage as a one-try guessing advantage after observing outputs.

Differential privacy bounds the probability ratio for the same output on databases differing in at most one row by e^ǫ.
An information-theoretic channel consists of an input, an output, and conditional probabilities describing each output given each input.
Min-entropy is the limit of Rényi entropy as α approaches infinity and equals −log2 of the highest outcome probability.
Min-entropy leakage is the difference between prior and posterior min-entropy, with worst-case leakage maximized over input distributions.
The corresponding attacker makes one equality-guessing attempt, and conditional min-entropy captures success after observing the output.

3 A model of utility and privacy for statistical databases

The paper represents randomized database queries as information-theoretic channels, separating leakage about databases from utility about true query answers.

A database is a tuple of individual values, and adjacent databases differ in exactly one individual’s value.
A randomized query K maps databases to reported outputs and is represented by a channel of conditional output probabilities.
Leakage measures information about the complete database obtained from the reported answer, while utility measures information about the true answer.
When randomization is oblivious, the system decomposes into a query channel and a mechanism channel, making utility depend on the latter.
For individual privacy, the model fixes all other individuals’ values and varies only the individual of interest.

4 Leakage

The paper bounds min-entropy leakage caused by ε-differential privacy, proves the general bound tight, and derives stronger bounds when the output range is fixed or leakage concerns one individual.

Theorem 1 bounds min-entropy leakage for every input distribution using ε and the numbers u and v of individuals and values.
B(u, v, ε) is continuous in ε, equals 0 at ε = 0, and converges to u log2 v as ε approaches infinity.
For every u, v, and ε, some ε-differentially private mechanism attains B(u, v, ε) under the uniform input distribution.
With output range cardinality at most r, Proposition 2 provides a potentially smaller leakage bound than the unrestricted Theorem 1 bound.When r = v, the restricted bound can be much smaller than B(u, v, ε).
For v = 2 and u approaching infinity, the restricted bound approaches 1 while B(u, v, ε) approaches infinity.
The restricted result does not contradict tightness of B(u, v, ε), because tightness allows choosing the range whereas the restricted setting fixes its dimension.
The bounds do not hold in the reverse direction: arbitrarily low min-entropy leakage can coexist with failure of ε-differential privacy for every ε.A negligible-probability observation for one user and zero probability for another can produce this separation.
For a fixed individual and fixed values of all others, Theorem 2 gives a stronger leakage bound depending only on ε, not u or v.

5 Utility

The paper defines utility through expected gain after Bayesian remapping and derives tight differential-privacy utility bounds under regular graph conditions. It also gives a mechanism that is optimal under those conditions, while examples show that optimality depends on the answer-graph structure.

Utility definition: Utility is the expected gain of an oblivious randomization mechanism after the user remaps reported answers to maximize guessing success.The mechanism maps real answers to reported answers, while Bayesian post-processing selects the final guess.
Utility definition: Binary gain assigns value 1 to an exact answer and 0 to every incorrect answer, making all wrong answers equally bad.The paper focuses on this utility function because it assumes no distance structure on the answer domain.
Utility definition: H∞(Y | Z) = −log2 U(Y, Z), and min-entropy leakage satisfies I∞(Y ; Z) = H∞(X) + log2 U(Y, Z).Thus utility is directly connected to conditional min-entropy and leakage.
Utility bounds: Under single-orbit graph conditions and border-size assumptions, ε-differential privacy imposes a utility bound.The answer graph must have a regular structure, such as a ring or clique, and the bound depends on its maximum distance and connectivity conditions.
Utility bounds: The utility bound is tight: for every ε and answer set Y, some adjacency relation admits a differentially private mechanism achieving it.Optimality requires each nonempty distance border to have exactly the same size c.
Mechanism construction: The constructed mechanism is optimal under Theorem 4’s regularity conditions, but adding artificial adjacencies generally preserves privacy without preserving optimality.The smaller the augmented adjacency relation, the higher the resulting utility.

6 Related work

Related work connects differential privacy with information-theoretic leakage and utility, but this paper extends those connections to the full database universe and establishes an optimal leakage bound.

Information leakage: An earlier unpublished report bounded Shannon and min-entropy leakage for channels whose inputs are databases adjacent to a fixed database.Its min-entropy result corresponds to this paper’s Theorem 2.
Information leakage: Barthe and Köp̈f studied min-entropy leakage for the entire database universe but restricted attention to participation hiding and supplied a non-tight bound.Their end-to-end mechanisms correspond to the paper’s channel K.
Information leakage: Other work analyzed database privacy through integrity quantification or program-based leakage analysis without establishing the same differential-privacy relationship.These approaches used different leakage notions or did not attempt to relate leakage to differential privacy.
Utility: The geometric mechanism provides optimal utility for counting queries under a general utility framework that accommodates side information and user preferences.The paper’s results extend beyond the particular counting-query setting described in that work.

7 Conclusion and future work

The paper frames differential privacy as a privacy–utility trade-off, derives strict leakage and utility bounds, and gives an optimization method for binary-gain mechanisms. It leaves more generic gain functions for future work.

Conclusion: The paper integrates differential privacy, information leakage, and utility to study the trade-off between privacy protection and useful query answers.It models the setting through randomized functions and utility of oblivious mechanisms.
Conclusion: It derives a strict bound on information leakage for randomized functions satisfying ε-differential privacy.The conclusion presents this as one of the paper’s central results.
Conclusion: It provides a method to optimize utility while guaranteeing differential privacy when utility is measured with a binary gain function.The construction is stated for the binary-gain case.
Future work: Future work will seek bounds for more generic gain functions, potentially using the Kantorovich metric to compare prior and posterior secret distributions.The paper does not claim that this extension has already been established.

Notation

The notation models randomized computation as an information-theoretic channel with input and output variables represented by conditional-probability matrices. It also defines matrix transformations, partial-function images, and indexing conventions.

Channels and matrices: A channel matrix M represents conditional probabilities pB|A(b | a), with rows indexed by inputs and columns by outputs.Given M and input random variable A, the output variable B is determined.
Channels and matrices: The notation H∞(A | B(M, A)) denotes conditional min-entropy after passing A through channel M.The paper also uses I∞(A; B(M, A)) for the corresponding min-entropy leakage.
Matrix operations: M[l → k] denotes the matrix obtained by collapsing column l into column k.The transformation combines the entries of the two columns and leaves other columns unchanged.
Functions and indices: For a partial function ρ, its image excludes undefined outputs represented by ⊥.The image is the set of defined values ρ(a).
Functions and indices: The symbols i, h, and l typically index rows, while j and k typically index columns; max_j M is the maximum entry in column j.These conventions support the matrix calculations used in the proofs.

Proofs

The proofs use matrix transformations that normalize channel structure by placing column maxima on the diagonal and equalizing diagonal entries.

The first transformation places every column maximum on the diagonal of a square matrix.The second transformation makes all diagonal elements equal.

Leakage

The leakage analysis derives upper bounds on min-entropy leakage under differential privacy and shows that the principal bound is tight. It also considers restricted output ranges and individual-level leakage.

The paper proves an upper bound on min-entropy leakage for every ε-differentially private channel.The proof first transforms the channel into a square matrix with equal diagonal maxima while preserving differential privacy and leakage.
The leakage bound is tight: for every u, v, and ε, a differentially private randomized function achieves B(u, v, ε).The construction uses probabilities determined by graph distance and attains I∞(X; Z) = B(u, v, ε).
When the randomized function has range size at most r < v^u, the paper derives a potentially better leakage bound than the general bound.This addresses mechanisms whose answer range is smaller than the full query domain.
An ε-ratio condition on all input pairs also yields an upper bound on min-entropy leakage.This condition requires each output probability under one input to be at most e^ε times that under any other input.
Differential privacy bounds the min-entropy leakage about an individual for every fixed configuration of the remaining individuals.The result is stated for all D− ∈ Val^(u−1).

Utility

The utility analysis bounds the accuracy of differentially private mechanisms on regular graph structures and constructs optimal mechanisms under stronger symmetry conditions.

The matrix transformations preserve ε-differential privacy while equalizing diagonal entries and keeping each diagonal entry maximal in its column.These properties support the utility proof for channels with a single-orbit adjacency graph.
Under a single-orbit graph automorphism and a lower bound on nonempty distance borders, the paper derives an upper bound on utility.The graph condition provides a regular structure for analyzing randomized answers by distance from the true query result.
When every nonempty distance border has the same size c, the constructed mechanism is legal, ε-differentially private, and utility-optimal for uniform query outputs.Theorem 4 states that the mechanism maximizes utility under a uniform distribution of Y.
The utility bound is strict: for every ε and Y, some adjacency relation admits a mechanism that achieves the bound.Such a mechanism is optimal because it provides the maximum possible utility for the given ε.