差分隐私：原理、应用与展望(新加坡国立大学 萧小奎)
讲座原视频链接：https://www.bilibili.com/video/BV1Tk4y117uA?from=search&seid=10380937147053242260
引入
由Dwork等人于2006年提出的一套关于隐私保护的理论框架。
既可用数据收集，也可以用于信息分享。
隐私保护的挑战
在上面的场景中，如果我们要与研究者分享病人的医疗数据，怎样才能保护病人的隐私了？
解决方法：
（1）单条数据的匿名化：不能真正保护隐私，因为匿名化之后的数据往往还保留着许多可能泄露隐私的信息。
（2）只发布统计数据：统计数据也可能泄露隐私，统计信息可以用来重构部分源数据！eg：人口普查的统计信息
在上面的例子中，我们从右边的两张表可以反推出源数据中有这样两个元组：【≥18,F,Yes】
美国普查局如何解决（见下图）？
■ 删除太小的统计数据 ；■ 统计数据中加入一定噪声。
但是，上述措施依然不够隐私保护，攻击者可以采取更加高级的攻击方法，例如数据重构攻击，其基本思想是用线性规划重构数据。Dinur和Nissim于2003年提出了一种从统计数据重构源数据的算法。
线性规划思想：
对每一个可能出现的元组用Count未知量表示其可能出现的次数。带入这些变量，通过统计数据构建一系列的线性不等式方程。联立不等式，求解该线性规划问题，其目标是最小化噪声量，从而得到一系列x1，x2，x3……的解，使得其与统计数据值尽可能的接近。因此，我们认为这些解是对源数据大致的重构。
重构结果有多准确？
[ Dinur and Nissim，2003]结论：哪怕每个统计数据都有着相当程度的噪声，只要有足够多的统计数据，我们总能重构出源数据中的大部分元组。
美国普查局用他们2010年发布的一组统计数据试验了数据重构攻击，结果表明，他们只能重构 17% 美国人口的数据。为此，他们宣布将于2020年的统计数据发布中使用差分隐私。
（3）机器学习模型发布数据：既然发布统计数据容易被重构算法攻击，我们是否能发布更复杂的数据形式，来使得重构难以进行？
如上图所示，先在源数据上构建一个机器学习的模型，将模型分享给第三方，机器学习模型较为复杂可以避免源数据的泄露。现有文献表明，即使是机器学习模型也有可能泄露隐私，原因如下：
机器学习模型往往不经意地“记住”源数据中的元组。因此，模型在那些元组上的表现可能跟在其他元组上的表现不一样。这就好比考试碰上之前做过的题和碰上没有做过的题反应是不一样的。同理，攻击者通过一个元组在机器学习模型上的表现可以反推出模型训练时是否有那个元组。
上图展示了对机器学习模型的攻击。假设被发布的模型是一个分类器：
■ 把一些人的元组挨个作为模型的输入，并观察模型的分类结果
■ 通过分类结果，反推每一个人是否有出现在源数据中
类似的攻击还有很多，eg：[Carlini et al. 2019]：从自然语言模型中有可能反推出源文本中的某些敏感词。
总而言之，攻击者可以有很多种不同方式来对隐私数据进行攻击，为了防范这些可能的攻击，我们需要有一个严谨的框架来对数据隐私进行保护。差分隐私正是这样的一个理论框架。
差分隐私的直观原理
● 将Alice换成另一个人的数据组成数据集D’，即D’和D的区别只在于其中Alice的数据。
● 直观原理：如果攻击者无法判别信息O是来自于D还是D’，那么我们可以认为Alice的隐私受到了保护
● 差分隐私要求任何被发布的信息都应当与上图中的信息O类似：
■ 应当避免让攻击者分辨出任何具体的个人信息
● 为此，差分隐私要求被发布的信息需经一个随机算法处理，且该随机算法会对信息做一些扰动
差分隐私的定义
上式表明，对源数据中任意一个人的数据进行修改时，得到的O的概率变化会很小。
修改一个人的数据不会对算法A的输出的分布带来太大的影响。
上图中x轴代表算法A的输出，y轴代表算法A输出O的概率。蓝线代表输入数据为D的时候算法A的输出的分布。红线代表输入数据为D’的时候算法A的输出的分布。即，算法的输出分布不会受某一个数据存在与否的太大影响。当攻击者观察算法的输出时，并不能反推出某个人是否在源数据中。
差分隐私的算法
如何设计满足差分隐私的算法？
一般做法：
● 从一个不满足差分隐私的算法出发
● 往算法里适当地加入一定噪声，以使其输出满足差分隐私地要求
5.1 拉普拉斯机制
FROM D
WHERE Type = "糖尿病患"
如果发布这个查询结果，如何才能满足差分隐私？
● 首先，让我们考虑这个查询的结果有多依赖于某个特定病人的信息
■ 如果我们修改D中任意一个病患的数据，上述查询结果最多会改变多少？—— 最多改变1
■ 直观的说，如果我们能用噪声来“掩盖”这种不大于1的改变，就能满足差分隐私
● 其次， 我们可以往查询结果中加入一个服从拉欧拉斯分布的噪声：
参数λ 设定为1/ϵ ，即能满足ϵ-差分隐私。
如果发布下面这个查询结果，如何才能满足差分隐私？
FROM D
WHERE Type = "糖尿病患"
● 首先，如果我们修改一个病患的数据，则上述查询结果最多改变3
● 其次，加入拉普拉斯噪声，并把参数λ设定为3/ϵ
一般而言，如果我们发布一组数值型查询结果，我们可以对每个结果加入独立的拉普拉斯噪声来满足差分隐私。噪声参数λ 取决于当我们修改一个人的数据时，查询结果总共会改变多少。一组查询总共的“最大改变”被称为他们的敏感度。取λ =敏感度/ ϵ ，即能满足 ϵ-差分隐私。
如果我们发布的数据并不是数值型的呢？eg：分类变量
答：可以用其他方法引入噪声机制 —— eg：用于数据采集的简单机制随机化回答
5.2 随机化回答
出于隐私，有的人可能不愿意给出真实答案
解决方案：让每个人在他的答案中加入噪声
● 随机化回答可以满足 ϵ-差分隐私
● 直观原因：由于其随机性，攻击者并不能从随机化的输出反推出输入到底是“yes”还是“no”
● 只要根据 ϵ 来调整随机化的概率（上图中的20%和80%）即可
与此同时，我们依然可以通过随机化回答的方法得到真实的统计数据值（大概有多少人的真实回答是“yes”）。我们采用一些方法对得到的统计数据进行修正，从而得到准确的真实估算值。
举例如下：
假设有10000人用随机化回答给出了回复，其中有5500个 yes 和4500个 no 。我并不知道哪些回复是假的，但我知道假回复的分布。
每个人会以80%概率给我假回复，所以大致上有总共8000个假回复。当中大致上有4000个假 yes 和 4000 个假 no。据此，我可以推出剩下的真实回复中大概有1500个 yes 和500个 no（这2000个数据是相当于是对源数据的压缩）。所以大概75%的人的真实答案为 yes。
总结：通过随机修改回复来满足差分隐私，由于修改时引入的噪声分布已知，因此我们仍可以反推源数据的大致分布。但是，我们并不能推断出某个具体个体回复的真假，只能得到一个统计值。
5.3 其他差分隐私机制
■ 但还有很多其他不同的算法
■ 一般而言，不同的应用场景、不同的数据集、不同的输出往往需要不同的算法设计
■ 如何根据应用来设计差分隐私方法是不少领域的学者都感兴趣的问题
● 数据库、数据挖掘、机器学习、计算理论、等等
差分隐私的应用
6.1 差分隐私数据库
只回答聚合查询的结果，通过往查询结果中加入噪声来满足差分隐私。eg：微软的PINQ，Uber的Chorus。应用于数据分析科学家对数据分析的同时保证数据的隐私。
技术难点：
■ 如何尽量少的噪声来达到ϵ-差分隐私
● 精确得到敏感度的困难较大，尤其是在查询需要连接多张数据库表的时候
■ 如何高效地计算查询的敏感度
■ 如何将差分隐私模块无缝整合到现有数据库当中
6.2 差分隐私机器学习
在机器学习算法中引入噪声，使得算法生成的模型能满足差分隐私
例子：谷歌的TensorFlow Privacy ( https://github.com/tensorflow/privacy ),可用于神经网络训练
TensorFlow Privacy的基本原理：
神经网络通常是用随机梯度下降来进行训练的：
1. 从一组随机的神经网络权重参数出发
2. 拿一组随机选取的元组来计算权重的梯度
3. 用梯度来更新权重参数
4. 重复步骤2-3
步骤2是唯一一个对源数据进行访问的步骤，故而对步骤2中计算出的梯度加入噪声，使得整个训练过程满足差分隐私，训练后产生的模型也满足了差分隐私。该系统的实现难点在于需要精确计算步骤2中所需要的噪声的大小，TensorFlow Privacy在这方面做了一些理论上的创新。
6.3 差分隐私数据采集
■ 场景：从移动设备采集用户数据，如应用程序的使用时长等
■ 为满足差分隐私，让用户采用类似于随机化回答的方法来提供数据
■ 例子：谷歌Chrome、苹果iPhone、iPad和Mac、微软Windows 10
■ 技术难点：需要采集的数据可能比较复杂，无法用传统随机化回答解决
● 例子：苹果公司需要采集用户输入的新词，但是字典里面并没有
■ 为此，谷歌、苹果和微软都因应其采集需要提出了新的随机化算法
6.4 差分隐私数据合成
当有一个数据集需要发布给第三方时，我们可以选择不发布源数据，而是对源数据进行建模得到一个统计模型，然后从统计模型中进行采样来得到一些虚拟的数据，将虚拟的数据分享给第三方，虚拟数据和源数据有一定的差异，但是分布相近。
○ 基本原理：
■ 先对源数据进行建模，得到一个统计模型用
■ 统计模型来合成出虚拟数据
○ 例子：美国普查局的一些数据产品
■ 如：https://onthemap.ces.census.gov/
○ 技术难点：
■ 如何找到一个合适的统计模型？
■ 如何在统计模型中加入噪声，以满足差分隐私？
前景展望
7.1 展望：弥补现有算法的不足
● 对刚才提到的几个应用，现有解决方案仍有不少需要提高的地方
● 对于差分隐私数据库：
○ 现有算法尚未能在隐私保护、查询准确性及计算效率三者间取得很好的平衡
■ 例子：Uber的Chorus在不少查询中误差可达100%以上
● 关于差分隐私机器学习，现有算法的不足：
○ 准确度还有待提高
○ 尚不能很好地处理复杂模型，如GAN
○ 另有一些新方向，如：
■ 联邦学习
■ 与多方安全计算结合
● 对于差分隐私数据采集：
○ 现有算法要求每个用户对其数据加入相当程度的噪声
○ 这对后期估算统计数据带来了一些困难（随机噪声太大，对后期估算统计数据带来困难）
○ 近年大家开始探索的新方向：
■ 与安全计算相结合，以减少满足差分隐私所需的噪声
● 对于差分隐私数据合成，目前的算法只能处理关系型数据
○ 对非关系型数据的合成基本上还在摸索阶段
■ 如图数据（没有很好的统计模型）、文本数据（统计模型较为复杂，不容易加入噪声）等
7.2 展望：弥补差分隐私本身的不足
● 差分隐私在很多时候其实是一个过于保守的模型：
原因：它对攻击者的假设大致如下
如果源数据里有 n 个人的信息，那么攻击者已知其中 n-1 个人的信息，并试图获得最后一个人的信息（这是一个非常强大的攻击者，这种假设不现实，也就是说目前差分隐私中的噪声是过量的）
● 如何设计一个更加贴近实际的隐私模型？
○ 对差分隐私的定义做弱化，使得其对攻击者的假设不那么保守
○ 现在文献中已有不少改进差分隐私的尝试，但是尚未得到广泛的应用（但是还是要对攻击者的已知信息做出假设）
○ 原因：额外的假设使得改进后的模型往往过于复杂，难以被大众所认同
● 差分隐私虽有着优雅的数学表达，但并不直接对应任何法律条文
○ 满足差分隐私 ≠ 满足隐私保护法律
○ 要解决这一问题，需要计算机界与法律界相互合作
○ 近来已有学者尝试从法律条文出发，设计出与条文相对应的隐私保护模型，并在模型中借鉴差分隐私的思想
总结
● 差分隐私是近年来受到较多关注的一个隐私保护模型
● 有着较强的理论保证，并在不少场景中得到了应用
● 但仍有许多有待解决的问题
往期推荐