隐私计算平台效率问题和加速策略-技术圈

👆点击“博文视点Broadview”，获取更多书讯

目前，隐私计算平台广泛用到了多种安全技术，包括同态加密、秘密共享、差分隐私、可信执行环境，以及其他一些安全多方计算技术。

虽然这些安全技术的应用很好地保证了数据价值的安全共享，但同时也带来了计算和通信效率的大幅下降。在对安全和效率的双重探索中，星云Clustar 的研究人员基于理论分析和实践应用，提供了一系列安全加速方案。

文献[1] 对联邦学习模型训练中存在的性能问题进行了全面的探讨，基于这些问题，文献[2~4] 提出了多样的解决方案。接下来，我们对隐私计算的效率问题及相应的解决方法进行详细的介绍。

隐私计算技术中的效率问题

01. 同态加密

对数据进行同态加解密需要进行一些数学运算。这些运算的计算复杂度既与所采用的同态加密算法相关，也与选取的密钥长度相关。通常来说，密钥越长，同态加密的安全性越高。

为了保证数据加密有足够好的安全性，目前普遍采用1024或更多比特的密钥长度。除了同态加解密运算本身带来的计算开销，加密后的密文在密态下的计算也会带来很大的计算开销。

以Paillier 同态加密为例，数据经过同态加密后，会从32 比特或64 比特的小数变成与密钥长度等长的大数（比如1024 比特或2048 比特长度的大数），使得通信的开销也大大增加。

此外，这些大数在密态下进行加法或乘法运算也不再是简单地将数据相加或相乘，而需要通过复杂的模乘或模幂运算来完成相应的密态下运算。

02. 秘密共享

在秘密共享中，秘密的分发和恢复都会导致效率的下降。

在秘密分发过程中，需要通过一定的数学计算将秘密分割成 $n$ 份，然后分发给 $n$ 个参与方。在秘密的恢复过程中，需要收集 $k$ 份（ $k \leqslant n$ ）分割后的不同秘密碎片，然后通过算法规定的数学计算将秘密恢复。

例如，Shamir 算法需要通过解一个同余方程组来恢复秘密。不难发现，秘密分发和恢复都需要进行额外的计算和通信操作，因此不可避免地会导致效率的下降。

03. 差分隐私

差分隐私需要给每一个查询结果加入一定的噪声，如通过Laplace 机制或指数机制来添加噪声，从而在查询结果中引入足够保证用户隐私的随机性。

向查询结果中添加噪声需要进行一定的额外数学计算，从而不可避免地导致效率的下降。

04. 不经意传输

为了保证发送者无法知道接收者到底接收了多条可选消息中的哪一条，不经意传输一方面需要使用加密算法（如RSA 算法）对消息数据及随机数进行加密，另一方面还需要在发送者和接收者之间进行多次数据传输，包括传输所选用的加密算法的公私钥。

因此，不经意传输会同时导致计算与传输两方面的效率下降。

05. 混淆电路

与不经意传输类似，能完成某一算法计算的混淆电路也涉及大量的加解密运算，以及对密态数的各类数学变换操作。

此外，所有参与方之间要做许多额外的数据传输，因此计算与传输的效率都会大大下降。

对于隐私计算技术导致的计算效率问题，可以通过异构计算解决。而传输效率的问题，则可以通过设计网络优化技术解决。

异构加速隐私计算

01. 异构计算定义

异构计算是指用不同类型的指令集和体系架构的计算单元组成系统的计算方式。常见的处理器包括CPU（X86、ARM、RISC-V 等）、GPU、FPGA 和ASIC。

下面对四类异构计算系统中常见的芯片做简要介绍。

02. 中央处理器

中央处理器（Central Processing Unit，CPU）是计算机系统的核心部件之一，其主要功能是读取指令，对指令译码并执行。CPU 的主要组成部分包括运算器（ALU）、控制单元（CU）、寄存器（Register）、高速缓存器（Cache），以及保持它们之间互相通信的数据、控制及状态的总线。

