differential privacy学习笔记（一）
什么是differential pravicy
differential privacy通常被翻译成差分隐私，为了了解什么是差分隐私，我们需要定义一下这个隐私是什么
我们通常理解为单个的数据即为隐私，例如我们可以在每年的人口普查中知道人均月收入为多少，但不能够轻易地获得具体的某个人比如小明他的月收入是多少，在这个问题中小明的月收入信息就是隐私，而人均月收入就是一个统计信息，这个统计信息通畅来说是有意义的，比如国家统计的GPA，可以显示出国家的发展速度，因此统计数据分析是有意义的，不可少的，但是作为小明，那他就会想到，会不会有别有用心的人能够通过这个统计结果能够分析出我的月收入是多少，这就涉及到隐私保护的问题。
一些隐私保护方案和攻击手法
通常我们能够想到的保护隐私的方式是抹去一些隐私信息，比如我们在参加调查问卷的时候，会更愿意参加那些不用提供个人信息的调查，但是单纯的抹去敏感信息并不能保证隐私的安全性。
上图是一个医院的患者信息表，把姓名信息进行了处理，但如果攻击者拥有下面这个表，然后将信息进行对应，很容易轻易地得到张三得了流感这一信息。
这种攻击方式我们称之为链接攻击（Linkage attacks）
基于这种攻击方式，提出K-匿名算法，k匿名性的概念最早由 Latanya Sweeney和 Pierangela Samarati在1998年发表的一篇论文中提出 [1]，以期解决该问题：“鉴于特定于人的领域结构化数据，科学地发布数据保证了在数据仍然实用的情况下，无法重新识别作为数据主体的个人。”
k-匿名之后：
k-匿名的通俗理解，将原始数据做一个泛化，提取共同的特征值，隐去一些信息。
但是k匿名算法不能抵御：
同质攻击（Homogeneity Attack）：这种攻击利用了一组k条记录中敏感值的所有值都相同的情况。在这种情况下，即使已对数据进行了k匿名化，也可以准确预测k个记录集的敏感值。如上图例子，假设现在有一个人他的数据在上表中，而且他的邮编开头是476 年龄是20多岁，那么我们就可以肯定他得了心脏病，他的隐私就会被泄露。
背景知识攻击（Background Knowledge Attack）:攻击者通过拥有的背景资料知识以及匿名化的数据对数据进行分析，从而达到获得隐私的目的。
一个背景攻击的例子：
假设攻击者预先知道Alice的数据在哪一行，如果想要获取Alice是否得艾滋病，只需要用前五行第三列的求和S减去第二到五行第三列求和S’。
在这种情况下，我们就希望两次的查询结果不能够反映出隐私数据，假如说这两次的查询结果在很大概率上是相同的话，那么攻击者就不能分析出Alice是否得了艾滋病。（为什么说是很大概率上是相同的?因为对于一对相邻数据集来说，如果输出结果完全相同，则说明不同的那一条数据对于这个数据集是不可用的，是无意义的，而我们的隐私保护是在数据可用的前提下。）
差分隐私的目的和ε-差分隐私的定义
所以差分隐私保护的基本思想就是对于每一对邻近数据集的输入，输出结果很大概率相同，敌手不能通过输出结果分辨出数据集中到底有没有相差的那一条数据。
2006年,Dwork，McSherry，Nissim和Smith的文章给出了ε-差分隐私的定义：
其中，D1和D2是邻近数据集，O是输出结果，ε是一个较小的正数，ε越小隐私保护的程度越高，但数据的可用性就越低。
这个定义表明：在数据库上运行的统计功能不应过分依赖任何个人的数据。
同时，任何个人对数据库结果的贡献程度部分取决于查询中涉及多少个人数据。如果数据库包含单个人的数据，则该人的数据占100％。如果数据库包含来自一百个人的数据，则每个人的数据仅贡献1％。差异性隐私的关键见解是，随着对越来越少的人的数据进行查询，需要向查询结果中添加更多的噪声以产生相同数量的隐私。