导读：本文将分享全同态密码与联邦学习结合的一些可能的新方式，将从联邦学习与隐私保护、全同态密码与联邦学习、全同态密码的新进展以及课题与展望四点展开。

01联邦学习与隐私保护

1. 联邦学习

联邦学习源起“大规模终端上的分布式训练”，通过收集终端上的信息, 如局部的梯度，以完成一个全局的计算，如全局的梯度。通信量很大的时候关心的是通信量的多寡，模型收敛速度和鲁棒性等问题。举个同构数据集上的逻辑回归模型训练的例子，每个数据持有者（DO）持有相同的特征，类比数据库表的水平分割；记当前全局的模型参数为 ，则数据持有者计算本地局部的梯度∇iθ；Parameter Server (PS) 收集所有的局部梯度，更新和发布新的全局模型参数 ← Σ∇iθ。主旨是能本地计算的都在本地计算，只交换少量信息达到全局训练的目的。

2. 联邦学习&数据的隐私保护

下面有三个数据隐私相关的问题：

联邦学习可以收集 & 交换什么信息？如数据本身不得出域；但是局部梯度是否可以出域 ?中间值哪些可以公开？如是否允许 PS 得到各个DO局部梯度？还是 PS 只能得到全局的梯度，还是什么都看不见 。如果可以收集和交换，那么如何收集 & 交换这些信息？

通过不同方式的组合，可以为信息提供不同程度的保护。在分布式训练里PS可以获取局部梯度信息，DO获取全局梯度信息；那么信息保护的力度是baseline。而联邦学习中PS和DO可以获取全局梯度,信息保护力度大于baseline。联邦学习Plus PS可以获取全局梯度，DO获取final model，信息保护力度大于联邦学习。多方安全计算PS可以不用获取任何信息，DO获取final model，信息保护力度大于联邦学习Plus。下面着重介绍同态密码在“如何收集 & 交换这些信息”里的作用。

02全同态密码与联邦学习

1. 同态密码

下面介绍同态密码（Homomorphic Encryption)。HE 并不是 hash，也不是单纯的加密算法 (e.g., AES)，HE 能在不解密的前提下，计算密文的加法和乘法。目前的联邦学习框架大多采用加法HE；如 FATE 用 Paillier 方案。它的优点是加密方案本身易于实现和易于封装成高级语言。缺点是大规模计算的性能瓶颈明显，如加密 10k 整数可能需要数分钟；它不支持密文乘法；对非线性计算如sigmoid无能为力。

2. 全同态密码

下面介绍一下全同态密码（Fully Homomorphic Encryption)，这里特指基于多项式格的 FHE；如 BFV 和 CKKS 方案。HE 和 FHE 的最大区别有两点：功能上FHE支持密文的加法和乘法，HE支持加法；FHE支持高延迟和高吞吐，而HE是低延迟和低吞吐。通过设计算法，FHE 可以获得远优于HE 的性能。通过设计系统，FHE 可以提供新的联邦模型，并且利用新型的分布式 FHE 能达到 FL-plus 以上的保护力度，因此FHE与联邦学习结合有较大优势。

3. Faster Building Block for FATE

通过设计算法，FHE 可以获得远优于HE的性能。下面举个例子：FATE 在异构数据集上训练逻辑回归模型。异构数据集Z ≔ Z1|Z2| … | Zn；模型 ≔ 1|2| … | n；梯度

。DO 不得知全局梯度，需要在每个 DO 本地计算明文矩阵 Zi与密文向量i的乘积。

如果使用基于 HE 的矩阵向量乘性能比较堪忧，如矩阵为4096行*4096列, FATE 需要耗时 1.5hr 计算单次矩阵-向量乘。如果使用同步计算，需要等上一个 DO 计算完，总耗时接近 1.5hr * #Dos。而Yang et al. 用 FPGA 实现 HE，但比 FATE’s HE 只快了 10x。与FHE 的矩阵-向量乘对比，我们的算法能在 不到2 秒处理 4096x4096 的乘积 (1/10^3 of FATE’s HE)。

3. 基于 FHE 的联邦计算模型

我们可以考虑FHE的新模型，因为基于 HE 的联邦学习一般需要长链接，多次通信，PS和DO 需要保持一直在线才能使得计算得以进行，即需要多轮通信来不断交换信息（如局部梯度的密文）。利用 FHE 能做到短链接，只需一次通信，一个 Master (如持有 label 的DO）去生成公私钥对，其他 DO 只需要加密数据上传到计算节点后数据拥有者即可离线；PS 负责所有的密文计算。最后返回结果给 Master 解密。如在逻辑回归训练的例子里，梯度是密文矩阵-密文向量乘积，可以利用 FHE 高效地计算而无须额外的通信。我们利用基于 SEAL 全同态库，实现了单中心的 LR-training 模块。在MNIST 集（11k*197 特征) 上，8核cpu，大概时间 200s/epoch；abalone 集合（3k*9 特征) 上，约 15s/epoch。

4. POSEIDON：分布式 FHE 与联邦学习

利用新型的全同态方式有更特别的玩法，之前的方案是属于单密钥 FHE 的方案，需要顾虑 PS 跟 Master 共谋的风险。相反在分布式FHE 中多个 DO 会独自生成密钥的一部分，需要所有 DO 协同生成公钥和一起协同解密（防止部分共谋）。

当秘钥生成后，可以将分布式转为单中心模式，即单个计算结点（如 PS）收集必要的密文进行计算，DO 无须干预，但这样不够联邦化。对于分布式模式（同构数据集上），彻底遵循“能本地计算的都在本地算，只交换少量信息”的主旨，中间不会解密。数据不出域，只交换梯度的密文，利用“掩码-分布式解密-再加密”，可以减轻一些同态操作的计算量（如密文自举）。再此之上Poseidon公海提供密钥旋转操作。类比代理-重新加密 Proxy re-encryption，把密文对应的密钥 SK 旋转为第三者 U (非 DO/SP) 持有的密钥 SK’，U 无需参与到 KeyGen。如 DO 们协同解密，然后U的公钥加密。在原论文POSEIDON: Privacy-Preserving Federated Neural Network Learning提供例子是10 DOs，分布式训练 MLP， 1 epoch 约 20s ( 共 2000 行数据)。

03全同态密码的新进展

1. PEGASUS 框架：FHE 功能增强

一般 FHE 只支持算术运算（加&乘法），对非算术运算（如求根，对数）需要额外办法。第一种解法是需要事前判断好近似的区间范围和需要的近似精度，如高阶多项式近似：

第二种解法是配合混淆电路（GC）等 MPC 工具去计算，再倒回 FHE 密文。解法二的优点是灵活性好，能计算各种负责函数；Gazelle, Delphi 等多种框架都采用，缺点是PS 跟 Master 之间需要多次通信。

我们提出PEGASUS 框架新方案， 能够在 FHE 密文上直接计算非线性函数。如FHE.Enc(x) -> FHE.Enc((x))。首先对输入空间离散化，然后进行计算。但是由于FHE 自身存在噪音，函数越光滑，误差就越小。它的优点是灵活性好，无须额外的通信，缺点是需要的计算量较大（0.5s –- 1s 一次)。这篇论文收录在今年的 S&P’21（PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption）。

04课题与展望

1. 主要课题：FHE 性能的优化

FHE 能为联邦学习提供灵活的计算模型，如单中心式、分布式等，但是单次 FHE 操作需要的耗时都比较大，如 ~100ms 量级的密文乘法，~1min 量级的密文自举。通用的 FHE 加速方案能利好以上各种方案和模型，针对 FHE 的最核心运算子（离散傅里叶变换）进行提速。而计算复杂度方面 O(N) 很难优化，如采用“混合蝴蝶网络”只有常数项级别的优化。那如何减少 NTT 的时耗？

使用 AVX-512 指令集：Intel 最近给 SEAL v3.6 的 PR，NTT 时耗减少 可以达到50%。GPGPU：Badawi et al. 实现了 GPU 版本的 NTT，K80 下耗时是 CPU 版本的5%。FPGA：Kim et al. 的 FPGA 实现的 NTT 是 CPU 版本的 0.8%。

2. THM & 愿景

FHE 可以为联邦学习提供灵活的计算模型，即使单纯作为 building block（如矩阵向量乘），性能也可以优于传统HE。而计算瓶颈能通过算法优化和硬件提升来缓解，我的愿景是通过（分布式）FHE和单一计算结点提供Federated-Learning-as-a-Service (FLAS)，计算结点可以做得很“重”，武装上 GPU，FPGA等，而客户端只需要关心 key-gen 和 加密逻辑（易于审计），配合 PEGASUS 来做 FHE 上的非线性运算。

05问答环节

Q：阿里的全同态是基于微软的seal还是自己实现的？

A：基于seal，算法基础逻辑不做改变，只是对算法的性能进行了一些优化。

Q：全同态和fate’s的半同态效果怎么样？

A：如果只是算两个密文加法fate半同态更快。如果是更大矩阵向量乘法，有办法做到比半同态快。

Q：加密数据上传，网络消耗是否很大？

A：网络消耗很大，耗时取决数据和计算模型。线性模型比多轮通信会少一点。

Q：半同态不能支持sigmoid，全同态不支持sigmoid，遇到逆运算、对数运算、除法运算怎么办？

A：参考我们发的论文，提供不需要解密直接在全同态密文上计算非线性函数。有办法解决只是性能比较慢。

Q：请问全同态联邦学习可以支撑多大数据联邦建模，有实际应用吗？

A：取决于单点多强大。我们用的是一台，实际上也可以用多台机器组成。多个同态密文，可以使用MapReduce，调度在工程上可以有优化。

今天的分享就到这里，谢谢大家。

分享嘉宾：

分享嘉宾：陆文杰博士 阿里巴巴

编辑整理：黄伟聪 南京大学

出品平台：DataFunTalk