2.3 形式化差分隐私

• 1.掷硬币。

• 2.如果是反面，那就如实回答。

• 3.如果是正面，则掷第二枚硬币，正面回答“是”，反面回答“否”。

“隐私”来源于对任何输出的合理否认；特别是，如果拥有财产 $P$ 相当于从事非法行为，即使是“是”答案也不构成犯罪，因为无论被告是否实际拥有财产 $P$ ，这个答案出现的概率至少为 $1/4$。准确度来自于对噪声产生过程的理解（随机分组中引入虚假的“是”和“否”答案）：预期的“是”答案的概率是：没有属性 $P$ 的参与者概率的 $1/4$ 加上有属性 $P$ 的概率的 $3/4$ 。因此，如果 $p$ 是具有 $p$ 属性的参与者的真实概率，则“是”答案的预期概率为 $(1/4)(1-p)+(3/4)p=(1/4)+p/2$。因此，我们可以将 $p$ 估计为回答“是”的概率的两倍减去 $1/2$ ，即 $2((1/4)+p/2)-1/2$ (此处个人感觉有误) 。

\begin{aligned} P_B &= 1/4 (1 - P_A) + 3/4 P_A \\ &= 1/4 + 1/2 P_A \\ P_A &= 2 * P_B - 1/2 \end{aligned}

$\Delta(B) = \{ x \in \mathbb{R}^{|B|} : x_i \geqslant 0\ for\ all\ i\ and\ \sum_{i=1}^{|B|}x_i = 1 \}$

\begin{aligned} if \ \overrightarrow{B} = \{ 0,1 \},then \ \mathbb{R}^{|B|} = R \times R \\ \overrightarrow{x} \in R \times R \ (i.e:(x_1,x_2) \in \overrightarrow{x}) \\ \sum_{i=1}^{|B|}x_i = \sum_{i=1}^{2}x_i = x_1 + x_2 = 1 \end{aligned}

I have contacted the authors and they were very helpful. The original quote says it all:

The book is about randomized algorithms that act on data sets. You can always view these as deterministic algorithms, which take two inputs -- the data set, and also a string of random bits.

The definition of differential privacy has a probability operator, and what that remark means is that the probability is taken over the randomness of the random bit string (i.e. the internal randomness of the algorithm), holding the data set fixed.

The key to this is that the definition says: "the algorithm $\mathcal{M}$ outputs ... with probability ...". This is a random choice, and the source of randomness is defined by the sentence "The probability space is over the coin flips of the algorithm $\mathcal{M}$".

$\Vert x\Vert _1 = \sum_{i=1}^{|\mathcal{X}|}|x_i|$