3.5.2 高级合成技术

除了允许参数降级得更慢之外，我们希望我们的定理能够处理更复杂的合成形式。但是，在开始之前，我们必须讨论合成对我们的确切含义。我们希望我们的定义涵盖以下两个有趣的场景：

• 1.在同一数据库上重复使用差分隐私算法。这允许多次重复使用相同的机制，以及从任意私有模块中模块化构造差分私有算法。
• 2.在不同的数据库上重复使用差分隐私算法，这些数据库可能包含与同一个人的有关信息。这使我们能够推断出一个个体的隐私累积损失，其数据可能分布在多个数据集上，每个数据库可能使用不同的差分隐私算法独立运行。由于新数据库一直在创建，并且对手实际上可能会影响这些新数据库的合成，因此与重复查询单个固定数据库相比，这是一个根本不同的问题。

我们希望对合成进行建模，在这些合成中攻击者可以适应性地影响未来机制输入的数据库以及对这些未来机制的查询。令 $\mathcal{F}$ 为一系列数据库访问机制。（例如 $\mathcal{F}$ 可以是所有 $\varepsilon-$差分隐私机制的集合）对于概率对手 $A$，我们考虑两个实验，实验0和实验1定义如下。

对机制集合 $\mathcal{F}$ 与对手 $A$ 进行实验 b ：

$i=1,...,k$

• 1. $A$ 输出两个相邻数据集 $x_i^0,x_i^1$，和机制 $\mathcal{M}_i \in \mathcal{F}$，且参数为 $w_i$。
• 1. $A$ 接收 $y_i \in_{R} \mathcal{M}_i(w_i,x_{i,b})$

我们允许上面的对手 $A$ 在整个实验中都是有状态的，因此，它可以根据先前机制的输出自适应地选择数据库，机制和参数。我们将 $A$ 对实验的观点定义为 {0，1}（$A$ coin tosses）和所有机制输出 $(y_1,...,y_k)$ 共同组成。（$x_i^j,\mathcal{M}_i,w_i$ 都可以从这些看法中重建。）

出于直观表示，我们假设一个对手总是选择 $x_i^0$ 保存 Bob 的数据，而 $x_i^1$ 与 $x_i^0$ 的区别只有 Bob 的数据在 $x_i^1$ 中被删除。然后实验0 可以被认为是“真实世界”，Bob 允许他的数据在许多数据发布中使用；实验1 是“理想世界”，这些数据发布的结果不依赖于 Bob 的数据。就像差分隐私定义所要求的那样，我们对隐私的定义仍然要求这两个实验相互“接近”。对 Bob 的直观保证是，即使给了攻击者所有 $k$ 个机制的输出，对手仍然“不知道” Bob 的数据是否被使用了。

定义 3.7 如果对每个对手 $A$，我们都有 $D_{\infty}(V^0||V^1)\leq \varepsilon$，则数据库访问机制族 $\mathcal{F}$ 满足 $k$ 倍自适应合成下的 $\varepsilon$-差分隐私(ε-differential privacy under k-fold adaptive composition)，其中 $V^b$ 表示在上述 $k$ 倍合成实验b 中 $A$ 的观点。 在 $k$ 倍自适应组合下的 $(\varepsilon,\delta)$-差分隐私要求$D_{\infty}^{\delta}(V^0||V^1)\leq \varepsilon$。

（个人理解：这里攻击者有很大的能力，可以构造查询，构造机制，构造参数等。合成差分隐私数据库需要防范的是，即使攻击者有如此多的攻击“能力”，也能保证攻击者无法辨别用户数据是否参与发布。

那么合成机制防范攻击的标准是什么？换句话说，合成机制最多能允许多少隐私损失？首先，作者在这里设置了两种情况（实验）代表攻击者对用户隐私的猜测，即：用户数据参与机制合成发布（实验0）、用户数据不参与合成发布（实验1）。其次，由于攻击者拥有很高的“权限”，所以可以获取合成数据库不同机制生成的不同结果（上文里的 $(y_1,...,y_k)$ ）。所以攻击者通过不同的结果，来判断两种实验发生的概率（对两种实验的观点）。若攻击者认为，用户参与到合成机制的发布中，那么 $V^0$ 的概率会远高于 $V^1$，反之亦然。只有两者概率相差大，才能作出判断，若两者概率接近，那么攻击者无法作出判断。这点可以与前几章提到的普通差分隐私概念做类比，将普通差分隐私概念扩展到了合成机制。

最后，作者使用 3.5.1节 定义3.6 (最大散度) 对合成机制下的差分隐私作出了定义，即：$k$ 倍自适应合成下的 $\varepsilon$-差分隐私 ）

定理 3.20（高级合成）。 对于所有 $\varepsilon,\delta,\delta'\geq 0$，$(\varepsilon,\delta)$-差分隐私机制类满足 $k$ 倍自适应合成下的 $(\varepsilon',k\delta+\delta')$-差分隐私，其中：

$\varepsilon' = \sqrt{2k\ln(1/\delta')}\cdot\varepsilon + k\varepsilon(e^{\varepsilon}-1)$ 【证明】 略

如果我们希望针对给定的 $\varepsilon',\delta'$ 确保 $(\varepsilon',k\delta+\delta')$-差分隐私，则一个直接有用的推论告诉我们一个 $\varepsilon$ 的安全选择（ 用在 $k$ 种机制中的每一个机制）。

推论 3.21 给定目标隐私参数 $0<\varepsilon'<1,\enspace\delta'>0$ ，为确保在 $k$ 个机制上的累积隐私损失是 $(\varepsilon',k\delta+\delta')$，只要每个机制是 $(\varepsilon,\delta)$-差分隐私即可，其中：

$\varepsilon = \frac{\varepsilon'}{2\sqrt{2k\ln(1/\delta')}}$

【证明】 当 $\varepsilon'<1$ 时，我们期望 $\varepsilon^*\leq\varepsilon'$。由定理 3.20 可知对于所有 $\delta'$ 合成的隐私损失为 $(\varepsilon^*,k\delta+\delta')$ ，其中 $\varepsilon^*=\sqrt{2k\ln(1/\delta')}\cdot\varepsilon + k\varepsilon^2$。

【推论 3.21 证毕】

（此处有疑问，是通过 $(e^\varepsilon-1) \backsim \varepsilon \implies \varepsilon^*=\sqrt{2k\ln(1/\delta')}\cdot\varepsilon + k\varepsilon^2$ 然后解一元二次方程得出公式？）

注意，上面的推论给出了如何在差分隐私合成中设置所需的隐私参数 $\varepsilon$ 的粗略指导。当我们关心优化常数（在处理实际实现时会这样做）时，可以通过直接应用合成定理来更紧密地设置 $\varepsilon$。

例 3.7 假设，Bob是一个 $k=10000 \ (\varepsilon_0,0)$-差异隐私数据库的成员。假设这些数据库之间没有协调（任何给定数据库的管理员可能甚至不知道其他数据库的存在）。那么 $\varepsilon_0$ 的值应该是什么才能在他数据的生命周期里，Bob 的累积隐私损失以 $\varepsilon=1$ 为界，且概率至少为$1-e^{-32}$呢 ?。定理3.20 指出，假设不同的私有数据库之间没有协调，取 $\delta'=e^{-32}$，就足以使 $ε_0\leq1/801$。这在本质上是针对任意对手的最佳选择。

那么，我们可以用非平凡（注：此处个人理解为高精度）精确度回答多少个查询呢？在一个大小为 $n$ 的数据库中，如果添加的噪声为 $o(n)$ 阶，我们可以说精度是非平凡的。定理3.20指出，对于 $\varepsilon,\delta$ 固定值，可以以非平凡精确度回答接近 $n^2$ 的计数查询。类似地，当回答接近 $n$ 个查询时，仍有噪声 $o(\sqrt{n})$ （即噪声小于采样误差）。通过数据库间协调添加到单个响应中的噪声，我们将看到有可能显著改善精确度。在某些情况下，即使是噪声仅略大于 $\sqrt{n}$ 的指数数量的查询也可以得到处理。事实证明，这种协调是必要的：没有协调，高级合成定理中的上下界几乎是相近的（tight bound）。