pdf串连一起(同态加密算力开销如何弥补？港科大提出同态加密算法硬件加速方案)

机器之心专栏

作者:杨，胡水海，陈凯

当前，各行各业的隐私泄露层出不穷，人们对隐私保护的需求与日俱增。随着相关法律法规的逐渐成熟，出现了很多隐私计算技术，联邦学习就是其中的佼佼者。通过组合诸如同态加密、秘密共享、无意传输等安全计算方法。，联邦学习使多个数据持有者在保证数据安全的前提下，合作构建机器学习模型。在联邦学习中使用的各种隐私计算技术中，同态加密的功能和实用性非常重要。

在各行各业，不难想象这样的场景。A公司有大量的数据，但没有人力或计算能力对数据进行分析和处理。因此，A公司想购买B公司的计算服务来处理数据。但是，A公司不希望B公司获得数据的具体信息。所以，如果能将数据加密后传输到B公司进行处理，A公司的所有需求都可以得到满足。所以在这样的场景下，我们需要一个加密系统，对密文进行的一些操作可以等价于对明文进行的操作。

支持密文操作的加密系统统称为同态加密，而同态操作一般是指对密文进行的各种操作。根据密文的运算范围，同态加密算法分为全同态加密、部分同态加密和近似同态加密。一般来说，对同态没有限制的加密算法称为全同态加密，而只支持单一同态运算的加密算法称为部分同态加密。诚然，全同态加密是一种非常理想的算法，需求巨大。然而，目前主流的全同态加密算法计算复杂度高，计算时间长，几乎不可能在生产行业实现。因此，部分同态加密成为了一种更现实的解决方案。Paillier加密是一种广泛使用的部分同态加密算法，它支持密文之间的加法。

虽然与同态加密相比，Paillier加密的计算效率已经相当可观，但是与高效的明文处理相比，Paillier加密系统不可避免地引入了大量的计算开销。在大数据相关产业飞速发展的今天，需要实时处理成千上万的数据，而传统CPU的计算能力已经不能满足需求。

FPGA(Field Programmable Gate Array)全称为现场可编程门阵列，是一种可以根据需要设计和更新底层电路结构的芯片，广泛应用于通信、图像处理等领域。利用FPGA内部逻辑资源构建计算电路，实例化大量计算引擎，可以提高计算并行性，加速指定算法的计算。传统上，FPGA开发是RTL(寄存器传输级)。开发者通过硬件描述语言(Verilog或VHDL)描述具体的硬件功能，控制寄存器读写，规划时序逻辑等等。这种开发模式需要大量的开发经验和较长的硬件开发周期，不适合开发人员经验不足或急需制作的项目开发。因此，HLS(高级综合)的开发受到许多开发者，尤其是研究人员的青睐。HLS是一种代码合成技术。开发人员可以用高级语言(C或C++)描述操作。HLS开发工具包将高级语言编译成Verilog或VHDL代码，然后生成特定的网表。开发人员不需要关心具体硬件电路的设计，只需要构造合理的运算逻辑就可以在短时间内完成一个FPGA项目。

利用HLS开发实现基于FPGA的Paillier加密运算，不仅可以提高运算效率，而且对同态加密和联邦学习的硬件加速探索具有重要意义。

为了实现硬件加速，需要选择合适的算法。基于二进制运算的芯片，包括CPU，可以轻松实现高效的加、乘、位移等运算；但模、除等运算一直是硬件电路的硬骨头，计算效率很低。显然，Paillier加密运算中不可避免地存在模运算和幂运算。众所周知，幂运算由若干乘法组成，而模幂运算

，可以用著名的快速幂算法拆解成几个。

少量的模乘

。

那么，有没有不单独取模就能实现模乘运算的算法呢？答案是肯定的，这个算法就是蒙哥马利模乘算法。

图1:蒙哥马利模乘算法。

蒙哥马利算法的基本思想如图1所示，其中L为M的位宽，K为基数，一般为16、32、64，远小于1024，FPGA可以直接乘以位宽。可以看出，这个算法本质上是一个双环，和普通的大数乘法很像，但是这个算法通过引入参数q保证了中间结果。

能够

整除(被2的整数次幂整除，本质上就是向右移位)，这样通过移位运算就可以无误差地完成除法，同时保证了除法的完成。

移位后获得的最终结果

它必须位于区间[0，2M]内，这样通过一个数值的比较和减法，最终结果可以限制在[0，M]内，幂运算就虚拟完成了。

基于蒙哥马利模乘

，然后意识到

就变成了一个很简单的操作，有很多种实现方式。

系统设计介绍

论文:https://arxiv.org/pdf/2007.10560.pdf

香港科技大学伊辛实验室等研究人员提出了以蒙哥马利模乘为核心的基于FPGA的同态加密加速系统。如图2所示，系统应该部署在云服务器上，云服务器属于联邦学习的参与者。该系统由上位机CPU和FPGA组成，通过PCIe接口相互通信。CPU负责机器学习模型的正常训练，将机器学习中使用的浮点数编码成适合同态加密方案的大整数，并将加密请求发送给FPGA分批。在FPGA中，为Paillier加密设计了高性能处理器，硬件模块封装成一个由CPU调用的OpenCL内核。接下来，我们详细介绍FPGA内部高性能处理器的设计。

图2: FPGA联邦学习加速系统。

Paillier处理器包含所需的运算功能，如模幂运算、随机数生成等。在HLS设计中，实例化了几个并行处理器来实现操作的并行处理。此外，为了管理多处理器的工作，需要顶层模块来执行数据分发和计算结果收集。显然，由于FPGA内部逻辑资源有限，这个系统的运行效率取决于能够实例化多少个Paillier处理器，而Paillier处理器的主要组成部分就是蒙哥马利模乘。因此，如何在硬件上优化Montgomery模乘成为了主要的工作。我们从资源分配和时间序列分析两个方面介绍优化工作。

资源分配

在一个以计算功能为主的FPGA工程设计中，DSP、LUT和RAM是最底层的逻辑资源，总量最有限，最需要精心规划和使用。DSP是FPGA中实现乘法运算不可或缺的底层逻辑资源。目前主流FPGA中的单个DSP模块可以在高时钟频率下实现两个16位无符号整数之间的乘法，通过串联多个DSP模块，可以构建位宽更高的乘法器。例如，需要16个DSP来实现两个64位无符号整数之间的乘法。LUT是FPGA中最基本的逻辑资源。我们需要结合LUT等逻辑资源来构建加法器、整数比较、有限状态机等其他逻辑电路。RAM是集成在FPGA底层的高速存储器，分为BRAM和URAM。一般来说，单个RAM可以存储36Kb的数据，而单个URAM可以存储288Kb的数据。在当前项目中，RAM可用于存储输入输出数据和中间运算结果。

如图1所示，蒙哥马利模乘算法由内环和外环组成。我们将单个内部循环操作打包成一个处理单元，如图3所示。每个处理单元包含两个乘法器，分别用于计算x*y和q*m，以及两个乘法结果和外循环最后的计算结果。

和进位(未示出)来执行加法运算。同时，为了避免HLS编译代码扩展后乘法器资源的巨大膨胀，需要使用分配指令将处理单元的数量限制为一个。

图3:算法1的内部循环处理单元。

图4: Karatsuba快速乘法。

在处理单元的设计中，同时采用了Karatsuba算法，如图4所示。根据乘法原理，很容易看出，如果乘法操作数的位宽减半，总的计算时间将减少到原来的四分之一左右。Karatsuba算法将整数乘法拆分为三个位宽只有原来一半的整数乘法，节省了计算时间。根据该算法的原理，可以利用DSP资源实例化所需的乘法器。

在RAM的使用方面，不难注意到，大部分用于加密的输入数据都是用浮点数编码的，与大整数位宽相比，有效位数很少。因此，输入数据可以存储为稀疏向量，即只记录非零元素及其索引，减少了存储占用。

时间序列分析

