Hyper の 个人博客

交流技术，分享生活

0%

论文阅读：基于格的数字签名方案 CRYSTALS-Dilithium

发表于 更新于 分类于 ， ， 阅读次数：
本文字数： 4.5k 阅读时长 ≈ 4 分钟

Info

文章出处：CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme

CRYSTALS-Dilithium 是 NIST 第四轮 Finalists 中唯二基于格的数字签名方案，另一方案 Falcon 基于 NTRU 格

1 引入

基于 An improved compression technique for signatures based on learning with errors 一文的简化版本，介绍此类签名方案的基本框架：

1.1 密钥生成

KeyGen()KeyGen()：

  • 生成一个大小为 k×ℓk \times \ell 的矩阵 AA，其中每个元素在多项式环 Rq=Zq[X]/(Xn+1)R_q = \mathbb{Z}_q[X]/(X^n + 1) 上，其中 q=223−213+1q = 2^{23} - 2^{13} + 1, n=256n = 256

  • 从随机分布中抽取两个秘密密钥向量 s1s_1 和 s2s_2，这些向量的系数属于环 RqR_q，且大小不超过 η\eta（一个小的上限）

  • 计算公钥的第二部分 t=As1+s2t = A s_1 + s_2

  • 输出密钥对 pk=(A,t)pk = (A, t), sk=(A,t,s1,s2)sk = (A, t, s_1, s_2)

1.2 签名

Sign(sk,M)Sign(sk, M)：接受私钥 sksk、消息 MM 作为输入

  • 初始化 z=⊥z = \bot，当 z=⊥z = \bot 时重复下述签名过程，直到生成有效的签名

  • 生成掩码向量 yy：签名者从集合 Sγ1−1ℓS_{\gamma_1 - 1}^{\ell} 中随机生成一个多项式向量 yy，其中 yy 的每个系数的大小小于 γ1\gamma_1。γ1\gamma_1 需要足够大，以确保签名不会泄露秘密密钥，但也足够小，使得签名不会被轻易伪造

  • 计算 w1w_1：计算 AyAy，将 AyAy 的每个系数拆分为高位和低位部分，依照 w=w1⋅2γ2+w0w = w_1 \cdot 2\gamma_2 + w_0 提取其高位部分 w1w_1，其中 ∣w0∣≤γ2|w_0| \leq \gamma_2

  • 生成挑战值 cc：挑战值 cc 由消息 MM 和 w1w_1 的哈希值生成，其中 cc 是环 RqR_q 中的多项式，具有 60 个 ±1\pm 1 的系数，其他系数为 00。这样做是为了确保 cc 的范数较小，且来自于一个大于 22562^{256} 的域

  • 计算初始签名值 zz：若直接输出 zz，则会泄露秘密密钥。因此，使用拒绝采样来确保安全性

  • 拒绝采样和低位校验：（1）设置参数 β\beta，其值为 cs1c s_1 的最大可能系数。由于 cc 只有 60 个 ±1\pm 1 的系数，且 s1s_1 的最大系数为 η\eta，因此有 β≤60η\beta \leq 60\eta；（2）检查 Ay−cs2Ay - cs_2 的低位部分。如果 zz 的任何系数大于 γ1−β\gamma_1 - \beta，或是 Az−ctAz - ct 低位部分的任何系数大于 γ2−β\gamma_2 - \beta，则拒绝签名并重新开始签名过程

  • 输出签名 σ=(z,c)\sigma = (z, c)

1.3 验签

