联邦学习与安全多方计算

联邦学习和安全多方计算是当前跨机构数据协同的两类主流技术，本文将从基本思想、安全性、性能等多个方面介绍二者的区别，并介绍阿里在安全多方计算方面的最新成果。

联邦学习的发展历史

1. 联邦学习

联邦学习在2016年由谷歌提出，因为Google有安卓系统，需要解决多个安卓设备的分布式建模问题。其中，主要是针对输入法的建模，比如客户在安卓输入法中输入单词“what”，或许他可能想继续输入“do you think”，Google输入法如果能自动联想出来，用户体验就会变得比较好，但是自动联想功能需要大量的用户数据才能学习出来，怎么获得这些用户数据呢？



一个比较粗暴的做法是用户输入了什么字就把这个字全部收集到云端上，但这种做法无疑是对用户隐私的一种破坏。由于谷歌崇尚不作恶，怎样在不收集用户输入文字的前提下，从而预测出用户接下来需要输入的文字？因此，产生了联邦学习。

2. 联邦学习用于多移动端分布式建模



联邦学习的设计优点就是用户数据尽量不离开用户自己的安卓设备，用户尽量在本地完成一部分的训练，然后把训练的梯度传到谷歌的云端，这样谷歌只看见一个梯度，它并没有获得这个用户的设备以前的聊天内容，这样在设计上有一种privacy by design的设计优点。有很多这样的安卓设备，比如：Parameter Server设备是谷歌的云端服务器，它开始会有一个全局的初始化模型，云端服务器会把模型推到各个设备上，然后各个设备基于本地的数据来优化模型，得到一个更新的梯度，把这个更新的梯度发给服务器，服务器收到这么多梯度之后，会更新全局模型，然后发到这些设备上，这些设备又迭代，直到这个模型在某种程度上收敛为止，这就是联邦学习最开始的一个雏形。

3. 国内联邦学习与谷歌联邦学习的区别

区别一：

大概在2018年左右，国内开始引入联邦学习概念，与谷歌的联邦学习相比有了一些发展和改变。两者主要的区别是谷歌的联邦学习主要是面向海量移动设备的数据之间的合作，但是国内主要是机构之间的合作，被称为cross silo FL，一般都是两个或者三个机构之间的合作。但是，目前的应用主要以信贷或者广告为主，例如：两个或多个机构一起判断用户的信用，从而决定要不要借钱给他，或者要不要给他推一些广告。这种情况下参与方的数目实际上跟Google的联邦学习相比是有很大的降低的。

区别二：



Google有很多的设备，每个设备上都有自洽的一些样本，也就是说数据在多个参与方之间，它是横向分割的，比如说这个绿色的在一个设备上，这个白色的在另一个设备上就是横向的分割，每个都有一个完整的样本。



但是国内经常使用的联邦学习，主要是面向数据的纵向分割的。以信贷为例，其通常都是针对一个人的不同特征并把它们组合起来做联邦学习。比如说特征1与特征2在一个机构，特征3与特征4以及label是在另外一个机构，也就是说它主要是面向数据的纵向分割。当然横向分割这种应用国内同样存在，但是用的比较多的或者说比较赚钱的，还是在这种纵向的分割法上。

联邦学习面临的安全挑战

谷歌原版的联邦学习有什么样的安全挑战？而在国内，会面临什么样的新的安全挑战?

1. 谷歌原版的联邦学习的安全挑战



首先是原版横向跨设备的联邦学习。因为它设计上只传梯度，梯度本质是一个函数，它是根据初始的模型以及本地的数据算出来的一个函数，那么这个函数可能是跟原数据是相关的，不能说有梯度就算不出原数据了，那多大程度上相关呢？其实算出来是有一定的难度，但是有一些学者也能算出来，比如说假设我们训练的模型是一个简单模型，比如逻辑回归，我们有了一堆梯度跟原始数据的这种关系，可以通过解方程组把这个未知数解出来的，这是我们在NIPS联邦学习workshop上的一个工作。如果这个模型比较复杂，解方程组算就变得不现实了。



这时有一些其他的方法，比如我们用machine learning的优化方法来反向的优化求得一个近似的解，可能求不到精确的结果，但可以取到一个大致差不多的结果，这里有一个去年的NIPS的文章，它可以反向的从梯度求出人脸，然后这个人脸可能只有若干个像素的区别。所以我们看到如果不保护这个梯度的话，本质上还是能推出原始数据的。

谷歌的解决方法：

① 加差分隐私





Google应对的方法，主要通过加差分隐私，也就是说client上传到云端的梯度，它不直接上传，而是加一个noise，但是准确率会下降。准确率的下降，对于Google输入法somehow是可以接受的，因为输入法的Top3顺序换了一下，或者推荐的东西错了一点，对于用户体验可能差别不大，但是对于我们这种用在广告或者信贷场景下，准确率差1%就可能差很多很多钱，所以对我们来说加差分隐私不是一种能够接受的方案。



② secure aggregation







Google还有一种方案叫做secure aggregation，也就是说要通过secure的方法把这些多梯度聚合在一起，最后效果就是Server只看到了n个梯度聚合在一起的结果。但是，不知道某个具体的client梯度是多少的，从而导致了Server要攻击某个client的概率非常的低，但是我们观察到secure aggregation只适用于client数目比较多的情况。我们可以假设只有两个client，那么这个aggregate的结果就是两个梯度的和，通过第一个client可以推出第二个人的梯度，所以参与方至少要三个人以上，而且这些参与方之间还不能够合谋，所以说这是secure aggregation的局限性。

2. 联邦学习应用面临的新安全挑战

讲解完横向联邦学习的问题之后，接下来了解下国内引入新的联邦学习应用后，会面临什么样的新的安全挑战。



① 参与方过少带来的问题



我们传的梯度是可以用半同态对它进行加密的，例如：Alice把它的梯度用半同态加密，然后传给Bob，这样是没问题的。Alice的参数确实是对Bob保密的，但是Bob在这个加密的数据上运算完之后他是需要传回给Alice，Alice最终需要解密，或者说每一个round都需要解密，每一个round中Bob的参数实际上是被Alice知道的。因为参与方只有两个，Alice得到两个人的计算结果，她肯定是可以从这中间推断出Bob的信息的。也就是说，在这种同态加密保护梯度中，只有一方是受益的，另一方他其实没有受益，跟普通的联邦学习是一样的。就是说半同态加密参数只能实现单向的防护。



② 纵向FL带来的问题



• 怎样对齐样本？



纵向的联邦学习又带来了一个新的问题——怎么对齐样本？例如：不安全的方法跟安全的方法，无论怎么对齐，其都是要按照主键对齐的。在对齐之后，不可避免的泄露了一个信息，对齐的用户都是谁？可能没对齐的用户呢? 我们是可以用PSI这种方法来保护它的。一旦建模，就不可避免的要把这些数据提取出来，也就是说只要在交集里面的那些用户，就会不可避免的泄露了，我们可以再往里面加入假数据等等，但毕竟它在里面就是在里面了。比如说A公司跟B公司合作，他们之间想进行一个聚合，可能A公司的用户并不想把我是A的注册用户这个信息告诉B，也就是说对齐这个东西它的somehow是在一个灰色地带，所以严格来说如果要对齐的话，应该用户显式的点击同意，我同意A把我的信息授权给B，所以纵向的样本对齐问题是一个老大难的问题，虽然现在可能大家都在做，但如果监管严格了，这个问题，我们需要一起来想怎么处理。



纵向的联邦学习肯定有一个人是无标签方，无标签方他可能需要做特征工程，他不能直接把这个特征直接传给别人或者直接进行联邦学习，那么有些特征工程是需要用到这个标签的，所以它怎么用呢？这也是一个难题。



实际上这个特征工程本身就是一个特定的算法，跟Google的横向联邦学习已经没有关系了，我们需要定制一种方案，比如说我们就是要算那个WOE。那我们就要定制一个方案来安全地算这个WOE，这也是第二个难题，也就是说纵向的联邦学习带来了很多新的我们以前传统的联邦学习没有遇到过的问题。





上图是WOE的例子，WOE它是要计算这个特征的重要性，比如说我想把年龄分成不同段，比如0~18岁等这样几个段，那么每个段段内都存在正样本数与负样本数。那么，这个WOE就是把反例总占比比上正例总占比，然后求一个log，这个数越大，说明这个特征这个分段对这个模型越重要，也就是它的判别度越高，我们最后就可以给它加一些分，这个分总可能比较好。但是，对绿色的参与方来说，他是不知道那个标签的（假设标签是在另一方），那他怎么知道这正样本数跟负样本数呢，所以他是没办法知道的。

所以，怎么计算WOE也是一个难题，这也是纵向联盟带来的新的难题。

安全多方计算解决方案

1. 安全多方计算



什么是安全多方计算？怎么用它来解决这些难题？

安全多方计算是一个密码学的定义，它叫secure multi party computation MPC，它是可证明安全的，也就是说它有一个严格的安全定义，双方想计算什么东西，除了这个计算的结果之外，中间的任何步骤都是不泄露任何数据内容的。



比如说a和b想一起算个f(a,b)，双方就真的就只知道f(a,b)，其他任何东西，都是零泄露的。当然它里面有细分，比如说有semi honest model跟malicious model，这个就是具体技术问题，就不细讲了。

2. 举例子说明安全多方计算到底怎么做？

比如说Alice跟Bob，他们分别拥有数据a和b，他们想进行一个联合的机器学习f(a,b)。这里我们不管它是纵向横向总之它就有一堆数据a，它有一堆数据b就对了。安全多方计算MPC有很多种，我们这里是用基于秘密共享的例子，就是说用秘密共享的MPC方法怎么做这个建模。









首先，a跟b会把他自己的这个数据进行一个随机拆分，比如a有一堆数据，生成了一堆随机数，a减去这个随机数，这个r是他本地生成的随机数，同理，Bob他也会本地生成随机数r'，那这个r跟r'先不告诉对方，那我就把这个数据分成了两份，任意一份单拎出来看好像都是个nonsense的garbage，因为它是随机的嘛，它减去随机的也是个随机的，然后，他们两个人可以交换一下这个分量，比如说Bob把这个b-r'发给对方，Alice把这个r发给Bob。之后，我们称这个数据集现在处于一个秘密共享的状态，也就是说单方视角上他们看到的都是乱码，只有双方同意的情况下，把这两个数据拼到一起，他才能知道最终的数据是什么。那么这个秘密共享状态下的数据集，它的优点就是它还是能够计算的。



我们怎么算a加b？其就是本地把这两个分量相加。比如Alice算出了a加b减去这两个东西，Bob就把这两个东西加起来，可以看到这两个东西如果拼在一起的话，它是可以得到a加b的。同理，我们也可以在秘密共享的状态下做a乘b、a除b，a greater than b等等，协议会复杂一点，但是都是能做的。然后这些操作它构成了整个机器学习的算法，比如说我可以在上面算一个f(a,b)，然后得到f(a,b)的秘密共享状态，我们两个人再商量一下，把这个拼起来，发现了f(a,b)是多少，同时中间的任何中间结果都是秘密共享状态的，都是零泄漏的。

3. WOE为例子，我们怎么来无泄漏的计算这个WOE呢？





因为WOE就是一个正负样本的比值，正负样本我不知道，但是知道标签的那一方可以发一个秘密共享的向量过来。比如，正样本的就是1，负样本的就是0，他把这个向量以秘密共享的方式发过来，我自己的这个向量跟这个秘密共享的向量进行一个乘法，得到一个秘密共享的这个结果，这个秘密共享的结果就是这个正样本的数。但是，它是秘密共享状态的，所以我也不知道它是多少。之后，我可以进行一个秘密共享的除法，可以再次进行一个秘密共享的log。最后，如果我要是必要的话，我就把这个数据复原出来，比如算出WOE是0.9，然后这个过程中任何数据都是没有泄露的，除了你要计算的那个WOE最终的结果。如果我们不用安全多方计算，用其他的自设方法来算WOE呢？比如说我们用半同态来算这个WOE，那边把加密的0跟1发过来，这样会泄露我每个分箱的样本数目，比如我0~18岁有150个人，这个数据有样本有标签的一方，不可避免的被他知道了，这个泄漏虽然少，但是中间肯定是有泄漏的。



对于这两个方法，因为我们安全多方计算的除法跟向量内积还是比较高效的，所以这个方法还是比较好的。

4. 安全多方计算不需要“数据对齐”就可以建模



比如说商家A持有用户1与用户2，商家B它持有用户2与用户3，然后他们可以把他们所有的数据都以秘密共享的形式分成两份。大家有4个秘密共享的数据，谁也不知道哪个是谁，然后在这个秘密共享状态下可以进行匹配，得到一个秘密共享的结果。从4行得到了1行，但是大家只看见了4行变成1行，谁也不知道这一行是user2，最后得到了秘密共享状态下的user2，然后秘密共享状态的数据是可以进行MPC建模的。这样完美的保护了用户的隐私，谁也不知道这是user2，user2呢也没有让任何人知道她是A的客户还是B的客户，那么这样做有什么好处呢？