时序分析在FPGA开发中的重要性不亚于算法的优化和逻辑资源的分配。从电路角度来说，如果没有合理的逻辑设计和资源布局，不仅会使信号传输时间过长，还会导致多组信号争夺同一硬件资源的问题，造成局部堵塞。

一般来说，开发者能够控制的最小粒度的FPGA的工作时间是一个时钟周期，FPGA完成一个时钟周期所需的时间由时钟频率决定，即

因此，在减少时钟周期数的同时提高时钟频率是提高FPGA性能的有效手段。

一般来说，实现一组算法所需的时钟周期数是由其关键路径决定的，关键路径是工作流中延时最大的路径。通过观察蒙哥马利模乘的双循环，我们可以整理出整个运算包括

乘法，因此，如果我们实例化n个乘法器，每个需要运行t个时钟周期，那么理想情况下整个蒙哥马利模乘

时钟周期为

。考虑到前面描述的内循环处理单元中的两个乘法可以并行执行，我们可以实例化两个乘法器来同时计算。但是，由于不同循环之间的数据依赖性，循环只能串行执行。

因此，系统设计的目标是使总时钟周期接近。

。为了实现这一目标，系统进行了以下三方面的优化。

图5:蒙哥马利模乘流水线处理示意图。

通过以上处理，不同迭代的操作最大程度的重叠。考虑到完成外循环需要多次迭代，可以近似认为完成整个蒙哥马利模乘运算所需的时钟周期约为

。

在达到时钟周期的设计目标后，我们还希望提高FPGA逻辑电路的时钟频率。虽然主流FPGA中DSP器件的工作频率可以达到400MHz以上，但是由于硬件资源的限制，考虑到系统中逻辑电路的复杂性，要将整个系统的工作频率提高到这个数值几乎是不可能的。为了尽可能提高工作频率，本系统的设计做了如下优化:

系统性能测试

硬件设计完成后，通过使用OpenCL API，上位机可以调用FPGA实现硬件加速运算。我们使用FPGA硬件加速内核分别构造Paillier加解密算子，并与CPU的运算性能进行比较，其中CPU运算是通过调用Paillier运算库PHE实现的。比较结果如图6和7所示。当公钥位宽为1024位时，FPGA加速系统在加密和解密操作中分别实现了10.62倍和2.76倍的加速比。

图FPGA和CPU的加密性能对比。

图FPGA和CPU的解密性能对比。

FPGA硬件加速集成到主流联邦学习框架FATE之后，我们也看到了不错的性能提升。我们使用PyOpenCL API将FPGA硬件加速功能集成到单个模块中，并嵌入到FATE中执行加密操作。分别执行十次逻辑回归迭代和十次线性回归迭代后，我们得到如图8所示的测试结果:FPGA加速FATE将原FATE的加密时间减少了71.2%。

图FPGA加速FATE和原始FATE在单次训练迭代中的加密时间比较。

总结和展望

同态加密是一种强有力的隐私保护技术，对它的探索是近年来的研究热点。FPGA是一种资源丰富的计算芯片，可以显著提高高并行计算任务的性能。对于追求高性能的FPGA工程来说，现阶段仍然难以摆脱长期的RTL发展。利用HLS快速开发基于FPGA的同态加密项目，是对FPGA在隐私安全计算行业中角色定位的有效探索和尝试。近年来，FPGA主流供应商Xilinx和Intel不断加大对可编程硬件高级语言开发的投入，FPGA入门难度逐渐降低。相信随着数据安全的日益重要，行业内会涌现出更多基于FPGA的安全计算产品，类似HLS的硬件上层开发模式也会逐渐在该领域占据一片天地。

作者是香港科技大学iSing实验室的杨、胡水海和陈凯。ISing Lab是一个专注于高性能数据中心网络、机器学习系统和联邦学习框架研究的实验室。在过去的五年中，实验室将在网络系统领域的顶级会议ACM SIGCOMM和USENIX NSDI发表10篇论文，根据计算机科学CSRankings的排名，这些会议在亚洲排名第一。