后处理不伤隐私的证明(不重要)

如果 M 已经保证“看不太出你在不在数据库里”，那你再对 M 的输出做任何加工 f**，也不可能凭空把隐私变差。**

这就是 post-processing 不伤隐私。

我先把命题本身翻译一下。

命题 2.1（后处理）说：

设

M:\mathbb{N}^{|X|}\to R 是一个满足 (\varepsilon,\delta)-差分隐私的随机算法。 再设 f:R\to R' 是任意一个随机映射。 那么复合函数 f\circ M:\mathbb{N}^{|X|}\to R' 仍然满足 (\varepsilon,\delta)-差分隐私。

先解释每个符号：

• \mathbb{N}^{|X|}：数据库的直方图表示空间
• R：机制 M 的输出空间
• R'：再加工之后的新输出空间
• f\circ M：先运行 M，再把输出喂给 f

所以这句话翻成人话就是：

先做一个 DP 机制，再对结果随便改造、分类、压缩、画图、加标签，隐私参数不会变坏。

下面看证明。

第一句：

We prove the proposition for a deterministic function f:R\to R'.

翻译：

“我们先只证明 f 是确定性函数的情况。”

也就是先假设 f 不带随机性。 比如：