FPGA加速同态加密矩阵运算优化实践

1. 同态加密与隐私消息检索的技术背景在当今数字通信中端到端加密E2EE虽然能保护消息内容但元数据如发送者和接收者信息仍然面临泄露风险。隐私消息检索OMR系统通过同态加密技术解决了这一痛点允许服务器在不解密的情况下处理加密数据。BFVBrakerski-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 Σ_{i0}^{k-1} diag_i(M) ⊙ Rot_i(v)其中M是N×k的明文矩阵v是加密的长度为k的向量diag_i(M)[j] M[j mod N][(ij) 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处理器我们发现在N2^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相对简单主要优化完全流水线化II1系数级并行PC16时延迟仅0.8ms资源消耗极低每个实例仅1个DSP3.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 (PI1)·d_CCadd PI·d_PCmul d_RotBRAM主要用于Rot中的NTTURAM用于旋转密钥缓冲区和矩阵缓冲区3.4 硬件架构细节整体架构如图4所示关键设计包括旋转核心共享单个Rot核心被Algorithm 1的line3和line10共享大容量存储管理旋转密钥共110MB部分缓存在URAM其余存于HBM2使用双缓冲技术隐藏片外存储器延迟并行PCmul核心PI个独立核心并行工作每个核心有专用矩阵缓冲区每个mj约1280Kb数据流控制密文分limb处理每次一个limb缓存在URAM专用缓冲区管理ctb、ctsum和ctout4. 实现结果与性能分析4.1 实验配置目标平台AMD Alveo U55C加速卡资源9024 DSP、2016 BRAM、960 URAM存储器16GB HBM2目标频率200MHzSophOMR参数环维度n2^16明文模数t786433密文模数Q1140位k50˜g23˜b464.2 最优配置选择通过DSE得到的前4名配置表III显示最佳配置PC16CCadd/PCmul、PB64Rot、PI2所有顶级配置都能并行处理32个系数Rot优化是首要任务因其是主要瓶颈PC16时URAM效率下降此时增加PI更优4.3 资源利用与加速效果实现结果表IV表明总资源使用DSP692076%BRAM153676%URAM65968%各算子延迟CCadd0.8ms加速3.05倍PCmul0.8ms加速19.13倍Rot31.35ms加速6.81倍整体加速单次MatMul2.15秒相比CPU29.8秒13.86倍加速4.4 关键优化技术效果肢体级流水线使Rot中的NTT与模乘并行减少30%延迟双缓冲技术有效隐藏95%的HBM2访问延迟系数并行PC16提升PCmul和CCadd吞吐16倍多实例PCmulPI2平衡资源使用与并行度5. 实际应用考量与扩展方向5.1 部署注意事项密钥管理旋转密钥需分片存储在HBM2和URAM中考虑密钥更新频率对性能的影响温度控制高DSP利用率可能导致局部热点需监控芯片温度必要时动态调整频率批处理优化多个MatMul操作可流水线执行共享公共旋转密钥减少加载开销5.2 性能优化空间Rot进一步优化探索更高效的NTT架构优化Galois自同构实现内存访问优化研究更智能的预取策略尝试压缩旋转密钥参数扩展性支持更大的环维度n适应不同的k值当前固定为505.3 应用场景扩展隐私保护加密货币隐藏交易双方身份保护交易图谱隐私安全多方计算作为基础算子加速复杂协议结合秘密共享提升效率联邦学习安全聚合梯度更新保护参与方数据隐私在AMD Alveo U55C平台上我们的实现证明了FPGA加速同态加密计算的可行性。通过系统级的优化策略和精细的硬件设计为OMR等隐私保护应用提供了实用的加速方案。未来工作将聚焦于Rot模块的深度优化和支持更大规模参数集的扩展性提升。