Page 68 - 《软件学报》2025年第10期

胡跃 等: 基于 FPGA 的格基数字签名算法硬件优化 4465

根据上文的分析, 对于 Dilithium 算法的纯硬件设计与实现方案的研究具有重要的价值, 同时考虑到签名运算
高维多项式向量的设计特点, 在方案设计过程中进一步提升算法运算效率应具备更高的优先级. 现有的纯硬件实
现方案有进一步优化的空间: Soni 等人 [22] 基于 HLS 方法完成签名算法的硬件设计, Ricci 等人 [23] 将算法流程直接
使用大量的硬件资源进行例化, 两个工作均未提出更好的硬件优化技术. Land 等人 [24] 使用 DSP 单元对多项式运
算模块进行优化设计, 有效提升了签名算法的运行效率, 但整体硬件架构的并行度和资源复用率较低. Wang 等人 [25,32]
基于不同的技术路径分别实现了两种四并行的多项式运算模块, 在提升运算效率的同时也在一定程度上节约了
DSP 资源的消耗. 但对于签名算法来说, 迭代型数论变换结构难以进一步地提升高维多项式向量的乘法运算效率.
与之相比, Zhao 等人 [26] 设计了流水线结构多项式运算模块, 使用 4 个蝴蝶运算单元分别完成数论变换过程中的相
邻两级运算, 辅以合适的时序状态机设计, 有效提升了签名算法的整体运行效率. 但是设计的运算模块每时钟周期
仅输入输出单个多项式系数, 完成 k 次数论变换需要 256k +296 个时钟周期, 其中的有效运算时间比例较低. 此外,
文献采用级联的方式设计 Keccak 核, 虽然可以将 SHA3 函数运算的效率加倍, 但过于复杂的组合逻辑运算限制了
最高时钟频率. 基于上述两点分析, Zhao 等人 [26] 的工作在运算效率方面具有进一步提升的可能性.
2 预备知识

本节将给出与本文具体工作相关的预备知识, 首先给出格困难问题的基本定义, 之后详细分析 Dilithium 算法
的核心运算流程, 为之后的硬件优化设计提供理论基础.
2.1 基本定义和符号说明
首先给出多项式环的基本定义, 设 n 和 q 为正整数, 其中, n 为 2 的幂次, Z 和 R 分别为有理数集合和实数集合.
n
令集合 Z q = Z/qZ = {0,1,...,q−1}, 集合 R q = R/q, 则 R = Z[x]/(x +1) 为多项式环, R 中元素为 n 次整系数多项
∑ n−1
n a = i a i ∈ Z q , 多项式
式. 定义 R q = Z q /(x +1), 其中的多项式系数均在 Z q 中. R q 中的多项式可表示为 a i x , 其中
i=0
T
T A 分
用向量形式可表示为 a = (a 0 ,a 1 ,...,a n−1 ). 进一步, 环 R/R q 上向量可表示为 a, 矩阵可表示为 A, 同时令 a 和
n−1
∑
i
别表示其转置. 在此基础上, 对于元素集合 a = w i x ∈ R, 其无穷范数 l ∞ 可以表示为 ∥ a∥ ∞ := max||a i || ∞ , 同样向量
i=0
k
a = [a i ] j ∈ R 的无穷范数可表示为 ∥ a∥ ∞ := max||a i || ∞ . 此外, 定义专用运算符 S η ⊆ R 表示元素集合满足 ∥ w∥ ∞ ⩽ η.
2.2 MLWE 和 MSIS 定义
n
T
LWE 问题是构建格基密码方案的底层数学原理之一. 定义分布 (a,b) = a s+e, 其中向量 a ← Z , 噪声 e ← ψ α .
q
令秘密 s 服从 Z q 上的均匀分布, 则计算型 LWE 问题为给定分布 (a,b), 计算得到秘密 s; 判定型 LWE 问题为区分
Z ×Z q 上的均匀分布. 由于经典的 LWE 问题所需的采样空间和运算量较大, 因此不适合直接
n
给定的 (a,b) 是否为 q
用于构建密码学方案. RLWE 通过引入一个额外的多项式环, 并利用负循环移位运算生成矩阵元素, 有效降低了采
样难度, 但同时更加稳定的代数结构特征也在一定程度上降低了安全性, 因此相关研究进一步提出了基于模格的
k×l
k
MLWE 问题. 定义运算 b := As+e, 其中矩阵 A ← R , 参数 k = poly(λ), 向量 (s,e) ← S ×S . 可以看出 MLWE 问
l
η
η
q
题是有多个 RLWE 实例组合而成, 兼顾了 LWE 的安全性和 RLWE 的运算效率, 因此多数格基密码方案选择基于
MLWE 问题进行构建.
k×l A 确定的多维格中寻找非零最
给定矩阵 A ← R , 其中 k = poly(λ), MSIS 问题在 β > 0 时可被参数化为在由
q
− → l − → ∥ x ∥⩽ β. 根据 l p (p ∈ [1,∞]) 范数中的假设, 在参数选择合适的条件
− →
短原相 x ∈ R , 满足公式 A· x = 0 且 MSIS 在
q
− →
下, 不存在多项式时间算法能够以不可忽略的概率寻找到正确的原像 x . 格基数字签名算法 Dilithium 的安全性同
时基于 MLWE 问题和 MSIS 问题, 并且更加关注无穷范数下的 MSIS 假设.
2.3 CRYSTALS-Dilithium 算法介绍
( )
CRYSTALS-Dilithium 由 3 个概率多项式时间算法 (KeyGen, Sign, Verify) 组成, 其中, KeyGen 1 λ 为密钥生成
λ M, 随后执行循
.
算法, 输入安全参数 1 , 输出公私钥对 (pk, sk) Sign(sk, M) 为签名算法, 输入私钥 sk 和待签名消息