差分隐私（Differential privacy）浅析

通过几天对差分隐私的左思右想，总算是摸到了点门道，顺着学习思路，就一些比较关键性概念说一下自己的看法：一、关键性概念1、查询对数据集的各种映射函数被定义为查询（Query），用 ={, , ......}来表示一组查询。2、邻近数据集（兄弟数据集）设数据集与，具有相同的属性结构，两者对称差记作，||表示对称差的数量。若||=1，则称和为邻近数据集...

Ano_onA

48373人浏览 · 2019-09-05 19:41:47

Ano_onA · 2019-09-05 19:41:47 发布

通过几天对差分隐私的左思右想，总算是摸到了点门道，顺着学习思路，就一些比较关键性概念说一下自己的看法：

一、关键性概念

1、查询

对数据集的各种映射函数被定义为查询（Query），用 ={ $f_{1}$ , $f_{2}$ , ......}来表示一组查询。

2、邻近数据集（兄弟数据集）

设数据集与 $D^{'}$ ，具有相同的属性结构，两者对称差记作 $\Delta$ $D^{'}$ ，| $\Delta$ $D^{'}$ |表示对称差的数量。若| $\Delta$ $D^{'}$ |=1，则称和 $D^{'}$ 为邻近数据集（又称兄弟数据集 ）。

For example：设集合 = {1,2,3,4,5,6}， $D^{'}$ = {1,2,4,6}，则 $\Delta$ $D^{'}$ = {3,5}，| $\Delta$ $D^{'}$ | = 2。

3、敏感度

（1）全局敏感度：

对于一个查询函数 $\rightarrow$ $R^{d}$ ，其中为一个数据集， $R^{d}$ 为维实数向量，是查询的返回结果。在任意一对邻近数据集和 $D^{'}$ 上的全局敏感度为：

$GS_{f}$ () = max () - ( $D^{'}$ )

注意：a. () - ( $D^{'}$ ) 是()和( $D^{'}$ )之间的曼哈顿距离；

b. 全局敏感度与数据集无关，只与查询结果有关。

（2）局部敏感度：

对于一个查询函数 $\rightarrow$ $R^{d}$ ，其中为一个数据集， $R^{d}$ 为维实数向量，是查询的返回结果。对于给定的数据集和它的任意邻近数据集 $D^{'}$ ，有在上的局部敏感度为：

$LS_{f}$ () = max () - ( $D^{'}$ )

全局敏感度和局部敏感度的关系为：

$GS_{f}$ () = max ( $LS_{f}$ ())

二、差分隐私

设有随机算法， $P_{M}$ 为所有可能输出构成的集合的概率，对于任意两个邻近数据集与 $D^{'}$ 以及 $P_{M}$ 的任意子集 $S_{M}$ ，若算法满足：

[ () $\in$ $S_{M}$ ] $\leq$ $e^{\varepsilon }$ $\times$ [ ( $D^{'}$ ) $\in$ $S_{M}$ ]

则称算法提供 $\varepsilon$ -差分隐私保护。

注意：a. $\varepsilon$ 越小，隐私保密度越高；

b. $\varepsilon$ 越大，数据可用性越高（保密度越低）；

c. $\varepsilon$ = 0时，针对与 $D^{'}$ 的输出概率完全相同。

通常情况下， $\varepsilon$ 值取很小， $e^{\varepsilon }$ 接近于1，即对于只有一条记录差别的两个数据集，如果查询它们的概率非常非常的接近，那么它们满足差分隐私保护（通俗的说法，不太严谨）。

For example：医院发布信息有10个人患AIDS，现在攻击者知道其中9个人的信息，通过和医院发布的信息进行比对就可以知道最后一个人是否患AIDS，这就是差分隐私攻击。如果查询9个人的信息和查询10个人的信息结果一致，那么攻击者就没有办法确定第10个人的信息，这就是差分隐私保护。

三、实现机制

1、拉普拉斯机制（常用于数值输出的函数）

（1）Laplace机制的敏感度：

给定一个函数集， $D_{1}$ 和 $D_{2}$ 为邻近数据集，其敏感度定义如下：

S(F) =

（2）期望为0，方差为2 $b^{2}$ 的Laplace分布，其概率密度函数为：

P(x) =

其中 = $\frac{\Delta f}{\varepsilon }$ ， $\Delta f$ 为敏感度。

（3）Laplace机制 $\varepsilon$ -差分隐私：

给定一个函数 $\rightarrow$ $R^{d}$ ，若隐私保护算法满足 $\varepsilon$ -差分隐私，当且仅当下述表达式成立：

= f(D) +

具体公式推导证明可参考：

差分隐私若干基本知识点介绍（一）_MathThinker的博客-CSDN博客_差分隐私

2、指数机制（常用于非数值输出的函数/添加数值噪声后无意义的函数）

（1）可用性函数：

设查询函数的输出域为，域中的每个值 $r\in R$ 为一实体对象，为给定数据集。在指数机制下，函数 $q(D,r)\rightarrow R$ 称为输出值的可用性函数。

（2）指数机制的敏感度：

给定可用性函数， $D_{1}$ 和 $D_{2}$ 为任意一对邻近数据集，为任意合法输出，其敏感度定义如下：

S(q) =

（3）指数机制 $\varepsilon$ -差分隐私：

给定数据集及可用性函数 $q(D,r)\rightarrow R$ ，隐私保护机制满足 $\varepsilon$ -差分隐私，当且仅当下述表达式成立：

A(D,q) $\propto$ （ $\propto$ 为正比于）

四、组合原理

1、串行组合原理（同一数据集、不同算法）：

给定数据集以及一组关于的差分隐私算法： $A_{1}(D),A_{2}(D),A_{3}(D),....,A_{m}(D)$ ，算法 $A_{i}(D)$ 分别满足 $\varepsilon _{i}$ -差分隐私且任意两个算法的随机过程独立，则这些算法组合起来满足。

2、并行组合原理（不同数据集、不同算法）：

记 $A_{1}(D_{1}),A_{2}(D_{2}),A_{3}(D_{3}),...,A_{m}(D_{m})$ 分别表示输入数据集为 $D_{1},D_{2},D_{3},...,D_{m}$ 的一系列满足 $\varepsilon$ -差分隐私算法且任意两个算法的随机过程相互独立，则这些算法组合起来满足 $\varepsilon$ -差分隐私。

3、推论（不同数据集、不同算法）：

记 $A_{1}(D_{1}),A_{2}(D_{2}),A_{3}(D_{3}),...,A_{m}(D_{m})$ 为一系列相互独立的差分隐私，且算法 $A_{i}(D)$ 分别满足 $\varepsilon _{i}$ -差分隐私，则这些算法组合起来满足。（不同数据集、不同算法，整体小于等于最大 $\varepsilon$ -差分隐私）