Advanced Composition

Once we have designed some basic differentially private algorithms, it is a natural idea to combine them and analysis the privacy loss. We begin with an illustrative example that sets up the mathematical model step by step.

Image yourself in front of the door of a safe vault protected by a password lock. To open the door, you need the correct password $P$. If tried with the wrong password, the lock would destroy itself automatically.

Luckily, you know two candidate passwords $P_1$ and $P_2$, with one of them being the correct one. Further, you notice that the designer of the lock left a collection of boxes near the door, which contain information on how they decide the correct passwords. Obtaining complete information of anyone of them gives you the correct password.

But the boxes are also protected and you don't have legally access to them. However, you can hack into the boxes. Hacking into the box won't give you all its information, but a random message. In particular, each box $B$ is associated with a set $\mathcal{R}_B$, which is a finite collection of messages (in English). When $B$ is hacked, it returns a message $Y_B$ generated randomly from $\mathcal{R}_B$, whose distribution depends on the correct password $P$.

Let $\mathcal{D}_{B, P_1}$ be the distribution of $Y_B$ if the correct password is $P_1$, and $\mathcal{D}_{B, P_2}$ be the one if the correct password is $P_2$. If there is a huge difference between $\mathcal{D}_{B, P_1}$ and $\mathcal{D}_{B, P_2}$, then you might be able to guess the correct password.

E.g., suppose $\mathcal{R}_B =$ { "Dog bites.", "Cat scratches." } and the distributions are given as

Hence, when you get $Y_B=$ "Dog bites.", you prefer $P_1$ over $P_2$ and vice versa.

Anticipating such potential information leakage, the designer of the lock equips the boxes with a defense mechanism, called $(\epsilon, 0)$-mechanism. It guarantees the distributions $\mathcal{D}_{B, P_1}$ and $\mathcal{D}_{B, P_2}$ are similar so that it is hard for you to infer the correct password from the message. In particular, $\forall S \subset \mathcal{R}_B$, if $S$ is measurable, it holds that

When these inequalities are satisfied, we say that $\mathcal{D}_{B, P_1}$ and $\mathcal{D}_{B, P_2}$ are $(\epsilon, 0)$ close. The inequalities require $\mathcal{D}_{B, P_1}$ and $\mathcal{D}_{B, P_2}$ to have the same support on $\mathcal{R}_B$. Therefore, throughout our discussion below, we assume that both $\mathcal{D}_{B, P_1}$ and $\mathcal{D}_{B, P_2}$ assign positive probability to each element in $\mathcal{R}_B$. Otherwise, we can just replace $\mathcal{R}_B$ with the support of $\mathcal{D}_{B, P_1}$ (which is also the support of $\mathcal{D}_{B, P_2}$).

Now, hacking one box is unlikely to help you to guess the correct password. You want to hack more boxes, with the hope that the information combined will assist you. Due to resource limit, you can't hack all boxes but only a finite number of them. You choose the first box randomly. Then you choose every new box based on the information obtained from the hacked boxes. The figure below shows an example of hacking five boxes.

Suppose that your resource enables you to hack $n$ boxes and let $\vec Y_n = (Y_1, Y_2, ..., Y_n)$ be the output messages you obtained. Similar to the situation of hacking one box, if the distribution of $\vec Y_n$, conditioned on $P = P_1$, is utterly distant from that conditioned on $P = P_2$, then there could be some cases when you can confidently infer the true password. Conversely, to prevent severe information leakage, the designer needs to ensure there isn't such case, i.e., the two distributions should be similar.

What makes things even more complicated is that, the distribution of $\vec Y_n$ depends not only on the output distributions of the boxes, but also on your strategy of choosing the boxes to hack. Let's use symbol $A$ to denote your strategy. Whatever $A$ is, the designer need to guarantee that the distribution of $\vec Y_n$ conditioned $P = P_1$ should be similar to that conditioned on $P = P_2$.

Surprisingly, this is in some sense achievable, as long as for each box, its output distribution conditioned on $P = P_1$ is $(\epsilon, 0)$ close to that conditioned on $P = P_2$.

Let $\mathcal{R}$ be the set of possible possible messages of all boxes.

