【中文翻译】第8章-The Algorithmic Foundations of Differential Privacy

由于GitHub项目仅翻译到前5章，我们从第6章开始通过大语言模型翻译，并导出markdown格式。
大模型难免存在错漏，请读者指正。

教材原文地址：https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

8 下界与分离结果

在本节中，我们将研究各种下界和权衡问题：

1. 为了不完全破坏任何合理的隐私概念，响应必须达到多大的不准确性？

2. 前一个问题的答案如何依赖于查询的数量？

3. 我们能否在每种差分隐私所允许的准确性方面，将 $\left(\epsilon ,0\right)$ -差分隐私与 $\left(\epsilon ,\delta \right)$ -差分隐私区分开来？

4. 在保持 $\left(\epsilon ,0\right)$ -差分隐私的同时，线性查询和任意低敏感度查询所能达到的效果之间是否存在本质差异？

另一种不同类型的分离结果区分了生成处理给定类中所有查询的数据结构的计算复杂度，与生成实现相同目标的合成数据库的计算复杂度。我们将对这一结果的讨论推迟到第9节。

8.1 重构攻击

我们在第1节中论证了，任何非平凡的机制都必须是随机化的。由此可知，至少对于某些数据库、查询和随机比特的选择，该机制产生的响应并非完全准确。为了保护隐私，答案必须达到多大的不准确性这一问题在所有计算模型中都有意义：交互式、非交互式以及第12节中讨论的模型。

对于失真的下界，为简单起见，我们假设数据库中每人只有一个——但非常敏感的——比特，因此我们可以将数据库视为一个 $n$ 比特的布尔向量 $d=\left(d_1,\dots ,d_n\right)$。这是对一种情况的抽象，在这种情况下，数据库行相当复杂，例如，它们可能是医疗记录，但攻击者只对一个特定字段感兴趣，比如是否存在镰状细胞特征。抽象后的攻击包括发出一系列查询，每个查询由数据库行的一个子集 $S$ 描述。该查询询问所选行中有多少个 1。将查询表示为集合 $S$ 的 $n$ 比特特征向量 $\mathbf{S}$，在对应于 $S$ 中行的所有位置上为 1，其他位置为 0，那么该查询的真实答案就是内积 $A\left(S\right)=\sum _{i=1}^n{d}_i{\mathbf{S}}_i.$

固定一个任意的隐私机制。我们用 $r\left(S\right)$ 表示对查询 $S$ 的响应。这可以通过显式方式获得，例如，如果该机制是交互式的且发出了查询 $S$，或者如果该机制预先获得了所有查询并生成了一个答案列表；也可以通过隐式方式获得，即如果该机制生成了一个概要，分析人员从中提取出 $r\left(S\right)$。请注意，$r\left(S\right)$ 可能取决于该机制所做的随机选择以及查询历史。用 $E\left(S,r\left(S\right)\right)$ 表示响应 $r\left(S\right)$ 的误差，也称为噪声或失真，因此 $E\left(S,r\left(S\right)\right)=\left|A\left(S\right)-r\left(S\right)\right|$。

我们想问的问题是：“为了保护隐私，需要多少噪声？”差分隐私是一种特定的隐私保证，但人们也可以考虑较弱的概念，因此在下界论证中，较为适度的目标不是保证隐私，而仅仅是防止出现隐私灾难。

定义 8.1。如果一个对手可以构建一个候选数据库 $c$，该数据库除了 $o\left(n\right)$ 个条目外，与真实数据库 $d$ 完全一致，即 $\parallel c-d{\parallel }_0\in o\left(n\right)$，则称该机制是明显非隐私的。

换句话说，如果一个机制允许进行重构攻击，使得对手能够正确猜出数据库中除 $o\left(n\right)$ 个成员之外所有成员的秘密位，则该机制是明显非隐私的。（不要求对手知道哪些答案是正确的。）

定理 8.1。设 $\mathcal{M}$ 是一个失真幅度受 $E$ 限制的机制。那么存在一个对手，他可以将数据库重构到误差不超过 $4E$ 个位置。

该定理的一个简单推论是，一个总是添加幅度受例如 $n/401$ 限制的噪声的隐私机制，会使对手能够正确重构 $99\%$ 个条目。

证明。设 $d$ 为真实数据库。对手分两个阶段进行攻击：

1. 估计所有可能集合中 1 的数量：对所有子集 $S\subseteq \left[n\right]$ 查询 $\mathcal{M}$。

2. 排除“遥远”的数据库：对于每个候选数据库 c ∈ { 0 , 1 } n c \in \{ 0,1{\} }^{n} c∈{0,1}n，如果存在 $\exists S\subseteq \left[n\right]$ 使得 $\left|\sum _{i\in S}{c}_i-\mathcal{M}\left(S\right)\right|>E$，则排除 $c$。如果 $c$ 未被排除，则输出 $c$ 并停止。

由于 $\mathcal{M}\left(S\right)$ 的误差从不超过 $E$，真实数据库不会被排除，因此这个简单（但效率不高！）的算法将输出某个候选数据库 $c$。我们将证明 $c$ 和 $d$ 不同的位置数量最多为 $4\cdot E$。