我们可以根据所支持的指令集对CPU 进行分类。指令集主要包括精简指令集（RISC）和复杂指令集（CISC）。

一般来说，RISC 指令的长度和执行时间相对固定，而CISC 里不同指令长度和执行时间存在差异。

RISC 指令的并行的执行程度更好，并且编译器的效率也较高。

CISC 指令则对不同的任务有针对性的优化，代价是电路复杂且较难提高并行度。典型的CISC 指令集是x86，典型的RISC 指令集包括ARM 和MIPS。

03. 图形处理器

图形处理器（Graphics Processing Unit，GPU）最早是一种专门用在个人电脑、服务器、游戏机和移动设备上做图像或图形处理相关运算的一种微处理器。

近年来，由于GPU 在浮点计算和并行计算上拥有极其出色的性能，已经被广泛应用于大数据处理、大规模科学研究计算、人工智能等需要大量算力的场景中。

从架构上来看，GPU 包含数十至数百个小型处理器。相比于CPU，GPU 单独来看性能都比较弱，但它们能很高效地进行并行运算。在对批量大数据进行相同的处理时，就会表现出相当高的执行效率。因为具有在架构上做并行计算的天然优势，GPU近年来在通用计算领域获得了迅猛的发展。使用GPU 做批量数据的并行计算已经变得越来越普遍。

04. 现场可编程门阵列

现场可编程门阵列（Field Programmable Gate Array，FPGA）是在PAL、GAL、EPLD 等可编程器件的基础上进一步发展而来的产物。

FPGA 采用了逻辑单元阵列（Logic Cell Array，LCA）的概念，内部包括可配置逻辑模块（Configurable Logic Block，CLB）、输入输出模块（Input Output Block，IOB）和内部连线（Interconnect）三个部分。

FPGA 是可编程器件，与PAL、GAL 及CPLD 器件等传统逻辑电路和门阵列相比，FPGA 具有不同的结构。FPGA 利用小型查找表实现组合逻辑，每个查找表连接到一个D 触发器的输入端，触发器再驱动其他逻辑电路或驱动I/O，由此构成了既可实现组合逻辑功能又可实现时序逻辑功能的基本逻辑单元模块，这些模块间利用金属连线互相连接或连接到I/O 模块。

FPGA 的逻辑是通过向内部静态存储单元加载编程数据实现的。存储在存储器单元中的值决定了逻辑单元的逻辑功能，以及各模块之间或模块与I/O 间的连接方式，并最终决定了FPGA 所能实现的功能。

FPGA 允许无限次地编程，作为一种半定制电路，既解决了定制电路的不足，又克服了原有可编程器件门电路数有限的缺点。

05. 专用集成电路

专用集成电路（Application-Specific Integrated Circuit，ASIC）是为了某种特定的需求而专门设计、制造的集成电路的统称。

集成电路（Itegrated Circuit）是一种微型电子器件或部件。采用一定的工艺，把一个电路中所需的晶体管、电阻、电容和电感等元件及布线互连在一起，制作在一块或几小块半导体晶片或介质基片上，然后封装在一个管壳内，成为具有所需电路功能的微型结构。

集成电路规模越大，组建系统时就越难以针对特殊要求加以改变。为解决这些问题。出现了以用户参加设计为特征的专用集成电路（ASIC）。

ASIC 分为全定制和半定制。全定制设计需要设计者完成所有电路的设计，因此需要大量人力物力，灵活性好但开发效率低下。半定制使用标准逻辑单元，设计时可以从标准逻辑单元库中选择需要的逻辑单元甚至乘法器、微控制器等系统级模块和IP 核。这些逻辑单元已经布局完毕，而且设计得较为可靠。设计者可以较方便地完成系统设计。

ASIC 的特点是面向特定用户的需求，品种多、批量少，要求设计和生产周期短。作为集成电路技术与特定用户的整机或系统技术紧密结合的产物，与通用集成电路相比，ASIC具有体积更小、质量更轻、功耗更低、可靠性更高、性能更好、保密性更强、成本更低等优点。

通过异构计算来解决隐私计算所面临的算力挑战已经成为当前学术界和工业界的一个热门研究方向。下面以联邦学习FATE 平台为例介绍如何通过异构计算加速隐私计算。联邦学习FATE 平台中的隐私计算算力瓶颈主要以通过Paillier 同态加密算法对数据进行加解密和数据在加密状态下进行计算为主。

06. 可行性分析

在联邦学习的数据加解密及密态计算中，不同数据的计算互不影响，也就是说计算是高度并行的。异构计算正好适合加速能高度并行的计算任务。
联邦学习涉及的计算公式本身不复杂，但重复执行次数巨大，属于重复的轻量级计算。异构计算正好适合加速重复的轻量级计算。
在联邦学习中，数据I/O 时间不到计算时间的0.1%，因此属于计算密集型任务。异构计算很适合加速计算密集型任务。
联邦学习中数据以批量形式产生，并且数据量巨大，满足批量大数据的特征，因此适合使用异构计算来加速。

综合以上四点分析，联邦学习非常适合使用异构计算来进行加速。

07. 异构加速挑战

虽然联邦学习有很多适合异构加速的特点，但也面临以下挑战：

联邦学习计算需要做2048 位大整数运算，但异构芯片不能直接支持大整数运算。
联邦学习计算涉及大量的模幂运算，但异构芯片做模幂运算的代价非常大。
联邦学习计算需要缓存大量的中间计算结果，但由于成本和能耗的限制，异构芯片的存储空间非常有限。

08. 加速方案

（1）基于分治思想做元素级并行。若将N 比特位长的大整数a 和b 分解成高位和低位两部分，则大整数间的加法和乘法运算就可以通过不断递归分解成很多可并行计算的小整数运算。这样，异构计算芯片就能高效地完成大整数的复杂计算。

（2）平方乘算法和蒙哥马利算法组合优化。FATE 平台中使用的Paillier 加密算法和密态下运算都大量使用模幂运算（ $a^{b} \bmod c$ ）。如何通过异构计算高效地计算模幂运算是提高计算效率的核心。首先，可以通过平方乘算法进行计算复杂度优化。平方乘算法主要基于这样一个观察：要计算 $a^{k}$ 的值，并不一定需要将 $a$ 自乘 $k$ 次，而是可以先计算出 $a^{k / 2}$ 的值，然后求平方。通过不断地对结果求平方，只需要 $\log k$ 次的乘法运算就可以得到 $a^{k}$ 的值。根据这种思想，可以将 $b$ 表示为二进制数，然后通过 $\mathcal{O}(N)$ 次乘法及取模运算得到计算结果。平方乘算法的优点是能够将复杂度降低到 $\mathcal{O}(N)$ ，且中间计算结果的大小不超过 $c$ 。缺点是需要做 $2N$ 次取模运算。对GPU 来说，做取模运算的时间代价很高。为了克服这个问题，FATE 引入了蒙哥马利模乘算法来高效地完成模乘计算。蒙哥马利算法的优点是计算模乘的过程中不需要进行取模的运算，从而大大加快取模的运算速度。

（3）中国剩余定理减小中间计算结果。从Paillier 解密计算公式

$m=\frac{L\left(c^{\lambda} \bmod n^{2}\right)}{L\left(g^{\lambda} \bmod n^{2}\right)}, n=p q, L(x)=\frac{x-1}{n}$ 式（1）

中不难发现，式(1) 的最终计算结果长度为N 比特，但是中间计算结果长度为 $2N$ 比特，因此需要2 倍显存进行存储。由于异构计算芯片的存储非常稀缺，因此计算性能受到很大影响。

$m_{p}=\frac{L\left(c^{p-1} \bmod p^{2}\right)}{L\left(g^{p-1} \bmod p^{2}\right)} \bmod p$ 式（3）

$m_{q}=\frac{L\left(c^{q-1} \bmod q^{2}\right)}{L\left(g^{q-1} \bmod q^{2}\right)} \bmod q$ 式（4）

