原文是https://zhuanlan.zhihu.com/p/264779199

一、前言

由于网上关于差分隐私（differential privacy, DP）的中文资料比较少，大部分文章仅着重于阐释差分隐私的基本概念，因此想写一些文章来总结差分隐私的研究成果。本文主要探讨如何深入理解几种著名的composition theorem的内在思想，包括最基础的Simple Composition，Dwork et al.在2010年提出的Advanced Composition[1]和Abadi et al.在2016年提出的Moments Accountant[2]。在此之上也有一些更新的理论成果，将会在之后的文章中介绍。本文不会着重介绍差分隐私的概念，因此在阅读本文之前，需要对差分隐私基本概念有一定的了解。

二、背景介绍

1、差分隐私的定义

假设存在一个随机函数 $\mathcal{M}$ ，使得 $\mathcal{M}$ 在任意两个相邻的数据集 D,D' （即 $\|D-D'\|_1\leq1$）上得到任意相同输出集合 S 的概率满足

$\Pr[\mathcal{M}(D)\in S]\leq e^\varepsilon\Pr[\mathcal{M}(D')\in S]+\delta$

则称该随机函数 $\mathcal{M}$ 满足 $(\varepsilon,\delta)-differential privacy$（差分隐私），简写为 $(\varepsilon,\delta)-DP$。

2、 Composition theorem探讨的问题

当 k 个随机函数 $(\mathcal{M}_1,\mathcal{M}_2,...,\mathcal{M}k)$ 作用在同一个数据集上时，将这些随机函数称作一个composition，记作 $\mathcal{M}{1:k}$ 。Composition theorem探讨的问题是：假设每一个随机函数 $\mathcal{M}_i$ 都满足 $(\varepsilon_i,\delta_i)-DP$ ，那么整个composition满足什么样的DP呢？

三、理解差分隐私：隐私损失（Privacy Loss）

差分隐私（DP）的定义实际上是保证去掉/改变一个样本不会对 $\mathcal{M}$ 的输出造成显著的影响。换言之，DP保证了 $\mathcal{M}(D)$ 和 $\mathcal{M}(D')$ 有着相似的概率分布。按照DP的定义，如果 $\mathcal{M}(D) 和 \mathcal{M}(D')$ 的概率分布相差越大，那么隐私损失就越大；如果 $\mathcal{M}(D) 和 \mathcal{M}(D')$ 的概率分布相差越小，那么隐私损失就越小。于是，我们可以按照概率分布的差距严格地定义隐私损失[3]如下。

**定义1:（隐私损失，Privacy Loss）**对于两个相邻的数据集 D,D' （即 $\|D-D'\|1\leq1$），输出 o 和随机函数 $\mathcal{M}$ ，该随机函数造成的隐私损失 $c{\mathcal{M}}(o,D,D')$ 定义为

$c_{\mathcal{M}}(o,D,D')\triangleq \ln\frac{\Pr\left[\mathcal{M}(D)=o\right]}{\Pr\left[\mathcal{M}(D')=o\right]}$

隐私损失与 $(\varepsilon,\delta)-DP$ 的定义紧密相关，这种关联在定理1中有很好的体现。

定理1[2]**：**随机函数 $\mathcal{M}$ 是 $(\varepsilon,\delta)-DP$ 的充分条件是其隐私损失 $c_{\mathcal{M}}(o,D,D')$ 满足

$\Pr\left[c_{\mathcal{M}}(o,D,D')> \varepsilon\right]\leq\delta （1）$

形象的证明可以从 下面这里的概率图里看到:

差分隐私（一） Differential Privacy 简介

证明：