设 $I_0$ 为满足 $d_i=0$ 的索引，即 I 0 = { i ∣ d i = 0 } {I}_{0} = \left\{ {i \mid {d}_{i} = 0}\right\} I0​={i∣di​=0} 。类似地，定义 I 1 = { i ∣ d i = 1 } {I}_{1} = \left\{ {i \mid {d}_{i} = 1}\right\} I1​={i∣di​=1} 。由于 $c$ 未被排除，$\mid \mathcal{M}\left(I_0\right)-$ $\sum _{i\in I_0}{c}_i\left|\le E\text{. However,by assumption}\right|\mathcal{M}\left(I_0\right)-\sum _{i\in I_0}{d}_i\mid \le E$ 。根据三角不等式可知，$c$ 和 $d$ 在 $I_0$ 中至多有 $2E$ 个位置不同；同理，它们在 $I_1$ 中也至多有 $2E$ 个位置不同。因此，$c$ 和 $d$ 至多在 $4E$ 个位置上不一致。

如果我们考虑对查询次数设置更现实的界限会怎样呢？我们认为 $\sqrt{n}$ 是噪声的一个有趣阈值，原因如下：如果数据库包含从规模为 $N\gg n$ 的总体中均匀随机抽取的 $n$ 个人，且满足给定条件的总体比例为 $p$ ，那么根据二项分布的性质，我们预计数据库中满足该属性的行数大约为 $np\pm \Theta \left(\sqrt{n}\right)$ 。也就是说，抽样误差约为 $\sqrt{n}$ 。我们希望为保护隐私引入的噪声小于抽样误差，理想情况下为 $o\left(\sqrt{n}\right)$ 。接下来的结果研究了当查询次数与 $n$ 呈线性关系时，实现如此小误差的可行性。结果是否定的。

忽略计算复杂度，为了理解为什么可能存在查询高效的攻击，我们稍微修改一下问题，考虑数据库 d ∈ { − 1 , 1 } n d \in \{ - 1,1{\} }^{n} d∈{−1,1}n 和查询向量 v ∈ { − 1 , 1 } n v \in \{ - 1,1{\} }^{n} v∈{−1,1}n 。真实答案再次定义为 $d\cdot v$ ，而响应是真实答案的含噪版本。现在，考虑一个与 $d$ 差异较大的候选数据库 $c$ ，例如 $\parallel c-d{\parallel }_0\in \Omega \left(n\right)$ 。对于一个随机的 v ∈ R { − 1 , 1 } n v{ \in }_{R}\{ - 1,1{\} }^{n} v∈R​{−1,1}n ，以恒定概率有 $\left(c-d\right)\cdot v\in \Omega \left(\sqrt{n}\right)$ 。为了说明这一点，固定 x ∈ { − 1 , 1 } n x \in \{ - 1,1{\} }^{n} x∈{−1,1}n 并选择 v ∈ R { − 1 , 1 } n v{ \in }_{R}\{ - 1,1{\} }^{n} v∈R​{−1,1}n 。那么 $x\cdot v$ 是独立随机变量 x i v i ∈ R { − 1 , 1 } {x}_{i}{v}_{i}{ \in }_{R}\{ - 1,1\} xi​vi​∈R​{−1,1} 的和，其期望为 0，方差为 $n$ ，并且服从缩放和平移后的二项分布。出于同样的原因，如果 $c$ 和 $d$ 至少在 $\alpha n$ 行上不同，并且随机选择 $v$ ，那么 $\left(c-d\right)\cdot v$ 服从均值为 0 且方差至少为 $\alpha n$ 的二项分布。因此，根据二项分布的性质，我们预计 $c\cdot v$ 和 $d\cdot v$ 以恒定概率至少相差 $\alpha \sqrt{n}$ 。注意，我们使用的是分布的反集中性质，而不是通常的集中性质。

当噪声被限制为$o\left(\sqrt{n}\right)$时，这为排除$c$提供了一种攻击方法：计算$c\cdot v$与含噪响应$r\left(v\right)$之间的差值。如果该差值的幅度超过$\sqrt{n}$（在$v-$的选择上，这种情况会以恒定概率发生），则排除$c$。下一个定理将这一论点形式化，并进一步表明，即使面对很大一部分完全任意的响应，这种攻击仍然有效：如果管理员被限制在绝对误差$o\left(\sqrt{n}\right)$内回答至少$\frac{1}{2}+\eta$个问题，攻击者使用线性数量的$\pm 1$个问题，几乎可以重构整个数据库。

定理8.2。对于任意的$\eta >0$和任意函数$\alpha =\alpha \left(n\right)$，存在常数$b$，并且有一种使用$bn\pm 1$个问题的攻击方法，如果管理员在绝对误差$\alpha$内回答至少$\frac{1}{2}+\eta$个问题，该方法可以重构一个与真实数据库最多只有${\left(\frac{2\alpha }{\eta }\right)}^2$个条目不同的数据库。

证明。我们从一个简单的引理开始。

引理8.3。设$Y=\sum _{i=1}^k{X}_i$，其中每个$X_i$是一个均值为零的$\pm 2$独立伯努利随机变量。那么对于任意的$y$和任意的$\ell \in \mathbb{N},\mathrm{Pr}\left[Y\in \left[2y,2\left(y+\ell \right)\right]\right]\le \frac{\ell +1}{\sqrt{k}}.$

证明。注意到$Y$总是偶数，并且$\mathrm{Pr}\left[Y=2y\right]=\left(\begin{array}{c}k\\ \left(k+y\right)/2\end{array}\right){\left(\frac{1}{2}\right)}^k$。这个表达式至多为$\left(\begin{array}{c}k\\ \lceil k/2\rceil \end{array}\right){\left(\frac{1}{2}\right)}^k$。使用斯特林近似（Stirling’s approximation），即$n$!可以近似为$\sqrt{2n\pi }{\left(n/e\right)}^n$，它的上界为$\sqrt{\frac{2}{\pi k}}$。通过对$\left[2y,2\left(y+\ell \right)\right]$中$Y$的$\ell +1$个可能值进行联合界（union bound），即可得到该结论。

攻击者的攻击方法是选择$bn$个随机向量 v ∈ { − 1 , 1 } n v \in \{ - 1,1{\} }^{n} v∈{−1,1}n，获取响应$\left(y_1,\dots ,y_{bn}\right)$，然后输出任何满足以下条件的数据库$c$：对于至少$\frac{1}{2}+\eta$个索引$i$，有$\left|y_i-{\left(Ac\right)}_i\right|\le \alpha$，其中$A$是以随机查询向量$v$为行的$bn\times n$矩阵。

设真实数据库为$d$，并设$c$为重构后的数据库。根据该机制行为的假设，对于$i\in \left[bn\right]$的$1/2+\eta$比例，有$\left|{\left(Ad\right)}_i-y_i\right|\le \alpha$。由于$c$未被排除，我们还可知对于$i\in \left[bn\right]$的$1/2+\eta$比例，有$\left|{\left(Ac\right)}_i-y_i\right|\le \alpha$。由于任意两组这样的索引在$i\in \left[bn\right]$的至少$2\eta$比例上是一致的，根据三角不等式，对于$i,\left|{\left[\left(c-d\right)A\right]}_i\right|\le 2\alpha$的至少$2\eta bn$个值成立。

我们希望证明，除了${\left(\frac{2\alpha }{\eta }\right)}^2$个条目外，$c$与$d$是一致的。我们将证明，如果重构后的$c$与$d$相差甚远，至少在${\left(2\alpha /\eta \right)}^2$个条目上不一致，那么随机选择的$A$对于$i$的至少$2\eta bn$个值满足$\left|{\left[A\left(c-d\right)\right]}_i\right|\le 2\alpha$的概率将极小——小到对于一个随机的$A$，甚至不太可能存在一个与$d$相差甚远且未被$A$中的查询排除的$c$。

假设向量 z = ( c − d ) ∈ { − 2 , 0 , 2 } n z = \left( {c - d}\right) \in \{ - 2,0,2{\} }^{n} z=(c−d)∈{−2,0,2}n的汉明重量（Hamming weight）至少为${\left(\frac{2\alpha }{\eta }\right)}^2$，因此$c$与$d$相差甚远。我们已经论证过，由于$c$是由攻击者生成的，对于$i$的至少$2\eta bn$个值，有$\left|{\left(Az\right)}_i\right|\le 2\alpha$。我们将这样的$z$称为相对于$A$的“坏”值。我们将证明，在$A$的选择上，大概率不会有相对于$A$的“坏”$z$。

对于任意的$i,v_{i}z$，它是至少${\left(\frac{2\alpha }{\eta }\right)}^2\pm 2$个随机值的和。设$k={\left(2\alpha /\eta \right)}^2$和$\ell =2\alpha$，根据引理8.3，$v_{i}z$落在大小为$4\alpha$的区间内的概率至多为$\eta$，因此$\left|v_{i}z\right|\le 2\alpha$成立的查询的期望数量至多为$\eta bn$。切诺夫界（Chernoff bounds）现在表明，这个数量超过$2\eta bn$的概率至多为$\exp \left(-\frac{\eta bn}{4}\right)$。因此，特定的$z=c-d$相对于$A$为“坏”的概率至多为$\exp \left(-\frac{\eta bn}{4}\right)$。

对至多 $3^n$ 种可能的 $z\mathrm{s}$ 取并集界，我们得到，至少以 $1-\exp \left(-n\left(\frac{\eta b}{4}-\ln 3\right)\right)$ 的概率，不存在不良的 $z$。取 $b>4\ln 3/\eta$ 时，存在这种不良 $z$ 的概率在 $n$ 上呈指数级小。

防止明显的非隐私性对于隐私机制来说是一个非常低的标准，因此，如果差分隐私有意义，那么防止明显非隐私性的下界也将适用于任何确保差分隐私的机制。尽管在本专著中我们大部分情况下忽略计算问题，但还存在攻击效率的问题。假设我们能够证明（也许在某些计算假设下）存在难以破解的低失真机制；例如，对于那些生成接近原始数据库的候选数据库 $c$ 很困难的机制呢？那么，尽管低失真机制在理论上可能无法实现差分隐私，但可以想象它能为有界对手提供隐私保护。不幸的是，情况并非如此。特别是，当噪声始终在 $o\left(\sqrt{n}\right)$ 中时，存在一种使用恰好 $n$ 个固定查询的高效攻击；此外，甚至存在一种计算高效的攻击，需要线性数量的查询，其中 0.239 的比例可能会被带有极大噪声的回答。

对于“互联网规模”的数据集，获取 $n$ 个查询的响应是不可行的，因为 $n$ 非常大，例如 $n\ge {10}^8$。如果数据管理者只允许进行亚线性数量的查询会怎样呢？这一探究引出了（后来发展为）$\left(\epsilon ,\delta \right)$ -差分隐私的首个算法结果，其中展示了如何通过向每个真实答案添加阶为 $o\left(\sqrt{n}\right)$ 的二项式噪声（小于采样误差！）来针对亚线性数量的计数查询保持隐私。利用差分隐私的工具，我们可以通过以下两种方式实现：（1）高斯机制或（2）拉普拉斯机制和高级组合。

8.2 差分隐私的下界

上一节的结果给出了确保任何合理隐私概念所需失真的下界。相比之下，本节的结果是针对差分隐私的。尽管证明中的一些细节相当技术性，但主要思想很精妙：假设（不知何故）对手已将可能的数据库集合缩小到一个相对较小的由 $2^s$ 个向量组成的集合 $S$，其中每对向量之间的 $L_1$ 距离是某个较大的数 $\Delta$。进一步假设我们可以找到一个 $k$ 维查询 $F$，其每个输出坐标都是 1 - 利普希茨的，并且具有这样的性质：在我们集合中的不同向量上，该查询的真实答案看起来非常不同（在 $L_{\infty }$ 范数下）；例如，集合中任意两个元素上的距离可能是 $\Omega \left(k\right)$。从几何角度思考“答案空间” ${\mathbb{R}}^k$ 会很有帮助。集合 $S$ 中的每个元素 $x$ 在答案空间中产生一个向量 $F\left(x\right)$。实际响应将是答案空间中该点的一个扰动。然后，基于体积的鸽巢原理（在答案空间中）表明，如果（带噪声的）响应以中等概率“合理地”接近真实答案，那么 $ϵ$ 不可能非常小。

这源于以下事实：对于$\left(\epsilon ,0\right)$ - 差分隐私机制$\mathcal{M}$，对于任意不同的数据库$x,y$，$\mathcal{M}\left(x\right)$的支撑集中的任何响应也在$\mathcal{M}\left(y\right)$的支撑集中。结合向量的适当集合构造和一个（人为设计的、非计数的）查询，该结果得出了一个线性的失真下界$k/\epsilon$。该论证引用了讨论群组隐私的定理2.2。在我们的例子中，所讨论的群组对应于$S$中一对向量之间$\left(L_1\right)$距离的贡献指标。

8.2.1 通过填充论证得出的下界

我们从一个直观的观察开始，即如果当查询为$F$时，“可能的”响应区域是不相交的，那么我们可以从下方界定$ϵ$，表明隐私性不能太好。当$\parallel F\left(x_i\right)-$ ${F\left(x_j\right)\parallel }_{\infty }$很大时，这意味着为了获得非常好的隐私性，即使限制在许多地方不同的数据库上，我们也必须在$F$的某些坐标上得到非常错误的响应。

该论证使用了数据库的直方图表示。在后续内容中，$d=\left|\mathcal{X}\right|$表示抽取数据库元素的全集的大小。

引理8.4。假设存在一个集合 S = { x 1 , … , x 2 s } S = \left\{ {{x}_{1},\ldots ,{x}_{{2}^{s}}}\right\} S={x1​,…,x2s​}，其中每个$x_i\in {\mathbb{N}}^d$，使得对于$i\ne j,{\Vert \begin{array}{c}{x}_i-x_j\end{array}\Vert }_1\le \Delta$。此外，设$F$ : ${\mathbb{N}}^d\to {\mathbb{R}}^k$是一个$k$维查询。对于$1\le i\le 2^s$，设$B_i$表示${\mathbb{R}}^k$（答案空间）中的一个区域，并假设$B_i$是相互不相交的。如果$\mathcal{M}$是$F$的一个$\left(\epsilon ,0\right)$ - 差分隐私机制，使得$\forall 1\le i\le 2^s,\mathrm{Pr}\left[\mathcal{M}\left(x_i\right)\in B_i\right]\ge 1/2$，那么$\epsilon \ge \frac{\ln \left(2\right)\left(s-1\right)}{\Delta }$。

