CIPT扩展知识-差分隐私
如我们在数据匿名化系列文章中讨论的，聚合后的数据比去标识化后的微数据有更好的隐私保护力度，但聚合数据也无法可靠的抵御攻击。
我们看一个例子，某医院周六公布了该院今年总共接治的HIV患者为20人，周日更新为21人。攻击者通过掌握的额外信息知晓1人(张三)在周日挂过该院相关科室的门诊号，由此即可确定张三被确诊HIV。这就是差分攻击，通过对比数据集中记录的变化来推测特定自然人的敏感信息。
统计数据也无法抵挡重构攻击，它是利用多次不同的查询的结果进行组合，构造出多个线性不等式，求解后的结果能重构出原始数据。如下例，通过第三行中男性的年龄中值和平均值，就可推理出这三人的可能年龄组合。如果再叠加上婚姻状态/种族等统计值可以进一步重构出原始数据情况。美国人口普查局在2010年的Census数据集上做过验证，最多可以重构出17%的美国人口数据。
图1-统计数据重构攻击示例
什么是差分隐私
为了提升发布数据集时的隐私保护，2008年由Dwork提出了差分隐私的概念，它通过严格的数学证明保证数据集的隐私泄漏始终低于某一个阈值。差分隐私的理念是如果对手看到发布后的数据集后，无法获得针对任何特定的自然人的新的（以前未知的）信息，就能充分保护该自然人的隐私。如下图，如果我们能通过添加噪音的方式，实现该自然人的数据是否加入数据集对统计结果的影响是非常有限的，就能说我们的隐私损失是小于ε的。
图2-差分隐私示意图
在算法层面，差分隐私的定义为：针对两个只差一个元素的数据集D和D'以及任意输出O，有随机函数M能满足如下公式
exp(-ε) <= Pr[M(D) =O] / Pr[M(D‘) =O]<=exp(ε)
这个公式有些难以理解，用直白的语言解释就是：用户A的数据未进去数据集之前（这是数据集D’），我们跑了一个统计语句，运行n次后，其中返回值为O的比例是P1。请注意我们使用了差分隐私后同一个统计语句的返回结果不是一致的。然后我们把用户A得数据加入到数据集中（数据集变成D），再跑这个同样的统计预计，运行n次后，我们拿到了比例分布，其中结果是O的概率是P2。 P2/P1应该在一个很小的范围内，这个范围就是自然对数e的-ε次方和之间ε。如果ε=0.1，那这个范围就是 0.905-1.105。这里ε也被称为隐私损失或者是隐私预算。
请注意这里的O是指该统计语句返回值的任意值，也就是说语句返回的结果会是一个结果集，这个集合中的每个数在D和D‘的概率对比都在这个范围内.
图3-差分隐私算法结果差异
实现方式
为了实现差分隐私，噪音可以在输入阶段即数据采集阶段，对每个输入的个体数据进行噪音添加。也可以是在分析处理阶段，对每次查询结果进行噪音添加，保证返回的统计结果符合差分隐私。
随机响应(Randomized Response)和拉普拉斯机制(Laplace)两种算法是差分隐私中最常用的.
拉普拉斯机制
在具体实现上，拉普拉斯机制使用以0为中心、以1/ε 为比例的拉普拉斯概率分布来对随机噪声进行采样，然后对每次查询结果添加获得的拉普拉斯噪声，扰动后的实际值会导致各种统计查询无法暴露单个用户的参与情况。
下图中红色就是拉普拉斯概率分布图，与蓝色的正态分布相比，服从拉普拉斯分布的随机变量，出现极端值的概率大于正态分布。
图4-拉普拉斯分布
还是以文章开头的医院统计为例，假设医院发布数据时使用了差分隐私来合成数据。现在，周六发布的统计数据时20.2取整到20人，周日统计出20.3取整后还是20，那么攻击者就没法知晓张三是否患有HIV。同时，每次的查询都在结果中添加了不同的噪音，也就无法利用不同统计间的相互约束，来重构原始数据。
随机响应
随机响应适合数据采集阶段的差分隐私保护，我们以一个场景化例子来看：
学校要调查有多少比例的学生下年度需要申请学生贷款，但有需求的同学都有疑虑不愿意暴露自己的这部分信息，所以学校设计了一个参与机制保障隐私。每个学生在填写答卷前都要求自行掷硬币，如果结果是正面，就填真实情况；如果反面，就再掷一次，第二次得到正面填“是”，反面填“否”。因为掷骰子的结果不记录，所以学生填写的答案不会暴露自己的贷款需求，因为没法知道这个填写的结果是真实情况还是反转后的。
图5-随机化回答
张同学是抽需要贷款的 --> 掷硬币得到正面 --> 填写 “是” --> 答案与事实相符
李同学是不需要贷款的 --> 掷硬币得到正面 --> 填写 “否” -->答案与事实相符
王同学是不需要贷款的 -->掷硬币得到反面-->再掷一次得到正面-->填写“是”-->答案与事实不符
赵同学是不需要贷款的--> 掷硬币得到反面-->再掷一次得到反面--> 填写 “否” -->答案与事实相符
最终我们得到的答案统计是，全体学生10000人，回答“是”的有4000人，回答“否”的有6000人。因为增加了噪音，单个学生的结果不再准确，但我们仍然可以反推出原始数据的大致分布
因为有50%的几率答案是随机的，所以我们先去除这部分值（2500-是，2500-否），这样剩下的真实答案分布： 是-1500，否-3500，比例是3:7。将这个比例放大回全体学生，则真实需要贷款人数估计为3000人左右。
那这个方案是不是满足ε 差分隐私的呢？我们尝试证明一下。
有一个吴同学，我们看他的实际值分别有“是”-D与“否”-D'的情况下，他实际提交的答案比例情况
Pr[M(D) =“是”] = (1-f)+f/2 ------- 真实需求为“是”且答案为“是”的比例
Pr[M(D‘) =“是”] = f/2 ----------------真实需求为“否”且答案为“是”的比例
Pr[M(D) =“否”] = f/2 ------- 真实需求为“是”且答案也为“否”的比例
Pr[M(D‘) =“是”] = (1-f)+f/2 ----------------真实需求为“否”且答案也为“否”的比例
因为提交的答案只可能是“是”与“否”， 所以
(f/2)/(1-f/2)<=Pr[M(D) =O] / Pr[M(D‘) =O]<=(1-f/2)/(f/2)
所以如果将ε设置为ln((1-f/2)/(f/2)), 就证明了这个随机响应的方法是满足ε-差分隐私的。
在上面的这个例子中，隐私预算ε = ln(0.75/0.25) = ln(3) = 1.0986。同时因为每条记录的值都有25%的几率是相反的，所以无论是差分攻击还是数据重构都不会暴露用户隐私。
ε的选择
ε 的值可以用来确定隐私级别。ε 值越小，隐私性越好，但结果的准确性可能受到影响。在前面的随机化回答例子中，我们可以容易算出不同的ε对应提交的数据真实比例。
图6-ε与数据可用度间的关系
苹果在MacOS上的应用使用数据采集上使用6作为ε，谷歌在chrome设置数据采集中用的ε是9. ε设置为多少最合适，这是一个没有答案的问题，需要根据实际的应用场景中的隐私风险可承受度来判断。
优势和应用方向
差分隐私可以防范包括链接攻击，差分攻击，数据重构等各类风险。 且它不仅仅是一个隐私保护手段，同时也是一个衡量和管理隐私风险的标准，它通过ε量化了隐私的泄漏程度。我们可以根据能承受的隐私泄漏风险与需要的数据精确度，来调整ε值。和用户沟通时，也可以告知ε值，支持用户对是否参与的科学决策。
差分隐私适用于数据的收集，分析和统计数据的发布，目前业界发布的主要应用方向有：
1. 差分隐私数据库 - 对聚合查询结果中加入噪声满足差分隐私，支持内外部用户的互动式数据查询。
2. 差分隐私机器学习 - 在算法中引入噪声，使生成的模型满足差分隐私。
3. 差分隐私数据采集 - 采集用户数据时使用随机化回答来进行处理后再上传。苹果在MacOS/iOS以及谷歌在Chrome上都采用了该技术。这是一种本地化差分隐私方式，数据在用户的本机就完成了噪音添加，保证个人用户的敏感信息不会在传输或数据处理中泄漏，能提供了更好的保护。
4. 差分隐私数据合成 - 数据集先建模获得统计模型，添加噪音后再合成出虚拟数据。美国人口普查局从2020年开始应用。
参考资料
1. 论文-Differential Privacy: A Primer for a Non-Technical Audience - 作者 Alexandra Wood等多位
2. B站-差分隐私：原理、应用与展望-主讲 萧小奎
3. B站-A Course on Differential Privacy - 主讲 Gautam Kamath
4. 博客-Tutorial #12: Differential Privacy I: Introduction - 作者M. Bruakers, S. Prince
5. 论文 - RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response - 作者 谷歌Ulfar Erlingsson
6. 公众号文章-从隐私到隐私计算-作者 半吊子全栈工匠
7. 博客 - Differential privacy, an easy case - 作者 Mark Hansen
