差分隐私技术

2016年，差分隐私从研究论文一跃成为科技新闻头条，在WWDC主题演讲中，苹果工程副总裁Craig Federighi宣布苹果使用这一概念来保护iOS用户隐私。目前，google的chrome以及apple的ios中均使用了差分隐私技术，最近一段时间，我也一直在看差分隐私的相关文献。

差分隐私（differential privacy）是一种隐私保护的技术。应用的场景如下：

某数据中心拥有许多病人的隐私数据，这些数据存储在数据库中。比如第一条记录是“张三，男，18岁，患有精神病”；第二条记录是“李四，男，22岁，患有前列腺炎”；第三条记录是“王五，女，31岁，患有肥胖症”等等。数据是以这样一条条记录的形式存储在数据库中。

此时，该数据中心为了响应国家大数据的号召，想要公布这些巨量的数据，以便让相关领域的专家对数据进行分析和挖掘，找出有价值的信息和规律。但是由于公民的个人隐私问题，数据中心不能直接公布原始数据，需要对这些数据进行隐私保护处理，隐私保护处理的方法使用的是差分隐私技术。

经过差分隐私处理后，若再对该数据集进行查询，则可以有效保护个人隐私。比如查询该数据集中前99个人性别为“男”的数量以及前100个人性别为“男”的数量，如果没有进行差分隐私处理，攻击者可以很轻松的知道第100个人具体的性别。但是经过差分隐私处理后，两次查询得到的结果都不是准确的，比如第一次得到结果为55，第二次得到结果为54，攻击者没有办法知道具体是多少。

差分隐私技术的主要原理并不复杂，就是向原始数据中，添加符合拉普拉斯分布的噪声，这样原始数据中就多了一些噪声数据。再将添加噪声后的数据公布给专家，就可以有效的保护个人隐私。上面写的只是差分隐私的大概描述，下面我将对差分隐私的细节进行描述，并且给出严格的数学定义。

差分隐私

有两个数据集分别为D和D'，D和D'之间只有一条记录是不同的，其他记录都是相同的。数学描述为|D△D'|=1。使用差分隐私技术，即向D和D'中添加符合拉普拉斯分布的噪声（还有其它噪声，拉普拉斯最为常用）。然后对D和D'两个数据集进行查询操作，比如操作1为查询D中99个用户的记录，操作2为查询D'中100个用户的记录，如果操作1返回的结果和操作2返回的结果一模一样（一模一样是理想状态，实际上只要接近就好，具体实施的时候会有一个隐私预算，只要低于某个阈值就ok），那么就是完美的保护了用户隐私。

这句话的意思其实是说，既然查询99个人的记录和查询100个人的记录返回的结果一致，那么第100个人就很乐意的奉献自己的隐私数据，反正有我没我攻击者查询得到的结果都是一样的。这里还需要注意的是，一般查询返回的结果都是统计查询，比如查询99个人的年龄总和，查询100个人的年龄总和等。如果不进行差分隐私保护的，那么攻击者只要对两次查询做减法，就知道第100个人的具体年龄，这就是差分攻击。

最后，需要注意的是，由于在原数据集中加入了噪声，所以公布的数据集是不准确的，具体不准确的程度要看加入多少噪声。但是这并不影响对数据集进行统计分析，还是可以统计分析出数据集的总体趋势的信息，得到数据集有价值的规律。

数学描述 设有两个数据集分别为D和D'，将D和D'中共有的记录从D和D'中删除，然后将D和D'合并所形成的新的数据集成为D和D'的对称差，记做D△D'。|D△D'|表示D△D'中记录的数量。 现有两个数据集D和D'，它们满足|D△D'|=1，M为一随机化算法，rang(M)表示算法M的所有可能的输出构成的集合，S是rang(M)的任一子集。如果算法M满足，

则该算法满足ε-差分隐私，其中P为概率。