可以,而且这个证明其实很短。
它之所以“立刻推出”,就是因为你把 两个输出一起看成一个联合输出 之后,直接套两次 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。
下面给你一个“简单但正式”的证明。
我们定义组合机制: