二次组合差分隐私分析(不重要)

可以,而且这个证明其实很短。

它之所以“立刻推出”,就是因为你把 两个输出一起看成一个联合输出 之后,直接套两次 DP 定义就行了。

先说结论在讲什么。

假设有两个机制:

这里的“composition of two mechanisms”意思是:

对同一个数据库 x,先跑 M_1(x),再跑 M_2(x),最后把别人能看到的总输出记成:

(M_1(x),\,M_2(x))

要证明的是:这个联合机制是 (2\varepsilon,0)-DP。也就是对任意相邻数据库 x,y,任意联合输出事件 S,都有

\Pr[(M_1(x),M_2(x))\in S]\le e^{2\varepsilon}\Pr[(M_1(y),M_2(y))\in S].

先讲最直觉的理解:

第一次发布 M_1 的结果,最多给攻击者一个 e^\varepsilon 的区分优势;

第二次再发布 M_2 的结果,在知道第一次结果的前提下,又最多再给一个 e^\varepsilon 的优势;

两次合起来,倍率相乘,就是

e^\varepsilon\cdot e^\varepsilon=e^{2\varepsilon}.

所以 log 视角下就是 \varepsilon+\varepsilon=2\varepsilon。

下面给你一个“简单但正式”的证明。

我们定义组合机制: