---
abstract: 'In this note we give a precise formulation of “resistance to arbitrary side information” and show that several relaxations of differential privacy imply it. The formulation follows the ideas originally due to Dwork and McSherry, stated implicitly in [@Dw06]. This is, to our knowledge, the first place such a formulation appears explicitly. The proof that relaxed definitions (and hence the schemes of [@DKMMN06; @NRS07; @MKAGV08]) satisfy the Bayesian formulation is new.'
author:
- |
    Shiva Prasad KasiviswanathanAdam Smith\
    Department of Computer Science and Engineering\
    Pennsylvania State University\
    e-mail: [$\{$kasivisw,asmith$\}$@cse.psu.edu]{}\
bibliography:
- '../bibfiles/master.bib'
title: |
    A Note on Differential Privacy:\
    Defining Resistance to Arbitrary Side Information
---

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 which 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 [@DMNS06]) are believed to compose securely even in the presence of arbitrary side information. In this note we give a precise formulation of this statement. First, we provide a Bayesian formulation of differential privacy which makes its resistance to arbitrary side information explicit. Second, we prove that the relaxed definitions of [@DKMMN06; @MKAGV08] still 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 the recent techniques mentioned above [@DKMMN06; @CM06; @NRS07; @MKAGV08] can be used modularly with the same sort of assurances as in the case of strictly differentially-private algorithms.

Differential Privacy
--------------------

Databases are assumed to be vectors in $\mathcal{D}^n$ for some domain $\mathcal{D}$. The Hamming distance ${{d}}({{\mathrm{x}}},{{\mathrm{y}}})$ on $\mathcal{D}^n$ is the number of positions in which the vectors ${{\mathrm{x}}},{{\mathrm{y}}}$ differ. We let $\Pr[\cdot]$ and ${{\mathbb{E}}}[\cdot]$ denote probability and expectation, respectively. Given a randomized algorithm $\mathcal{A}$, we let $\mathcal{A}({{\mathrm{x}}})$ be the random variable (or, probability distribution on outputs) corresponding to input ${{\mathrm{x}}}$. If $\erert$ and $\Q$ are probability measure on a discrete space $D$, the [*statistical difference*]{} (a.k.a. [*total variation distance*]{}) between $\erert$ and $\Q$ is defined as: $${\mathbf{SD}{\left( {{\erert,\Q}} \right)}}= \max_{S \subset D}|\erert[S]-\Q[S)|.$$

\[def:ind\] A randomized algorithm ${\mathcal{A}}$ is said to be ${\epsilon}$-differentialy private if for all databases ${{\mathrm{x}}},{{\mathrm{y}}}\in \mathcal{D}^n$ at Hamming distance at most 1, and for all subsets $S$ of outputs $$\begin{aligned}
\Pr[{\mathcal{A}}({{\mathrm{x}}})\in S] \leq e^{{\epsilon}} \Pr[{\mathcal{A}}({{\mathrm{y}}})\in S].\end{aligned}$$

This definition states that changing a single individual’s data in the database leads to a small change in the [*distribution*]{} on outputs. Unlike more standard measures of distance such as total variation (also called statistical difference) or Kullback-Leibler divergence, the metric here is multiplicative and so even very unlikely events must have approximately the same probability under the distributions ${\mathcal{A}}({{\mathrm{x}}})$ and ${\mathcal{A}}({{\mathrm{y}}})$. This condition was relaxed somewhat in other papers [@DiNi03; @DwNi04; @BDMN05; @DKMMN06; @CM06; @NRS07; @MKAGV08]. The schemes in all those papers, however, satisfy the following relaxation [@DKMMN06]:

\[def:indd\] A randomized algorithm ${\mathcal{A}}$ is $({\epsilon},\delta)$-differentially private if for all databases ${{\mathrm{x}}},{{\mathrm{y}}}\in {{\mathcal{D}}}^n$ that differ in one entry, and for all subsets $S$ of outputs, $\Pr[{\mathcal{A}}({{\mathrm{x}}})\in S] \leq e^{{\epsilon}} \Pr[{\mathcal{A}}({{\mathrm{y}}})\in S]+\delta\,.$

The relaxations used in [@DwNi04; @BDMN05; @MKAGV08] were in fact stronger (i.e., less relaxed) than [Definition \[def:ind\]]{}. One consequence of the results below is that all the definitions are equivalent up to polynomial changes in the parameters, and so given the space constraints we work only with the simplest notion.[^1]

Semantics of Differential Privacy {#sec:bayes}
=================================

There is a crisp, semantically-flavored interpretation of differential privacy, due to Dwork and McSherry, and explained in [@Dw06]: [*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 data.*]{} (the use of the term “semantic” for such definitions dates back to semantic security of encryption [@GM84]). In this section, we develop a formalization of this interpretation and show that the definition of differential privacy used in the line of work this paper follows ([@DiNi03; @DwNi04; @BDMN05; @DMNS06]) is essential in order to satisfy the intuition.

We require a mathematical formulation of “arbitrary external knowledge”, and of “drawing conclusions”. The first is captured via a [*prior*]{} probability distribution $b$ on ${{\mathcal{D}}}^n$ ($b$ is a mnemonic for “beliefs”). Conclusions are modeled by the corresponding posterior distribution: given a transcript $t$, the adversary updates his belief about the database ${{\mathrm{x}}}$ using Bayes’ rule to obtain a posterior $\bar{b}$:

$$\begin{aligned}
 \label{eqn:bel}
\bar{b}[{{\mathrm{x}}}| t] = \frac{\Pr[{\mathcal{A}}({{\mathrm{x}}})=t] b[{{\mathrm{x}}}]}{\sum_{{\mathrm{y}}}\Pr[{\mathcal{A}}({{\mathrm{y}}})=t]b[{{\mathrm{y}}}]}\ . \end{aligned}$$

Note that in an interactive scheme, 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.

For a database ${{\mathrm{x}}}$, define ${{\mathrm{x}}}_{-i}$ to be the same vector where position $i$ has been replaced by some fixed, default value in $D$. Any valid value in $D$ will do for the default value. We can then imagine $n+1$ related games, numbered 0 through $n$. In Game 0, the adversary interacts with ${\mathcal{A}}({{\mathrm{x}}})$. This is the interaction that actually takes place between the adversary and the randomized algorithm ${\mathcal{A}}$. In Game $i$ (for $1\leq i \leq n$), the adversary interacts with ${\mathcal{A}}({{\mathrm{x}}}_{-i})$. Game $i$ describes the hypothetical scenario where person $i$’s data is not included.

For a particular belief distribution $b$ and transcript $t$, we can then define $n+1$ [*a posteriori*]{} distributions $\bar{b}_0,\dots,\bar{b}_n$, where the $\bar{b}_0$ is the same as $\bar{b}$ (defined in \[eqn:bel\]) and, for larger $i$, the $i$-th belief distribution is defined with respect to Game $i$: $$\bar{b}_i[{{\mathrm{x}}}| t] = \frac{\Pr[{\mathcal{A}}({{\mathrm{x}}}_{-i})=t] b[{{\mathrm{x}}}]}{\sum_{{\mathrm{y}}}\Pr[{\mathcal{A}}({{\mathrm{y}}}_{-i})=t]b[{{\mathrm{y}}}]}.$$

Given a particular transcript $t$, the 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. It turns out that the exact measure of “different” here does not matter much. We chose the weakest notion that applies, namely statistical difference. We say there is a problem for transcript $t$ if 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 happening for any potential participant. This is captured by the following definition.

\[def:sem\] A randomized algorithm ${\mathcal{A}}$ is said to be ${\epsilon}$-semantically private if for all belief distributions $b$ on $\mathcal{D}^n$, for all databases ${{\mathrm{x}}}\in \mathcal{D}^n$, for all possible transcripts $t$, and for all $i = 1,\ldots,n$$\mathrm{:}$ $${\mathbf{SD}{\left( {{\bar{b}_0[{{\mathrm{x}}}|t]\ ,\  \bar{b}_i[{{\mathrm{x}}}|t]\ }} \right)}} \leq {\epsilon}.$$

Dwork and McSherry proposed the notion of semantic privacy, informally, and observed that it is equivalent to differential privacy. We now formally show that the notions of ${\epsilon}$-differential privacy (Definition \[def:ind\]) and ${\epsilon}$-semantic privacy (Definition \[def:sem\]) are very closely related.

(Dwork-McSherry) \[thm:eind\] ${\epsilon}$-differential privacy implies $\bar{\epsilon}$-semantic privacy, where $\bar{\epsilon}=e^{{\epsilon}}-1$. $\bar{\epsilon}/2$-semantic privacy implies $2{\epsilon}$-differential privacy.

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

A randomized algorithm is $({\epsilon},\delta)$-semantically private if for all belief distributions $b$ on $\mathcal{D}^n$, with probability at least $1-\delta$ over pairs $({{\mathrm{x}}},t)$, where the database ${{\mathrm{x}}}$ is drawn according to $b$, and transcript $t$ is drawn according to ${\mathcal{A}}({{\mathrm{x}}})$, and for all $i =1,\dots,n$: $${\mathbf{SD}{\left( {{\bar{b}_0[{{\mathrm{x}}}|t]\ ,\  \bar{b}_i[{{\mathrm{x}}}|t]\ }} \right)}} \leq {\epsilon}.$$

This definition is only interesting when ${\epsilon}>\delta$; otherwise just use statistical difference $2\delta$ and leave ${\epsilon}=0$. Below, we assume ${\epsilon}>\delta$. In fact, in many of the proofs we will be assuming that $\delta$ is a negligible function (of $O(1/n^2)$). In Appendix A, we provide another related definition of $({\epsilon},\delta)$-semantic privacy.

\[thm:ind2sdp\] (${\epsilon},\delta$)-differential privacy implies $({\epsilon}',\delta')$-semantic privacy for arbitrary (not necessarily informed) beliefs with ${\epsilon}'=e^{3{\epsilon}}-1+2\sqrt{\delta}$ and $\delta' = O(n\sqrt{\delta})$. $(\bar{\epsilon}/2,\delta)$-semantic privacy implies $(2{\epsilon},2\delta)$-differential privacy with $\bar{\epsilon}=e^{{\epsilon}}-1$.

Some Properties of $({\epsilon},\delta)$-Differential Privacy
=============================================================

We now describe some properties of $({\epsilon},\delta)$-differential privacy that would be useful later on. This section could be of independent interest. Instead of restricting ourselves to outputs of randomized algorithms, we consider a more general definition of $({\epsilon},\delta)$-differential privacy.

\[$({\epsilon},\delta)$-indistinguishability\] Two random variables $X,Y$ taking values in a set $D$ are $({\epsilon},\delta)$-indistinguishable if for all sets $S\subseteq D$, $$\begin{aligned}
\Pr[X\in S] \leq e^{\displaystyle {\epsilon}} \Pr[Y\in S] + \delta \ \ \ \ \mbox{ and } \ \ \ \ \Pr[Y\in S] \leq e^{\displaystyle {\epsilon}} \Pr[X\in S] + \delta.\end{aligned}$$

We will also be using a simpler variant of $({\epsilon},\delta)$-indistinguishability, which we call [*point-wise*]{} $({\epsilon},\delta)$-indistinguishability. Claim \[lem:proof\] (Parts \[it:pw2ind\] and \[it:ind2pw\]) shows that $({\epsilon},\delta)$-indistinguishability and point-wise $({\epsilon},\delta)$-indistinguishability are almost equivalent.

\[Point-wise $({\epsilon},\delta)$-indistinguishability\] 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: $$e^{-{\epsilon}}\Pr[Y=a] \leq \Pr[X=a] \leq e^{{\epsilon}} \Pr[Y=a].$$

The following are useful facts about indistinguishability.[^2] \[lem:proof\]

\[it:pw2ind\] If $X,Y$ are point-wise $({\epsilon},\delta)$-indistinguishable then they are $({\epsilon},\delta)$-indistinguishable.

\[it:ind2pw\] If $X,Y$ are $({\epsilon},\delta)$-indistinguishable then they are point-wise $(2{\epsilon},\frac{2\delta}{e^{{\epsilon}}{\epsilon}})$-indistinguishable.

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

\[it:joint\] Let $X$ be a random variable. Suppose with probability at least $1-\delta$ over $a {\leftarrow}X$ $(a\,$ drawn from $X)$, ${\mathcal{A}}(a)$ and ${\mathcal{A}}'(a)$ are $({\epsilon},\delta)$-indistinguishable (for some randomized algorithms ${\mathcal{A}}$ and ${\mathcal{A}}'$). Then the pairs $(X,\ {\mathcal{A}}(X))$ and $(X,\ {\mathcal{A}}'(X))$ are $({\epsilon},2\delta)$-indistinguishable.

\[it:prob\] If $X,Y$ are $({\epsilon},\delta)$-indistinguishable and ${{\cal G}}$ is some randomized algorithm, then ${{\cal G}}(X)$ and ${{\cal G}}(Y)$ are $({\epsilon},\delta)$-indistinguishable.

\[it:sd\] If $X,Y$ are $({\epsilon},\delta)$-indistinguishable, then ${\mathbf{SD}{\left( {{X,Y}} \right)}} \leq \bar{\epsilon}+\delta$, where $\bar{\epsilon}=e^{{\epsilon}}-1$.

[*Proof of Part \[it:pw2ind\].*]{} Let $Bad$ be the set of [*bad*]{} values of $a$, that is $$Bad = \{a \,:\, \Pr[X=a] < e^{-{\epsilon}} \Pr[Y=a] \mbox{ or }  \Pr[X=a]> e^{{\epsilon}} \Pr[Y=a] \}.$$ By definition, $\Pr[X\in Bad]\leq \delta$. Now consider any set $S$ of outcomes. $$\Pr[X\in S] \leq \Pr[X \in S \setminus Bad] + \Pr[X\in Bad].$$ 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 \[it:ind2pw\].*]{} Let $S= \{a \,:\, \Pr[X=a] > e^{2{\epsilon}} \Pr[Y=a]\}$. Then, $$\Pr[X \in S] > e^{2{\epsilon}} \Pr[Y \in S] > e^{{\epsilon}}(1+{\epsilon})\Pr[Y \in S] \Rightarrow \Pr[X \in S] - e^{{\epsilon}}\Pr[Y \in S] > {\epsilon}e^{{\epsilon}} \Pr[Y \in S].$$ Since, $\Pr[X \in S] - e^{{\epsilon}}\Pr[Y \in S] \leq \delta$, we mush have ${\epsilon}e^{{\epsilon}} \Pr[Y \in S] < \delta$. A similar argument when considering the set $S'=\{a \,:\, \Pr[X=a] < e^{-2{\epsilon}} \Pr[Y=a]\}$ shows that ${\epsilon}e^{{\epsilon}} \Pr[Y \in S'] < \delta$. Putting both arguments together, $\Pr[Y \in S \cup S'] \leq 2\delta/({\epsilon}e^{{\epsilon}})$. Therefore, with probability at least $1-2\delta/(e^{{\epsilon}}{\epsilon})$ for any $a$ drawn from 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 \[it:ajoint\].*]{} Let $(X,{{\cal A}}(X))$ and $(X,{{\cal A}}'(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\}$. $$\begin{aligned}
\Pr[(X,{{\cal A}}(X)) \in S] &\leq& \sum_{a \in D}\Pr[{{\cal A}}(X) \in S_a \,:\, X=a]\Pr[X=a] \\
& < & \sum_{a \in D}(e^{{\epsilon}}\Pr[{{\cal A}}'(X) \in S_a \,:\, X=a]+\delta)\Pr[X=a] \\
& < & \delta + e^{{\epsilon}}\Pr[(X,{{\cal A}}'(X)) \in S].\end{aligned}$$ By symmetry, we also have $\Pr[(X,{{\cal A}}'(X)) \in S] < \delta+\Pr[(X,{{\cal A}}(X)) \in S]$. Since $S$ was arbitrary, $(X,{{\cal A}}(X))$ and $(X,{{\cal A}}'(X))$ are $({\epsilon},\delta)$-indistinguishable.\
[*Proof of Part \[it:joint\].*]{} Let $(X,{{\cal A}}(X))$ and $(X,{{\cal A}}'(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}}'(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\}$. $$\begin{aligned}
\Pr[(X,{{\cal A}}(X)) \in S] &\leq& \Pr[X \notin T] + \sum_{a \in T}\Pr[{{\cal A}}(X) \in S_a \,:\, X=a]\Pr[X=a] \\
& < & \delta + \sum_{a \in T}(e^{{\epsilon}}\Pr[{{\cal A}}'(X) \in S_a \,:\, X=a]+\delta)\Pr[X=a] \\
& < & 2\delta + e^{{\epsilon}}\Pr[(X,{{\cal A}}'(X)) \in S].\end{aligned}$$ By symmetry, we also have $\Pr[(X,{{\cal A}}'(X)) \in S] < 2\delta+\Pr[(X,{{\cal A}}(X)) \in S]$. Since $S$ was arbitrary, $(X,{{\cal A}}(X))$ and $(X,{{\cal A}}'(X))$ are $({\epsilon},2\delta)$-indistinguishable.\
[*Proof of Part \[it:prob\].*]{} Let $D$ be some domain. A randomized procedure ${{\cal G}}$ is a pair ${{\cal G}}=(g,R)$, where $R$ is a random variable on some set $E$ and $g$ is a function from $D \times E$ to any set $F$. If $X$ is a random variable on $D$, then ${{\cal G}}(X)$ denotes the random variable on $F$ obtained by sampling $X \otimes R$ and applying $g$ to the result, where the symbol $\otimes$ denotes the tensor product. Now for any set $S \subset F$, $$\begin{aligned}
\lefteqn{\Pr[{{\cal G}}(X) \in S] - e^{{\epsilon}}\Pr[{{\cal G}}(Y) \in S]}\\ &=& \Pr[g(X \otimes R) \in S] - e^{{\epsilon}} \Pr[g(Y \otimes R) \in S] \\
&=&\Pr[X\otimes R \in g^{-1}(S)] -e^{{\epsilon}} \Pr[Y\otimes R \in g^{-1}(S)] \\
& \leq & \sum_{r \in E} \Pr[X \in S_r \,:\, R=r]\Pr[R=r] - e^{{\epsilon}} \sum_{r \in E} \Pr[Y \in S_r \,:\, R=r]\Pr[R=r] \\
& =& \sum_{r \in E}(\Pr[X \in S_r \,:\, R=r]-e^{{\epsilon}}\Pr[Y \in S_r \,:\, R=r])\Pr[R=r] \\
&\leq &\sum_{r \in E}\delta \Pr[R=r]  =\delta.\end{aligned}$$ By symmetry, we also have $\Pr[{{\cal G}}(Y) \in S] - e^{{\epsilon}}\Pr[{{\cal G}}(X) \in S] \leq \delta$. Since $S$ was arbitrary, ${{\cal G}}(X)$ and ${{\cal G}}(Y)$ are $({\epsilon},\delta)$-indistinguishable.\
[*Proof of Part \[it:sd\].*]{} 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$, $$\begin{aligned}
\lefteqn{2|\Pr[X  \in S]-\Pr[Y \in S]|} \\
&=& \left |\Pr[X  \in S]-\Pr[Y  \in S]\right | + \left |\Pr[X  \notin S]-\Pr[Y  \notin S] \right | \\
&=& \left |\sum_{c \in S}(\Pr[X =c]-\Pr[Y =c])\right | + \left |\sum_{c \notin S}(\Pr[X =c]-\Pr[Y =c])\right | \\
&\leq& \sum_{c \in S}\left |\Pr[X =c]-\Pr[Y =c] \right | + \sum_{c \notin S}\left |\Pr[X =c]-\Pr[Y =c]\right |  \\
&=& \sum_{c \in D } \left |\Pr[X =c]-\Pr[Y =c] \right | \\ &\leq& \sum_{c \in D}(e^{{\epsilon}}\Pr[Y =c] + \delta - \Pr[Y =c]) + \sum_{c \in D}(e^{{\epsilon}}\Pr[X =c] +\delta - \Pr[X =c]) \\
&=& 2\delta + (e^{{\epsilon}}-1) \sum_{c \in D}\Pr[Y =c] + (e^{{\epsilon}}-1) \sum_{c \in D}\Pr[X =c] \\ &=& 2(e^{{\epsilon}}-1)+2\delta=2\bar{{\epsilon}}+ 2\delta.\end{aligned}$$ 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$.

Proofs of Theorems \[thm:eind\] and \[thm:ind2sdp\]
===================================================

This section is devoted to proving Theorems \[thm:eind\] and \[thm:ind2sdp\]. For convenience we restate the theorem statements.

\[Dwork-McSherry\] ${\epsilon}$-differential privacy implies $\bar{\epsilon}$-semantic privacy, where $\bar{\epsilon}=e^{{\epsilon}}-1$. $\bar{\epsilon}/2$-semantic privacy implies $2{\epsilon}$-differential privacy.

Consider any database ${{\mathrm{x}}}$. Consider belief distributions $\bar{b}_0[{{\mathrm{x}}}|t]$ and $\bar{b}_i[{{\mathrm{x}}}|t]$. differential privacy implies that the ratio of $\bar{b}_0[{{\mathrm{x}}}|t]$ and $\bar{b}_i[{{\mathrm{x}}}|t]$ is within $e^{\pm {\epsilon}}$ on every point, i.e., for every $i$ and for every possible transcript $t$: $$e^{-{\epsilon}}\bar{b}_i[{{\mathrm{x}}}|t]  \leq \bar{b}_0[{{\mathrm{x}}}|t] \leq e^{{\epsilon}}\bar{b}_i[{{\mathrm{x}}}|t].$$ In the remainder of the proof we fix $i$ and $t$. Substituting $\delta=0$ in Claim \[lem:proof\] (part \[it:sd\]), implies that ${\mathbf{SD}{\left( {{\bar{b}_0[{{\mathrm{x}}}|t],\bar{b}_i[{{\mathrm{x}}}|t]}} \right)}}=\bar{\epsilon}$. To see that $\bar{{\epsilon}}$-semantic privacy implies $2{\epsilon}$-differential privacy, consider a belief distribution $b$ which is uniform over two databases ${{\mathrm{x}}},{{\mathrm{y}}}$ which are at Hamming distance of one. Let $i$ be the position in which ${{\mathrm{x}}}$ and ${{\mathrm{y}}}$ differ. The distribution $\bar{b}_i[\cdot|t]$ will be uniform over ${{\mathrm{x}}}$ and ${{\mathrm{y}}}$ since they induce the same distribution on transcripts in Game $i$. This means that $\bar{b}_0[\cdot|t]$ will assign probabilities $1/2 \pm \bar{\epsilon}/2$ to each of the two databases (follows from ${\epsilon}$-semantic privacy definition). Working through Bayes’ rule shows that $$\frac{\Pr[{\mathcal{A}}({{\mathrm{x}}})=t]}{\Pr[{\mathcal{A}}({{\mathrm{y}}})=t]}=  \frac{\Pr[\bar{b}_0[{{\mathrm{x}}}|t]={{\mathrm{x}}}]}{\Pr[\bar{b}_0[{{\mathrm{y}}}|t]={{\mathrm{x}}}]} \leq \frac{{\frac{1}{2}}(1+\bar{\epsilon})}{{\frac{1}{2}}(1-\bar{\epsilon})} \leq e^{2{\epsilon}}.$$ This implies that ${\mathcal{A}}$ is point-wise $2{\epsilon}$-differentialy private. Using Claim \[lem:proof\] (part \[it:pw2ind\]), implies that ${\mathcal{A}}$ is $2{\epsilon}$-differentialy private.

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$.

\[lem:bayes\] Suppose two pairs of random variables $(X,{\mathcal{A}}(X))$ and $(Y,{\mathcal{A}}'(Y))$ are $({\epsilon},\delta)$-differentialy private (for some randomized algorithms ${\mathcal{A}}$ and ${\mathcal{A}}'$). Then with probability at least $1-\delta''$ over $t{\leftarrow}{\mathcal{A}}(X)$ (equivalently $t {\leftarrow}{{\cal A}}'(Y)$), the random variables $X|_{{\mathcal{A}}(X) =t}$ and $Y|_{{\mathcal{A}}'(Y)=t}$ are $(\hat{\epsilon},\hat\delta)$-differentialy private with $\hat{\epsilon}=3{\epsilon}$, $\hat\delta=2\sqrt{\delta}$, and $\delta''=\sqrt{\delta}+\frac{2\delta}{{\epsilon}e^{{\epsilon}}}=O(\sqrt{\delta})$.

Let $(X,{{\cal A}}(X))$ and $(Y,{{\cal A}}'(Y))$ be random variables on $D \times E$. The first observation is that ${{\cal A}}(X)$ and ${{\cal A}}(Y)$ are $({\epsilon},\delta)$-differentialy private. To prove that consider any set $P \in E$, $$\begin{aligned}
\Pr[{{\cal A}}(X) \in P] & =& \Pr[(X,{{\cal A}}(X)) \in D \times P]  \leq e^{{\epsilon}}\Pr[(Y,{{\cal A}}'(Y)) \in D \times P] + \delta \\ &=& e^{{\epsilon}}\Pr[{{\cal A}}'(Y) \in P] + \delta.\end{aligned}$$ Since $P$ was arbitrary, ${{\cal A}}(X)$ and ${{\cal A}}'(Y)$ are $({\epsilon},\delta)$-differentialy private. In the remainder of the proof, we will use the notation $X|_t$ for $X|_{{{\cal A}}(X)=t}$ and $Y|_t$ for $Y|_{{{\cal A}}'(Y)=t}$. Define, $$\begin{aligned}
 &Bad_0 = \{a\,:\, e^{-2{\epsilon}}\Pr[{{\cal A}}'[Y]=a] > \Pr[{{\cal A}}(X)=a] > e^{2{\epsilon}} \Pr[{{\cal A}}'[Y]=a]  \}& \\
&Bad_1=\{a \, : \, \exists S \subset D \mbox{ such that } \Pr[X|_a \in S] > e^{\hat{\epsilon}}\Pr[Y|_a \in S] + \hat\delta\}& \\ 
&Bad_2=\{a \, : \, \exists S \subset D \mbox{ such that } \Pr[Y|_a \in S] > e^{\hat{\epsilon}}\Pr[X|_a \in S] + \hat\delta\}.& \end{aligned}$$ We need an upper bound for the probabilities $\Pr[{{\cal A}}(X) \in Bad_1 \cup Bad_2]$ and $\Pr[{{\cal A}}'(Y) \in Bad_1 \cup Bad_2]$. We know from Claim \[lem:proof\] (part  \[it:ind2pw\]), that $$\Pr[{{\cal A}}(X) \in Bad_0] \leq \frac{2\delta}{{\epsilon}e^{{\epsilon}}} \ \ \mbox{ and } \ \ \Pr[{{\cal A}}'(Y) \in Bad_0] \leq \frac{2\delta}{{\epsilon}e^{{\epsilon}}}.$$ Note that from the initial observation ${{\cal A}}(X)$ and ${{\cal A}}'(Y)$ are $({\epsilon},\delta)$-differentialy private, therefore the condition required for applying Claim \[lem:proof\] (part \[it:ind2pw\]) holds. Now define, $$Bad_1'=Bad_1 \setminus Bad_0 \ \ \mbox{ and } \ \ Bad_2'=Bad_2 \setminus Bad_0.$$ For each $a \in Bad_1'$ and $T \subset D \times E$, define $S_a=\{b \in D \,:\, (b,a) \in T\}$. Define $T_1 = S_a \times \bigcup_{a \in Bad_1'} \{a\}$. $$\begin{aligned}
\Pr[(X,{{\cal A}}(X))\in T_1] &=& \sum_{a \in Bad_1'} \Pr[X \in S_a \,:\, {{\cal A}}(X)=a] \Pr[{{\cal A}}(X)=a]  \\
&>& \sum_{a \in Bad_1'} (e^{\hat{\epsilon}}\Pr[Y \in S_a \,:\, {{\cal A}}'(Y)=a]+\hat\delta)\Pr[{{\cal A}}(X)=a] \\
&=&\sum_{a \in Bad_1'} e^{\hat{\epsilon}}\Pr[Y \in S_a \,:\, {{\cal A}}'(Y)=a]\Pr[{{\cal A}}(X)=a] + \hat\delta\sum_{a \in Bad_1'} \Pr[{{\cal A}}(X)=a] \\
&=& \sum_{a \in Bad_1'} e^{3{\epsilon}}\Pr[Y \in S_a \,:\, {{\cal A}}'(Y)=a]e^{-2{\epsilon}} \Pr[{{\cal A}}'(Y)=a]  + \hat\delta\Pr[{{\cal A}}(X) \in Bad_1']  \\
&=& e^{{\epsilon}}\Pr[(Y,{{\cal A}}'(Y)) \in T_1] + \hat\delta\Pr[{{\cal A}}(X) \in Bad_1'].\end{aligned}$$ The inequality follows because of the definition of $Bad_1'$. By $({\epsilon},\delta)$-differential privacy, $\Pr[(X,{{\cal A}}(X))\in T_1] \leq e^{{\epsilon}}\Pr[(Y,{{\cal A}}(X)) \in T_1] + \delta$. Therefore, $$\hat\delta\Pr[{{\cal A}}(X) \in Bad_1'] \leq \delta \Rightarrow \Pr[{{\cal A}}(X) \in Bad_1'] \leq \delta/\hat\delta.$$ Similarly, $\Pr[{{\cal A}}(X) \in Bad_2'] \leq \delta/\hat\delta.$ Finally, $$\begin{aligned}
\Pr[{{\cal A}}(X) \in Bad_1 \cup Bad_2] &\leq& \Pr[{{\cal A}}(X) \in Bad_0] +\Pr[{{\cal A}}(X) \in Bad_1']+\Pr[{{\cal A}}(X) \in Bad_2'] \\ 
&=& \frac{2\delta}{{\epsilon}e^{{\epsilon}}}+\frac{\delta}{\hat\delta}+\frac{\delta}{\hat\delta}
= \frac{2\delta}{{\epsilon}e^{{\epsilon}}}+\sqrt{\delta}.\end{aligned}$$ By symmetry, we also have $\Pr[{{\cal A}}'(Y) \in Bad_1 \cup Bad_2] \leq \frac{2\delta}{{\epsilon}e^{{\epsilon}}}+\sqrt{\delta}$. Therefore, with probability at least $1-\delta''$, $X|_{t}$ and $Y|_{t}$ are $(\hat{\epsilon},\hat\delta)$-differentialy private.

The following corollary follows by using the above proposition (with $Y=X$) in conjunction with Claim \[lem:proof\] (part \[it:sd\]).

\[cor:bayes\] Let $(X,{\mathcal{A}}(X))$ and $(X,{\mathcal{A}}'(X))$ be $({\epsilon},\delta)$-differentialy private. Then, with probability at least $1-\delta''$ over $t{\leftarrow}{\mathcal{A}}(X)$ $($equivalently $t {\leftarrow}{{\cal A}}'(X)$$)$, the statistical difference between $X|_{{\mathcal{A}}(X) =t}$ and $X|_{{\mathcal{A}}'(X)=t}$ is at most $e^{\hat{\epsilon}}-1+\hat\delta$ with $\hat{\epsilon}=3{\epsilon}$, $\hat\delta=2\sqrt{\delta}$, and $\delta''=O(\sqrt{\delta})$.

(${\epsilon},\delta$)-differential privacy implies $({\epsilon}',\delta')$-semantic privacy for arbitrary (not necessarily informed) beliefs with ${\epsilon}'=e^{3{\epsilon}}-1+2\sqrt{\delta}$ and $\delta' = O(n\sqrt{\delta})$. $(\bar{\epsilon}/2,\delta)$-semantic privacy implies $(2{\epsilon},2\delta)$-differential privacy with $\bar{\epsilon}=e^{{\epsilon}}-1$.

Let ${\mathcal{A}}$ be a $({\epsilon},\delta)$-differentialy private algorithm. Let $b$ be any belief distribution. From Claim \[lem:proof\] (part \[it:ajoint\]), we know that $(b,{\mathcal{A}}(b))$ and $(b,{\mathcal{A}}_i(b))$ are $({\epsilon},\delta)$-differentialy private. Let $\delta''=O(\sqrt{\delta})$. From Corollary \[cor:bayes\], we get that with probability at least $1-\delta''$ over $t {\leftarrow}{\mathcal{A}}(b)$, the statistical difference between $b|_{{\mathcal{A}}(b) =t}$ and $b|_{{\mathcal{A}}_i(b)=t}$ is at most ${\epsilon}'$. Therefore, for any ${{\mathrm{x}}}{\leftarrow}b$, with probability at least $(1-\delta'')$ over $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Taking union bound over all coordinates $i$, implies that for any ${{\mathrm{x}}}{\leftarrow}b$ with probability at least $1-n\delta''$ over $t {\leftarrow}{\mathcal{A}}(b)$, for all $i=1,\dots,n$, we have ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Therefore, ${\mathcal{A}}$ satisfies $({\epsilon}',\delta')$-semantic privacy for $b$. Since $b$ was arbitrary, we get that (${\epsilon},\delta$)-differential privacy implies $({\epsilon}',\delta')$-semantic privacy.

To see that $(\bar{\epsilon}/2,\delta)$-semantic privacy implies $(2{\epsilon},2\delta)$-differential privacy, consider a belief distribution $b$ which is uniform over two databases ${{\mathrm{x}}},{{\mathrm{y}}}$ which are at Hamming distance of one. The proof idea is same as in Theorem \[thm:eind\]. Let $i$ be the position in which ${{\mathrm{x}}}$ and ${{\mathrm{y}}}$ differ.

Let $\bar{\mathcal{A}}$ be an algorithm that with probability $1/2$ draws an output from ${\mathcal{A}}({{\mathrm{x}}})$ and with probability $1/2$ draws an output from ${\mathcal{A}}({{\mathrm{y}}})$. Consider a transcript $t$ drawn from $\bar{\mathcal{A}}$. The distribution $\bar{b}_i[\cdot|t]$ will be uniform over ${{\mathrm{x}}}$ and ${{\mathrm{y}}}$ since they induce the same distribution on transcripts in Game $i$. This means that with probability at least $1-\delta$ over $t {\leftarrow}\bar{\mathcal{A}}$, $\bar{b}_0[\cdot |t]$ will assign probabilities $1/2\pm \bar{\epsilon}/2$ to each of the two databases. Working through Bayes’ rule as in Theorem \[thm:eind\] shows that $\bar{\mathcal{A}}$ is point-wise $(2{\epsilon},\delta)$-differentialy private (with probability at least at least $1-2\delta$ of $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, $e^{-2{\epsilon}}\Pr[{\mathcal{A}}({{\mathrm{y}}})=t] \leq \Pr[{\mathcal{A}}({{\mathrm{x}}})=t] \leq e^{2{\epsilon}} \Pr[{\mathcal{A}}({{\mathrm{y}}})=t]$). Therefore, with probability at least $1-\delta$ of $t {\leftarrow}\bar{\mathcal{A}}$, $e^{-2{\epsilon}}\Pr[{\mathcal{A}}({{\mathrm{y}}})=t] \leq \Pr[{\mathcal{A}}({{\mathrm{x}}})=t] \leq e^{2{\epsilon}} \Pr[{\mathcal{A}}({{\mathrm{y}}})=t]$. Similarly, for $t {\leftarrow}{\mathcal{A}}({{\mathrm{y}}})$. This implies that ${\mathcal{A}}$ is point-wise $(2{\epsilon},2\delta)$-differentialy private. Using Claim \[lem:proof\] (part \[it:pw2ind\]), implies that ${\mathcal{A}}$ is $(2{\epsilon},2\delta)$-differentialy private.

Discussion and Consequences
===========================

[Theorem \[thm:ind2sdp\]]{} states that the relaxations notions of differential privacy used in some previous work still imply privacy in the face of arbitrary side information. This is [*not*]{} the case for [*all*]{} possible relaxations, even very natural ones. For example, if one replaced the multiplicative notion of distance used in differential privacy with total variation distance, then the following “sanitizer” would be deemed private: choose an index $i\in\{1,\dots,n\}$ uniformly at random and publish the entire record of individual $i$ together with his or her identity (example 2 in [@DMNS06]). Such a “sanitizer” would not be meaningful at all, regardless of side information.

Theorems \[thm:ind2sdp\] and A.3 give some qualitative improvements over existing security statements. Theorem A.3 implies that the claims of [@DiNi03; @DwNi04; @BDMN05] can be strengthened to hold for *all* predicates of the input simultaneously (a switch in the order of quantifiers). The strengthening does come at some loss in parameters since $\delta$ is increased. This incurs a factor of 2 in ${\log{\left( {\tfrac{1}{\delta}} \right)}}$, or a factor of $\sqrt{2}$ in the standard deviation. More significantly, [Theorem \[thm:ind2sdp\]]{} shows that noise processes with negligible probability of bad events have nice differential privacy guarantees even for adversaries who are not necessarily informed. There is a hitch however only adversaries whose beliefs somehow represent reality, i.e. for whom the real database is somehow “representative" of the adversary’s view can be said to learn nothing.

Finally, the techniques used to prove [Theorem \[thm:ind2sdp\]]{} can also be used to analyze schemes which do not provide privacy for [*all*]{} pairs of neighboring databases ${{\mathrm{x}}}$ and ${{\mathrm{y}}}$, but rather only for [*most*]{} such pairs (remember that neighboring databases are the ones that differ in one entry). Specifically, it is sufficient that those databases where the “differential privacy” condition fails occur only with small probability.

\[thm:dsemantic\] Let ${\mathcal{A}}$ be a randomized algorithm. Let $$\mathcal{E} = \{{{\mathrm{x}}}: \forall \mbox{ neighbors }{{\mathrm{y}}}\mbox{ of } {{\mathrm{x}}}, {\mathcal{A}}({{\mathrm{x}}}) \mbox{ and } {\mathcal{A}}({{\mathrm{y}}}) \mbox{ are } ({\epsilon},\delta)\mbox{-differentialy private}\}.$$ Then ${\mathcal{A}}$ satisfies $({\epsilon}',\delta')$-semantic privacy for any belief distribution $b$ such that $b[\mathcal{E}] = \Pr_{{{\mathrm{x}}}{\leftarrow}b}[{{\mathrm{x}}}\in \mathcal{E}] \geq 1-\delta$ with ${\epsilon}'=e^{3{\epsilon}}-1+2\sqrt{\delta}$ and $\delta'=O(n\sqrt{\delta})$.

Let $b$ be a belief distribution with $b[\mathcal{E}] \geq 1-\delta$. Let $\delta''=O(\sqrt{\delta})$. From Claim \[lem:proof\] (part \[it:joint\]), we know that $(b,{\mathcal{A}}(b))$ and $(b,{\mathcal{A}}_i(b))$ are $({\epsilon},2\delta)$-differentialy private. From Corollary \[cor:bayes\], we get that with probability at least $1-\delta''$ over $t {\leftarrow}{\mathcal{A}}(b)$, the statistical difference between $b|_{{\mathcal{A}}(b) =t}$ and $b|_{{\mathcal{A}}_i(b)=t}$ is at most ${\epsilon}'$. Therefore, with probability at least $(1-\delta'')$ over pairs $({{\mathrm{x}}},t)$ where ${{\mathrm{x}}}{\leftarrow}b$ and $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Taking union bound over all coordinates $i$, implies that with probability at least $1-n\delta''$ over pairs $({{\mathrm{x}}},t)$ where ${{\mathrm{x}}}{\leftarrow}b$ and $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, for all $i=1,\dots,n$, we have ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Therefore, ${\mathcal{A}}$ satisfies $({\epsilon}',\delta')$-semantic privacy for belief distribution $b$.

Let $LS_f(\cdot)$ denote the local sensitivity of function $f$ (defined in [@NRS07]). Let $Lap(\lambda)$ denote the Laplacian distribution. This distribution has density function $h(y) \propto \exp(-|y|/\lambda)$, mean $0$, and standard deviation $\lambda$. Using the Laplacian noise addition procedure of [@DMNS06; @NRS07], along with Theorem \[thm:dsemantic\] we get,

Let $\mathcal{E} =\{ {{\mathrm{x}}}\,:\, LS_f({{\mathrm{x}}}) \leq s \}$. Let ${\mathcal{A}}({{\mathrm{x}}}) = f({{\mathrm{x}}}) + \text{Lap}\left(\frac{s}{{\epsilon}}\right )$. Let $b$ be a belief distribution such that $b[\mathcal{E}] = \Pr_{{{\mathrm{x}}}{\leftarrow}b}[{{\mathrm{x}}}\in \mathcal{E}] \geq 1-\delta$. Then ${\mathcal{A}}$ satisfies $({\epsilon}',\delta')$-semantic privacy for the belief distribution $b$ with ${\epsilon}'=e^{3{\epsilon}}-1+2\sqrt{\delta}$ and $\delta'=O(n\sqrt{\delta})$.

Acknowledgements {#acknowledgements .unnumbered}
================

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

Appendix A: Another View of Semantic Privacy {#appendix-a-another-view-of-semantic-privacy .unnumbered}
============================================

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.

\[reality-oblivious (${\epsilon},\delta$)-semantic privacy\] A randomized algorithm is reality-oblivious $({\epsilon},\delta)$-semantically private if for all belief distributions $b$ on $\mathcal{D}^n$, for all databases ${{\mathrm{x}}}\in \mathcal{D}^n$, with probability at least $1-\delta$ over transcripts $t$ drawn from ${{\cal A}}({{\mathrm{x}}})$, and for all $i=1,\dots,n$: $${\mathbf{SD}{\left( {{\bar{b}_0[{{\mathrm{x}}}|t]\ ,\  \bar{b}_i[{{\mathrm{x}}}|t]\ }} \right)}} \leq {\epsilon}.$$

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

\[lem:noind2sdp\][^3] (${\epsilon},\delta$)-differential privacy does not imply reality-oblivious $({\epsilon}',\delta')$-semantic privacy for any reasonable values of ${\epsilon}'$ and $\delta'$.

This counterexample is due to Dwork and McSherry: suppose that the belief distribution is uniform over $\{(0^n),(1,0^{n-1})\}$, but that real database is $(1^{n})$. Let the database ${{\mathrm{x}}}=(x_1,\dots,x_n)$. Say we want to reveal $f({{\mathrm{x}}})=\sum_ix_i$. Adding Gaussian noise with variance $\sigma^2={\log{\left( {\tfrac{1}{\delta}} \right)}}/{\epsilon}^2$ satisfies $({\epsilon},\delta)$-differential privacy (refer [@DMNS06; @NRS07] for details). However, with overwhelming probability the output will be close to $n$, and this will in turn induce a very non-uniform distribution over $\{(0^n),(1,0^{n-1})\}$ since $(1,0^{n-1})$ is exponentially (in $n$) more likely to generate a value near $n$ than $(0^n)$. More precisely, due to the Gaussian noise added, $$\frac{\Pr[{\mathcal{A}}({{\mathrm{x}}})=n \, | \, {{\mathrm{x}}}=(0^n)]}{\Pr[{\mathcal{A}}({{\mathrm{x}}})= n \, | \, {{\mathrm{x}}}=(1,0^{n-1})]} = \frac{\exp\left (\frac{-n^2}{2\sigma} \right)}{\exp \left(\frac{-(n-1)^2}{2\sigma}\right )} = \exp\left (\frac{-2n+1}{2\sigma} \right).$$ Therefore, given that the output is close to $n$, the posterior distribution of the adversary would be exponentially more biased toward $(1,0^{n-1})$ than $(0^n)$. Hence, it is exponentially far away from the prior distribution which was uniform. On the other hand, if the adversary believes he is seeing ${\mathcal{A}}({{\mathrm{x}}}_{-1})$, then no update will occur and the posterior distribution will remain uniform. Since the posterior distributions in these two situations are exponentially far apart (one exponentially far from uniform, other uniform), it shows that (${\epsilon},\delta$)-differential privacy does not imply any reasonable guarantee on reality-oblivious semantic privacy.

However, $({\epsilon},\delta)$-differential privacy does provide a strong reality-oblivious $({\epsilon}',\delta')$-semantic privacy guarantee for [*informed*]{} belief distributions. Using terminology from [@BDMN05; @DMNS06], we say that a belief distribution $b$ is informed if $b$ is constant on $n-1$ coordinates and agrees with the database in those coordinates. This corresponds to the adversary knowing some set of $n-1$ entries in the database before interacting with the algorithm, and then trying to learn the remaining one entry from the interaction. Let ${\mathcal{A}}_i$ be a randomized algorithm such that for all databases ${{\mathrm{x}}}$, ${\mathcal{A}}_i({{\mathrm{x}}})={\mathcal{A}}({{\mathrm{x}}}_{-i})$.

\[thm:ind2sdp-inf\] (${\epsilon},\delta$)-differential privacy implies reality-oblivious $({\epsilon}',\delta')$-semantic privacy for informed beliefs with ${\epsilon}'=e^{3{\epsilon}}-1+2\sqrt{\delta}$ and $\delta' = O(n\sqrt{\delta})$.[^4]

Let ${\mathcal{A}}$ be a $({\epsilon},\delta)$-differentialy private algorithm. Let ${{\mathrm{x}}}$ be any database. Let $b$ be any informed belief distribution. This means that $b$ is constant on all $n-1$ coordinates, and agrees with ${{\mathrm{x}}}$ in those $n-1$ coordinates. Let $i$ be the coordinate which is not yet fixed in $b$. From Claim \[lem:proof\] (part \[it:ajoint\]), we know that $(b,{\mathcal{A}}(b))$ and $(b,{\mathcal{A}}_i(b))$ are $({\epsilon},\delta)$-differentialy private. Therefore, we can apply Lemma \[lem:bayes\]. Let $\delta''=O(\sqrt{\delta})$. From Corollary \[cor:bayes\], we get that with probability at least $1-\delta''$ over $t {\leftarrow}{\mathcal{A}}(b)$, the statistical difference between $b|_{{\mathcal{A}}(b) =t}$ and $b|_{{\mathcal{A}}_i(b)=t}$ is at most ${\epsilon}'$. Therefore, for ${{\mathrm{x}}}$, with probability at least $(1-\delta'')$ over $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Taking union bound over all coordinates $i$, implies that with probability at least $1-n\delta''$ over $t {\leftarrow}{\mathcal{A}}({{\mathrm{x}}})$, for all $i=1,\dots,n$, we have ${\mathbf{SD}{\left( {{b|_{{\mathcal{A}}({{\mathrm{x}}}) =t},b|_{{\mathcal{A}}_i({{\mathrm{x}}}) =t}}} \right)}} \leq  {\epsilon}'$. Therefore, ${\mathcal{A}}$ satisfies reality-oblivious $({\epsilon}',\delta')$-semantic privacy for $b$. Since ${{\mathrm{x}}}$ was arbitrary, we get that (${\epsilon},\delta$)-differential privacy implies reality-oblivious $({\epsilon}',\delta')$-semantic privacy for informed beliefs.

[^1]: That said, some of the other relaxations, such as probabilistic differential privacy from  [@MKAGV08], might lead to better parameters in [Theorem \[thm:ind2sdp\]]{}.

[^2]: A few similar properties relating to statistical difference were shown in [@SV99]. Note that $({\epsilon},\delta)$-indistinguishability is not a metric, unlike statistical difference. But it does inherit some nice metric like properties.

[^3]: Note that adversaries whose belief distribution is very different from the real database (as in the counterexample of Theorem A.2 may think they have learned a lot. But does such “learning" represent a breach of privacy? We do not think so, but leave the final decision to the reader.

[^4]: Reality-oblivious $(\bar{\epsilon}/2,\delta)$-semantic privacy implies $(2{\epsilon},2\delta)$-differential privacy with $\bar{\epsilon}=e^{{\epsilon}}-1$. For details see the proof of Theorem \[thm:ind2sdp\].
