同态加密算力开销如何弥补？港科大提出同态加密算法硬件加速方案( 二 ) 机器之心专栏作者：杨照雄、

文章图片
，可以由大名鼎鼎的快速幂算法拆解为若干
少量的模乘运算

文章图片
。
那么是否存在一种算法，无需单独取模，就可以实现模乘运算呢？答案是肯定的，这个算法就是蒙哥马利模乘算法。

文章图片
图一：蒙哥马利模乘算法。
蒙哥马利算法的基本思想如图一所示，其中l为M的位宽， k为基数，一般为16、32、64这样远小于1024 ，且FPGA可以直接进行乘法运算的位宽。可以看到，这个算法本质上是一个二重循环，和普通的大数乘法十分相似，但是该算法通过引入参数q ，保证中间结果

文章图片
可以被

文章图片
整除（被2的整数次幂除本质上就是向右移位），从而可以无误差地通过移位操作完成除法，同时保证，完成了
移位之后得到的最终结果

文章图片
一定位于区间[0,2M），从而可以通过一次数值比较和减法，将最终结果限制在[0,M），无形中完成了幂运算。
基于蒙哥马利模乘运算

文章图片
，再实现

文章图片
就成为了非常简单的操作，实现的方法也有很多。
系统设计介绍

文章图片
论文链接：https://arxiv.org/pdf/2007.10560.pdf
来自港科大iSingLab等机构的研究者以蒙哥马利模乘运算为核心，提出了一套基于FPGA的同态加密加速体系，如图二所示，该系统被设想为部署在云服务器端，这些服务器属于联邦学习的参与方。该系统包括上位机CPU以及FPGA ，二者使用PCIe接口通信。 CPU负责机器学习模型的正常训练工作，并将机器学习使用的浮点数编码为适配同态加密方案的大整数，同时它将加密请求分批发送给FPGA；FPGA中为Paillier加密设计了高性能处理器，且硬件模块被封装为OpenCL内核由CPU进行调用。接下来，我们对FPGA内部高性能处理器的设计进行详细介绍。

文章图片
图二：FPGA联邦学习加速系统。
一个Paillier处理器中包含了模幂、随机数生成等所需的运算功能，此HLS设计中例化了若干Paillier处理器以实现运算的并行处理。此外，为了管理多处理器的工作，需要顶部模块执行数据分发以及计算结果收集的工作。显然，由于FPGA内部逻辑资源有限，此系统的运算效率取决于可以例化多少Paillier处理器，而Paillier处理器的主要组成部分是蒙哥马利模乘。因此，如何在硬件上优化蒙哥马利模乘运算成为了主要工作。我们从资源分配和时序分析两个方面对优化工作进行介绍。
资源分配
对于一个以计算功能为主的FPGA工程设计中， DSP、LUT和RAM是总量最有限、最需要仔细规划使用的底层逻辑资源。 DSP是FPGA内部实现乘法运算不可缺少的底层逻辑资源，目前主流FPGA中的单个DSP块，可以在高时钟频率下实现两个16比特无符号整数之间的乘法运算，而通过串联多个DSP块，可以搭建出位宽更高的乘法器，比如，实现两个64比特无符号整数之间的乘法运算需要16个DSP；LUT（lookuptable查找表）是FPGA内部最基本的逻辑资源，我们需要结合LUT和其他逻辑资源构建加法器、整数比较、有限状态机等其他逻辑电路；RAM是FPGA底层集成的高速存储器，分为BRAM和URAM两类，一般来说，单个RAM可以存储36Kb数据，而单个URAM可存储288Kb数据，在当前工程中，可以使用RAM存放输入输出数据以及运算中间结果。