DP-Composition Theorem（二）

参考资料：https://zhuanlan.zhihu.com/p/212819144

Basic Composition

并行组合

串行组合

Advanced Composition

这里面想更高级一点的攻击，假设攻击者可以自适应地影响数据库及对应的查询机制，即查询与查询之间是有关联的，如下图所示：

Advanced Composition. For all $\epsilon, \delta, \delta’\ge 0$, the class of $(\epsilon,\delta)$-DP mechanisms satisfies $(\epsilon’,k\delta+\delta’)$-DP under $k$-fold adaptive composition, where:

$$\varepsilon^{\prime}=\sqrt{2 k \ln \left(1 / \delta^{\prime}\right)} \varepsilon+k \varepsilon\left(e^{\varepsilon}-1\right)$$

证明过程可以参考《Privacy Book》中的定理3.20。

Moment Accountant