5.2.2　安全计算协议

在本节中，我们将安全多方计算加入上述计算过程，以保证数据的安全性。本协议基于半诚实模型，即假设被攻陷方只是从协议中收集信息，而没有偏离协议规范。与Yang等人提出的依赖可信的第三方的方式不同，出于安全性和公平性考虑，其采用去中心化架构，即在该协议中，所有运算均由参与方执行，不依赖可信第三方。需要指出的是，在该协议中，需从参与方中随机选出一个Master，这个Master可以是参与方中的任何一个，同时也不要求此方是可信的。Master和其他参与方仅仅在计算任务上有所区别：Master所做的工作包括在同态加密下的聚合和己方数据的处理，而非Master节点只负责处理本参与方的数据。作为对比，Yang等人提出的方法要求第三方必须是独立于任何参与方并且可信的。

1. 密码学基本组件和基本假设

首先介绍我们用到的几个基本组件和基本假设。

（1）Shamir秘密共享

Shamir秘密共享由Shamir等人提出。其利用“一个t阶多项式可以被这个多项式中的t+1个点完全确定”这一性质，将一个明文隐藏在一个随机多项式中，并通过对多项式取值来分解成多个部分，然后对这个多项式执行拉格朗日插值，通过多个部分的结合恢复明文。严格地说，假设我们想把一个秘密s拆分为n份（每一份被称为一个Share），至少有任意t+1（n>t+1）个Share才能恢复s。Shamir秘密共享的做法是在有限域F中定义t阶随机多项式P（X），令P（0）=s，并取n个不同的值构成（x1，P（x1）），（x2，P（x2）），···，（xn，P（xn））。在本文中，我们默认取x1=1，x2=2，···，xn=n，则这n个取值为n个Share。恢复秘密时，任取其中的t+1个点，执行拉格朗日插值法：

其中，li称为拉格朗日系数，即

并取P（0）即可恢复s。

（2）BGW安全多方计算协议

BGW协议是最早的安全多方计算协议之一。它利用Shamir秘密共享中每个Share在加法和乘法下的同态性来实现在密文状态下（即明文通过Share的方式被分享到不同的参与方）的加法和乘法，可用于评估任意四则运算表达式。Ben-Or等人在论文中证明了BGW在多数诚实条件下是安全的。Beaver在其论文中提出了一种对BGW乘法运算进行加速的方法。该方法将协议执行分为线上/线下两个部分，并使用线下预处理得到的三元组，使得乘法运算不需要额外的网络交互。

（3）同态加密

同态加密是实现安全多方计算的有效手段之一。它令人们可以在加密的数据中进行诸如检索、比较等操作，得出正确的结果，而在整个处理过程中无须对数据进行解密。全同态加密可以实现加法和乘法在密文下的计算，但速度往往较慢；半同态加密只能实现加法或者乘法运算，但往往速度较快。关于同态加密的详细内容，建议读者参考Acar等人于2018年提出的关于同态加密的综述。由于联邦学习的诸多场景对时间有较高的要求，并且对于绝大多数线性模型，诸如线性回归和逻辑回归，均只用密文加法运算（对于逻辑函数可做线性近似），因此我们采用了较为高效的Paillier方案进行密文计算，详细严谨的讨论可参考Paillier于1999年发表的论文。

在此，我们对Paillier方案的公/私钥生成过程进行简述：在中随机取两个大质数p和q，并计算它们的乘积N，公钥为g=N+1，私钥为N的欧拉函数，即ϕ（N）=（p-1）（q-1）。

加密时，随机取对明文进行如下计算得到密文c：

c=gmrN mod N2

解密时，计算

m=L（cλ mod N2）λ−1 mod N

其中，L（x）=（x-1）/N。

（4）安全性假设

考虑在绝大多数业务中的实际情况，我们假设参加联邦学习的各个参与方是满足半诚实模型的。相比较而言，对于更强的安全性假设——恶意模型，半诚实模型在时间效率上更好，且在安全性方面，半诚实模型符合绝大多数业务的实际情况。

（5）通信网络结构

每个参与方均可直接与其他参与方通信。在执行协议之前，随机选出一个参与方作为Master来收集并聚合各方加密后的本地信息。

