同态加密中多输入密文乘法的优化技术与硬件实现
1. 同态加密与密文乘法基础
同态加密（Homomorphic Encryption, HE）技术允许在加密数据上直接进行计算操作，而无需事先解密。这项技术为云计算、医疗数据分析等需要隐私保护的场景提供了革命性的解决方案。在众多同态加密方案中，RNS-CKKS（Residue Number System-Cheon-Kim-Kim-Song）因其支持浮点数近似计算和相对较高的效率，成为当前最实用的方案之一。
密文乘法是RNS-CKKS中最核心也是最耗时的操作。与传统加密方案不同，同态加密中的密文乘法涉及多项式环上的复杂运算，主要包括三个关键步骤：
- 多项式乘法（Polynomial Multiplication, PM）
- 重线性化（Relinearization）
- 重缩放（Rescaling, RS）
在硬件实现层面，这些操作通常基于数论变换（Number Theoretic Transform, NTT）来加速。NTT是有限域上的快速傅里叶变换，能够将多项式乘法的时间复杂度从O(n²)降低到O(n log n)。然而，即使采用NTT加速，密文乘法仍然是整个系统中的性能瓶颈。
提示：在RNS-CKKS方案中，每个密文实际上由两个多项式组成（通常记为ct = (c0, c1)），且这些多项式系数采用余数系统（RNS）表示，即将大整数分解为多个小整数的模运算，便于硬件并行处理。
2. 多输入密文乘法的核心挑战
2.1 噪声增长与乘法深度
同态加密的核心挑战在于密文运算过程中噪声的快速增长。每次密文乘法操作都会导致噪声呈指数级增长，而噪声一旦超过特定阈值就会使解密失败。重缩放操作虽然可以降低噪声规模，但同时也会减少密文的"计算容量"（即剩余可进行的乘法次数）。
对于n个密文的连续乘法，传统的二叉树结构需要⌈log₂n⌉次乘法深度。例如：
- 4输入：乘法深度2（(a×b)×(c×d)）
- 5输入：乘法深度3（((a×b)×c)×(d×e)）
乘法深度直接影响噪声增长速度和最终可支持的计算复杂度，因此需要精心设计计算路径。
2.2 重线性化的计算开销
重线性化是密文乘法后的必要步骤，用于将乘法结果的三项式密文（ct = (c0,c1,c2)）转换回标准的两项式形式（ct' = (c0',c1')）。这个过程涉及：
- 对c2进行分解和模切换
- 与评估密钥（Evaluation Key）的乘积累加
- 结果校正
在硬件实现中，重线性化需要大量NTT/INTT（逆NTT）转换和模乘操作，通常占总计算量的40%以上。
2.3 重缩放操作的瓶颈
重缩放用于控制噪声增长，但本身也是计算密集型操作。在传统实现中，每个重缩放单元包含：
- 系数缩放（乘以Δ⁻¹）
- 模切换（q → q'）
- 噪声校正
对于n输入乘法，可能需要多达O(n)次重缩放操作。更糟糕的是，这些操作通常无法并行，导致严重的流水线停顿。
3. 多输入乘法优化技术
3.1 动态输入分组策略
本文提出的核心创新之一是动态输入分组方法。不同于传统的固定二叉树结构，我们根据输入数量智能选择最优分组策略，在保证乘法深度不变的前提下最小化重缩放次数。
3.1.1 分组原则
对于n个输入，将其划分为m组(n₁,n₂,...,nₘ)，满足：
- n₁ + n₂ + ... + nₘ = n
- 每组乘法深度 ≤ ⌈log₂n⌉ - (m-1)
- 优先合并小规模组（减少后续重缩放）
以6输入为例，两种分组方式对比：
| 分组策略 | 乘法深度 | 总重缩放次数 | 可合并RS |
|---|---|---|---|
| (2,2,2) | 3 | 8 | 是 |
| (3,3) | 3 | 6 | 是 |
| (5,1) | 4 | 10 | 否 |
3.1.2 硬件友好分组
在硬件实现中，我们倾向于选择：
- 组内元素数量为2或3（对应优化后的乘法器单元）
- 组间元素数量平衡（减少关键路径延迟）
- 最大化可合并的重缩放操作
表1展示了不同输入规模下的最优分组策略：
表1. 3-12输入最优分组策略与性能对比
| 输入数n | 最优分组 | 传统RS次数 | 优化后RS次数 | 降低比例 |
|---|---|---|---|---|
| 3 | (1,1,1) | 3 | 0+2 | 33% |
| 4 | (2,2) | 6+2 | 6+2 | 0% |
| 5 | (2,2,1) | 11+2 | 6+2 | 45% |
| 6 | (3,3) | 14+2 | 8+2 | 43% |
| 7 | (4,3) | (2,2) | 18+2 | 15+2 |
| 8 | (4,4) | (2,2) | 22+2 | 22+2 |
| 9 | (3,3,3) | 31+2 | 12+2 | 61% |
| 10 | (3,3,4) | (2,2) | 34+2 | 19+2 |
注意：当n是2的幂次时（如4,8），传统二叉树已是最优结构，优化空间有限。但对于其他情况，特别是n=2^k+1时，优化效果最为显著。
3.2 组合重缩放技术
3.2.1 基本思想
传统实现中，μ次连续重缩放需要：
- 1次INTT（转换到系数域）
- μ次独立缩放和模切换
- 1次NTT（转换回NTT域）
我们提出的组合重缩放（Combined μ-RS）通过数学重构，将μ次操作合并为：
- 在NTT域内直接进行多项式系数调整
- 共享中间计算步骤
- 仅需1次INTT和1次NTT，无论μ值大小
3.2.2 硬件架构优化
组合重缩放的硬件实现关键点：
- 并行处理单元：支持同时处理多个模数通道
- 共享预处理电路：统一计算公共子表达式
- 流水线重组：消除传统架构中的数据依赖
图1展示了传统与组合重缩放的数据流对比：
传统μ-RS： NTT域 → INTT → RS₁ → RS₂ → ... → RSₙ → NTT → 输出 组合μ-RS： NTT域 → 组合处理单元 → NTT → 输出3.2.3 性能分析
对于L层模数和μ次重缩放组合：
- (I)NTT操作：从2L-1减少到L
- 模乘操作：从μL增加到(μ+1)L-μ(μ+3)/2
- 内存访问：减少约30-40%
由于NTT是主要性能瓶颈，这种交换带来显著加速。实测在Xilinx UltraScale+ FPGA上，4-RS组合单元比串联实现快2.8倍。
3.3 改进的重线性化流程
3.3.1 传统流程瓶颈
标准重线性化需要：
- 分解c₂为多个小多项式
- 对每个分段进行模切换
- 与评估密钥相乘后累加
这导致：
- 2L次NTT（L为模数层数）
- 大量中间结果存储
- 长关键路径（约4NTT延迟）
3.3.2 优化方案
我们提出两项关键改进：
- 共享模切换：在分解前统一进行模切换，减少NTT次数
- 流水线重组：将逐段处理改为批处理，增加并行度
改进后的数据流：
输入c₂ → 统一模切换 → 分解 → 并行NTT → 批量乘加 → INTT → 输出3.3.3 硬件实现
优化后的重线性化单元包含：
- 2个并行NTT核
- 共享的模切换预处理单元
- 交叉开关连接的乘加阵列
在GlobalFoundries 22nm工艺下，改进设计实现：
- 面积减少15%（从0.42mm²降至0.36mm²）
- 延迟降低50%（从0.66ms降至0.33ms）
- 功耗降低22%（从98mW降至76mW）
4. 硬件架构设计与实现
4.1 整体架构
多输入密文乘法器的顶层架构如图2所示，包含以下关键模块：
输入缓冲 → 动态分组控制器 → 并行乘法阵列 → 重线性化单元 → 组合重缩放单元 → 输出缓冲4.1.1 动态分组控制器
功能特性：
- 实时分析输入数量（3-12个）
- 根据预存策略表选择最优分组
- 动态调整数据路由路径
硬件成本：
- 约5k等效门
- 2周期决策延迟
- 支持运行时策略更新
4.1.2 并行乘法阵列
核心参数：
- 4个并行NTT核（支持同时处理2组乘法）
- 可配置为2×2或3×1模式
- 128-bit宽数据通路
关键优化：
- 时分复用NTT核
- 交叉开关连接
- 流水线平衡寄存器
4.2 关键子模块设计
4.2.1 可配置NTT核
采用改进的Radix-2^2架构：
- 支持N=2^16点变换
- 5级流水线
- 双端口SRAM存储旋转因子
性能指标：
- 频率：450MHz@22nm
- 延迟：1.1μs/NTT
- 面积：0.15mm²
4.2.2 组合重缩放单元
创新设计：
- 多模数并行处理通道
- 共享的预计算模块
- 可配置μ值（1-4）
资源利用率：
- 16个64-bit Barrett乘法器
- 8个模加器链
- 12KB SRAM缓冲
4.2.3 评估密钥管理
专用存储架构：
- 2个独立的评估密钥存储区
- 128-bit宽DMA接口
- 智能预取机制
存储优化：
- 压缩格式（节省30%空间）
- 动态加载活跃部分
- 错误校正编码
4.3 性能评估
4.3.1 实验设置
- 工艺：GlobalFoundries 22FDX
- 设计参数：L=24, K=24, N=2^16
- 基准：传统二叉树结构乘法器
4.3.2 结果分析
表2展示了3-12输入场景下的性能对比：
表2. 硬件实现性能对比（22nm工艺）
| 输入数n | 面积(mm²) | 延迟(ms) | 功耗(mW) | 面积节省 | 延迟降低 |
|---|---|---|---|---|---|
| 3 | 0.33 | 0.33 | 76 | 15% | 50% |
| 4 | 0.45 | 0.39 | 102 | 12% | 25% |
| 5 | 0.51 | 0.40 | 118 | 27% | 50% |
| 6 | 0.58 | 0.40 | 135 | 31% | 50% |
| 7 | 0.72 | 0.52 | 168 | 19% | 33% |
| 8 | 0.86 | 0.53 | 201 | 8% | 33% |
| 9 | 0.81 | 0.40 | 189 | 42% | 62% |
| 10 | 0.95 | 0.53 | 222 | 28% | 50% |
4.3.3 瓶颈分析
在7输入以上场景，主要瓶颈转为：
- 评估密钥带宽（需约50GB/s）
- 中间结果存储压力
- 电源网络IR drop
对应的优化方向：
- 3D堆叠存储
- 更激进的数据压缩
- 电压岛划分
5. 应用案例与部署建议
5.1 典型应用场景
5.1.1 医疗数据分析
在跨机构医疗数据联合分析中：
- 各医院加密本地数据
- 云端直接执行密文计算（如逻辑回归）
- 结果返回后解密
实测在乳腺癌风险预测模型中（10个特征），优化后的乘法器使端到端延迟从3.2秒降至1.7秒。
5.1.2 基因计算
隐私保护的基因序列比对：
- 加密的DNA片段（约100bp）
- 密文上计算编辑距离
- 返回匹配结果
采用8输入乘法优化后，100bp×100bp比对从14分钟缩短至8分钟。
5.2 部署配置建议
5.2.1 云计算场景
推荐配置：
- 多芯片并行（4-8个实例）
- 共享评估密钥存储
- 动态电压频率调整
预期性能：
- 吞吐量：120-180次乘法/秒
- 能效：35-50 GOPs/W
5.2.2 边缘计算场景
优化方向：
- 减少模数层数（L=12-16）
- 降低NTT点数（N=2^14）
- 精简控制逻辑
实测结果（N=2^14, L=16）：
- 面积：0.28mm²
- 功耗：49mW
- 适合集成到移动SoC
5.3 实用技巧与注意事项
密钥管理：评估密钥应存储在隔离的安全区域，建议采用物理不可克隆函数（PUF）保护
温度控制：高频运行下，每10°C温度升高会导致NTT时序余量减少0.12ns，需动态调频
测试模式：
- 注入已知明文测试向量
- 验证各阶段模数一致性
- 监测噪声增长曲线
错误处理：
- 模运算溢出检测
- NTT蝶形运算校验
- 安全中断机制
性能调优：
- 对于固定输入规模，可静态配置最优分组策略
- 平衡NTT核利用率与数据局部性
- 采用异步时钟域减少关键路径压力
6. 未来优化方向
虽然当前设计已取得显著改进，仍有以下优化空间：
近似计算：在允许一定误差的应用中，可探索：
- 降低NTT计算精度
- 简化模运算
- 截断噪声校正项
新型存储器：采用MRAM或ReRAM可能：
- 减少评估密钥加载延迟
- 降低存储功耗（约40%）
- 增强抗侧信道攻击能力
算法-架构协同：
- 定制化模数选择
- 稀疏多项式优化
- 动态精度调整
3D集成：通过硅通孔（TSV）技术：
- 堆叠存储与逻辑层
- 增加数据带宽
- 减少互连延迟
在实际部署中，我们观察到当输入规模超过12时，分组策略的选择空间急剧增加。此时可以采用机器学习方法离线搜索最优分组方案，建立查找表供实时查询。对于超大规模应用（如全基因组分析），建议采用分块计算策略，将大问题分解为多个可并行处理的密文乘法子任务。