FPGA加速同态加密矩阵运算优化实践
1. 同态加密与隐私消息检索的技术背景
在当今数字通信中，端到端加密（E2EE）虽然能保护消息内容，但元数据（如发送者和接收者信息）仍然面临泄露风险。隐私消息检索（OMR）系统通过同态加密技术解决了这一痛点，允许服务器在不解密的情况下处理加密数据。BFV（Brakerski-Fan-Vercauteren）方案作为主流同态加密方案之一，支持在加密数据上直接进行加法和乘法运算。
同态加密的核心数学基础是环学习有误问题（RLWE），它将明文编码为多项式环Zt[X]/(X^n +1)中的元素，其中t是明文模数，n是环维度。加密过程使用公钥将明文多项式转换为两个大系数多项式（密文），这些系数模一个非常大的数Q（通常数百或数千位）。为了高效处理如此大的数，实际实现中采用余数系统（RNS），将Q分解为多个小素数的乘积，使各系数能独立并行处理。
在OMR系统中，接收者将加密的检测密钥提交给服务器（检测器），服务器使用同态操作扫描公告板上的所有消息，找出与接收者相关的少量消息。这一过程涉及两个关键阶段：1）同态检测（Detect），通过矩阵向量乘法标记相关消息；2）同态压缩（Comp），将结果压缩为紧凑的摘要。整个过程服务器无法获知哪些消息真正与接收者相关。
2. 矩阵向量乘法的算法优化与瓶颈分析
2.1 SophOMR中的矩阵向量乘法算法
在SophOMR方案中，同态矩阵向量乘法（MatMul）是Detect阶段的核心操作，其数学表达式为： Mv = Σ_{i=0}^{k-1} diag_i(M) ⊙ Rot_i(v)
其中M是N×k的明文矩阵，v是加密的长度为k的向量，diag_i(M)[j] = M[j mod N][(i+j) mod k]，⊙表示明文与密文的乘法，Rot_i表示密文旋转i个位置。
直接实现需要k次旋转操作，计算开销巨大。SophOMR采用"baby-step giant-step"优化技术，将k分解为˜g·˜b，将旋转次数从k降低到˜g+˜b（仅需两个旋转密钥）。优化后的算法如Algorithm 1所示，分为两个嵌套循环：内循环（˜b步）处理小步旋转和乘法累加，外循环（˜g步）处理大步旋转和结果合并。
2.2 性能瓶颈的量化分析
通过CPU性能剖析（Intel Xeon W-2295处理器），我们发现：
- 在N=2^16的消息规模下，Detect阶段中affine变换（含MatMul）耗时是range check的1.5倍
- MatMul操作中，PCmul（明文-密文乘）占50%以上时间，Rot（旋转）占30%以上
- 单次Rot操作耗时是PCmul的3-4倍，但PCmul总次数更多
这表明加速MatMul需要：1）优化Rot操作本身；2）并行化大量PCmul操作。FPGA的并行计算能力和定制化硬件设计恰好能针对这两点进行优化。
3. FPGA加速器设计与实现
3.1 整体设计流程
我们的FPGA加速器设计采用高层次综合（HLS）方法，主要流程包括：
- 从Microsoft SEAL库提取核心函数并重构为HLS兼容代码
- 为每个同态算子（CCadd、PCmul、Rot）实现多版本设计
- 基于合成结果建立延迟和资源成本模型
- 设计空间探索（DSE）寻找最优参数配置
- 生成最终MatMul加速器硬件
3.2 关键算子优化
3.2.1 旋转操作(Rot)优化
Rot操作包含ApplyGalois和KeySwitch两步，其中KeySwitch占主要耗时，涉及：
- 大数模乘（使用旋转密钥）
- 数论变换（NTT）
我们采用以下优化技术：
- 肢体级流水线：将NTT与模乘并行执行
- NTT加速：使用多个蝶形单元（BU）并行，BU数量PB作为关键设计参数
- 系数级并行：每个时钟周期处理PC个系数
使用开源的autoNTT库（迭代架构+Barrett约减版本）实现高效NTT。
3.2.2 明文-密文乘(PCmul)优化
PCmul的优化策略包括：
- HLS PIPELINE指令：设置启动间隔(II)为1，最大化吞吐
- 系数级并行：每个周期处理PC个系数
- 多实例并行：部署PI个独立PCmul核心
每个PCmul核心需要897个DSP切片，但无需BRAM/URAM资源。
3.2.3 密文加(CCadd)优化
CCadd相对简单，主要优化：
- 完全流水线化（II=1）
- 系数级并行（PC=16时延迟仅0.8ms）
- 资源消耗极低（每个实例仅1个DSP）
3.3 设计空间探索策略
我们定义了三个层次的并行参数：
- 系数级(PC)：控制每个算子内部处理的系数并行度
- NTT BU级(PB)：控制Rot中NTT的并行度
- 实例级(PI)：控制并行PCmul核心数量
基于合成结果建立精确的成本模型，快速评估不同配置下的性能和资源使用，避免为每个配置都运行耗时的HLS合成。
3.3.1 延迟模型
单次外循环迭代延迟： IL' = max{˜b/PI·L'_M + L'_A, L'_R} + L'_A
总MatMul延迟： TL' = (˜b-1)·L'_R + ˜g·IL'
其中L'_M、L'_A、L'_R是通过HLS合成获得的各算子延迟。
3.3.2 资源模型
重点关注有限资源：
- DSP总量：D = (PI+1)·d_CCadd + PI·d_PCmul + d_Rot
- BRAM：主要用于Rot中的NTT
- URAM：用于旋转密钥缓冲区和矩阵缓冲区
3.4 硬件架构细节
整体架构如图4所示，关键设计包括：
- 旋转核心共享：单个Rot核心被Algorithm 1的line3和line10共享
- 大容量存储管理：
- 旋转密钥（共110MB）部分缓存在URAM，其余存于HBM2
- 使用双缓冲技术隐藏片外存储器延迟
- 并行PCmul核心：
- PI个独立核心并行工作
- 每个核心有专用矩阵缓冲区（每个mj约1280Kb）
- 数据流控制：
- 密文分limb处理，每次一个limb缓存在URAM
- 专用缓冲区管理ctb、ctsum和ctout
4. 实现结果与性能分析
4.1 实验配置
目标平台：AMD Alveo U55C加速卡
- 资源：9024 DSP、2016 BRAM、960 URAM
- 存储器：16GB HBM2
- 目标频率：200MHz
SophOMR参数：
- 环维度n=2^16
- 明文模数t=786433
- 密文模数Q（1140位）
- k=50（˜g=23，˜b=46）
4.2 最优配置选择
通过DSE得到的前4名配置（表III）显示：
- 最佳配置：PC=16（CCadd/PCmul）、PB=64（Rot）、PI=2
- 所有顶级配置都能并行处理32个系数
- Rot优化是首要任务，因其是主要瓶颈
- PC>16时URAM效率下降，此时增加PI更优
4.3 资源利用与加速效果
实现结果（表IV）表明：
- 总资源使用：
- DSP：6920（76%）
- BRAM：1536（76%）
- URAM：659（68%）
- 各算子延迟：
- CCadd：0.8ms（加速3.05倍）
- PCmul：0.8ms（加速19.13倍）
- Rot：31.35ms（加速6.81倍）
- 整体加速：
- 单次MatMul：2.15秒
- 相比CPU（29.8秒）：13.86倍加速
4.4 关键优化技术效果
- 肢体级流水线：使Rot中的NTT与模乘并行，减少30%延迟
- 双缓冲技术：有效隐藏95%的HBM2访问延迟
- 系数并行（PC=16）：提升PCmul和CCadd吞吐16倍
- 多实例PCmul（PI=2）：平衡资源使用与并行度
5. 实际应用考量与扩展方向
5.1 部署注意事项
- 密钥管理：
- 旋转密钥需分片存储在HBM2和URAM中
- 考虑密钥更新频率对性能的影响
- 温度控制：
- 高DSP利用率可能导致局部热点
- 需监控芯片温度，必要时动态调整频率
- 批处理优化：
- 多个MatMul操作可流水线执行
- 共享公共旋转密钥减少加载开销
5.2 性能优化空间
- Rot进一步优化：
- 探索更高效的NTT架构
- 优化Galois自同构实现
- 内存访问优化：
- 研究更智能的预取策略
- 尝试压缩旋转密钥
- 参数扩展性：
- 支持更大的环维度n
- 适应不同的k值（当前固定为50）
5.3 应用场景扩展
- 隐私保护加密货币：
- 隐藏交易双方身份
- 保护交易图谱隐私
- 安全多方计算：
- 作为基础算子加速复杂协议
- 结合秘密共享提升效率
- 联邦学习：
- 安全聚合梯度更新
- 保护参与方数据隐私
在AMD Alveo U55C平台上，我们的实现证明了FPGA加速同态加密计算的可行性。通过系统级的优化策略和精细的硬件设计，为OMR等隐私保护应用提供了实用的加速方案。未来工作将聚焦于Rot模块的深度优化和支持更大规模参数集的扩展性提升。