2. 基于分布式密钥生成和阈值解密的Paillier算法

在不存在可信第三方的情况下，密钥生成和解密相对于整个训练过程较为独立，我们在本小节单独介绍这两个过程。

由于安全训练和推理采用了去中心化架构，因此我们使用了无可信第三方的分布式密钥生成和阈值解密的Paillier算法。该算法可分为无可信第三方的分布式密钥生成和阈值解密两个部分。它们分别由Boneh和Fouque等人于2001年的论文中首次提出，并由Nishide等人给出整个协议的安全性证明。Veugen等人在论文中描述了该算法的实现过程并给出了若干优化。

在介绍基于分布式密钥生成和阈值解密的Paillier算法之前，我们有必要先介绍它的基础——基于阈值解密的Paillier算法。

（1）基于阈值解密的Paillier算法

阈值解密（Threshold Decryption）是秘密共享在公钥密码体系中的应用之一。它利用秘密共享将私钥分成多个Share，在解密时，首先用Share对密文进行初次解密，产生多个中间结果，然后将中间结果聚合起来再次解密得到明文。基于阈值解密的Paillier算法由Fouque等人在论文中首次介绍。作者假设在多个参与方之外还存在一个可信的第三方，这个第三方通过Shamir秘密共享为各个参与方生成不同的Paillier密钥，解密时需要一定数量的参与方共同解密。

在我们的应用中，规定每个参与方都生成密钥，且每个参与方都必须参与解密。因此，Shamir秘密共享中随机多项式的阶数即参与方的个数减1。那么，第三方的密钥生成过程可以简述为：假设参与方的个数为p，随机取，并生成λβ的p个Share，每个Share为各个参与方的私钥，公钥为（g，λβ mod N）。假设λβ的Share对应的多项式为h（X），在各个参与方1，2，···，p上的Share分别为h（1），h（2），···，h（p）。

假设密文为c且参与方j需要对c解密。图5-2描述了解密步骤。在解密开始时，每个参与方首先计算中间结果ci，并传给参与方j：

ci=ch（i） mod N2

参与方j收集各参与方的中间结果ci后，通过公式（5.6）计算拉格朗日系数li，再解密得到明文m：

m=L（cλβ mod N2）θ−1 mod N

其中， mod N2。

（2）无可信第三方的Paillier分布式密钥生成

与基于阈值解密的Paillier算法不同的是，在无可信第三方的情况下，生成密钥的操作不能由一方单独完成，因此需要一套新的公钥密钥生成方法。Boneh在其2001年的论文中首先介绍了RSA的分布式密钥生成协议，Nishide等人将其扩展到Paillier分布式密钥生成上并给出了整个协议的安全性证明。Veugen等人在论文中描述了该算法的实现过程并给出了若干优化。

接下来，基于Thijs等人发表于2019年的文献，我们简要介绍无可信第三方的Paillier分布式密钥生成过程。Paillier分布式密钥生成可分为两个阶段：分布式生成模数N；多方生成公钥和各自的私钥。

分布式生成模数N：与RSA相似，Paillier密钥生成也基于两个大质数p和q的乘积N。在分布式密钥生成的过程中，需要各个参与方协同生成各自的pi、qi，使得p=∑ipi，q=∑iqi，N=（∑ipi）（∑iqi），但要求每个参与方都只知道N和己方的pi、qi，而无法获知p、q的具体值。在Boneh等人于2001年发表的文献中，每个参与方首先生成随机数pi和qi，通过BGW协议计算N=（∑ipi）（∑iqi）。由于这个N可能不是两个素数的乘积，故需要进行双素数判定。如果是双素数，则进入下一个阶段，否则丢弃生成的N，从头开始。通过BGW协议生成合适的N后，对各方公布N的值。

注意，生成模数的步骤一般会重复较多的次数，但实验证明它的时间开销仍然在可接受范围内。在Malkin等人于1999年发表的论文的实验中：3个参与方各自使用6线程的机器生成2048位的RSA密钥，平均耗时约18分钟。另外，注意到密钥生成过程独立于训练和推理过程，可作为线下预处理步骤提前进行以节省时间开销。