证明。根据假设$\mathrm{Pr}\left[\mathcal{M}\left(x_j\right)\in B_j\right]\ge 2^{-1}$。由于区域$B_1,\dots ,B_{2^s}$是不相交的，$\exists j\ne i\in \left[2^s\right]$使得$\mathrm{Pr}\left[\mathcal{M}\left(x_i\right)\in B_j\right]\le 2^{-s}$。也就是说，对于至少一个$2^s-1$区域$B_j$，$\mathcal{M}\left(x_i\right)$被映射到这个$B_j$的概率至多为$2^{-s}$。将此与差分隐私相结合，我们有

$$\frac{2^{-1}}{2^{-s}}\le \frac{\underset{\mathcal{M}}{\mathrm{Pr}}\left[B_j\mid x_j\right]}{\underset{\mathcal{M}}{\mathrm{Pr}}\left[B_j\mid x_i\right]}\le \exp \left(\epsilon \Delta \right).$$

推论8.5。设 S = { x 1 , … , x 2 s } S = \left\{ {{x}_{1},\ldots ,{x}_{{2}^{s}}}\right\} S={x1​,…,x2s​}如引理8.4中所定义，并假设对于任意$i\ne j,{\Vert \begin{array}{c}F\left(x_i\right)-F\left(x_j\right)\end{array}\Vert }_{\infty }\ge \eta$ 。设$B_i$表示${\mathbb{R}}^k$中以$x_i$为中心、半径为$\eta /2$的$L_{\infty }$球。设$\mathcal{M}$是满足以下条件的$F$的任意$\epsilon$ -差分隐私机制

$$\forall 1\le i\le 2^s:\mathrm{Pr}\left[\mathcal{M}\left(x_i\right)\in B_i\right]\ge 1/2.$$

那么$\epsilon \ge \frac{\left(\ln 2\right)\left(s-1\right)}{\Delta }$ 。

证明。区域$B_1,\dots ,B_{2^s}$是不相交的，因此引理8.4的条件得到满足。通过应用该引理并取对数可得出此推论。

在下面的定理8.8中，我们将考虑查询$F$，它们只是$k$个独立随机生成的（非线性！）查询。对于合适的$S$和$F$（我们将努力找到这些值），该推论表明，如果至少以概率$1/2$所有响应同时具有小误差，那么隐私性就不会太好。换句话说，

断言8.6（推论8.5的非正式重述）。为了获得$\epsilon \le \frac{\ln \left(2\right)\left(s-1\right)}{\Delta }$的$\left(\epsilon ,0\right)$ -差分隐私，该机制必须以超过$1/2$的概率添加$L_{\infty }$范数大于$\eta /2$的噪声。

作为一个热身练习，我们证明一个需要大数据域的较简单定理。

定理8.7。设 X = { 0 , 1 } k \mathcal{X} = \{ 0,1{\} }^{k} X={0,1}k 。设$\mathcal{M}:{\mathcal{X}}^n\to {\mathbb{R}}^k$是一个$\left(\epsilon ,0\right)$ -差分隐私机制，使得对于每个数据库$x\in {\mathcal{X}}^n$，至少以概率$1/2\mathcal{M}\left(x\right)$输出$x$的所有一维边际分布，且误差小于$n/2$ 。也就是说，对于每个$j\in \left[k\right]$，$\mathcal{M}\left(x\right)$的第$j$个分量应近似等于$x$中第$j$位为1的行数，误差小于$n/2$ 。那么$n\in \Omega \left(k/\epsilon \right)$ 。

注意，根据简单组合定理，这个界在常数因子范围内是紧的，并且对于$\delta \in 2^{-o\left(n\right)}$，它将$\left(\epsilon ,0\right)$ -差分隐私与$\left(\epsilon ,\delta \right)$ -差分隐私区分开来，因为根据高级组合定理（定理3.20），参数为$b=\sqrt{k\ln \left(1/\delta \right)}/\epsilon$的拉普拉斯噪声足以满足前者，而后者需要$\Omega \left(k/\epsilon \right)$ 。取$k\in \Theta \left(n\right)$，例如$\delta =2^{-{\log }^{2}n}$，就可以得到这种区分。

证明。对于每个字符串 w ∈ { 0 , 1 } k w \in \{ 0,1{\} }^{k} w∈{0,1}k，考虑由 $n$ 个相同行组成的数据库 $x_w$，所有这些行都等于 $w$。设 $B_w\in {\mathbb{R}}^k$ 由所有能为 $x$ 上的单向边际提供误差小于 $n/2$ 的答案的数字元组组成。即，

B w = { ( a 1 , … , a k ) } ∈ R k : ∀ i ∈ [ k ] ∣ a i − n w i ∣ < n / 2 } . {B}_{w} = \left\{ \left( {{a}_{1},\ldots ,{a}_{k}}\right) \right\} \in {\mathbb{R}}^{k} : \forall i \in \left\lbrack k\right\rbrack \left| {{a}_{i} - n{w}_{i}}\right| < n/2\} . Bw​={(a1​,…,ak​)}∈Rk:∀i∈[k]∣ai​−nwi​∣<n/2}.

换句话说，$B_w$ 是以 n w ∈ { 0 , n } k {nw} \in \{ 0,n{\} }^{k} nw∈{0,n}k 为中心、半径为 $n/2$ 的开 ${\ell }_{\infty }$。注意，集合 $B_w$ 是互不相交的。

