联邦学习中的安全多方计算
Secure Multi-party Computation in Federated Learning
什么是安全多方计算
安全多方计算就是许多参与方需要共同工作完成一个计算任务或者执行一个数学函数,每个参与方针对这个执行构建自己的数据或份额,但不想泄露自己的数据给其他参与方。
在安全多方计算中的定义包括以下几个方面:
- 一组有私有输入的参与者,对他们的输入执行一些联合功能。
- 参与者希望保留一些安全属性,例如,选举协议中的隐私性和正确性。
- 安全性必须在面对某些参与者或外部各方的敌对行为时保持不变。
研究人员通常利用真实/理想的模型范式来探索安全协议的安全性。
- 在理想的模型中,安全性是绝对的,例如服务器是绝对可靠和可信的,并且对服务器进行成功攻击的概率为零。
- 在真实模型中,我们也可以通过各种方式来实现理想模型的安全性。任何可以从真实模型中学习或获得的信息敌手也可以从理想模型中学习或获得。换句话说,安全性在理想模型和真实模型之间是不可区分的。
举个例子:在理想模型中,假设有一个可信服务器能够聚合各参与方并且产生正确预期输出;在真实模型中,不存在可信服务器,参与方可以通过点对点方式交换输入和信息来达到这种形式。
安全多方计算中有三个安全模型:
- 半诚实敌手模型:被腐化的参与方忠实执行既定协议;而敌手尽可能收集所有信息以获得额外的机密信息
- 恶意敌手模型(强安全模型):腐化参与方可能在任何时候根据敌手指示违背协议。
- 隐蔽对手模型:介于上述两极端模型之间
安全多方计算的基础组件
不经意传输(茫然传输,Oblivious Transfer,OT)
不经意传输(OT):发送者S想发送n个消息中的一个给接受者R,目标是S不知道哪个消息被R接收,而且R没有获得S发送的其他n-1个消息中的任何信息。
一个标准的二选一函数被描述为
- 输入:
- 发送方
输入两个消息S S ,m1 m1 .m2 m2 - 接收方输入一个随机比特
.σ∈[0,1] σ∈[0,1]
- 发送方
- 输出:
- 发送方
没有输出.S S - 接收方
获得R R ,并且没有获得关于mσ mσ 的任何知识.m1−σ m1−σ
- 发送方
实现OT协议的方法有很多,例如RAS或基于离散对数问题的方法。
混淆电路
双方将共同协作实现:一方将设计一个逻辑电路,另一方将检查并使用该逻辑电路。
秘密共享
秘密共享(Secret Sharing, SS)是密码学中的一个重要元素。对称或非对称加密更侧重于两方之间的秘密共享。然而某些时候,例如在联邦学习中则需要在多个参与者之间共享一个秘密,此时就需要秘密共享。
一般来说,有三种类型的秘密共享协议:算术秘密共享、Shamir秘密共享和Goldreich-Micali-Wigderson(GMW)共享。算术秘密共享是利用数论的特征在两方之间共享一个秘密,而GMW共享主要使用XOR来隐藏私有值,而Shamir秘密共享可能是实践中最流行的秘密分享的原语。
在Shamir秘密共享中,一个秘密
由于每个参与者
另一种流行的秘密共享方法是使用拉格朗日插值法。我们用一个简单的例子来说明这项技术。假设
,其中
分配者可以在
两种方法的主要区别:
- Shamir秘密共享是
到x1 x1 是随机选取且公开的,之后随机选取xn xn 个多项式系数,求得y值进行分配,秘密份额是y值。需要分配方分发两次,一次公开的,一次秘密份额。t−1 t−1 - 拉格朗日插值法是先找一个多项式,再随机选
个点,这样每个点(即n n 值和x x 值)共同作为秘密份额,y y 到x1 x1 不公开。分配方只需要分发一次。xn xn
同态加密
目前同态加密的性能有很大挑战,阻碍了实践中的部署。
联邦学习中的安全多方计算
成对掩蔽技术(pairwise masking)数据聚合
假设我们有两个客户端
对掩蔽方法进一步推广:假设有多个客户端参与该任务,使用客户端集合
我们注意到,上述掩蔽的正项或负项的数量是动态的,并取决于用户
这里贴一下我理解的成对掩码加减的示意图,以便于理解:
此外注意:这里的每对客户端之间生成的虚拟向量应该是不保存的,直接加在真实值上面,因此如果发生掉线情况,就会出问题。
由于掩码是成对出现的,所以如果出现参与方掉线的情况就聚合之后的总和会出现问题,因此最重要的就是解决参与方掉线的问题。
联邦学习中的秘密共享
根据前文,可以使用秘密共享来解决客户端掉线问题。
在系统启动阶段,一个给定用户
也就是说如果有一个客户端
这里我本来有个疑问:此处为什么不用与他结对的客户端持有的值直接恢复?
我思考了一下之后觉得与它结对的客户端并不持有这个虚拟向量(我感觉这个虚拟向量就是个一次性的随机数),虚拟向量使用完之后两方都不存储。两方只是在生成之后根据这个虚拟向量值生成了秘密共享份额以备恢复它,但原始的虚拟向量值就销毁了,加完或减完只保留
此外有一种潜在的攻击是服务器可能声称用户
为了应对这种攻击,提出了一种双掩蔽方法(待后续学习)。
为了处理掉线带来的昂贵代价,Zheng等人提出了一个轻量级的加密解决方案:
思路类似于DH密钥交换协议,每个客户端生成一个私钥和一个公钥,每两方通过密钥交换得到一个公共密钥,这个公共密钥就作为虚拟向量,这样子后续如果有一方掉线,而另一方知道这个公共密钥,可以直接恢复。