多方生成公钥和各自的私钥：在无可信第三方的情况下，每个参与方可以通过BGW协议计算出（λβ mod N）和λβ的Share。该计算的具体过程较为烦琐，为保证本章叙述的连贯性，详细过程建议读者参考Paillier公钥密码系统等文章。

3. 训练过程

在本节中，我们对式（5.4）和式（5.5）描述的训练过程构造一个安全计算协议。首先是训练过程，整个训练过程大致可分为4个步骤：1）为各个参与方生成公钥和私钥，同时在线下生成BGW协议进行乘法计算所需要的三元组；2）参与方用Paillier算法计算梯度g并对各个参与方解密；3）各个参与方计算本地的skdk，然后通过BGW协议计算H；4）最后在每个参与方中更新W的值并对更新后的W进行解密，进入下一次迭代或终止。

步骤1中生成公钥和分布式密钥的详细过程已经在前文中介绍了，三元组的计算在Beaver的文献中有详细描述，此处不再赘述。接下来我们给出步骤2到步骤4的详细过程。由于除Master外所有参与方的操作都相同，此处以参与方j为例进行介绍。

（1）计算梯度g

计算梯度的过程分为以下4个步骤。

1）所有参与方计算本地预测值。首先，每个参与方按照式（5.1）计算己方非私有样本的预测值f（j），并进行同态加密得到[[f（j）]]，其中

有标签的参与方将加密后的标签[[{y}]]传给Master。

2）Master聚合各方发来的f（j）。各个参与方将[[f（j）]]传给Master进行求和，得到[[∂L/∂wi]]=[[f-y]]，然后返给各个参与方：

注意，虽然Master获得了各方的f（j），但是由于阈值解密需要所有方共同参与，由此Master无法知晓任何有效信息。

3）各个参与方计算本方的梯度中间值。每个参与方收到Master传来的[[f-y]]后，计算本方的梯度中间值：

4）Master聚合各方发来的[[gj]]。Master聚合各方发来的[[gj]]（j∈{1，2，···，p}），得到梯度密文，并返给各个参与方。各参与方随之对[[g]]进行解密（参考前文），得到本轮迭代梯度g。同样，基于阈值解密的性质，除非所有参与方共同解密或者Master获得了所有参与方的密钥，否则它不能获得任何有效信息。

（2）计算H

求H时需要进行密文乘法计算，由于Paillier算法不能完成此功能，我们选择使用BGW协议进行计算。需要计算的内容参考式（5.3）。在计算过程中，BGW协议的通信复杂度为，其中m为样本特征数。由于在绝大多数情况下样本特征数较小，故而总的时间消耗较少。BGW协议执行过程在Cramer等人2015年发表的文章中有详细介绍，为了避免内容冗杂，建议读者直接参考。

（3）更新W的值

各个参与方更新得到，其中j∈{1，2，···，p}，k表示第k轮迭代，并检查g二范数的大小，符合条件时停止迭代。

（4）安全性简要证明

我们对整个计算过程的安全性进行简要说明。在求g的过程中，任何发送到他方的数据均经过了加密，解密时必须由所有参与方共同参与。因此，所有参与方仅仅能获得密文，而无法知晓其中的信息。在求解H的过程中，所有计算均通过BGW协议进行，所以计算过程中的安全性由BGW协议的安全性保证。各个参与方在整个训练过程中仅仅获得属于自己特征的那部分梯度和参数W，所以计算过程是安全的。

4. 预测过程

预测过程的前两步与训练过程中计算梯度的前两步相似。

1）所有参与方计算本地预测值。计算己方非私有样本的预测值f（j），并进行同态加密得到[[f（j）]]，其中

2）Master聚合各方发来的f（j）。各个参与方将f（j）加密得到[[f（j）]]，并将其传给Master进行求和，得到预测值[[f]]，然后返给各个参与方。

3）各方解密得到最终结果。各个参与方收到[[f]]并按照前文所述的方式进行两步解密，然后计算己方私有样本的预测值并返回结果。注意，有时并不需要所有参与方均得到预测结果，这时可以由需要预测值的那一方发起解密请求，各方在本地解密后仅将解密中间结果返给请求方，最后由该方解密得到结果。

与训练过程相似，各个参与方传出的数据均经过加密且解密过程由所有参与方共同执行。每个参与方只能获得各自的预测结果。