Theorem. $\forall A$, $\forall S \subset \mathcal{R}^n$, it holds that $\forall \delta' \in (0, 1)$,

$$\Pr[ \vec Y_n \in S \ | \ P = P_1, A] \le e^{\epsilon'} \cdot \Pr[ \vec Y_n \in S \ | \ P = P_2, A] + \delta' \\ \Pr[ \vec Y_n \in S \ | \ P = P_2, A] \le e^{\epsilon'} \cdot \Pr[ \vec Y_n \in S \ | \ P = P_1, A] + \delta'$$

where $\epsilon' = k\epsilon(e^\epsilon - 1) + \epsilon \sqrt{2 n \log \frac{1}{\delta'} }$.

If we view $\epsilon$ as the privacy loss of a single box, then the theorem states that the privacy loss grows to $O(\sqrt {n} \epsilon )$ is $n$ boxes are hacked.

To prove the theorem, we need a rigorous model for the problem.

Definitions.

1. $\mathcal{I}$: the index set.

2. $\{ B_\alpha : \alpha \in \mathcal{I} \}$: the collection of boxes.

3. $\{ \mathcal{R}_{\alpha} : \alpha \in \mathcal{I} \}$: the ranges of the outputs of the boxes.

4. $\mathcal{R} \doteq \cup_{\alpha \in \mathcal{I} } R_\alpha$: the range of any possible output by any box.

5. $\{ \mathcal{D}_{\alpha, P_1} : \alpha \in \mathcal{I} \}$ ($\{ \mathcal{D}_{\alpha, P_2} : \alpha \in \mathcal{I} \}$): the set of output distribution when the correct password is $P_1$ ($P_2$). Without loss of generality, we assume that for a fixed $\alpha \in \mathcal{I}$, the distribution $\mathcal{D}_{\alpha, P_1}$ ($\mathcal{D}_{\alpha, P_2}$) assigns positive probability to each element in $\mathcal{R}_\alpha$. Moreover, $\mathcal{D}_{\alpha, P_1}$ and $\mathcal{D}_{\alpha, P_2}$ are $(\epsilon, 0)$ close.

6. $n$: the number of boxes you can hack.

7. $\vec i_k \doteq (i_1, i_2, ..., i_k)$: the index sequence of boxes you have chosen to hack up to time $k$, where $k \in [0, n]$. When $k = 0$, $\vec i_0$ corresponds to a empty sequence.

8. $\vec Y_k = (Y_1, Y_2, ..., Y_k):$ the random variables that represent messages outputted by the chosen boxes up to time $k \in [1, n]$, where $Y_t \in \mathcal{R}_{i_t} \subset \mathcal{R}$ for $t \in [1, k]$. Therefore, $\vec Y_k$ can be view as random vector in $\mathcal{R}^k$.

9. $\vec x_k = (x_1, x_2, ..., x_k) \in \mathcal{R}^k:$ a point in $\mathcal{R}^k$, where $k \in [0, n]$. When $k = 0$, we define $\vec x_0 = \emptyset$.

10. $\vec h_k = \left< \vec i_k, \vec x_k \right> = \left< (i_1, i_2, i_3, ..., i_k), (x_1, x_2, ..., x_k) \right>:$ the history up to $k \in [0, n]$, which consists of the chosen indexes and observations up to time $k$. We use $\vec h_0$ to denote the empty history.

11. $A:$ your strategy (policy) for choosing boxes. It works as follows: for any fixed history $\vec h_k = \left< \vec i_k, \vec x_k \right>$, A is associated with a fixed distribution $\mathcal{D}_{A, \vec h_k}$ over $\mathcal{I} \setminus \vec i_k$, the set of indexes of the unchosen boxes. When inputted with $\vec h_k$, $A$ returns a random variable $A(\vec h_k)$ that follows the distribution $\mathcal{D}_{A, \vec h_k}$.

We will show that, no matter what strategy you use, it is unlikely that you distinguish via the output $\vec Y_n$ whether the correct password is $P_1$ or $P_2$. This is because whether $P = P_1$ or not, the output distributions of $\vec Y_n$ are similar.

Proof of the theorem. We will just prove the first inequality, and the second one follows from symmetry. We consider a bad set in $\mathcal{R}^n$:

and will use the following lemma.

