Differential Privacy-Differential Privacy Fundamentals

Privacy

根据之前文中的reconstruction attacks我们发现，有许多种方法可以泄露我们的隐私，对于防护手段，我们希望它可以防护所有种类的攻击，因此，我们想要引入一种理论来描述一种防护方法面对所有攻击时可以不让隐私泄露的能力。
$k$-Anonymity
$k$-Anonymity是一种无法满足隐私的例子。它被定义为

Definition
Formally, we say that a dataset $D$ satisfies $k$-Anonymity for a value of $k$ if:

• For each row $r_1 \in D$, there exist at least $k-1$ other rows $r_2 \dots r_k \in D$ such that $\Pi_{qi(D)} r_1 = \Pi_{qi(D)} r_2, \dots, \Pi_{qi(D)} r_1 = \Pi_{qi(D)} r_k$

where $qi(D)$ is the quasi-identifiers of $D$, and $\Pi_{qi(D)} r$ represents the columns of $r$ containing quasi-identifiers (i.e. the projection of the quasi-identifiers)

通俗来讲，就是指对于数据表中的某一属性，每种类型都至少有k个样本，即有k行。比如下图

$k$-Anonymity仍然有可能泄露个人信息，从上图中我们依然可以推断出一些个人信息。比如：每个三十多岁的人都有cancer。
这里有些可以代码可以直观了解$k$-Anonymity

Differential Privacy

Definition

接下来引入Differential Privacy 差分隐私
令$\mathcal{X}$ 代表一个record所有可能情况的集合，那么一个数据集可以被视为由$\mathcal{X}$内的元素构成的集合，当$n$的大小固定时，可将其视为一个列表$x=(x_1,\dots,x_n) \in \mathcal{X}^n$（或常用直方图表示，可以写成$\mathcal{X} \rightarrow \mathbb{N}$）

我们称两个只有一个记录不同的两个数据集为neighbors。比如如果它们在下标$i$处不同，则它们应该是这样的：

$$\begin{aligned} &\mathbf{x}=\left(x_{1}, x_{2}, \ldots, x_{i-1}, \quad x_{i}, \quad x_{i+1}, \ldots, x_{n}\right)\\ &\mathbf{x}^{\prime}=\left(x_{1}, x_{2}, \ldots, x_{i-1}, \quad x_{i}^{\prime}, \quad x_{i+1}, \ldots, x_{n}\right) \end{aligned}$$

我们考虑一个算法$A$，对于每个可能的输入数据集$x$，它返回一个随机变量$A(x)$，当在两个相邻数据集上使用这种算法后，它们的输出的分布非常接近，我们称这个算法满足差分隐私。

Definition ( $\varepsilon$-DP with fixed-size data sets).
A randomized algorithm $A: \mathcal{X}^{n} \rightarrow \mathcal{Y}$ taking inputs in $\mathcal{X}^{n}$ is $\varepsilon$-differentially private for size $n$ data sets if, for every pair of neighboring data sets $\mathrm{x}^{\prime}, \mathrm{x}^{\prime}$, for all events $ E \subseteq \mathcal{Y}:$

$$\mathbb{P}(A(\mathbf{x}) \in E) \leq e^{\varepsilon} \cdot \mathbb{P}\left(A\left(\mathbf{x}^{\prime}\right) \in E\right)$$

DP的定义使用$\varepsilon$来控制$A(\mathbf{x})$和$A(\mathbf{x}^{\prime})$分布的距离。比如上图就是一个满足$\varepsilon= \frac{1}{4}$的分布，$\epsilon$越小意味着输出的分布越接近，当$\epsilon$为0时，对于所有的输入，算法都将返回相同的随机变量，即不会体现输入的任何隐私信息，但也没有了实际意义。

Randomized Response

随机化响应是一个满足DP的例子

Basic RR

一个简单的RR可以是：

Input: Data set of $n$ bits: $\mathrm{x}=\left(x_{1}, \ldots, x_{n}\right) \in\{0,1\}^{n}$
Output: Bits $Y_{1}, \ldots, Y_{n}$
for $i=1$ to $n$ do
$ \quad Y_{i}=\left\{\begin{array}{ll}x_{i} & \text { w.p. } 2 / 3 \\ 1-x_{i} & \text { w.p. } 1 / 3\end{array} ;\right.$
return $\left(Y_{1}, \ldots, Y_{n}\right)$

即对于输出是比特序列的算法，对于给定输入，有三分之二概率输出正确输出，有三分之一概率输出为原有的输出取反。