On the `Semantics' of Differential Privacy: A Bayesian Formulation

Introduction

Privacy is an increasingly important aspect of data publishing. Reasoning about privacy, however, is fraught with pitfalls. One of the most significant is the auxiliary information (also called external knowledge, background knowledge, or side information) that an adversary gleans from other channels such as the web, public records, or domain knowledge. Schemes that retain privacy guarantees in the presence of independent releases are said to compose securely. The terminology, borrowed from cryptography (which borrowed, in turn, from software engineering), stems from the fact that schemes that compose securely can be designed in a stand-alone fashion without explicitly taking other releases into account. Thus, understanding independent releases is essential for enabling modular design. In fact, one would like schemes that compose securely not only with independent instances of themselves, but with arbitrary external knowledge.

Certain randomization-based notions of privacy (such as differential privacy, due to Dwork, McSherry, Nissim, and Smith ) are viewed as providing meaningful guarantees even in the presence of arbitrary side information. In this paper. we give a precise formulation of this statement. First, we provide a Bayesian formulation of “pure” differential privacy which explicitly models side information. Second, we prove that the relaxed definitions of Blum et al. , Dwork et al. and Machanavajjhala et al. imply the Bayesian formulation. The proof is non-trivial, and relies on the “continuity” of Bayes’ rule with respect to certain distance measures on probability distributions. Our result means that techniques satisfying the relaxed definitions can be used with the same sort of assurances as in the case of pure differentially-private algorithms, as long parameters are set appropriately. Specifically, $(\epsilon,\delta)$-differential privacy provides meaningful guarantees whenever $\delta$, the additive error parameter, is smaller than about $\epsilon^{2}/n$, where $n$ is the size of the data set.

After introducing the basic definitions, we state and discuss our main results in Section 2. In Section 2.1, we relate our approach to other efforts—subsequent to the initial version of this work—that sought to pin down mathematical precise formulations of the “meaning” of differential privacy. Section 3 proves our main theorems. Along the way, we develop lemmas about $(\epsilon,\delta)$-indistinguishability—the notion of similarity that underlies $(\epsilon,\delta)$-differential privacy—-that we believe are of independent interest. The most useful of these, which we dub the Conditioning Lemma, is given in Section 3.3. Finally, we provide further discussion of our approach in Section 4.

1 Differential Privacy

Semantics of Differential Privacy

There is a crisp, semantically-flavoredThe use of the term “semantic” for definitions that deal directly with adversarial knowledge dates back to semantic security of encryption . interpretation of differential privacy, due to Dwork and McSherry, explained in : Regardless of external knowledge, an adversary with access to the sanitized database draws the same conclusions whether or not my data is included in the original database. One might hope for a stronger statement, namely that the adversary draws the same conclusions whether or not the data is used at all. However, such a strong statement is impossible to provide in the presence of arbitrary external information (Dwork and Naor , Dwork ; see also Kifer and Machanavajjhala ), as illustrated by the following example.

Consider a clinical study that explores the relationship between smoking and lung disease. A health insurance company who had no a priori understanding of that relationship might dramatically alter its “beliefs” (as encoded by insurance premiums) to account for the results of the study. The study would cause the company to raise premiums for smokers and lower them for nonsmokers, regardless of whether they participated in the study. In this case, the conclusions drawn by the company about the riskiness of any one individual (say Alice) are strongly affected by the results of the study. This occurs regardless of whether Alice’s data are included in the study. $\diamondsuit$

When the mechanism ${\cal A}$ is interactive, the definition of $\mathcal{A}$ depends on the adversary’s choices; for legibility we omit the dependence on the adversary in the notation. Also, for simplicity, we discuss only discrete probability distributions. Our results extend directly to the interactive, continuous case.

Given a particular transcript $t$, we say privacy has been breached if the adversary would draw different conclusions about the world and, in particular, about a person $i$, depending on whether or not $i$’s data was used. One could formally define “different” in many ways. In this paper, we choose a weak (but popular) measure of distance between probability distributions, namely statistical difference. We say the adversary has learned something, if for any transcript $t$ the distributions $\bar{b}_{0}[\cdot|t]$ and $\bar{b}_{i}[\cdot|t]$ are far apart in statistical difference. We would like to avoid this from happening for any potential participant. This is captured by the following definition.

Our formulation of semantic privacy is inspired by Dwork and McSherry’s interpretation of differential privacy . We now formally show that the notions of $\epsilon$-differential privacy (Definition 1.1) and $\epsilon$-semantic privacy (Definition 2.1) are essentially equivalent.

For all $\epsilon>0$, $\epsilon$-differential privacy implies $\bar{\epsilon}$-semantic privacy, where $\bar{\epsilon}=e^{\epsilon}-1$. For $0<\epsilon\leq 0.45$, $\epsilon/2$-semantic privacy implies $3\epsilon$-differential privacy.

The proof of this and all other results in this section may be found in Section 3.

We can extend the previous Bayesian formulation to capture situations where bad events can occur with some negligible probability. Specifically, we formulate $(\epsilon,\delta)$-semantic privacy and show that it is closely related to $(\epsilon,\delta)$-differential privacy.

The $(\epsilon,\delta)$-privacy definition is most interesting when $\epsilon\gg\delta$, since every $(\epsilon,\delta)$-private algorithm is also $(0,\delta+(e^{\epsilon}-1))$-differentially private. Below, we assume $\epsilon>\delta$. In fact, many of our results are meaningful only when $\delta$ is less than $1/n$, while $\epsilon$ must generally be much larger than $1/n$ to allow for useful algorithms.

If $\epsilon,\delta>0$ and $\delta<(1-e^{-\epsilon})^{2}/n$, then ($\epsilon,\delta$)-differential privacy implies $(\epsilon^{\prime},\delta^{\prime})$-semantic privacy on databases of size $n$ with $\epsilon^{\prime}=e^{3\epsilon}-1+2\sqrt{n\delta}$ and $\delta^{\prime}=4\sqrt{n\delta}$.

If $\epsilon,\delta>0$ and $\epsilon\leq 0.45$, then $(\epsilon,\delta)$-semantic privacy implies $(3\epsilon,2\delta)$-differential privacy.

In Appendix B, we discuss a stronger notion of $(\epsilon,\delta)$-semantic privacy and show that $(\epsilon,\delta)$-differential privacy need not imply this stronger semantic privacy guarantee.

The implications in Theorems 2.2 and 2.4 would not hold if differential privacy were defined in terms of statistical difference (total variation distance) or mutual information instead of the multiplicative metric used in Definitions 1.1 and 1.2. For example, one could change the last line of the Definition 1.2 to

In the original paper on differential privacy, Dwork et al. defined a notion of “semantic” privacy that involved comparing the prior and posterior distributions of the adversary. In the language of the preceding section, they require that $\mathbf{SD}\left({{b[\cdot]\ ,\ \bar{b}_{i}[\cdot|t]\ }}\right)\leq\epsilon$ for a subclass of belief distributions, called “informed beliefs”, in which all but one of the data set entries are fixed (constant). They show that this definition is equivalent to differential privacy. Kifer and Machanavajjhala use this prior-to-posterior approach to generalize differential privacy to other settings.

However, the impossibility results of Dwork and Naor and Kifer and Machanavajjhala , exemplified by the smoking example in Example 1, imply that no mechanism that provides nontrivial information about the data set satisfies such a prior-to-posterior definition for all distributions.

This impossibility motivated the posterior-to-posterior comparison espoused in this paper, and subsequently generalized by Bassily et al. . In contrast to the prior-to-posterior approach, the framework discussed in this paper does generalize to arbitrary distributions on the data (and, hence, to arbitrary side information). Bassily et al. suggest the term “inference-based” for definitions which explicitly discuss the posterior distributions constructed by Bayesian adversaries.

Hypothesis Testing.

where $\alpha$ is the significance level (maximum type-I error) and $1-\beta$ is the power (maximum type-II error) of the test. In other words, the test rejects the hypothesis with approximately the same probability regardless of whether the hypothesis is true. This perspective was extended to $(\epsilon,\delta)$-differential privacy by Hall et al. .

This is a reasonable requirement. Note, however, that it holds only for product distributions, which limits its applicability. More importantly, a very similar statement can be proven for the statistical difference-based definition discussed in Remark 1. Specifically, one can show that

when the mechanism satisfies the definition of Remark 1. Equation (4) has the same natural language interpretation as equation (5), namely, “the test rejects the hypothesis with approximately the same probability regardless of whether the hypothesis is true”. However, as mentioned in the Remark 1, the statistical difference-based definition allows mechanisms that publish detailed personal data in the clear. This makes the meaning of a hypothesis-testing-based definition hard to evaluate intuitively. We hope the definitions provided here are easier to interpret.

Proofs of Main Results

We begin this section by defining $(\epsilon,\delta)$-indistinguishability and stating a few of its basic properties (Section 3.1, with proofs in Appendix A). Section 3.2 gives the proof of our main result for $\epsilon$-differential privacy. In Section 3.3 we state and prove the Conditioning Lemma, the main tool which allows us to prove our results about $(\epsilon,\delta)$-differential privacy (Section 3.4).

The relaxed notions of $(\epsilon,\delta)$-differential privacy implicitly uses a two-parameter distance measure on probability distributions (or random variables) which we call $(\epsilon,\delta)$-indistinguishability. In this section, we develop a few basic properties of this measure. These properties listed in Lemma 3.3 will play an important role in establishing the proofs of Theorems 2.2 and 2.4

Two random variables $X,Y$ taking values in a set $D$ are $(\epsilon,\delta)$-indistinguishable if for all sets $S\subseteq D$,

We will also be using a variant of $(\epsilon,\delta)$-indistinguishability, which we call point-wise $(\epsilon,\delta)$-indistinguishability. Lemma 3.3 (Parts 1 and 2) shows that $(\epsilon,\delta)$-indistinguishability and point-wise $(\epsilon,\delta)$-indistinguishability are almost equivalent.

Two random variables $X$ and $Y$ are point-wise $(\epsilon,\delta)$-indistinguishable if with probability at least $1-\delta$ over $a$ drawn from either $X$ or $Y$, we have:

Indistinguishability satisfies the following properties:

If $X,Y$ are point-wise $(\epsilon,\delta)$-indistinguishable then they are $(\epsilon,\delta)$-indistinguishable.

If $X,Y$ are $(\epsilon,\delta)$-indistinguishable then they are point-wise $\left(2\epsilon\ ,\ \delta\cdot\frac{2}{1-e^{-\epsilon}}\right)$-indistinguishable.

Let $X$ be a random variable on $D$. Suppose that for every $a\in D$, $\mathcal{A}(a)$ and $\mathcal{A}^{\prime}(a)$ are $(\epsilon,\delta)$-indistinguishable (for some randomized algorithms $\mathcal{A}$ and $\mathcal{A}^{\prime}$). Then the pairs $(X,\mathcal{A}(X))$ and $(X,\mathcal{A}^{\prime}(X))$ are $(\epsilon,\delta)$-indistinguishable.

Let $X$ be a random variable. Suppose with probability at least $1-\delta_{1}$ over $a\sim X$, $\mathcal{A}(a)$ and $\mathcal{A}^{\prime}(a)$ are $(\epsilon,\delta)$-indistinguishable (for some randomized algorithms $\mathcal{A}$ and $\mathcal{A}^{\prime}$). Then the pairs $(X,\ \mathcal{A}(X))$ and $(X,\ \mathcal{A}^{\prime}(X))$ are $(\epsilon,\delta+\delta_{1})$-indistinguishable.

If $X,Y$ are $(\epsilon,\delta)$-indistinguishable (or $X,Y$ are point-wise $(\epsilon,\delta)$-indistinguishable), then $\mathbf{SD}\left({{X,Y}}\right)\leq\bar{\epsilon}+\delta$, where $\bar{\epsilon}=e^{\epsilon}-1$.

2 Case of ϵitalic-ϵ\epsilon-Differential Privacy: Proof of Theorem 2.2

$\epsilon/2$-differential privacy implies $\bar{\epsilon}$-semantic privacy, where $\bar{\epsilon}=e^{\epsilon}-1$. $\epsilon/2$-semantic privacy implies $3\epsilon$-differential privacy as long as $\epsilon\leq 0.45$.

This implies that the random variables (distributions) $\bar{b}_{0}[\cdot|t]$ and $\bar{b}_{i}[\cdot|t]$ are point-wise $(\epsilon,0)$-indistinguishable. Applying Lemma 3.3 (Part 5) with $\delta=0$, gives $\mathbf{SD}\left({{\bar{b}_{0}[\cdot|t],\bar{b}_{i}[\cdot|t]}}\right)\leq\bar{\epsilon}$. Repeating the above arguments for every belief distribution, for every $i$, and for every $t$, shows that $\mathcal{A}$ is $\bar{\epsilon}$-semantically private.

3 A Useful Tool: The Conditioning Lemma

We will use the following lemma to establish connections between $(\epsilon,\delta)$-differential privacy and $(\epsilon,\delta)$-semantic privacy. Let $B|_{A=a}$ denote the conditional distribution of $B$ given that $A=a$ for jointly distributed random variables $A$ and $B$.

Suppose the pair of random variables $(A,B)$ is $(\epsilon,\delta)$-indistinguishable from the pair $(A^{\prime},B^{\prime})$. Then, for $\hat{\epsilon}=3\epsilon$ and for every $\hat{\delta}>0$, the following holds: with probability at least $1-\delta^{\prime\prime}$ over $t\sim B$ (or, alternatively, over $t\sim B^{\prime}$), the random variables $A|_{B=t}$ and $A^{\prime}|_{B^{\prime}=t}$ are $(\hat{\epsilon},\hat{\delta})$-indistinguishable, where $\delta^{\prime\prime}=\frac{2\delta}{\hat{\delta}}+\frac{2\delta}{1-e^{-\epsilon}}$.

We can satisfy the conditions of the preceding lemma by setting $\hat{\delta}=\delta^{\prime\prime}=O(\sqrt{\delta})$ for any constant $\epsilon$. However, the proof of our main theorem will use a slightly different setting (with $\delta^{\prime\prime}$ smaller than $\hat{\delta}$).

Let $(A,B)$ and $(A^{\prime},B^{\prime})$ take values in the set $D\times E$. In the remainder of the proof, we will use the notation $A|_{t}$ for $A|_{B=t}$ and $A^{\prime}|_{t}$ for $A^{\prime}|_{B^{\prime}=t}$. Define,

To prove the lemma, it suffices to show that the probabilities $\Pr[B\in Bad_{1}\cup Bad_{2}]$ and $\Pr[B^{\prime}\in Bad_{1}\cup Bad_{2}]$ are each at most $\delta^{\prime\prime}$. To do so, we first consider the set

We will separately bound the probabilities of $Bad_{0}$, $Bad_{1}^{\prime}=Bad_{1}\setminus Bad_{0}$ and $Bad_{2}^{\prime}=Bad_{2}\setminus Bad_{0}$.

To bound the mass of $Bad_{0}$, note that $B$ and $B^{\prime}$ are $(\epsilon,\delta)$-indistinguishable (since they are functions of $(A,B)$ and $(A^{\prime},B^{\prime})$)Note: Even if we started with the stronger assumption that the pairs $(A,B)$ and $(A^{\prime},B^{\prime})$ are point-wise indistinguishable, we would still have to make a nontrivial argument to bound $Bad_{0}$, since point-wise indistinguishability is not, in general, closed under postprocessing.. Since $(\epsilon,\delta)$-indistinguishability implies point-wise $(2\epsilon,\frac{2\delta}{1-e^{-\epsilon}})$-indistinguishability (Lemma 3.3, Part 2), we have

We now turn to $Bad_{1}^{\prime}=Bad_{1}\setminus Bad_{0}$. For each $t\in Bad_{1}^{\prime}$, let $S_{t}$ be any set that witnesses $t$’s membership in $Bad_{1}$ (that is, for which $\Pr[A|_{t}\in S_{t}]$ exceeds $e^{\hat{\epsilon}}\Pr[A^{\prime}|_{t}\in S_{t}]+\hat{\delta}$). Consider the critical set

Intuitively, this set will have large mass if $Bad_{1}^{\prime}$ does. Specifically, by the definition of $S_{t}$, we get a lower bound on the probability of $T_{1}$:

Because $Bad_{1}^{\prime}$ does not contain points in $Bad_{0}$, we know that $\Pr[B=t]\geq e^{-2e}\Pr[B^{\prime}=t]$. Substituting this into the bound above and using the fact that $\hat{\epsilon}=3\epsilon$ and $\Pr[A^{\prime}|_{t}\in S_{t}]=\Pr[A^{\prime}\in S_{t}\,|\,B^{\prime}=t]$, we get

By $(\epsilon,\delta)$-indistinguishability, $\Pr[(A,B)\in T_{1}]\leq e^{\epsilon}\Pr[(A^{\prime},B^{\prime})\in T_{1}]+\delta$. Combining the upper and lower bounds on the probability that $(A,B)\in T_{1}$, we have $\hat{\delta}\Pr[B\in Bad_{1}^{\prime}]\leq\delta$, which implies that

By a similar argument, one gets that $\Pr[B\in Bad_{2}^{\prime}]\leq\delta/\hat{\delta}.$ Finally,

By symmetry, we also have $\Pr[B^{\prime}\in Bad_{1}\cup Bad_{2}]\leq\frac{2\delta}{1-e^{-\epsilon}}+\frac{2\delta}{\hat{\delta}}$. Therefore, with probability at least $1-\delta^{\prime\prime}$, $A|_{t}$ and $A^{\prime}|_{t}$ are $(\hat{\epsilon},\hat{\delta})$-indistinguishable, as claimed. ∎

4 The General Case: Proof of Theorem 2.4

If $\epsilon,\delta>0$ and $\delta<(1-e^{-\epsilon})^{2}/n$, then ($\epsilon,\delta$)-differential privacy implies $(\epsilon^{\prime},\delta^{\prime})$-semantic privacy on databases of size $n$ with $\epsilon^{\prime}=e^{3\epsilon}-1+2\sqrt{n\delta}$ and $\delta^{\prime}=4\sqrt{n\delta}$.

If $\epsilon,\delta>0$ and $\epsilon\leq 0.45$, then $(\epsilon,\delta)$-semantic privacy implies $(3\epsilon,2\delta)$-differential privacy.

To complete the proof of (1), recall that $(\hat{\epsilon},\hat{\delta})$-indistinguishability implies statistical distance at most $e^{3\hat{\epsilon}}-1+\hat{\delta}=\epsilon^{\prime}$.

Further Discussion

Theorem 2.4 states that the relaxations of differential privacy in some previous work still provide meaningful guarantees in the face of arbitrary side information. This is not the case for all possible relaxations, even very natural ones, as noted in Remark 1.

We first define a weakening of Definition 2.3 so that it only holds for specific belief distributions.

Let $\mathcal{A}$ be a randomized algorithm. Let

We now discuss a simple consequence of the above theorem to the technique of adding noise according to local sensitivity of a function.

Let $Lap(\lambda)$ denote the Laplacian distribution. This distribution has density function $h(y)\propto\exp(-|y|/\lambda)$, mean , and standard deviation $\lambda$. Using the Laplacian noise addition procedure of , along with Theorem 4.2 we getSimilar corollaries could be derived for other differential privacy mechanisms like those that add Gaussian noise instead of Laplacian noise.,

The approach discussed here was generalized significantly by Bassily et al. ; we refer to their work for a detailed discussion.

Acknowledgements

We are grateful for helpful discussions with Cynthia Dwork, Daniel Kifer, Ashwin Machanvajjhala, Frank McSherry, Moni Naor, Kobbi Nissim, and Sofya Raskhodnikova.

References

Appendix

Appendix A Proof of Lemma 3.3

Proof of Part 1. Let $Bad$ be the set of bad values of $a$, that is

By definition, $\Pr[X\in Bad]\leq\delta$. Now consider any set $S$ of outcomes.

The first term is at most $e^{\epsilon}\Pr[Y\in S\setminus Bad]\leq e^{\epsilon}\Pr[Y\in S]$. Hence, $\Pr[X\in S]\leq e^{\epsilon}\Pr[Y\in S]+\delta$, as required. The case of $\Pr[Y\in S]$ is symmetric. Therefore, $X$ and $Y$ are $(\epsilon,\delta)$-indistinguishable.

Proof of Part 2. Let $S=\{a\,:\,\Pr[X=a]>e^{2\epsilon}\Pr[Y=a]\}$. Then

By $(\epsilon,\delta)$ indistinguishability, we have $\delta\geq\Pr[X\in S]-e^{\epsilon}\Pr[Y\in S]>(e^{2\epsilon}-e^{\epsilon})\Pr[Y\in S]$. Equivalently,

Now consider the set $S^{\prime}=\{a\,:\,\Pr[X=a]<e^{-2\epsilon}\Pr[Y=a]\}$. A symmetric argument to the one above shows that $\Pr[X\in S^{\prime}]<\delta/(e^{2\epsilon}-e^{\epsilon})$. Again using indistinguishability, we get

The bound of (8) is always larger than that of (7), so we have $\Pr[Y\in S\cup S^{\prime}]\leq\delta\cdot\frac{2e^{\epsilon}}{e^{\epsilon}-1}$. We can get the same bound on $\Pr[X\in S\cup S^{\prime}]$ by symmetry. Therefore, with probability at least $1-\delta\cdot\frac{2e^{\epsilon}}{e^{\epsilon}-1}$ for $a$ drawn from the distribution of either $X$ or $Y$ we have: $e^{-2\epsilon}\Pr[Y=a]\leq\Pr[X=a]\leq e^{2\epsilon}\Pr[Y=a]$.

Proof of Part 3. Let $(X,{\cal A}(X))$ and $(X,{\cal A}^{\prime}(X))$ be random variables on $D\times E$. Let $S$ be an arbitrary subset of $D\times E$ and, for every $a\in D$, define $S_{a}=\{b\in E\,:\,(a,b)\in S\}$.

By symmetry, we also have $\Pr[(X,{\cal A}^{\prime}(X))\in S]<\delta+e^{\epsilon}\Pr[(X,{\cal A}(X))\in S]$. Since the above inequalities hold for every selection of $S$, implies that $(X,{\cal A}(X))$ and $(X,{\cal A}^{\prime}(X))$ are $(\epsilon,\delta)$-indistinguishable.

Proof of Part 4. Let $(X,{\cal A}(X))$ and $(X,{\cal A}^{\prime}(X))$ be random variables on $D\times E$. Let $T\subset D$ be the set of $a$’s for which ${\cal A}(a)\leq e^{\epsilon}{\cal A}^{\prime}(a)$. Now, let $S$ be an arbitrary subset of $D\times E$ and, for every $a\in D$, define $S_{a}=\{b\in E\,:\,(a,b)\in S\}$.

By symmetry, we also have $\Pr[(X,{\cal A}^{\prime}(X))\in S]<\delta+\delta_{1}+e^{\epsilon}\Pr[(X,{\cal A}(X))\in S]$. Since the above inequalities hold for every selection of $S$, implies that $(X,{\cal A}(X))$ and $(X,{\cal A}^{\prime}(X))$ are $(\epsilon,\delta+\delta_{1})$-indistinguishable.

Proof of Part 5. Let $X$ and $Y$ be random variables on $D$. By definition $\mathbf{SD}\left({{X,Y}}\right)=\max_{S\subset D}|\Pr[X\in S]-\Pr[Y\in S]|$. For any set $S\subset D$,

This implies that $|\Pr[X\in S]-\Pr[Y\in S]|\leq\bar{\epsilon}+\delta$. Since the above inequality holds for every $S\subset D$, it immediately follows that the statistical difference between $X$ and $Y$ is at most $\bar{\epsilon}+\delta$. ∎

Appendix B Another View of Semantic Privacy

In this section, we discuss another possible definition of $(\epsilon,\delta)$-semantic privacy. Even though this definition seems to be the more desirable one, it also seems hard to achieve.

We prove that if the adversary has arbitrary beliefs, then $(\epsilon,\delta)$-differential privacy doesn’t provide any reasonable reality-oblivious $(\epsilon^{\prime},\delta^{\prime})$-semantic privacy guarantee.

($\epsilon,\delta$)-differential privacy does not imply reality-oblivious $(\epsilon^{\prime},\delta^{\prime})$-semantic privacy for any reasonable values of $\epsilon^{\prime}$ and $\delta^{\prime}$.

The counterexample of Theorem Theorem A.2 implies that adversaries whose belief distribution is very different from the real database may observe a large change in their posterior distributions. We do not consider this a ‘violation of “privacy”, since the issue lies in the incorrect beliefs, not the mechanism per se.