离散高斯采样在后量子密码学中的关键作用与优化

1. 离散高斯采样在后量子密码学中的核心地位离散高斯采样是后量子密码学Post-Quantum Cryptography, PQC中基于格的密码方案的核心运算之一。在Falcon签名方案中离散高斯采样占据了签名生成过程中72%的计算时间成为性能瓶颈。其本质是通过数学方法生成服从特定离散高斯分布的随机整数这些整数作为短向量用于构造格密码中的困难问题实例。离散高斯分布与连续高斯分布类似但定义在整数域上。对于一个整数集合Z中心μ和标准差σ的离散高斯分布定义为D_{Z,μ,σ}(z) ρ_{μ,σ}(z)/ρ_{μ,σ}(Z)其中ρ_{μ,σ}(z) exp(-(z-μ)²/(2σ²))是高斯函数分母是归一化因子。在Falcon中每个签名需要生成大量这样的随机整数且参数μ和σ随不同系数变化。2. Falcon签名方案中的采样需求分析Falcon签名方案作为NIST后量子密码标准化项目选定的标准算法其签名生成过程高度依赖离散高斯采样。具体表现在递归采样结构Falcon采用快速傅里叶采样(FFS)算法在递归的每一层都需要调用SamplerZ子程序。如算法1所示当递归到n1时需要同时生成两个独立的离散高斯样本(z₀, z₁)。参数动态性与大多数格密码方案不同Falcon的每个系数对应不同的(μ, σ)参数无法使用固定参数的采样器。这增加了硬件实现的复杂度。精度要求采样过程涉及浮点运算和特殊函数计算(如指数函数)需要保持足够的数值精度以确保密码学安全性。拒绝采样特性SamplerZ采用拒绝采样算法每次尝试都有概率失败导致采样延迟不确定。统计显示约42.42%的采样需要重试其中约24.39%需要重试一次10.47%需要重试两次。3. Bi-SamplerZ架构设计原理3.1 双数据路径并行化传统硬件采样器通常采用单数据路径设计无法充分利用Falcon采样过程中的并行性机会。Bi-SamplerZ的创新点在于观察到在FFS算法的递归叶子节点(n1)两个SamplerZ调用(z₀和z₁)完全独立可并行执行两个采样过程共享相同的σ参数(但μ不同)可复用部分计算逻辑通过设计辅助机制一个数据路径的中间结果可帮助另一个路径提高接受概率基于这些观察Bi-SamplerZ采用如图1所示的双数据路径架构其中共享模块Pre_samp(参数预处理)、BaseSampler(基础采样)独立模块Bef_loop(循环前处理)、For_loop(核心循环)、CMP(比较判断)协同模块Fpr_adder(最终结果处理)3.2 辅助机制设计当一条路径采样成功而另一条失败时传统设计会丢弃成功结果并重新开始。Bi-SamplerZ引入创新的辅助机制成功路径保留其有效样本利用成功路径的中间值(如μ)重新计算失败路径的预处理值仅需额外7个周期即可将联合接受概率从57.58%提升至82.3%该机制相比文献[19]的四路径设计更节省硬件资源避免了单纯增加并行度带来的面积开销。3.3 精细流水线设计Bi-SamplerZ将采样过程分解为多个精细的流水级基于数据依赖关系而非软件子程序划分。关键优化包括预处理阶段集中计算不随拒绝循环变化的参数(r, ccs等)基础采样提前生成候选z₀值与后续处理重叠执行核心循环将ApproxExp的12次迭代展开为专用硬件比较判断并行执行Bernoulli试验的位比较这种流水线设计使得关键路径延迟从传统的数十周期降低到平均8.3周期(ASIC实现)。4. 关键微架构优化技术4.1 81位定点数表示法传统实现使用IEEE 754浮点数硬件开销大。Bi-SamplerZ采用自定义81位定点格式(9位整数72位小数)通过严格数学分析证明动态范围足够中间变量最大值361 2⁹512精度等同双精度对于e ≥ -20的输入可无损表示52位尾数硬件优势乘法器面积减少63%关键路径延迟降低41%具体实现中将算法2中的所有变量乘以2⁷²后作为整数处理最后再缩放回去。这避免了浮点运算又保持数值精度。4.2 查找表优化策略针对采样过程中的重复计算Bi-SamplerZ设计了多种专用查找表RCDT表存储反向累积分布函数用于BaseSamplerT[z₀]表预计算z₀²/(2σ²_max)避免实时运算常数表存储算法3中的12个ApproxExp常数项浮点缓存直接存储⌊μ⌋的浮点表示避免整数转浮点转换这些优化使得每个采样可减少15-20次算术运算显著降低功耗。4.3 三态门基采样器传统BaseSampler使用累加器结构需要18个比较器加法树。Bi-SamplerZ创新性地利用RCDT的单调性设计了三态门阵列比较结果必然形如111...100...0用XOR检测最后一个1的位置通过三态门直接输出对应索引值完全组合逻辑实现零周期延迟该设计将BaseSampler面积减少58%功耗降低63%且不再成为关键路径。5. 硬件实现与性能分析5.1 ASIC实现结果采用TSMC 28nm工艺综合实现关键指标频率1.2GHz面积0.32mm²功耗49mW 1.2GHz平均延迟8.3周期/样本吞吐量289MSamples/s与现有设计对比相比FalconSign[23]周期数减少54.1%相比RISC-V方案[21]吞吐量提升7.8倍面积时间积(ATP)最优0.026mm²·ns5.2 FPGA实现结果在Xilinx UltraScale VU9P上实现频率312MHz资源占用LUT14,372 (6.8%)FF9,855 (2.3%)DSP48 (7.1%)功耗8.3W性能表现每样本平均需要25周期吞吐量达到12.5MSamples/s比纯软件实现快23倍5.3 实际应用测试集成到完整Falcon签名生成流程中测试Falcon-512签名延迟1.2ms (ASIC)比最优软件快15倍比现有硬件加速器快2.7倍能效比3.2μJ/签名6. 设计经验与优化建议在实际硬件实现中我们总结了以下关键经验随机数管理ChaCha20 PRNG的输出带宽必须匹配双路径的消耗速率我们设计了128位宽随机数缓冲每周期可提供足够熵。时序收敛技巧将81位乘法分解为3个27位段进行流水配合进位保留加法器确保1.2GHz频率下时序收敛。面积优化共享Pre_samp模块节省22%面积双路径间复用常数乘法器节省15%逻辑。验证方法采用形式验证确保拒绝采样的统计特性χ²测试显示实际输出与理论分布的最大偏差0.3%。可配置性支持运行时参数更新适应Falcon-512/1024等不同参数集仅需3周期重配置。对于希望实现类似设计的工程师建议优先优化BaseSampler和ApproxExp循环这两个模块占据85%的计算延迟采用分层验证策略先验证单个SamplerZ的正确性再测试双路径交互在面积和速度间权衡时优先保证单路径时序再考虑资源共享为拒绝采样设计充足的随机数缓冲避免因随机数饥饿导致性能下降7. 扩展应用与未来方向Bi-SamplerZ的设计理念可推广到其他需要离散高斯采样的后量子密码方案CRYSTALS-Dilithium通过调整参数表可支持该签名方案的采样需求Kyber需修改为模数采样但核心架构可复用随机预言模型可作为哈希函数的硬件加速组件未来优化方向包括支持更多采样算法如Knuth-Yao探索近似计算在采样中的应用研究低精度采样对安全性的影响边界3D堆叠技术下的内存计算架构我们在Github开源了RTL代码开发者可基于现有设计快速适配不同应用场景。实际部署表明该架构特别适合物联网终端设备可在资源受限环境下实现高安全性的后量子签名生成。