3.2.1　差分隐私

随着互联网行业的飞速发展，随之而产生的用户数据也越来越多。基于大数据和机器学习等技术，人们可以对这些海量用户数据进行分析，让用户享受更高质量的服务。然而，对这些数据进行大量的统计和分析将严重威胁相关用户的隐私。差分隐私（Differential Privacy，DP）针对数据隐私保护和数据分析之间潜在的利益冲突，从技术上提供了一种解决方案。为了让广大研究者和从业者对基于差分隐私的联邦学习有所了解，下面首先介绍差分隐私的基础知识，如定义、分类等；然后介绍其在联邦学习中的应用。

1. 引言

差分隐私模型是一种被广泛认可的严格的隐私保护模型。它通过对数据添加干扰噪声的方式保护所发布数据中潜在的用户隐私信息，使得攻击者即便掌握了除某一条信息以外的其他信息，仍然无法推测出这条信息。因此，这是一种从数据源头彻底切除隐私信息泄露可能性的方法。

差分隐私形式化了隐私的概念，从而允许正式证明某些数据收集方法可以保护用户的隐私。此外，它使我们能够通过一个具体的值来量化隐私泄露（这使得比较不同的技术成为可能），并定义允许隐私泄露程度的范围。它也不受后期处理的影响，这意味着没有数据分析师可以利用差分隐私算法的输出使算法失去其对应的隐私保护能力。如果应用正确，差分隐私允许在保护个人隐私的同时揭示整个用户群体的属性。

差分隐私的概念来自密码学中语义安全的概念，即攻击者无法区分不同明文的加密结果。该模型通过加入随机噪声来确保公开的输出结果不会因为个体是否在数据集中而产生明显的变化，并对隐私泄露程度给出了定量化模型。因为一个个体的变化不会对数据查询结果有显著的影响，所以攻击者无法以明显的优势通过公开发布的结果推断出个体样本的隐私信息。也就是说，差分隐私模型不需要依赖攻击者所拥有的背景知识，而且对隐私信息提供了更高级别的语义安全保护，因此被作为一种新型的隐私保护模型而被广泛使用。

差分隐私由Dwork于2005年在一篇专利中首次提及，并于2006年在论文中首次被Dwork正式提出。从那以后，人们进行了大量的工作来描述差分隐私的性质和机理，并对其结果进行了回顾，如Dwork在2007、2008、2010和2011年发表的论文。

最初的差分隐私研究工作主要集中在需要为数据添加多少噪声来实现隐私的问题上，于是引入了拉普拉斯方案。基于这些工作，Hardt等人在2010年证明了达到差分隐私所需的噪声水平下限。关于添加噪声的问题，Lee等人在2011年的论文中研究了如何选择合适的参数（该参数定义了隐私保护的水平，参数越小表示隐私保护程度越高）。

2. 差分隐私

接下来正式介绍差分隐私，首先介绍常用的术语，然后用一个具体实例给出差分隐私的数学定义，最后引出经典的-DP和，δ-DP。常用术语如下。

数据管理员：数据管理员在其整个生命周期中管理收集到的数据，包括数据清理、注释、发布和表示等。其目标是确保数据可以可靠地重用和保存。在差分隐私中，数据管理员负责确保数据隐私不会被侵犯。

攻击者：攻击者对找出数据集中的个人敏感信息感兴趣。在差分隐私中，数据集的合法用户甚至也会被称为攻击者，因为他的分析可能会侵犯个人的隐私。

数据集：可以把数据集D看成一个多重集合（多重集合是一个数学概念，是集合概念的推广。在一个集合中，相同的元素只能出现一次，因此只能显示出有或无的属性。在多重集合之中，同一个元素可以出现多次），该集合的实体（元素）来自有限集X。

数据集的ℓ1范数：数据集D的ℓ1范数可以表示为∥D∥1。它衡量了数据集D的大小，即数据集包含的记录d的个数。其数学定义如下：

数据集的ℓ1距离：数据集D1和D2之间的ℓ1距离可以表示为∥D1−D2∥1。它衡量了两个数据集之间有多少个数据记录是不同的。其数学定义如下：

∥D∥12　（3.2）

相邻数据集：两个数据集被称为“相邻数据集”，即两个数据集最多只有一个元素不同，也即∥D1-D2∥1≤1。

方案：差分隐私本身是一个抽象的概念，只能通过具体的方案或机制来实现。该方案往往表示发布数据集统计信息的一种算法。

接下来通过一个简单的例子介绍差分隐私的场景。一个数据管理员执行了一个求统计量操作，称为（对任意的k）。比如，这个统计量是数据集中吸烟者的百分比。一个攻击者找出两个数据集D1和D2，数据集包含了参与者的吸烟状况的信息以及一个集合S，该集合包含所有可能的返回值。在这个例子中，数据集D1和D2都代表参与者是否抽烟的调查结果。其中，抽烟用“1”表示，不抽烟用“0”表示。让两个数据集的大小为100，且分别具有如下形式：

D1={0:100，1:0}（100个0）　　（3.3）

以及

D2={0:99，1:1}（99个0以及一个1）　　（3.4）

攻击者也可以选择边界S=[T，1]，使得（Di）≥T当且仅当i=2。这意味着，操作是在数据集D2上进行的。攻击者的目标就是利用操作来区分数据集D1和D2，从而泄露一定的隐私。而数据管理员有着完全对立的目标。首先，管理员需要选一个统计量操作，使得（D1）和（D2）特别接近，以至于找不到一个可行T可以将它们完全区分，以确保差分隐私。其次，该操作还必须是数据分析所需统计量的良好估计。如果是一个确定的统计量，例如数据集的均值，则有（D1）=0和（D2）=0.01。在这种情况下，如果攻击者选择T=0.005，则他可以很好地区分两个数据集。如上所述，在确定的设置下（即统计量是确定的），隐私保护的目的无法达到。因此，为了达到差分隐私目的，数据管理员需要对每次查询结果添加一个可控的随机噪声，该噪声能起到隐藏数据集间区别的作用。一个可能的噪声分布是拉普拉斯分布。一个简单的图示实例见图3-2。

图3-2中红色区域表示（D1）返回值比阈值T大的概率。这表示攻击者会将D1误判为D2。如果噪声幅度更大的话，则会导致两个阴影部分的大小差不多。

由例子可以直观地看出，统计量的隐私量取决于D1和D2概率之间的比率。在任一点，对数据集D1和D2执行求统计量操作，得到特定结果的概率应该非常相近。该相近程度可以通过接近1的乘性因子表达，如（1 + ）。

前面的示例直观地说明了为什么需要添加噪声以及隐私参数表示什么，接下来将介绍Dwork等人引入的-差分隐私的正式定义。

定义3.1　如果域上的一个随机算法，对于所有相邻数据集D1，D2∈N和所有S∈Im（），都符合-差分隐私，则

由于D1和D2可以交换，因此该定义可直接导出下界：

结合上面两个公式，可以得到

其中，log x用来表示ln x。

基于在实例中见到的乘性因子（1 + ），Sarathy在2011年的论文中采用了略有不同的公式。该文献定义一个机制为-差分隐私，如果它满足

并称该式为另一个e-差分隐私的定义。当比较小的时候，（1 + ）和e之间的差距很小。但是当≥0.5时，e至少要大10%。当递增的时候，两者的取值越来越发散。然而，e是一个通用因子。Bambauer在其2013年的论文中认为使用e有更大的优势，因为它对应着一个完全已知的分布曲线，即拉普拉斯分布曲线。据此，我们可以得到对于差分隐私来说曲线必须要有的特性：当曲线平移固定量的时候，原始曲线和移动曲线的概率比率保持在一个预先指定的范围内。对于e-差分隐私来说，其至少有如下优势。

1）计算速度快：两个概率的乘积对应对数空间中的一个加法，而乘法在计算上比加法成本高。

2）精度高：当概率非常小时，使用对数概率可以提高数值的稳定性，这是由计算机近似实数时采用的方法决定的。在正常概率下，它们会产生更多的舍入误差。

3）简洁：许多概率分布具有指数形式，特别是从随机噪声中提取的概率分布。对这些分布取对数，可消除指数函数，使其用于指数计算。

-差分隐私对机制有较高的隐私要求。但是如果对原始数据添加过多的噪声会导致信息的损失，因此有不少弱化版本的差分隐私机制被提出。其中一个最流行的版本是，δ-差分隐私。

定义3.2　如果域上的一个随机算法，对于所有相邻数据集D1，D2∈N和所有S∈Im（），都符合，δ-差分隐私，则

，δ-差分隐私允许以δ的加性程度违背-差分隐私。如果从概率角度看，δ-差分隐私，则δ表示相邻数据集的查询输出相差超过因子e的概率。或者更正式地说，隐私损失的绝对值最少以概率1-δ取上界。如果δ=0，，δ-差分隐私退化为-差分隐私。

除了上述的-差分隐私和，δ-差分隐私外，还有Taylor等人研究的群体隐私以及组合差分隐私机制等。其中，组合差分隐私机制又包括序列组合、并行组合和高级组合等。另一种对差分隐私机制分类的方法是将其分为局部差分隐私和全局差分隐私机制。根据Dwork在2006年发表的论文，在一个局部差分隐私中，数据在输入阶段就被扰动了，没有任何值得信任的数据管理员，因此，每个用户都有责任在共享数据之前给自己的数据增加噪声。在全局差分隐私中，数据在输出时被扰动。在全局设定下，每个用户都需要值得信任的数据管理员。局部方法是一种更为保守和安全的模型。在局部隐私下，每个单独的数据点都是非常嘈杂的，因此，它本身并不是很有用。然而，对于大量的数据点，噪声可以被过滤掉，从而在数据集上执行有意义的分析。总体而言，全局方法更准确，因为分析是在“干净”数据上进行的，在过程结束时只需要添加少量的噪声。

3. 差分隐私的应用

随着人们对个人信息数据安全意识的不断提高，隐私保护已经成为一个全球性的重大问题，特别是对于大数据应用和分布式学习系统。FL的一个突出优点是，它可以进行本地训练，而不需要在服务器和客户端之间交换个人数据，从而保护客户端数据不被隐藏的对手窃听。然而，通过分析客户上传参数的差异，比如深度神经网络训练的权重，隐私信息仍然会被泄露。防止信息泄露的一种自然方法是添加人工噪声，即差分隐私技术。

（1）NbAFL算法

Wei等人于2020年基于差分隐私概念提出了一种新的框架NbAFL，即在客户端参数中加入人工噪声后再进行聚合。首先，文章证明了通过适当地适应不同的人工噪声方差，在不同的保护级别下，NbAFL可以满足差分隐私。然后在NbAFL中建立了训练后的FL模型的损失函数的理论收敛界。具体来说，该理论收敛界揭示了以下三个关键性质：①收敛性能和隐私保护级别之间存在一个权衡，即收敛性能越好，保护级别越低；②在固定的隐私保护级别下，增加参与联邦学习的整体客户端数量N可以提高收敛性能；③对于给定的隐私保护级别，在收敛性能方面存在一个最优的最大聚合次数（通信轮数）。此外，该文章提出了一个K随机调度策略。该策略从N个用户中随机选择K（1<K<N）个用户参与每轮聚合。文章也建立了该策略下相应的损失函数的收敛界，K随机调度策略也能保持上述三个性质。此外，该文献发现在固定的隐私保护级别下存在一个最优的K，以达到最佳收敛性能。实验表明，理论结果与仿真一致，从而促进了在收敛性能和隐私保护级别上有不同的权衡要求时联邦学习算法的设计。NbAFL的具体步骤见算法3.1。

算法3.1列出了在，δ-差分隐私上使用NbAFL算法训练模型的过程。在该算法的开始，服务器广播所需的隐私保护级别参数、δ，并将初始化的参数w0发送给各个用户。在第t次聚合时，N个活动客户端使用本地数据库在预设的终止条件下分别训练参数。在完成本地训练后，第i个用户将会添加噪声给训练得到的参数，然后更新添加噪声的参数并用于聚合。最后服务器通过对不同权重的局部参数进行聚合来更新全局参数wt。

（2）LDP-Fed算法

有的文献还提出了基于局部差分隐私的联邦学习算法。Truex等人于2020年提出了一种新的联邦学习系统，即LDP-Fed，该系统使用局部差分隐私（Local Differential Privacy，LDP）。现有的局部差分隐私协议主要是为了保证单个数值或类别值集合中的数据私密性而开发的，例如Web访问日志中的点击计数。但是，在联邦学习模型中，参数更新是迭代地从每个参与者中收集的，由高维、连续、精度高的值组成（可达小数点后10位数），使得现有的LDP协议不适用。为了应对基于局部差分隐私的联邦学习中的这一挑战，该文献设计并开发了两种新的方法。首先，LDP-Fed的局部差分隐私模块为大规模神经网络联合训练中在多个单独的参与方的私有数据集上重复收集模型训练参数提供了形式化的差分隐私保证。其次，LDP-Fed实现了一套选择和过滤技术，用于对服务器上选择更新的参数进行扰动（即添加噪声）和共享。

LDP-Fed系统通过N个参与方（客户端）和一个参数服务器协调深度神经网络的联邦学习，它在联邦学习算法的总体架构中集成了局部差分隐私，以保护参与方的数据不受推理攻击。具体地，考虑N个具有相同数据集结构和学习任务的参与方，他们希望以联邦学习的模式协同训练一个深度神经网络。也就是说，每个参与方都希望对自己的私有数据只进行本地训练，并且只向服务器共享参数以实现模型更新。此外，参与方希望在避免隐私泄露的同时达到个性化的局部差分隐私。为了介绍该算法是如何达到目的的，接下来将从用户端（即参与方）和服务器视角介绍LDP-Fed的联邦训练过程。

客户端：

1）参与方使用模型参数θ0初始化本地深度神经网络，局部隐私差分模块则根据用户偏好使用不同的隐私参数进行初始化。

2）每个参与方根据他们私有的本地数据集在本地计算训练所需的梯度。

3）每个参与方根据自己的局部隐私差分模块对自己的梯度添加噪声。

4）更新的模型参数被匿名发送到k-客户端选择模块，该模块以均匀概率（q=k/N）随机地接受或拒绝更新。

5）每个参与方等待接收来自参数服务器的更新后的聚合参数。在接收到更新的聚合参数后，每个参与者更新其本地深度神经网络模型，并开始下一个迭代。

服务器端：

1）参数服务器初始化模型参数θ0并将其发送给每个参与方。

2）服务器等待接收由k-客户端选择模块随机选择的k个参数。

3）一旦接收到更新参数，聚合模块就会对更新参数进行聚合，即对梯度更新取平均以确定新的模型参数。

4）参数服务器更新模型参数，并将更新后的值发送回参与方以更新本地模型。

以上步骤在N个参与方和服务器上进行迭代，直到达到预先确定的收敛条件，例如达到最大轮数（迭代次数）或在测试集上不再有性能的提高。与传统的联邦学习系统相比，LDP-Fed引入了两个新组件：运行在N个客户端上的局部差分隐私模块和k-客户端选择模块。其中，前者负责对输入数据添加一定的噪声，以实现差分隐私；后者就像传统的联邦学习系统中不要求每个参与者在每一轮中分享他们的本地训练参数更新一样，在任何一轮迭代中，只随机选择k个参与方的参数更新并将其上传到服务器。大量基准数据集上的实验结果表明，从技术角度讲，LDP-Fed在模型准确性、隐私保护等方面都比现有的最先进的方法好很多。

4. 其他算法

联邦学习是隐私保护方面的最新进展。在这种情况下，受信任的服务器端以分散的方式聚集由多个客户端优化的参数。最终模型被分发回所有客户端，最终收敛到一个联合的表示模型，而无须显式地共享数据。然而，该训练协议容易受到差别攻击，这种攻击可能来自联邦优化期间的任何一方。特别是在这种攻击中，通过对分布式模型的分析，能揭示客户在训练过程中的贡献以及客户数据集信息。因此，Geyer等人在其2017年发表的论文中针对这一问题提出了一种客户端视角的基于差分隐私的联邦优化算法。其目的是在训练期间隐藏客户的贡献，以达到隐私损失和模型性能之间的平衡。首先，文献展示了在联邦学习中，当模型性能保持较高时，参与方可以被隐藏并证明了该文献所提出的算法可以在模型性能损失较小的情况下实现客户端级别的差分隐私。其次，该算法能在分散训练中动态适应差分隐私保持机制。实例研究表明，模型性能能通过这种方式得到提高。这与集中式训练的最新进展形成了鲜明对比。这种性能差异可以与以下事实联系起来：与集中式学习相比，联邦学习中的梯度在整个训练过程中对噪声和训练批次（batch）的大小表现出不同的敏感性。

有人就某个具体应用开展了相关研究。例如Mcmahan等人研究了手机键盘的单词预测问题上的隐私问题，并将其作为一个验证例子。特别地，该工作在联邦平均算法中添加了用户级的隐私保护，这使得从用户级数据进行“大步”更新成为可能。此外，该工作表明，给定一个具有足够多用户的数据集（即使是小型互联网规模的数据集也能轻松满足这一需求），实现不同级别的隐私是以增加计算量为代价的，而不是像以前大多数工作中那样降低模型性能。而且，实验表明当在大型数据集上训练时，具有隐私保护功能的LSTM语言模型在性能上与无噪声模型相似。

还有人就差分隐私机制下的随机梯度下降算法进行了研究。如Koskela等人在2018年提出了一种算法，以自适应的学习速率进行随机梯度下降。该算法可以避免使用验证集，自适应的思想来自外推（Extrapolation）技术。为了估计SGD下梯度流的误差，作者比较了一个完整SGD步骤和两个部分（确切地说是半个）SGD步骤组合得到的结果。算法可以应用于两个独立的框架：联邦学习和基于差分隐私的隐私学习。文章表明，与常用的优化方法不同，该算法在联邦学习的情况下具有很强的鲁棒性。