1. 项目概述FPGA加速同态矩阵向量乘法的技术背景同态加密Homomorphic Encryption, HE作为密码学领域的重大突破允许在加密数据上直接执行计算而无需解密。这项技术从根本上改变了传统隐私计算的范式使得数据在处理过程中始终保持加密状态。在隐私消息检索Oblivious Message Retrieval, OMR场景中HE使得服务器能够在不解密用户消息的情况下帮助用户筛选出相关消息同时保护了通信双方的元数据隐私。然而HE的计算开销一直是制约其实际应用的主要瓶颈。以BFVBrakerski-Fan-Vercauteren方案为例其核心运算涉及大规模多项式环上的模乘和模加操作这些操作在通用处理器CPU上的执行效率极低。特别是当处理矩阵向量乘法MatMul这类基础线性代数运算时性能问题尤为突出。FPGA现场可编程门阵列因其可重构特性和并行计算能力成为加速HE运算的理想平台。与CPU相比FPGA可以实现指令级并行同时执行多个同态运算操作数据级并行对多项式系数进行批量处理流水线设计隐藏运算延迟提高吞吐量本项目的核心创新点在于针对OMR中的关键MatMul运算提出了一套完整的FPGA加速方案通过多层次并行化设计和自动化设计空间探索Design Space Exploration, DSE实现了13.86倍的性能提升。2. 同态加密基础与矩阵向量乘法原理2.1 BFV同态加密方案解析BFV方案作为目前最主流的全同态加密方案之一其数学基础建立在环学习有误RLWE难题之上。方案的核心参数包括环维度n决定安全性和计算复杂度的关键参数通常取2的幂次明文模数t限定明文数据的取值范围密文模数Q一个大整数通常分解为多个小素数的乘积RNS表示BFV的核心运算流程包括密钥生成# 伪代码示例BFV密钥生成 def key_generation(n, q, t): secret_key sample_from_error_distribution(n) public_key (a, b) # 其中b [-(a*s e)]_q evaluation_keys generate_galois_keys(secret_key) return (secret_key, public_key, evaluation_keys)加密/解密加密将明文多项式m编码为环元素添加噪声后生成密文(ct0, ct1)解密计算[ct0 ct1s]_q ≈ mt (mod q)同态运算加法CCadd简单对应系数相加明文-密文乘法PCmul明文多项式与密文多项式的逐系数乘法旋转Rot通过Galois自同构实现密文slot的循环移位2.2 矩阵向量乘法的同态实现在OMR的Detect阶段核心计算可以抽象为M·v Σ_{i0}^{k-1} diag_i(M) ⊙ Rot^i(v)其中M是N×k的明文矩阵v是长度为k的密文向量diag_i(M)表示矩阵M的第i条对角线⊙表示明文-密文点乘。SophOMR采用的优化算法Algorithm 1通过baby-step giant-step技巧将旋转次数从k减少到√k级别。该算法的主要计算瓶颈在于PCmul操作占总计算时间的50%以上Rot操作虽然数量较少但单次执行时间较长关键观察在FPGA实现中PCmul具有极高的并行潜力而Rot则需要特殊的优化策略。3. FPGA加速架构设计3.1 整体硬件架构基于Alveo U55C FPGA平台的加速器设计采用分层结构图示简化版硬件架构包含Rot核心、多个PCmul核心和数据通路主要功能单元包括旋转核心Rot Core集成KeySwitch模块采用limb-based流水线设计配置64个并行NTT蝶形单元PB64并行乘法核心PCmul Cores16个并行实例PI16每个实例处理16个系数PC16采用完全流水线设计II1数据通路基于URAM的双缓冲设计矩阵数据分布式存储使用AXI4接口连接HBM2内存3.2 关键优化技术3.2.1 多层次并行设计系数级并行PC// HLS代码示例PCmul核心的系数并行处理 #pragma HLS PIPELINE II1 for(int i0; iCOEFF_NUM/PC; i) { #pragma HLS UNROLL for(int j0; jPC; j) { res_coeff[i*PCj] mul_mod(p_coeff[i*PCj], c_coeff[i*PCj]); } }操作级并行PI同时运行16个PCmul核心通过加法树adder tree合并部分结果NTT蝶形单元并行PB采用autoNTT库的优化实现配置64个并行蝶形单元3.2.2 内存子系统优化旋转键存储方案原始旋转键大小55MB × 2 110MBFPGA片上存储URAM共270MB采用滑动窗口策略动态加载所需键片段矩阵数据分布// 矩阵存储分布示例 module matrix_buffer #(PI16) ( input logic [PI-1:0] sel, output logic [127:0] data [PI-1:0] ); // 每个PCmul核心对应独立的BRAM存储体 for(genvar i0; iPI; i) begin bram #(.WIDTH(128), .DEPTH(1024)) bram_inst (.addr(sel[i]), .data(data[i])); end endmodule双缓冲设计使用URAM实现ping-pong缓冲隐藏DDR/HBM访问延迟3.3 设计空间探索策略DSE流程采用多目标优化方法权衡延迟和资源利用率参数空间定义参数类型影响范围候选值PC所有算子2,4,8,16PBRot核心16,32,64PIPCmul实例数1,2,4,8,16成本模型延迟模型公式(5)(6)资源模型def estimate_dsp_usage(PC, PI, PB): dsp_pcmul 897 * PI dsp_rot 5123 * (64/PB) return dsp_pcmul dsp_rot (PI2)*16探索结果配置PCPIPB延迟(ms)DSP利用率最优161664215076%次优16864217072%4. 实现细节与性能分析4.1 硬件实现结果基于Vitis HLS 2024.1的实现指标模块DSP用量BRAMURAM延迟(ms)加速比CCadd1000.803.05×PCmul897000.8019.13×Rot5123153631331.356.81×总计69201536659215013.86×4.2 性能瓶颈分析Rot核心限制因素KeySwitch占Rot时间的85%NTT运算占KeySwitch时间的70%内存带宽影响矩阵数据带宽需求1.28GB/sHBM2实际带宽460GB/s利用率仅0.28%资源平衡pie title FPGA资源分配 Rot核心 : 65 PCmul核心 : 30 其他 : 54.3 对比实验与CPU实现Intel Xeon W-2295的对比指标CPUFPGA加速比单次MatMul29.8s2.15s13.86×功耗105W38W2.76×能效提升吞吐量0.03 ops/s0.47 ops/s15.67×5. 工程实践中的挑战与解决方案5.1 HLS实现挑战复数控制流处理原始SEAL代码包含大量条件分支解决方案使用#pragma HLS LOOP_FLATTEN合并嵌套循环大整数运算优化// Barrett约减优化实现 inline uint64_t barrett_reduce(uint64_t a, uint64_t q, uint64_t mu) { #pragma HLS INLINE uint64_t hi ((__uint128_t)a * mu) 64; return a - hi * q; }5.2 精度保障措施RNS一致性检查在每个limb处理完成后添加CRC校验发现错误时触发流水线刷新边界条件处理预计算特殊系数处理表使用ROM存储异常处理规则5.3 实际部署经验散热考虑通过Vivado功耗分析确定热点区域在Rot核心周围添加散热约束时序收敛技巧对NTT关键路径使用register_duplication设置多周期路径约束6. 应用前景与扩展方向6.1 在隐私计算中的应用隐私保护通信消息检索延迟从分钟级降至秒级支持同时处理多个接收者的请求区块链增强实现交易内容的隐私保护验证典型应用保密交易金额的UTXO验证6.2 未来优化方向Rot核心架构改进采用混合基NTT算法探索近似计算的可能性系统级优化与GPU组成异构计算系统研究流水线化的多MatMul并行算法-硬件协同设计定制化HE参数选择基于硬件特性的算法变形在实际部署中我们发现当N增加到2^18时现有架构的URAM容量成为瓶颈。一个可行的解决方案是采用矩阵分块策略将大矩阵分解为适合FPGA处理的子块。同时通过重叠计算和数据传输可以进一步隐藏内存访问延迟。