Lemma. $\Pr[ \vec Y_n \in \mathcal{W}\ | \ P = P_1, A] \le \delta'$.

Hence,

The first inequality follows from monotonicity of probability, the second one from the lemma, and the final one from the definition of $\mathcal{W}$.

Proof of the lemma. To prove the lemma, we need only to consider those point $\vec x_n$ with

Otherwise, $\vec x_n$ contributes to 0 probability to the set $\mathcal{W}$ (whether it belongs to $\mathcal{W}$ or not).

Now, we expand the probability $\Pr[ \vec Y_n = \vec x_n \ | \ P = P_1, A]$. To obtain the $k$-th output, there are two steps

1. $A$ generates a index $i_k$ of a box based on the known history $\vec h_{k - 1}$.
2. The box $B_{i_k}$ is hacked, and output a random message $x_k$ sampled from its distribution $D_{i_k, P_1}$.

Let $\vec H_k$ be a random variable that represents the history up to $k$. By chain rule, we have

By $\Pr[ \vec Y_n = \vec x_n \ | \ P = P_1, A] > 0$, each term in the expansion are positive. Similarly,

As both $\mathcal{D}_{i_k, P_1}$ and $\mathcal{D}_{i_k, P_2}$ assign positive probability to each point in $\mathcal{R}_{i_k}$, we know $\Pr[ \vec Y_n = \vec x_n \ | \ P = P_2, A] > 0$.

We are ready to consider the ratio:

If we replace $x_k$ by a random variable $X_k \sim \mathcal{D}_{i_k, P_1}$, then

is a random variable. As $\mathcal{D}_{i_k, P_1}$ and $\mathcal{D}_{i_k, P_2}$ are $(\epsilon, 0)$ close, we have

Further, we have

Fact 1. For any $\alpha \in \mathcal{I}$, it holds that

$$\begin{aligned} \mathbb{E}_{ X \sim \mathcal{D}_{\alpha, P_1} } \left[ \ln \frac{ \underset{ Y \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ Y = X] } { \underset{ Y \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ Y = X] } \right] &= \sum_{x \in \mathcal{R}_\alpha } \underset{ X \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ X = x] \cdot \ln \frac{ \underset{ Y \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ Y = x] } { \underset{ Y \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ Y = x] } \\ &\le \sum_{x \in \mathcal{R}_\alpha } \underset{ X \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ X = x] \cdot \ln \frac{ \underset{ Y \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ Y = x] } { \underset{ Y \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ Y = x] } \\ &+ \sum_{x \in \mathcal{R}_\alpha } \underset{ X \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ X = x] \cdot \ln \frac{ \underset{ Y \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ Y = x] } { \underset{ Y \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ Y = x] } \\ &= \sum_{x \in \mathcal{R}_\alpha } \left[ \underset{ X \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ X = x] - \underset{ X \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ X = x] \right] \cdot \ln \frac{ \underset{ Y \sim \mathcal{D}_{\alpha, P_1} }{ \Pr } [ Y = x] } { \underset{ Y \sim \mathcal{D}_{\alpha, P_2} }{ \Pr } [ Y = x] } \\ &\le (e^\epsilon - 1) \epsilon \end{aligned}$$

Therefore, $\mathbb{E} [C_k] \le (e^\epsilon - 1) \epsilon$.

Fact 2. (Azuma Inequality). Let $C_1, ...., C_n$ be random variables such that $\forall k \in [n]$, $\Pr[ |C_k| \le \epsilon ] = 1$, and for every $(c_1, ..., c_{k -1} ) \in \text{Supp} (C_1, ..., C_{k - 1} )$, we have

$$\mathbb{E}[ C_i \mid C_1 = c_1, ..., C_{k -1} = c_{k - 1} ] \le \beta,$$

Then for every $z > 0$, we have

$$\Pr[ \sum_{k = 1}^n C_i - n \beta > z] \le \exp(- \frac{z^2}{ 2 n\epsilon^2 } )$$

Finally, applying Azuma Inequality with $z = \sqrt{ 2n \log \frac{1}{\delta'} }$ and $\beta = (e^\epsilon - 1) \epsilon$, we get the desired result.

$\blacksquare$

Reference.

[1] C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,” Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2013