$\left\{\begin{array}{l} x \equiv m_{p}(\bmod p) \\ x \equiv m_{q}(\bmod q) \end{array}\right.$ 式（5）

通过中国剩余定理可以分解解密计算，从而减小中间计算结果。首先，定义 $m_{p}$ 和 $m_{q}$ 两个子项，见式(3) 和式(4) ，并依据它们构造一个满足中国剩余定理的同余方程组，见式(5) 。用 $\mathrm{CRT}\left(m_{p}, m_{q}\right)$ 表示这个同余方程组的解。

可以证明，解密计算公式等价于 $\mathrm{CRT}\left(m_{p}, m_{q}\right) \bmod p q$ ，所以，可以通过计算这个新的表达式来求解 $m$ 的值。观察这三个计算表达式，我们有两个发现：首先，三部分的中间计算结果都不超过 $N$ 比特，因此减小了中间计算结果的规模；其次，计算公式从 $2N$ 比特数的模幂运算简化成N 比特数的模幂运算，计算量大幅度减小。

根据实际实验结果，采用上述三种加速方案的优化后，使用异构加速技术可以将联邦学习的计算效率提升50～70 倍。

网络优化解决数据传输问题

常见的网络优化方案主要包括：升级网络基础设施；传输层协议优化；网络流量调度；搭建专用网络；应用层优化。

01. 升级网络基础设施

通过升级网络硬件设备，可以大幅度提升网络数据传输的效率。对于数据中心网络场景（所有隐私计算的参与方之间的通信都发生在一个服务器集群内部），可以通过升级网络带宽，例如从10Gb/s 网络升级到100Gb/s 网络，来提高网络数据传输的效率。这需要为数据中心采购支持更高带宽的交换机或路由器、网卡和网线。

另外，还可以通过采购支持远程直接数据存取（Remote Direct Memory Access，RDMA）高性能网络技术的网络设备来大幅度降低网络基础延迟，从而减小一轮数据传输需要的时间。对于跨数据中心通信场景，可以通过采购更高带宽的网卡和网线，以及向电信运营商购买更高的网络带宽来提高网络数据传输的效率。

02. 传输层协议优化

为了提高数据传输的性能，研究人员一直致力于设计高效的网络传输层协议。这方面的优化主要分为两类。

第一类是对现在被广泛采用的TCP 进行若干优化，例如：TCP Cubic 用一个cubic 函数替换了TCP 原本的拥塞控制窗口变化增长逻辑，窗口的增长依赖两次丢包的时间，因此窗口的增长独立于RTT，具有RTT 公平性特征；数据中心TCP（Data Center TCP，DCTCP）结合数据中心网络交换机普遍支持显式拥塞通知（Explicit Congestion Notification，ECN）这一特点，根据一个往返延时内发送的数据包被打为ECN 的比例来决定拥塞控制窗口的增减；TCPBBR 利用估算的带宽和延迟直接推测拥塞程度从而计算滑动窗口，而不再像传统TCP 算法那样基于丢包（拥塞）信息反馈来计算滑动窗口。

第二类是设计新的传输层协议取代TCP。例如，谷歌提出的快速UDP 网络连接（Quick UDP Internet Connections，QUIC）协议通过5 个方面的创新设计，包括利用缓存显著减少连接建立时间、改善拥塞控制从内核空间到用户空间、没有head of line 阻塞的多路复用、前向纠错来减少重传和连接平滑迁移等，大幅提升了网络数据传输的性能。

03. 网络流量调度

近年来，网络流量调度已经成为网络领域的热门话题。网络流量调度主要指决定何时以及以多大速率传输网络中的每条数据流，对网络数据传输性能具有十分重要的影响。

通过制定调度目标并设计相应的流量调度算法，能很好地规划数据如何在网络中传输，进而大幅减少网络传输时间。

常见的调度目标包括为计算任务的数据传输提供带宽保障、为计算任务的数据传输提供截止时间保障、最小化所有数据传输任务的平均完成时间、最小化属于同一个计算任务的一组网络流量的整体完成时间、最小化流量传输成本和公平共享带宽等。

常见的调度管理方式主要分为分布式调度、集中式调度和混合式调度。根据不同的通信场景，现有方案又可分为面向数据中心内部的流量调度、面向数据中心间的流量调度和面向个人终端和数据中心间的流量调度。

在调度的粒度方面，主要分为基于流组的调度、基于单条流的调度、基于流切片的调度和基于单个数据包的调度四种。

通过网络流量调度来提升隐私计算数据传输效率的关键是明确通信场景和调度目标，选择合适的调度管理方式和调度粒度，设计有效的调度算法。

04. 搭建专用网络

对于跨数据中心的网络数据传输，可以通过搭建或购买专用网络的办法避免与其他用户的网络流量争抢带宽，从而优化网络数据传输所需要的时间。相比公网传输，专用网络主要具有两大优势：

（1）延迟较小。因为跨数据中心专用网络一般用于跨省数据中心之间的通信，距离远。如果通过公网传输，经过的跳转节点较多，在传输速度上相对延迟较大。例如，北京数据中心到上海数据中心之间的跨地域通信在使用公网传输的延迟最优的情况下可以达到1000ms，但如果换成跨数据中心专线（或叫作长途传输），在速度上就会提升不少，可以把延迟缩短至50ms 以内。

（2）稳定性强。由于异地传输通过公网会受到各种骨干网节点传输的影响，造成极大的不稳定。而建立专用网络以后，能实现两个或多个异地数据中心的直接互通，从而避免单点故障造成的网络不通及丢包，最大限度地保证传输的稳定性，不受公网故障点的影响。

05. 应用层优化

应用层也可以有多种方式进行网络传输优化：

一是DNS 优化，使用HTTPDNS 替代Local DNS。大部分标准DNS 都是基于UDP 与DNS 服务器交互的，HTTP DNS 则是利用HTTP 与DNS 服务器交互，从而绕开了运营商的Local DNS服务，有效防止了域名劫持，并提高域名解析效率。

二是连接重用，避免重复握手。对于需要频繁通信的两台服务器，可以保持长连接，从而避免重新建立网络连接的时间开销。

三是数据压缩与加密，发送与接收的优化可以通过减少传输的数据量实现。

第一种方式是进行数据压缩，目前已经有很多成熟的算法可以对传输数据进行压缩，如Gzip、谷歌的Brotli 和FaceBook 的Z-standard 等。第二种方式是结合应用的特点只传输部分的数据。比如在有些分布式AI 模型训练中，并不需要100%同步不同服务器上的计算数据。在这种情况下，可以选择只传输一部分数据。

实验结果显示，基于以上五种网络优化方案，高性能网络加速技术可以显著强化分布式集群的通信效率，降低网络延迟75%，提升性能200%，极致性能可达至450%，大幅提高隐私计算的数据传输效率。

参考文献：

[1] JING Q, WANG W, ZHANG J, et al. Quantifying the performance of federatedtransfer learning[J]. arXiv preprint, 2019. arXiv:1912.12795.

[2] YANG Z, HU S, CHEN K. Fpga-based hardware accelerator of homomorphic encryption for efficient federated learning[J]. arXiv preprint 2020. arXiv:2007.10560.

[3] ZHANG C, ZHANG J, CHAI D, et al. Aegis: A trusted, automatic and accurate verification framework for vertical federated learning[J]. arXiv preprint, 2021.arXiv:2108.06958.

[4] CHENG X, LU W, HUANG X, et al. Haflo: Gpu-based acceleration for federated logistic regression[J]. arXiv preprint, 2021. arXiv:2107.13797.

本文节选自陈凯和杨强教授新书《隐私计算》，想要了解更所关于隐私计算的内容，欢迎阅读本书！

下单立减50

快快扫码抢购吧！

如果喜欢本文

欢迎在看丨留言丨分享至朋友圈 三连

热文推荐

你还在因为数学对AI望而却步？看看这本秘籍吧！
“工具自由”：一个职业黑客的基本修养
书单 | 轻松掌握数据分析技巧，高效工作，快乐摸鱼！
运维人必知必会的Zabbix核心命令

▼点击阅读原文，了解本书详情~