如果 $\mathrm{M}$ 是一个用于回答单向边际的准确机制，那么对于每个 $w$，当数据库为 $x_w$ 时落入 $B_w$ 的概率至少应为 $1/2:\mathrm{Pr}\left[\mathcal{M}\left(x_w\right)\in B_w\right]\ge 1/2$。因此，在推论 8.5 中令 $\Delta =n$ 和 $s=k$，我们有 $\epsilon \ge \frac{\left(\ln 2\right)\left(s-1\right)}{\Delta }$。

定理 8.8。对于任意的 $k,d,n\in \mathbb{N}$ 和 $\epsilon \in (0,1/40]$，其中 $n\ge$ min ⁡ { k / ε , d / ε } \min \{ k/\varepsilon ,d/\varepsilon \} min{k/ε,d/ε}，存在一个每个坐标敏感度至多为 1 的查询 $F:{\mathbb{N}}^d\to {\mathbb{R}}^k$，使得任何 $\left(\epsilon ,0\right)$ -差分隐私机制在某些权重至多为 $n$ 的数据库上以至少 $1/2$ 的概率添加 $L_{\infty }$ 范数为 Ω ( min ⁡ { k / ε , d / ε } ) \Omega \left( {\min \{ k/\varepsilon ,d/\varepsilon \} }\right) Ω(min{k/ε,d/ε}) 的噪声。

注意，与定理 8.7 中的要求不同，这里的 $d=\left|\mathcal{X}\right|$ 不必很大。

证明。设 ℓ = min ⁡ { k , d } \ell = \min \{ k,d\} ℓ=min{k,d}。利用纠错码，我们可以构造一个集合 S = { x 1 , … , x 2 s } S = \left\{ {{x}_{1},\ldots ,{x}_{{2}^{s}}}\right\} S={x1​,…,x2s​}，其中 $s=\ell /400$，使得每个 $x_i\in {\mathbb{N}}^d$，此外

1. $\forall i:{\Vert \begin{array}{c}{x}_i\end{array}\Vert }_1\le w=\ell /\left(1280\epsilon \right)$

2. $\forall i\ne j,{\Vert \begin{array}{c}{x}_i-x_j\end{array}\Vert }_1\ge w/10$

我们在此不给出详细信息，但我们注意到$S$中的数据库大小至多为$w<n$，因此${\Vert \begin{array}{c}{x}_i-x_j\end{array}\Vert }_1\le 2w$。取$\Delta =2w$，集合$S$满足推论8.5的条件。我们接下来的工作是得到查询$F$，以便应用推论8.5。给定 S = { x 1 , … , x 2 s } S = \left\{ {{x}_{1},\ldots ,{x}_{{2}^{s}}}\right\} S={x1​,…,x2s​}，其中每个$x_i\in {\mathbb{N}}^d$，第一步是定义一个从直方图空间到${\mathbb{R}}^{2^s},{\mathcal{L}}_S:{\mathbb{N}}^d\to {\mathbb{R}}^{2^s}$中向量的映射。直观地（且不精确地！），给定一个直方图$x$，该映射会列出对于每个$x_i\in S$，从$x$到$x_i$的$L_1$距离。更精确地说，设$w$是我们集合中任何$x_i$的权重上限，我们按如下方式定义该映射。

• 对于每个$x_i\in S$，在映射中有一个坐标$i$。

• ${\mathcal{L}}_S\left(x\right)$的第$i$个坐标是$\max \left\{w/30-{\Vert \begin{array}{c}{x}_i-z\end{array}\Vert }_1,0\right\}$。

命题8.9。如果$x_1,\dots ,x_{2^s}$满足条件

1. $\forall i{\Vert \begin{array}{c}{x}_i\end{array}\Vert }_1\le w$；并且

2. $\forall i\ne j{\Vert \begin{array}{c}{x}_i-x_j\end{array}\Vert }_1\ge w/10$

那么映射${\mathcal{L}}_S$是1 - 利普希茨的；特别地，如果${\Vert \begin{array}{c}{z}_1-z_2\end{array}\Vert }_1=1$，那么${\Vert \begin{array}{c}{\mathcal{L}}_S\left(z_1\right)-{\mathcal{L}}_S\left(z_2\right)\end{array}\Vert }_1\le 1$，假设$w\ge 31$。证明。由于我们假设$w\ge 31$，我们有如果$z\in {\mathbb{N}}^d$接近某个$x_i\in S$，即$w/30>{\Vert \begin{array}{c}{x}_i-z\end{array}\Vert }_1$，那么$z$不可能接近任何其他$x_j\in S$，并且对于所有${\Vert \begin{array}{c}{z}^{\prime }-z\end{array}\Vert }_1\le 1$都成立。因此，对于任何满足$\Vert \begin{array}{c}{z}_1-z_2\end{array}\Vert \le 1$的$z_1,z_2$，如果$A$表示${\mathcal{L}}_S\left(z_1\right)$或${\mathcal{L}}_S\left(z_2\right)$中至少有一个非零的坐标集合，那么$A$要么为空集，要么为单元素集。鉴于此，该命题中的陈述可直接从对应于任何特定坐标的映射显然是1 - 利普希茨的这一事实得出。