Verify(pk,M,σ)Verify(pk,M,\sigma)：接受公钥 pkpk、消息 MM 和签名 σ\sigma 作为输入

  • 计算 w1′w'_1：Az−ctAz - ct 实际上等于 Ay−cs2Ay - cs_2，这是因为将 z=y+cs1z = y + cs_1 代入得到 Az−ct=A(y+cs1)−ct=Ay+Acs1−ct=Ay+c(As1−t)=Ay−cs2Az - ct = A(y + cs_1) - ct = Ay + Acs_1 - ct = Ay+c(As_1-t)=Ay - cs_2

  • 验证：（1）zz 的所有系数是否小于 γ1−β\gamma_1 - \beta；（2）cc 是否等于 H(M∣∣w1′)H(M || w'_1)

2 Dilithium 方案

与 1 的方案对比：公钥大小减少了约 2.5 倍，但签名大小有一个增加 150 字节左右的 tradeoff，这一改动主要涉及方案的第 6 步，这样并不公开完整的 tt，而是只有 tt 的高位部分 t1t_1；即公钥中只包含其高位部分 t1t_1，而低位部分 t0t_0 保留在私钥中

2.1 密钥生成

KeyGen()KeyGen()：

  • 生成两个 256 位的随机数 ρ,K\rho, K

  • 从随机分布中抽取两个秘密密钥向量 s1s_1 和 s2s_2，这些向量的系数属于环 RqR_q，且大小不超过 η\eta

  • 矩阵扩展：将种子 ρ\rho 扩展成一个大小为 k×ℓk \times \ell 的矩阵 AA，其中每个元素在多项式环 Rq=Zq[X]/(Xn+1)R_q = \mathbb{Z}_q[X]/(X^n + 1) 上，其中 q=223−213+1q = 2^{23} - 2^{13} + 1, n=256n = 256。但为了更快的实现考虑，矩阵 AA 实际上是以系数在 Zq256\mathbb{Z}^{256}_q 中的矩阵格式输出并存储的

  • 计算 t=As1+s2t = A s_1 + s_2

  • 将 tt 分解为高位 t1t_1 和低位 t0t_0 两个部分。本方案中公钥的第二部分为 t1t_1 而非 tt，使得此时的公钥只需要 ⌈log⁡q⌉−d\lceil \log q \rceil − d 字节，而非 ⌈log⁡q⌉\lceil \log q \rceil 字节

  • 将 ρ\rho 和 t1t_1 打包并使用 SHAKE-256 哈希，得到 384 位的 trtr，用于签名时的消息摘要

  • 输出密钥对 pk=(ρ,t1)pk = (\rho, t_1), sk=(ρ,K,tr,s1,s2,t0)sk = (\rho, K, tr, s_1, s_2, t_0)

2.2 签名

Sign(sk,M)Sign(sk, M)：

  • 由种子 ρ\rho 生成矩阵 AA

  • 将 trtr 和消息 MM 打包并使用 SHAKE-256 哈希，得到 384 位的消息摘要 μ\mu

  • 初始化 κ=0,(z,h)=⊥\kappa=0,(z, h)=\bot，当 (z,h)=⊥(z, h)=\bot 时重复下述签名过程并累加计数器 κ\kappa，直到生成有效签名

  • 生成掩码向量 yy：扩展 K∥μ∥κK \|\mu \|\kappa 生成多项式向量 yy，其中 y∈Sγ1−1ℓy \in S_{\gamma_1 - 1}^{\ell}。由于签名可能需要重复尝试多次，每次尝试时附加的计数器 κ\kappa 可以确保相同消息的多次签名尝试会输出不同的随机数

  • 计算 w=Ayw = Ay

  • 计算 w1w_1：将 ww 的每个系数拆分为高位和低位部分，依照 w=w1⋅2γ2+w0w = w_1 \cdot 2\gamma_2 + w_0 提取其高位部分 w1w_1，其中 ∣w0∣≤γ2|w_0| \leq \gamma_2

  • 生成挑战值 cc：挑战值 cc 由消息 MM 和 w1w_1 的哈希值生成，cc 是环 RqR_q 中的多项式，具有 60 个 ±1\pm 1 的系数，其他系数为 00

  • 计算初始签名值 zz

  • 将 w−cs2w - cs_2 分解为高位 r1r_1 和低位 r0r_0，以进一步检查签名的有效性

  • 拒绝采样、高低位校验：（1）设置参数 β\beta，其值为 cs1c s_1 的最大可能系数。由于 cc 只有 60 个 ±1\pm 1 的系数，且 s1s_1 的最大系数为 η\eta，因此有 β≤60η\beta \leq 60\eta；（2）检查 Ay−cs2Ay - cs_2 的低位部分；（3）检查 Ay−cs2Ay - cs_2 的高位部分。如果 zz 的任何系数大于 γ1−β\gamma_1 - \beta、 Ay−cs2Ay - cs_2 低位部分的任何系数大于 γ2−β\gamma_2 - \beta、Ay−cs2Ay - cs_2 高位部分不为 w1w_1 中的任意一项成立，则拒绝此签名

  • 生成附加提示 hh 用于验证，确保验证者可以正确恢复出高位信息。由于公钥只包含高位部分 t1t_1，验证时无法直接计算 Az−ctAz - ct 的完整值，而是只能计算 Az−ct1⋅2d=Az−ct+ct0Az - ct_1 \cdot 2^d = Az - ct + ct_0。为了弥补这一点，签名者需要发送提示 hh，告知验证者 ct0ct_0 导致进位的位置，从而能够正确恢复 Az−ctAz - ct 的高位部分。此时，如果 ct0ct_0 的任何系数大于 γ2\gamma_2，或是提示 hh 中的 1 的数目超出限制 ω\omega，则同样拒绝此签名

  • 输出签名 σ=(z,h,c)\sigma = (z, h, c)

2.3 验签

Verify(pk,M,σ)Verify(pk,M,\sigma)：

  • 由种子 ρ\rho 生成矩阵 AA

  • 将 ρ\rho 和 t1t_1 打包并使用 SHAKE-256 哈希后，整体再和 MM 哈希得到 384 位的消息摘要 μ\mu

  • 计算 w1′w'_1：使用提示 hh 恢复 Az−ct1A z - c t_1 的高位部分 w1′w'_1。验证者计算 Az−ct1⋅2dAz - ct_1 \cdot 2^d，这只包含 AzAz 和 ct1ct_1 的高位部分，并使用 hh 中包含的进位信息恢复 w1′w'_1

  • 验证：（1）zz 的所有系数是否小于 γ1−β\gamma_1 - \beta；（2）cc 是否等于 H(M∣∣w1′)H(M || w'_1)；（3）提示 hh 中的 1 的数目是否超出限制 ω\omega



参考
[1] CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme
[2] An improved compression technique for signatures based on learning with errors

相关文章：