差分隐私

informal examples

如果算法不具有 privacy-preserving, 可能会有下述情况出现:

• adversary 可以通过算法的输出重构得到用户敏感的数据集
• adversary 可以判断某一个用户是否在数据集中

一个例子是 adversary 可以通过数据库的查询语句重现整个数据集, 由下面的缓解方式:

• -Anonymity: 如果 query 涉及到少于 人则算法拒绝给出结果

• Noise Addition: 给查询结果添加 noise, 这是差分隐私使用的一种方法

定义

设 是模型. -DP 的定义是, 对每一对 neighboring datasets 以及每一个输出 的集合, 都有 的定义是 是 增加或减少一个数据得到的.

的定义是 是 中的一个数据更改得到的.

这个定义的 intuition 是一个数据的改变不会导致输出的分布大幅度改变.

-DP 等价于 -DP.

Privacy Loss: 对于 , 输出 的 privacy loss 是 定理 1 (Pure-DP Condition) 是 -DP 当且仅当对所有 , 都有 .

对于连续的随机变量, 可以使用密度函数定义

Basic Mechanism: Noise Addition

通过一个 Analyzer 得到 , 现在要在 上加上一个随机噪声.

加噪的直觉是噪声需要足够大以隐藏用户的贡献. 噪声的选取取决于

• 的敏感程度

Discrete Laplace Mechanism

假设 , 定义 的敏感度 .

Discrete Laplace Distribution 的定义是对每一个整数 , . 那么 Discrete Laplace Mechanism 中 random noise 为 . 比如若 , 那么输出是 , 更具体地, 是:

• w.p.
• 3 w.p.
• 4 w.p.

等等.

定理 2 假定 , 则 Discrete Laplace Mechanism 是 -DP.

定理 3 Discrete Laplace Mechanism 有 .

• .
• .

定理 3 说明误差与数据集大小无关.

的敏感度可推广定义为 -sensitivity . random noise 可以写为 , 其中 表示噪声项关于坐标独立.

定理 4 假定 , 则 Discrete Laplace Mechanism 是 -DP.

Laplace Mechanism

连续版本 .

定理 5 假定 , 则 Laplace Mechanism 是 -DP.

Gaussian Mechanism

, 其中 .

定理 6 假定 且 , 则 Gaussian Mechanism 是 -DP.

定义 是 的分布, 其中 . 则 approximation-DP Condition 是在说 是 -DP, 如果对所有 , 成立, 其中 .

这和 Pure-DP condition 的区别在于, Pure-DP Condition 是充要条件, 而 approximation-DP Condition 只是充分条件.

定理 7 random noise 是 且 , 假定 且 , 则 Gaussian Mechanism 是 -DP.

DP 的性质

定理 8 如果 是 -DP 且 是一个任意的函数, 则 仍然是 -DP.

定理 8 是在说 DP 具有 Post-Processing 的性质, 即 “Result of DP algorithm can be used in arbitrary manner and it remains DP.”

Composition

定理 9 (Basic Composition Theorem) 一个数据集通过 个 DP 算法 分别为 -DP, , -DP 得到的 个输出组合起来得到的是 -DP 算法 .

Proof 考虑验证 即可. 以及 上式成立的原因是 是相互独立的算法, 它们之间互不影响.

推论: 是 的卷积.

Approx-DP Condition: 是 -DP 当且仅当对任意 , , 其中 .

Advanced Composition Theorem: 所有的输出组合是 -DP, 其中 .

Proof Sketch:

• Recall that PLD of M is convolution of PLDs of
• For pure-DP:
  • Each PLD of is bounded in
  • Can be shown to have mean at most
  • Apply concentration inequality to the sum
    • PLD of exceeds with less than probability
• For approx-DP:
  • (Not tight) Truncate the PLD to be at most, say,
  • (Tight) Use a characterization of approx-DP in terms of pure-DP

composition 可以进行 adaptive setting, 即将第 个输出用在第 个算法中, Basic Composition Theorem 对于 adaptive setting 仍然适用.

Amplification by Subsampling

subsampling 会使算法更具有隐私性.

步骤: 从一个大小为 的数据集中随机采样 个数据, 然后用 substitution DP -DP 得到输出. Amplification-by-Subsampling Theorem: 上面算法的输出组合之后是 -DP, 其中 , , 且 .

Proof. 我们在这里只证明 的情形.

设 是 的大小为 的随机子集. 考虑任意 , , 不妨设 的第 个样本不同, 那么只需要验证 注意到 , 于是只需要证明 对于采样方式 , 考虑到 仅有最后一个元素不同, 因此它等价于下述采样方式:

• 选择
• 随机采样 , 满足 , , 其中 .
• 将 作为最终采样出的结果输出

那么就有 成立. 考虑到对 而言, 采样时 服从完全相同的分布, 那么只需要考虑 , 即只需要证明 对任意 都成立即可.

定义 , 并可以注意到 由于 是 -DP, 则 对任意 都成立, 则 那么

Amplification-by-Subsampling Theorem: 上面算法的输出组合之后是 -DP, 其中 , .

Proof. 这个证明就是类似的, 考虑等价的采样方法, 根据构造出的几个数据集间的 关系进行放缩即可.

Exponential Mechanisms

解决 Selection Problem:

• 输入 为 candidate set, 每一个 以及数据集 有一个分数
• 输出 with approx max score

且 表示敏感性.

EM: -DP 算法使 以 的概率成立.

指数机制是: 以 的概率输出 , 其中 , 且 .

定理: 指数机制是 -DP.