Processing math: 100%

DP-Composition Theorem

在之前的文章《DP-拉普拉斯机制》和《DP-指数机制》中,我们介绍了两个应用场景下的差分隐私算法设计。就像一般的运算一样,我们定义了某种运算就想知道这种运算的一些性质以便于后续更加方便的使用这种运算。本章节我们关心差分隐私的运算性质。

  • 为什么有组合性质
  • 组合性质
  • 简单应用

为什么有组合性质

在《DP-Differential Privacy概念介绍》中的背景知识小节中,我们举了一个对数据库查询以得到某个具体记录的案例:

patient has cancer
Amy 0
Tom 1
Jack 1

假设 sum(n) 表示前n行的统计结果,则通过

sum(3)sum(2)=21=1

可以得到 Jack 的患病信息(假设我们拥有背景知识是Jack在第三行)。

在使用了DP机制之后,由于 DP 对相邻数据集的不可区分性,sum(3)sum(2) 是很可能相等的,所以sum(3)sum(2) 得到的结果可能是 0,可能是 1,甚至可能是-1. 通过这种手段,敌手无法得知Jack的患病情况。

但是:为了保证数据可用性,添加的噪声均值必须为0。这就意味着

E[sum(3)sum(2)]=E[sum(3)]E[sum(2)]=1

即,如果敌手可以无限制地对数据集进行查询,最终一定会得到真实结果。

实际上,对于同一个查询来说,查询次数越多,得到的结果平均值越收敛于真实值,隐私保护等级就越低。

所以从这个角度来说,我们想知道随着连续的查询,隐私保护等级会如何变化呢?

组合性质

我们来看看什么是组合机制:

Composition Theorem: Let M1:N|X|R1 be an ϵ1-differentially private algorithm, and let M2:N|X|R2 be an ϵ2-differentially private algorithm. Then their combination, defined to be M1,2:N|X|R1×R2 by the mapping: M1,2(x)=(M1(x),M2(x)) is (ϵ1+ϵ2)-differentially private.

组合机制的理解其实很简单,即如果算法M1ϵ1-DP的,M2ϵ2-DP的,那么把M1M2放到一起就是(ϵ1+ϵ2)-DP的。证明过程如下:

Let x,yN|X| be such that ||xy||11. Fix any (r1,r2)R1×R2. Then:

Pr[M1,2(x)=(r1,r2)]Pr[M1,2(y)=(r1,r2)]=Pr[M1(x)=r1][M2(x)=r2]Pr[M1(y)=r1][M2(y)=r2]=Pr[M1(x)=r1]Pr[M1(y)=r1]×Pr[M2(x)=r2]Pr[M2(y)=r2]exp(ϵ1)exp(ϵ2)=exp(ϵ1+ϵ2)

有了两个机制的组合机制之后,我们自然会将这个机制推广到 n 个机制的组合情况,在这里总的结论就不放了。

简单应用

根据组合机制,如果敌手可以对数据集进行查询,那么只需要重复执行同一个查询再对结果求平均,就可以很大程度上得到真实结果。所以在一般的实际应用中,限定一个隐私保护预算上界,如果查询的总预算那么禁止用户对数据集进行查询。这就有点类似于访问控制的意思了。

fig-application

总结

本章介绍了组合机制,下面是我的公众号二维码,所有的内容也同步在公众号上面,希望大家关注。

Thanks for rewarding

Related Issues not found

Please contact @forestneo to initialize the comment