我们可以下结论说我们这样做是合规的。例如：我们以GDPR为例子，其第5条规定：对个人数据的处理不应当违反最初收集该数据时的初始目的，意思就是：用户让你干什么你就可以干什么，用户没答应干什么你就不能干什么。严格来说对齐数据的处理这个过程，用户是没有同意商家A把我是你的注册用户这个信息告诉商家B的，所以，这个过程somehow是存在风险的。但是GDPR也规定，统计用途是可以超出这个初始目的，很明显建模是一个统计性的。比如，他在这个交集上建出一个模型，这个肯定是一个统计性的模型，也就是我们可以说秘密共享状态下的数据对齐是合规的，这是安全多方计算的一个优势。

具体的算法比较密码学，大家可以参考一下Facebook最近发的一个blog，上面的方法就是在秘密共享状态下进行数据对齐，这是安全多方计算解决的第二个数据挑战——怎么对齐数据。

5. 安全多方学习缺点





安全多方计算有什么缺点呢？它的缺点就是它性能肯定是低于联邦学习的，为什么这么说？

因为联邦学习中每个round总有一部分是可以本地算的，不需要网络，然后算完之后再交互一次。但是安全多方计算，他每一个操作都需要交互，例如：每一个乘法，每一个比较都需要双方的交互，也就是说它的性能可能是比较弱的。但是，目前在logistic regression这种简单模型下，它的性能经过我们的优化已经是完全可接受了。比如说万级样本百级特征可以10秒钟跑完，我们去年参加了一个iDASH的安全多方计算比赛，他的题目是：有三个医院，每个医院是有一些病人的数据，他们规定这个病人的数据是严格不能够传给别的医院的，他们三个医院想合作在这个数据上进行一个建模，也就是说判断某些基因的人可能/不可能得某些病，这样数据越多建模是越准确的。但是，由于合规问题，医院之间不能互传数据，所以比赛要求要使用安全多方计算来实现医院之间的联合建模。



我们是取得了这个比赛的冠军，我们是唯一一个准确率超过70%的队伍，我们的性能也非常好，是20秒，这也是这个比赛6年以来第一次有中国队获得冠军。



总的来说，安全多方计算在某些场景是完全可用的，但是我们不能否认它对复杂模型，比如说XGBoost等等，多方安全计算的性能还是存在明显的瓶颈，这方面Secure Boost的性能就会比它强很多

总结



技术角度来讲，国内的联邦学习主要类似于cross silo的这种联邦学习，它是纵向的，Google的联邦学习主要是横向的，国内联邦学习主要是面向少量的两个或三个机构的合作，Google联邦学习面向海量的安卓终端之间的合作。



这个变化肯定带来了新的安全挑战，当我们要面对这些安全挑战时，我们设计上必须慎之又慎，我们要设计完善的解决方案。如果我们为了性能进行了妥协，这是无可厚非的，但是我们一定要详细的对参与方说明，我们这个算法解决方案是解决了什么样的安全问题？提供了何种安全保障？比如说对谁可能会产生何种信息泄露，能抵抗何种攻击，让用户有这样一种知情权。



安全多方计算解决方案，它是有其独到的安全优势，因为其中间没有结果泄露，那么它是有更广阔的应用前景。我们也很高兴看到FATE他也现在已经提出了SPDZ的安全多方计算protocol，我们相信它可以进行更好的后面的迭代开发。



这是我们阿里安全双子座实验室，这个平台的logo叫可用不可见，就是BLINDFOLDED COMPUTING，闭着眼睛计算，并看不到数据的内容。



嘉宾介绍：

洪澄，阿里巴巴集团高级安全专家，2006年获中国科学技术大学软件工程学士学位，2012年获中国科学院大学信息安全博士学位。研究兴趣包括数据库安全、数据安全与隐私保护、应用密码学等，曾在EUROCRYPT，SIGMOD、VLDB等国内外相关期刊、会议发表论文10余篇，担任密码学报，IEEE Transactions on Dependable and Secure Computing (TDSC) 等审稿人。现在阿里安全部负责安全多方计算、同态加密等前沿技术的研究，及其在阿里经济体的推广应用。



原文链接：联邦学习与安全多方计算