我们最终可以描述查询 $F$。对应于任意 $r\in$ { − 1 , 1 } 2 s \{ - 1,1{\} }^{{2}^{s}} {−1,1}2s，我们将 $f_r:{\mathbb{N}}^d\to \mathbb{R}$ 定义为

$$f_r\left(x\right)=\sum _{i=1}^d{\mathcal{L}}_S{\left(x\right)}_i\cdot r_i$$

这仅仅是内积 ${\mathcal{L}}_S\cdot r.F$ 将是一个随机映射 $F:{\mathbb{N}}^d\to {\mathbb{R}}^k$：独立且均匀地随机选取 r 1 , … , r k ∈ { − 1 , 1 } 2 s {r}_{1},\ldots ,{r}_{k} \in \{ - 1,1{\} }^{{2}^{s}} r1​,…,rk​∈{−1,1}2s 并定义

$$F\left(x\right)=\left(f_{r_1}\left(x\right),\dots ,f_{r_k}\left(x\right)\right).$$

也就是说，$F\left(x\right)$ 仅仅是 ${\mathcal{L}}_S\left(x\right)$ 与随机选取的 $k$ 个 $\pm 1$ 向量的内积结果。

注意，对于任意 $x\in S{\mathcal{L}}_S\left(x\right)$ 有一个坐标的值为 $w/30$（其他坐标均为零），因此对于 ∀ r i ∈ { − 1 , 1 } 2 s \forall {r}_{i} \in \{ - 1,1{\} }^{{2}^{s}} ∀ri​∈{−1,1}2s 和 $x\in S$，我们有 $\left|f_{r_i}\left(x\right)\right|=w/30$。现在考虑任意 $x_h,x_j\in S$，其中 $h\ne j$。由此可知，对于任意 r i ∈ { − 1 , 1 } 2 s {r}_{i} \in \{ - 1,1{\} }^{{2}^{s}} ri​∈{−1,1}2s，

$$\underset{r_i}{\mathrm{Pr}}\left[\left|f_{r_i}\left(x_h\right)-f_{r_i}\left(x_j\right)\right|\ge w/15\right]\ge 1/2$$

（当 ${\left(r_i\right)}_h=-{\left(r_i\right)}_j$ 时，此事件发生）。切尔诺夫界（Chernoff bound）的一个基本应用表明

$$\underset{r_1,\dots ,r_k}{\mathrm{Pr}}\text{[For at least}1/10\text{of the}{r}_i\mathrm{s}\text{,}$$

$$\left|f_{r_i}\left(x_h\right)-f_{r_i}\left(x_j\right)\right|\ge w/15]\ge 1-2^{-k/30}.$$

现在，满足 $x_i,x_j\in S$ 的数据库对 $\left(x_i,x_j\right)$ 的总数至多为 $2^{2s}\le 2^{k/200}$。取并集界，这意味着

$$\underset{r_1,\dots ,r_k}{\mathrm{Pr}}[\forall h\ne j,\text{ For at least }1/10\text{ of the }{r}_i\mathrm{s},$$

$$\left|f_{r_i}\left(x_h\right)-f_{r_i}\left(x_j\right)\right|\ge w/15]\ge 1-2^{-k/40}$$

这意味着我们可以固定 $r_1,\dots ,r_k$，使得以下情况成立。

$\forall h\ne j,$ 对于 $r_i\mathrm{s},\left|f_{r_i}\left(x_h\right)-f_{r_i}\left(x_j\right)\right|\ge w/15$ 中的至少 $1/10$ 个。因此，对于任意 $x_h\ne x_j\in S,{\Vert \begin{array}{c}F\left(x_h\right)-F\left(x_j\right)\end{array}\Vert }_{\infty }\ge w/15$。

设置 $\Delta =2w$ 和 $s=\ell /400>3\epsilon w$（如我们上面所做的），以及 $\eta =w/15$，我们满足推论 8.5 的条件，并得出 $\Delta \le \left(s-1\right)/\epsilon$，从而证明了该定理（通过断言 8.6）。

该定理几乎是紧的：如果 $k\le d$，那么我们可以对 $F$ 中每个敏感度为 1 的分量查询应用参数为 $k/\epsilon$ 的拉普拉斯机制（Laplace mechanism），并且我们预计最大失真为 $\Theta \left(k\ln k/\epsilon \right)$。另一方面，如果 $d\le k$，那么我们可以对表示数据库的 $d$ 维直方图应用拉普拉斯机制，并且我们预计最大失真为 $\Theta \left(d\ln d/\epsilon \right)$。

