收录于 · 差分隐私合集

258 人赞同了该文章

差分隐私中的三种机制

在应用差分隐私进行隐私保护中，需要处理的数据主要分为两大类，一类是 数值型 的数据，比如说数据集中已婚人士的数量；另外一类是 非数值型 的数据，比如喜欢人数最多的颜色。这两者，主体分别是 数量(连续数据) 和 颜色(离散数据)

• 对于 数值型 的数据，一般采用 Laplace 或者 高斯 机制，对得到数值结果加入随机噪声即可实现差分隐私；
• 而对于 非数值型 的数据，一般采用 指数 机制并引入一个 打分函数 ，对每一种可能的输出都得到一个分数，归一化之后作为查询返回的概率值。比如现在有 $\left{\right. 红 色 : 20 , 绿 色 : 30 , 紫 色 : 50 \left.\right}$ ，将数量作为 打分函数 ，那么得到对应输出概率为 $\left{\right. 红 : 3 e - 7 , 绿 色 : 4 e - 5 , 紫 色 : 0.999 \left.\right}$ ，当接收到一个查询之后，就以对应的概率值返回结果。

下面分别从数值型和非数值型两个方面对三种机制进行介绍。

1 - 数值型查询

1.1 Laplace机制

定义-敏感度

首先定义一下敏感度，它代表的意思是对于两个 兄弟数据集（只相差一个元素） $D , D^{'}$ ，一个查询函数 $f \left(\right. \cdot \left.\right)$ 最大的变化范围，比如查询数量，敏感度就是1。

敏感度是和查询函数相关的，而这里的定义主要是为了后面满足差分隐私的证明。

我们可以有以下洞察:

1. 计算采取的是1 范数,也就是$f(D) - f(D')$得到的是高维空间里的一个向量;这个向量的$\frac{1}{n} \sum_{i = 1}^n |x_i|$就是1 范数
2. 由于求出来的值是max , 并且输入空间是相差为1的数据集,所以实际的含义就是拨动一下输入,看看f最大能变多大
3. 这个敏感度是是只与f相关,因此,只要f固定了,敏感度就固定了.
4. 这个敏感度实际上是结合实际情况来看的.比如我们查询f是查询数据库里有多少人,那么多一人少一人也就差1,因此对于这个f,敏感度就是1

理论-Laplace机制

数学可见: