差分隐私直观原理

差分隐私csdn的举例解释： 我们设想这样一种情况：医院发布了一系列信息，说我们医院这个月有100个病人，其中有10个感染HIV。假如攻击者知道另外99个人是否有HIV的信息，那么他只需要把他知道的99个人的信息和医院发布的信息比对，就可以知道第100个人是否感染HIV。这种对隐私的攻击行为就是差分攻击。

差分隐私顾名思义就是防止差分攻击了，它想做的事情就是即使你小子知道我发布的100个人的信息，以及另外99个人的信息，你也绝对没办法把这两个信息比对之后获取第100个人的信息。怎么才能做到这一点呢？差分隐私于是定义：如果你能找出一种方法让攻击者用某种方式查询100个信息和查询那99个信息得到的结果是一致的，（比如查100个人人得hiv和99个人得hiv大家结果都是一样的）那攻击者就没办法找出那第100个人的信息了。但这个“一致” 怎么做到呢？那就加入随机性吧。如果查询100个记录和查询99个记录，输出同样值的概率是一样的，攻击者就无法进行差分攻击。这里我们就得到了差分隐私的核心思想：对于差别只有一条记录的两个数据集，查询它们获得相同值的概率非常非常的接近。Wait，不是说一致的么？（ 想让概率一致很简单，每个人随机的，最后结果不管是99还是100人答案都是各个百分之50，但是你这没有意思啊。数据 ）为什么变成了非常接近了？ 这是因为，如果概率一样，就表示数据集需要完全随机化，那数据的可用性就没有了，隐私保护也没有意义了。所以，我们尽可能的把概率做的接近，而不是一致，以期在隐私和可用性之间找一个平衡。下面用bilibili的讲解刚好适合上面这个例子：

假设我向这100个人问他们有没有hiv病毒我统计回答yes的人和 no的人。但是按理来说没人会告诉你真实的答案。为了不影响我的统计的结果的真是性。我可以使用随机化回答的方法（差分隐私的一种算法）来让每个人以一种系统的方式来保护她的隐私：即在他的答案中加入噪声()使我不知道他们到底是不是得了HIV。具体的随机化方法如下：
让这个人投掷一个筛子以一定的概率来回答他得真实答案（假设为百分之20），剩下的百分之80随便给一个yes或者是no。同理一个人的答案如果是no也是这样的规则。 

这种方法虽然对数据做了严重的修改，但是并不影响我们对结果的统计。但是我们可以用一些方法对数据进行修正还或者一个准确的计算。下面是讲解
这样我们既得到了统计数据，也能保护隐私了。因为我们并不知道这1500个人是哪1500个人。
差分隐私直观原理：用一个例子来解释差分隐私
数据集D中有一个人家Alice，数据集D’放了另外一个人替换Alice。这两个数据集唯一的不同就是D里面有Alice的数据，而D'里面没有。随机挑选这个两个数据集中的一个，从挑选的数据集里面提取一些信息，把这些信息发布给一个攻击者。让这个攻击者去猜这些信息是从D里面提取出来的还是从D”里面提取出来的。那我们可以想象一下，如果攻击者不能分辨这些信息是从D还是D'里面提取出来的那就意味着这些被发布的信息保护了Alice的隐私。因为攻击者都搞不清楚原数据是D还是D’的话，那么他就不知道Alice到底在不在原数据里面，如果他都不知道Alice到底在不在原数据里面的话他就没对Alice的信息做任何有用的推断。

差分隐私正是基于这样的直观原理来构建的，差分隐私认为当我们从数据集里面发布一些信息的时候。我们应当保证，攻击者无法从我们发布的信息里面推断某一个人是否在原数据里。通过这样，我们就可以保护数据集里面每一个人的隐私。为了达到这个目标，差分隐私要求我们所发布的信息要经过一个 随机算法来处理，随机算法会对发布的信息做一定程度的扰动。来使这个攻击者无法利用扰动后的信息无法反推某个人是否存在在原数据里面。
具体的差分隐私定义是这样的：
一个扰动性随机算法A 满足ε-差分隐私，当且仅当满足上面的不等式。这个不等式中间是两个概率的比值。上面的那个是当我们以数据集D为这个算法A的输入时候这个算法输出O的概率,O是一个任意可能的输出。（下面的那个和上面的理解是一样的只是换成了D’）D和D’是两个相领的数据集，也就是说，他两的数据大部分都一样，就唯一一个不一样。这样就是说当我们对任意一个数据做修改的时候，这个比值的变化范围比较小，要满足在e的ε之间。这也就意味着修改一个人的数据并不会对算法A的输出分布造成太大的影响。也就是说一个攻击者当他观察算法A的输出的时候，他很难知道原数据是D还是D’。
差分隐私定义的要求无非是说，当我们在x轴取任意一个点我们看他们在y轴对应的概率的时候概率的比值一定要在e的ε之间。
那么现在问题来了，我们怎样才能让一个算法满足这样一个复杂的不等式呢？

进行高斯差分的结果是DOG（Difference of Gaussian），这个DOG是LOG（laplacian of Gaussian）的近似。
LOG图像是目前来说尺度变换最好的，特精确。
但是由于计算LOG图像很费劲，作者Lowe呢就对LOG图像进行了近似，他发现如果是用DOG的话呢，只和原来的LOG差了一个常数，这样的话最大值最小值的位置是不变的。
而我们的目的呢，就是要找到这个最大最小值然后找到这个兴趣点的位置。
关键是DOG计算起来很方便，只要两张相减就好了。
所以就用到高斯图的差啦！
好好看论文是关键！论文说的很详细的，静下心来两天看完了~

---