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

4466 软件学报 2025 年第 36 卷第 10 期

环签名运算, 直到产生满足安全边界条件的签名 . pk、待验证消息 M
σ Verify(pk, M,σ) 为签名验证算法, 输入公钥
b ∈ {0,1}, 用于判断是否为正确的签名.
及其签名 σ, 输出
如算法 1 所示, Dilithium 算法中的核心运算过程包括 ˆ A◦ ˆ y, ˆc◦ ˆ s 1 , ˆc◦ ˆ s 2 , ˆc· ˆ t 0 等环上的多项式乘法运算, 通常使
用数论变换技术加速其运算效率. 由于 Dilithium 的环参数 (n, q) 的选择刚好满足公式 q ≡ 1(mod 2n), 因此可以使
n
∗
用经典数论变换加速多项式运算的过程. 此时, 在循环群 Z 上存在 512 次本原单元根 α, 满足公式 x +1 (x−α)
q
( 3 )( 511 ) n ( )
3
x−α x−α . 根据中国剩余定理可知, 每一个多项式 a ∈ R q = Z q [x]/(x +1) 可以被唯一地表示为 [a(α),a α ,...,
( )
n
T
a α 2n−1 ] ∈ P . 因此多项式乘法运算可以分解为子多项式乘法的形式, 并使用迭代的思想最终分解为系数点乘运
q
( )
算, 在 256 维多项式系数的数论变换过程中共包含 8 级运算, 进而将环上的多项式乘法运算的复杂度由 O n 2 降
)
(
低为 O nlogn . 此外多项式系数采样同样是签名算法中关键且较为耗时的运算过程, 在 Dilithium 算法中使用了两
种 XOF 计算实例: 运算过程 ExpandS、ExpandMask、SampleInBall 对应计算实例 SHAKE-256, 而运算过程
ExpandA 对应计算实例 SHAKE128, 其中耗时最多的两个运算过程分别为 H (ρ ∥ t 1 ) 和矩阵 A 的采样运算 ExpandA.
在进行硬件实例化设计时, 需要重点考虑上述核心运算步骤的优化实现方案.
算法 1. Dilithium 算法核心运算过程.
KeyGen()
1. (ρ,ρ ,K) ∈ {0,1} 256 ×{0,1} 512 ×{0,1} 256 ⇐ H(ζ ||k||l) // ζ ⇐ {0,1} 256
′
κ
2. (s 1 , s 2 ) ∈ S ×S ⇐ ExpandS(ρ )
l
′
η
η
3. ˆ A ∈ R k×l ⇐ ExpandA(ρ)
q
−1
4. t ⇐ NTT ( ˆ A◦ ˆ s 1 )+ s 2 // ˆ s 1 = NTT(s 1 )
5. (t 1 , t 0 ) ⇐ Power2Round q (t,d)
6. tr ∈ {0,1} 256 ⇐ H (ρ ∥ t 1 )
7. return (pk = (ρ, t 1 ), sk = (ρ,K,tr, s 1 , s 2 , t 0 ))
Sign(sk, M)
1. ˆ s 1 = NTT(s 1 ), ˆ s 2 = NTT(s 2 ), ˆ t 0 = NTT(t 0 )
2. ˆ A ∈ R k×l ⇐ ExpandA(ρ)
q
′
3. µ ∈ {0,1} 512 ⇐ H(tr ∥ M) ρ ∈ {0,1} 512 ⇐ H(K ∥ rnd ∥ µ)
,
4. κ ⇐ 0,(z, h) ⇐⊥
5. while (z, h) ⇐⊥ do
6. y ∈ S ι ⇐ ExpandMask(ρ ,κ)
′
γ 1
−1
7. w ⇐ NTT ( ˆ A◦ ˆ y) // ˆ y = NTT(y)
8. w 1 ⇐ HighBits(w)
9. ˜ c ∈ {0,1} 256 ⇐ H (µ ∥ w 1 )
10. c ∈ R q ⇐ SampleInBall (˜c)
11. ˆ c ⇐ NTT(c)
−1
12. z ⇐ y+⟨cs 1 ⟩ // ⟨cs 1 ⟩ = NTT (ˆc◦ ˆ s 1 )
−1
13. r 0 ⇐ LowBits(w−⟨cs 2 ⟩) // ⟨cs 2 ⟩ = NTT (ˆc◦ ˆ s 2 )
14. if ∥ z∥ ∞ ⩾ γ 1 −β and ||r 0 || ∞ ⩾ γ 2 −β then (z, h) ⇐⊥
15. else
( )
16. ⟨ct 0 ⟩ = NTT −1 ˆ c· ˆ t 0
17. h ⇐ MakeHint (−⟨ct 0 ⟩,w−⟨cs 2 ⟩+⟨cs 1 ⟩)
||ct 0 || ∞ ⩾ γ 2 or (z, h) ⇐⊥
18. if [[the number of 1 in h is greater than ω]] then