Gundam and DP

In this article, we introduce differential privacy, starting with with a story of information leakage.

Twin Drive or Not

Celestial Being is a private military organization known for its cutting-edge technology. Among its four advanced machines, the most powerful one is Gundam 00.

The Gundam 00 is about to engage the enemy.

Under ideal conditions, Gundam 00 is equipped with two engines, known as the twin drive system. However, due to maintenance, this is not always the case. At the moment of deployment:

• With probability 0.5, Gundam 00 has both drives.
• With probability 0.5, it has one drive.

We describe the drive configuration as follows:

• Twin drive: ($T = (1, 1)$)
• Single drive: $S = (1, 0)$ (or $(0, 1)$)

Let $X$ be a random variable representing the drive status. Then,

Raiser Sword

The Raiser Sword is one of Gundam 00's most powerful weapon. Its energy level depends heavily on the machine's drive configuration.

Let $Y \in [0, 100]$ be the random variable that denotes the energy level of the Raiser Sword. The distribution, written as $\Pr[\cdot \mid X]$, depends on the drive status:

• $\Pr[Y = y \mid X = T]$: energy level given twin drive
• $\Pr[Y = y \mid X = S]$: energy level given single drive

Specifically,

where $B(n, p)$ denotes a binomial distribution. What matters most is the takeaway:

• With the twin drive, the expected energy level is $81$.
• With a single drive, it drops dramatically to $9$.

This dramatic gap is known as the "squaring" phenomenon of the twin drive---the combined system is far more powerful than the sum of its parts.

Now suppose that you're the enemy pilot, flying a mobile suit with just average performance.

Before you even see Gundam 00, it launches a long-range Raiser Sword attack. Against the odds, you survive.

You must now make a critical decision.

• If Gundam 00 is equipped with the twin drive, you stand no chance in close combat. Retreat is the only rational option.
• If it is running on a single drive, you actually outperform it---and engaging could lead to victory.

Having survived the Raiser Sword strike, you now have one crucial piece of information: the observed energy level, denoted by $y$. This single number already tells you something about Gundam 00’s drive system. To turn that intuition into a concrete belief, you use Bayes’ theorem, which updates prior uncertainty using new evidence.

Substituting with $\Pr[X = S] = \Pr[X = T] = 0.5$, we get

The distributions $B(100, 0.09)$ and $B(100, 0.81)$ are plotted together below.

Immediately, you can draw some conclusions based on single value of $y$, such as

1. If $y = 10$, it is likely 00 has only one drive.
2. If $y = 75$, it is likely 00 has twin drive.

Or you can conclude based on the range of $y$, such as

1. If $y \in [0, 20]$, it is likely 00 has single drive.
2. If $y \in [70, 90]$, it is likely 00 has twin drive.

Before the observation of $y$, as $\Pr[X = S] = \Pr[X = T] = 0.5$, you have only random guess over the engine status of 00. After the observation, you might be much more confident about your guess, even though the energy level of the raiser sword is a random variable.

Why does this happen? Because the two distributions are well-separated. They are far from each other. Further, the prior probabilities $\Pr[X = S]$ and $\Pr[X = T]$ play important roles. If you know $\Pr[X = S] = 10^{-10}$, even if you observe an energy level of $y = 10$, you had better not engage Gundam 00. You know it could be just a trap!

Differential Privacy

Database managers face similar scenarios in privacy protection. We know define the setting for differential privacy. We view a dataset $D$ as a table of $n$ rows, each of which comes from a domain $\mathcal{X}$. Hence $D \in \mathcal{X}^n$. Instead of releasing the dataset directly, the manager runs a randomized algorithm $A: \mathcal{X}^n \rightarrow \mathcal{Y}$ on $D$, and outputs $Y = A(D) \in \mathcal{Y}$. Here $\mathcal{Y}$ is called the co-domain of $A$ and does not necessarily equal to $\mathcal{X}^n$. Note that the output distribution of $A$ may depend on the input $D$. Further, for simplicity of discussion, we believe a uniform prior distribution over datasets in $\mathcal{X}^n$.

In the Gundam 00's story, $\mathcal{X} = \{0, 1\}^2$, and $\mathcal{Y} = [0, 100]$.

Suppose there is another dataset $D'$ that differs only one row from $D$. The algorithm $A$ is said to be differentially private if a malicious user is unlikely to distinguish the input to $A$ between $D$ and $D'$, by merely observing $A$'s output. Simply put, the conditional distributions of $\Pr[\cdot \mid X = D]$ and $\Pr[\cdot \mid X = D']$ should be similar, where $X$ is a variable that denotes the input dataset.

We observe in the previous section that, if the distributions are well separated, then we can infer the underlying input with high confidence when the output value takes specific values or lies in certain ranges.

There are many ways to characterize the closeness of two distributions. We introduce the one proposed in [1].

Algorithm $A$ is called $(\epsilon, \delta)$ differentially private, if for any pair of neighboring datasets $D$ and $D'$ (the ones that differ in only one row), and for any (measurable) subset $\mathcal{R} \subset \mathcal{Y}$, it holds that

$$\Pr[Y \in \mathcal{R} \mid X = D ] \le \exp(\epsilon) \cdot \Pr[Y \in \mathcal{R} \mid X = D' ]+ \delta$$

In other words, we can't find a subset $\mathcal{R}$, with which we can distinguish $D$ and $D'$ with high confidence. In the previous example, such $\mathcal{R}$ exists. E.g., $R = [70, 90]$. If $Y$ lies in $\mathcal{R}$, we can infer that Gundam 00 is likely to have twin drive.

Hypothesis Testing

There is alternative view of $(\epsilon, 0)$ differential privacy as hypothesis testing. Suppose that we know the underlying dataset is either $D$ or $D'$ with equal probability. After observing the output of $A$, we need to decide which hypothesis of the following holds:

Assume that we adopt a fixed strategy:

1. First we choose a fixed subset $\mathcal{R} \subset \mathcal{Y}$,
2. If $Y \in \mathcal{R}$, we choose to accept $H_0$,
3. Otherwise, we accept $H_1$.

There are two kinds of errors we can make. The type I error is the one when the true hypothesis is $H_0$ and we accept $H_1$. Conversely, type II error is the one when the true hypothesis is $H_1$ and we accept $H_0$. Let $p$ and $q$ be the probabilities we make type I and II errors respectively. The following theorem holds

Algorithm A is $(\epsilon, 0)$ differentially private then

1. $\frac{1}{1 + \exp(\epsilon) } \le q \le \frac{1}{1 + \exp(-\epsilon) }$
2. $\frac{1}{1 + \exp(\epsilon) } \le p \le \frac{1}{1 + \exp(-\epsilon) }$

Proof. By definition,

As $A$ is $(\epsilon, 0)$ differentially private, it holds that

and

therefore,

By symmetry, we also have

$\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
[2] L. Wasserman and S. Zhou, “A statistical framework for differential privacy,” arXiv:0811.2501 [math, stat], Oct. 2009, Accessed: Oct. 27, 2020.