差分隐私

差分隐私(Differential Privacy)是Dwork[3] 在2006年针对数据库的隐私泄露问题提出的一种新的隐私定义。主要是通过使用随机噪声来确保，查询请求公开可见信息的结果，并不会泄露个体的隐私信息，即提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会，简单来说，就是保留统计学特征的前提下去除个体特征以保护用户隐私。

差分隐私基本原理如下图：当用户(也可能是潜藏的攻击者)向数据提供者提交一个查询请求时，如果数据提供者直接发布准确的查询结果，则可能导致隐私泄漏，因为用户可能会通过查询结果来反推出隐私信息。为了避免这一问题，差分隐私系统要求从数据库中提炼出一个中间件，用特别设计的随机算法对中间件注入适量的噪音，得到一个带噪中间件；再由带噪中间件推导出一个带噪的查询结果，并返回给用户。这样，即使攻击者能够从带噪的结果反推得到带噪中间件，他也不可能准确推断出无噪中间件，更不可能对原数据库进行推理，从而达到了保护隐私的目的。
 

差分隐私中一个关键概念是相邻数据集，假设给定两个数据集D和D’，如果它们有且仅有一条数据不一样，那么这两个数据集可称为相邻数据集。那么如果对于一个随机算法A如果其分别作用于两个相邻数据集得到的两个输出分布式难以区分的，那么这个算法就被认为达到差分隐私的效果。这里的随机算法，是指对于特定输入，该算法的输出不是固定值，而是服从某一分布的算法。下面公式是Dwork的差分隐私定义：

也就是说这个算法作用于任何相邻数据集，得到一个特定输出O的概率是差不多，从而观察者通过观察输出结果很难觉察出数据集的细小变化，通过这种方式来达到保护隐私的目的。

差分隐私的主要实现机制，主要是在输入或输出上加入随机化的噪音：拉普拉斯噪音(Laplace Noise)，高斯噪音(Gaussian Noise)，指数机制等

一些企业已经开展了相关的工程实践。Google利用本地化差分隐私保护技术从Chrome浏览器每天采集超过1400万用户行为统计数据。在2016年WWDC主题演讲中，苹果工程副总裁Craig Federighi宣布苹果使用本地化差分隐私技术来保护iOS/MacOS用户隐私。根据其官网披露的消息，苹果将该技术应用于Emoji、QuickType输入建议、查找提示等领域。例如，Count Mean Sketch算法（CMS）帮助苹果获得最受欢迎的Emoji表情用来进一步提升Emoji使用的用户体验，下图展示了利用该技术获得的US English使用者的表情使用倾向。

差分隐私具有三个最重要的优点：

(1) 差分隐私严格定义了攻击者的背景知识：除了某一条记录，攻击者知晓原数据中的所有信息——这样的攻击者几乎是最强大的，而差分隐私在这种情况下依然能有效保护隐私信息；

(2) 差分隐私拥有严谨的统计学模型，极大地方便了数学工具的使用以及定量分析和证明。

(3) 差分隐私不需要特殊的攻击假设，不关心攻击者拥有的背景知识，量化分析隐私泄露风险。