该定理实际上表明，给定集合$S$的知识以及实际数据库是元素$x\in S$的知识，如果失真的$L_{\infty }$范数过小，攻击者可以完全确定$x$。在现实生活中，攻击者如何获得攻击中使用的那种集合$S$呢？当一个非隐私数据库系统在一个数据集（例如$x$）上运行时，就可能出现这种情况。例如，$x$可以是 { 0 , 1 } n \{ 0,1{\} }^{n} {0,1}n中的一个向量，攻击者可能通过一系列线性查询得知$x\in \mathcal{C}$，即一个距离为（例如$n^{2/3}$）的线性码。当然，如果数据库系统不承诺隐私，那就没有问题。问题在于，如果管理员在多次查询收到无噪声响应后，决定用差分隐私机制取代现有的系统。特别是，如果管理员选择对后续的$k$查询使用$\left(\epsilon ,\delta \right)$ - 差分隐私，那么失真可能会低于$\Omega \left(k/\epsilon \right)$下界，从而允许进行定理8.8证明中描述的攻击。

该定理还强调，关于数据库成员（集合）的辅助信息与关于整个数据库的信息之间存在根本差异。当然，我们早已知道这一点：被告知秘密比特的总数恰好为5000，会完全破坏差分隐私，而且一个已经知道除了一个个体之外数据库中每个成员的秘密比特的攻击者，就可以推断出剩余个体的秘密比特。

额外的结论。假设$k\le d$，那么在定理8.8中$\ell =k$。上一节中概述的针对$k$查询的关于$k/\epsilon$的线性噪声下界，立即揭示了计数查询和任意1 - 敏感度查询之间的区别，因为SmallDB构造在保持差分隐私的同时，以大约$n^{2/3}$的噪声回答（超过）$n$个查询。实际上，这个结果还使我们能够得出结论，对于任意低敏感度查询的大集合，不存在小的$\alpha$ - 网，对于$\alpha \in o\left(n\right)$（因为否则网机制将产生一个具有所需精度的$\left(\epsilon ,0\right)$算法）。

8.3 参考文献注释

包括定理8.1在内的第一批重构攻击归功于迪努尔（Dinur）和尼斯姆（Nissim）[18]，他们还给出了一种攻击方法，只要噪声始终为$o\left(\sqrt{n}\right)$，该攻击只需要多项式时间计算和$O\left(n{\log }^{2}n\right)$次查询。迪努尔、德沃克（Dwork）和尼斯姆意识到，当$n$达到“互联网规模”时，需要$n$次随机线性查询的攻击是不可行的，于是他们给出了第一个正面结果，表明对于次线性数量的子集和查询，可以通过添加缩放为$o\left(\sqrt{n}\right)$的噪声来实现一种隐私形式（现在已知这意味着$\left(\epsilon ,\delta \right)$ - 差分隐私）[18]。这很令人兴奋，因为它表明，如果我们认为数据库是从一个基础总体中抽取的，那么，即使对于相对大量的计数查询，也可以用小于采样误差的失真来实现隐私。这最终通过更一般的查询[31, 6]引出了差分隐私。将这些查询视为一种隐私保护编程原语[6]的观点，启发了麦克谢里（McSherry）的隐私集成查询编程平台[59]。

定理8.2的重构攻击出现在[24]中，德沃克、麦克谢里和塔尔瓦尔（Talwar）在该文献中表明，即使有0.239比例的响应具有极大的任意噪声，只要其他响应的噪声为$o\left(\sqrt{n}\right)$，就可以进行多项式时间重构。

几何方法，尤其是引理8.4，归功于哈特（Hardt）和塔尔瓦尔（Talwar）[45]，他们还给出了一种基于几何的算法，在一个普遍被认可的猜想下，证明了对于少量$k\le n$查询，这些边界是紧的。后来，巴斯卡拉（Bhaskara）等人[5]消除了对该猜想的依赖。尼科洛夫（Nikolov）等人[66]将几何方法扩展到任意数量的查询，他们给出了一种具有实例最优均方误差的算法。对于少量查询的情况，通过一个增强论证，这会导致较低的预期最坏情况误差。定理8.8归功于德（De）[17]。

目录导航

第1章：https://blog.csdn.net/AdamCY888/article/details/146454841
第2章:https://blog.csdn.net/AdamCY888/article/details/146455093
第3章(1/3):https://blog.csdn.net/AdamCY888/article/details/146455756
第3章(2/3):https://blog.csdn.net/AdamCY888/article/details/146455796
第3章(3/3):https://blog.csdn.net/AdamCY888/article/details/146455328
第4章:https://blog.csdn.net/AdamCY888/article/details/146455882
第5章:https://blog.csdn.net/AdamCY888/article/details/146456100
第6章(1/2):https://blog.csdn.net/AdamCY888/article/details/146456712
第6章(2/2):https://blog.csdn.net/AdamCY888/article/details/146456972
第7章:https://blog.csdn.net/AdamCY888/article/details/146457037
第8章:https://blog.csdn.net/AdamCY888/article/details/146457172
第9章:https://blog.csdn.net/AdamCY888/article/details/146457257
第10章:https://blog.csdn.net/AdamCY888/article/details/146457331
第11章:https://blog.csdn.net/AdamCY888/article/details/146457418
第12章:https://blog.csdn.net/AdamCY888/article/details/146457489
第13章(含附录):https://blog.csdn.net/AdamCY888/article/details/146457601