Differential Privacy

1. 差分隐私的定义

$\epsilon$-indistinguishability. Two random variables $A$ and $B$ are $\epsilon$-indistinguishable, denoted $A\approx_\epsilon B$, if for all measurable sets $X$ of possible events:

$$\mathbb{P}[A\in X] \leq e^\epsilon \cdot \mathbb{P}[B\in X]$$

and

$$\mathbb{P}[B\in X] \leq e^\epsilon \cdot \mathbb{P}[A\in X]$$

差分隐私的定义 2

A privacy mechanism $\mathcal{M}$ is $\epsilon$-differential private (or $\epsilon$-DP) if for all datasets $D_1$ and $D_2$ that differ only in one record, $\mathcal{M}(D_1)\approx_\epsilon \mathcal{M}(D_2)$

---

2. 差分隐私的分类

关于差分隐私的分类目前还没有定论，一种观点是从两个角度来看差分隐私：

• 从 associative 的角度，
• 从 causal 的角度，

Privacy axioms:

• Post-processing, for any mechanism $\mathcal{M}$ satisfying Def and any probabilistic function $f$, the mechanism $D\to f(M(D))$ also satisfies Def.
• Convexity, for any two mechanisms $\mathcal{M}_1$ and $\mathcal{M}_2$ satifying Def, the mechanism $\mathcal{M}$ defined by $\mathcal{M}(D)=\mathcal{M}_1(D)$ with probability $p$ and $\mathcal{M}(D)=\mathcal{M}_2(D)$ with probability $1-p$ also satisfies Def.

Privacy loss random variable. Let $\mathcal{M}$ be a mechanism, and $D_1$ and $D_2$ two datasets. The privacy loss random variable between $\mathcal{M}(D_1)$ and $\mathcal{M}(D_2)$ is defined as:

$$\mathcal{L}_{\mathcal{M}(D_1)/ \mathcal{M}(D_2)} (O) = \ln\big(\frac{\mathbb{P}[\mathcal{M}(D_1) = O]}{\mathbb{P}[\mathcal{M}(D_2) = O]}\big)$$

$(\epsilon-\delta)$-differential privacy. A privacy mechanism $\mathcal{M}$ is $(\epsilon-\delta)$-DP if for any datasets $D_1$ and $D_2$ that differ only on one record, and for all $S\subseteq \mathcal{O}$:

$$\mathbb{P}[\mathcal{M}(D_1)\in S] \leq e^\epsilon \cdot \mathbb{P}[\mathcal{M}(D_2) \in S] + \delta$$

$(\epsilon-\delta)$-probabilistic differential privacy. A privacy mechanism $\mathcal{M}$ is $(\epsilon-\delta)$-probabilistically DP (ProDP) if for any datasets $D_1$ and $D_2$ that differ from only on one record there is a set $S_1\subseteq \mathcal{O}$ where $\mathbb{P}[\mathcal{M}(D_1)\in S_1] \leq \delta$, such that for all measurable sets $S\subseteq \mathcal{O}$:

$$\mathbb{P}[\mathcal{M(D_1)}\in S\backslash S_1] \leq e^\epsilon \cdot \mathbb{P}[\mathcal{M}(D_2) \in S\backslash S_1]$$

---

3. 本地差分隐私 (Local Differential Privacy)