CRYSTALS-Dilithium 后量子数字签名算法中的挑战哈希与掩码生成
字数 3477 2025-12-08 09:19:22

CRYSTALS-Dilithium 后量子数字签名算法中的挑战哈希与掩码生成

题目描述：在基于格的数字签名算法 CRYSTALS-Dilithium 中，签名者需要生成一个包含挑战多项式 c 的签名。挑战 c 是从消息和承诺哈希计算得出的，而签名中的一个关键部分是“掩码”（Masking），它用于隐藏签名中的秘密信息，防止私钥泄露。本题将详细讲解 Dilithium 签名生成过程中，如何从消息和承诺计算挑战哈希，以及如何生成和使用掩码向量 y 及其处理后得到的 z，以完成安全的签名生成。

核心目标：理解挑战多项式 c 的确定性生成过程，以及掩码如何在不泄露私钥的前提下，将秘密信息嵌入到最终签名中。

解题过程循序渐进讲解

我们将以 Dilithium 的简化核心流程（忽略部分优化细节）为例，分为两个主要阶段讲解：

第一阶段：挑战多项式 c 的生成

这个阶段的目标是产生一个与消息和签名者临时公开的“承诺”绑定的、短小的随机多项式 c，它决定了后续签名的随机性，但本身是确定性的。

  1. 预备知识与符号

    • 设所有运算在多项式环 \(R_q = \mathbb{Z}_q[X] / (X^n + 1)\) 中进行，其中 \(n\) 通常为 256，\(q\) 是一个模数（如 8380417）。
    • 签名者的公钥是矩阵 A（公开）和向量 t（公开）。
    • 私钥是短向量 s（秘密）和随机种子用于生成矩阵 A。
    • 要签名的消息为 \(M\)。

  2. 签名生成的初始步骤

    • 签名者首先需要生成一个随机、短的掩码向量 y，其系数从某个中心二项分布或均匀分布（在有限区间内）中采样。设 y ∈ \(R_q^k\)（k 是向量的维度，例如 4 或 6）。
    • 然后，计算 承诺 (Commitment)：\(w = A y\)。这里 \(A\) 是公开的矩阵，y 是临时的秘密掩码。计算后，对 \(w\) 进行“压缩”（一种取模、舍入操作），得到一个更紧凑的表示 \(w_1\)。这个 \(w_1\) 可以公开，因为它是由 A 和随机的 y 计算而来，不直接泄露私钥。

  3. 生成挑战哈希

    • 现在，签名者需要生成挑战多项式 c。c 是一个“短”多项式，其系数是 0、±1 的小整数，并且其汉明重量（非零系数的数量）是固定的一个较小值（记为 τ）。
    • c 的生成是确定性的，输入是：
      1. \(w_1\)（压缩后的承诺）
      2. \(M\)（待签名的消息）
      3. 可能还包括公钥的一部分（如 t 的压缩形式）以绑定上下文，具体取决于 Dilithium 的变体。
    • 签名者将这些数据连接起来，作为一个字节串输入给一个抗碰撞的密码哈希函数（如 SHA3-256 或 SHAKE-256）。哈希函数的输出（例如 256 或 512 比特）用作一个随机种子。
    • 使用这个随机种子，通过一个特定的、确定性的采样算法（例如，基于 XOF 如 SHAKE-128 的拒绝采样或 Fisher-Yates 洗牌算法），从所有可能的、重量为 τ 的 {0, ±1}^n 多项式集合中，均匀地选出一个多项式 c。
    • 关键点：因为 c 由 \(w_1\) 和 \(M\) 哈希确定，所以任何验证者只要知道同样的 \(w_1\)、\(M\) 和公钥信息，就能独立、确定性地重新生成完全相同的 c。这确保了签名的不可伪造性（签名必须对应特定的 \(w_1\) 和 \(M\) 的组合）。

第二阶段：掩码的作用与签名计算

这个阶段的目标是利用挑战 c 和私钥 s，结合最初的掩码 y，计算出最终的签名部分 z，同时确保 z 的分布独立于私钥 s。

  1. 计算中间签名向量

    • 现在签名者有了挑战 c 和私钥 s。Dilithium 的核心签名方程（高度简化）是：\(z = y + c s\)。
    • 这里 s 是私钥（短向量），y 是第一步生成的随机掩码（短向量），c 是一个标量多项式，它与向量 s 的乘法是多项式的标量乘法（c 的每个系数乘以 s 的每个多项式，在环上运算）。
    • 直观理解：z 是掩码 y 加上一个由挑战 c 和私钥 s 决定的“偏移量”。y 就像一层“面具”，掩盖了 c s 的真实值。

  2. 掩码的核心安全作用：防止私钥泄露

    • 如果直接公布 \(c s\)，因为 c 公开，可能会泄露 s 的信息。y 的加入使得 z 的分布看起来是随机的（服从与 y 类似的分布），前提是 y 的范数（大小）足够大，足以“淹没” \(c s\) 的贡献。
    • 拒绝采样（Rejection Sampling）：为了确保 z 的分布完全独立于私钥 s，Dilithium 使用了一个关键的拒绝采样步骤。在计算出 \(z = y + c s\) 后，签名者会检查向量 z 的每个系数的绝对值是否小于某个预设的边界 \(\beta\)（例如，\(\beta = \gamma_1\)）。
    • 检查目的：如果 z 的某些系数太大（绝对值 ≥ \(\beta\)），说明在这个特定位置，y 可能不够大，无法完全掩盖 \(c s\) 的特征，导致 z 的分布略微偏离理想的随机分布，从而可能通过统计分析泄露私钥 s 的信息。
    • 如果检查失败（存在系数超过边界），签名者必须丢弃当前的 y 和计算出的 z，然后返回第一步，重新采样一个新的随机掩码 y‘，重新计算 \(w_1'\)，重新生成挑战 c'（因为 \(w_1\) 变了），再计算 \(z' = y' + c' s\) 并再次进行边界检查。这个过程重复直到找到一组（y, z）使得 z 的系数都在安全边界内。

  3. 生成最终签名

    • 一旦找到通过边界检查的 z，签名就基本完成了。最终的签名通常是三元组 \((\rho, z, h)\) 或类似形式，其中：
      • \(\rho\) 是生成矩阵 A 的随机种子（通常公钥中包含或从公钥推导）。
      • \(z\) 是上面计算出的签名向量。
      • \(h\) 是一些辅助信息（在 Dilithium 优化版本中，是用于帮助验证时高效重建 \(w_1\) 的“提示”，它是对原始承诺 \(w\) 与用公钥、z、c 等计算出的值之间差异的压缩编码，用于验证时更精确地恢复 \(c\)）。
    • 在某些简化描述中，签名就是 \((z, c)\)，但标准 Dilithium 为了减小签名大小，不直接发送 \(c\)，而是发送提示 \(h\)，让验证者从 \(h, z, M, pk\) 中重新推导出 \(c\)。

  4. 验证侧的逻辑闭环

    • 验证者收到签名 \((\rho, z, h)\) 和消息 \(M\) 后，利用 \(\rho\) 重建矩阵 A，利用公钥 t 和签名中的 \(h, z\) 等信息，可以重新计算出一个承诺的近似值 \(w_1'\)。
    • 然后，验证者将自己计算出的 \(w_1'\)、收到的 \(M\) 以及公钥信息进行哈希，用同样的确定性过程重新生成挑战多项式 \(c'\)。
    • 接着，验证者检查两件事：1) 签名向量 z 的系数是否确实小于安全边界 \(\beta\)。2) 利用公钥等式 \(A z - c' t\) 计算出的值与从签名中恢复出的承诺是否“足够接近”（在压缩误差范围内）。
    • 如果 \(c'\) 与签名生成时使用的 \(c\) 一致（这是由哈希确定性保证的，前提是承诺正确），并且 z 是合法计算的（即 \(z = y + c s\)），那么验证等式就会成立。同时，边界检查保证了 z 不会泄露私钥。

总结：
挑战哈希过程（c = Hash(\( w_1\), M, ...)）将签名与特定的消息和承诺唯一且确定性地绑定，是安全性的基石。掩码 y 和拒绝采样技术共同作用，确保最终发布的签名部分 z 在数学上隐藏了私钥 s 的信息，使得即使攻击者收集大量签名，也无法推断出私钥，从而实现了基于格问题的数字签名安全。

CRYSTALS-Dilithium 后量子数字签名算法中的挑战哈希与掩码生成 题目描述 ：在基于格的数字签名算法 CRYSTALS-Dilithium 中，签名者需要生成一个包含挑战多项式 c 的签名。挑战 c 是从消息和承诺哈希计算得出的，而签名中的一个关键部分是“掩码”（Masking），它用于隐藏签名中的秘密信息，防止私钥泄露。本题将详细讲解 Dilithium 签名生成过程中，如何从消息和承诺计算挑战哈希，以及如何生成和使用掩码向量 y 及其处理后得到的 z ，以完成安全的签名生成。 核心目标 ：理解挑战多项式 c 的确定性生成过程，以及掩码如何在不泄露私钥的前提下，将秘密信息嵌入到最终签名中。 解题过程循序渐进讲解 我们将以 Dilithium 的简化核心流程（忽略部分优化细节）为例，分为两个主要阶段讲解： 第一阶段：挑战多项式 c 的生成 这个阶段的目标是产生一个与消息和签名者临时公开的“承诺”绑定的、短小的随机多项式 c ，它决定了后续签名的随机性，但本身是确定性的。 预备知识与符号 设所有运算在多项式环 \( R_ q = \mathbb{Z}_ q[ X ] / (X^n + 1) \) 中进行，其中 \( n \) 通常为 256，\( q \) 是一个模数（如 8380417）。 签名者的公钥是矩阵 A （公开）和向量 t （公开）。 私钥是短向量 s （秘密）和随机种子用于生成矩阵 A 。 要签名的消息为 \( M \)。 签名生成的初始步骤 签名者首先需要生成一个随机、短的掩码向量 y ，其系数从某个中心二项分布或均匀分布（在有限区间内）中采样。设 y ∈ \( R_ q^k \)（k 是向量的维度，例如 4 或 6）。 然后，计算 承诺 (Commitment) ：\( w = A y \)。这里 \( A \) 是公开的矩阵， y 是临时的秘密掩码。计算后，对 \( w \) 进行“压缩”（一种取模、舍入操作），得到一个更紧凑的表示 \( w_ 1 \)。这个 \( w_ 1 \) 可以公开，因为它是由 A 和随机的 y 计算而来，不直接泄露私钥。 生成挑战哈希 现在，签名者需要生成挑战多项式 c 。 c 是一个“短”多项式，其系数是 0、±1 的小整数，并且其汉明重量（非零系数的数量）是固定的一个较小值（记为 τ）。 c 的生成是 确定性的 ，输入是： \( w_ 1 \)（压缩后的承诺） \( M \)（待签名的消息） 可能还包括公钥的一部分（如 t 的压缩形式）以绑定上下文，具体取决于 Dilithium 的变体。 签名者将这些数据连接起来，作为一个字节串输入给一个抗碰撞的密码哈希函数（如 SHA3-256 或 SHAKE-256）。哈希函数的输出（例如 256 或 512 比特）用作一个随机种子。 使用这个随机种子，通过一个特定的、确定性的采样算法（例如，基于 XOF 如 SHAKE-128 的拒绝采样或 Fisher-Yates 洗牌算法），从所有可能的、重量为 τ 的 {0, ±1}^n 多项式集合中，均匀地选出一个多项式 c 。 关键点 ：因为 c 由 \( w_ 1 \) 和 \( M \) 哈希确定，所以任何验证者只要知道同样的 \( w_ 1 \)、\( M \) 和公钥信息，就能独立、确定性地重新生成完全相同的 c 。这确保了签名的不可伪造性（签名必须对应特定的 \( w_ 1 \) 和 \( M \) 的组合）。 第二阶段：掩码的作用与签名计算 这个阶段的目标是利用挑战 c 和私钥 s ，结合最初的掩码 y ，计算出最终的签名部分 z ，同时确保 z 的分布独立于私钥 s 。 计算中间签名向量 现在签名者有了挑战 c 和私钥 s 。Dilithium 的核心签名方程（高度简化）是：\( z = y + c s \)。 这里 s 是私钥（短向量）， y 是第一步生成的随机掩码（短向量）， c 是一个标量多项式，它与向量 s 的乘法是多项式的标量乘法（ c 的每个系数乘以 s 的每个多项式，在环上运算）。 直观理解： z 是掩码 y 加上一个由挑战 c 和私钥 s 决定的“偏移量”。 y 就像一层“面具”，掩盖了 c s 的真实值。 掩码的核心安全作用：防止私钥泄露 如果直接公布 \( c s \)，因为 c 公开，可能会泄露 s 的信息。 y 的加入使得 z 的分布看起来是随机的（服从与 y 类似的分布），前提是 y 的范数（大小）足够大，足以“淹没” \( c s \) 的贡献。 拒绝采样（Rejection Sampling） ：为了确保 z 的分布完全独立于私钥 s ，Dilithium 使用了一个关键的拒绝采样步骤。在计算出 \( z = y + c s \) 后，签名者会检查向量 z 的每个系数的绝对值是否小于某个预设的边界 \( \beta \)（例如，\( \beta = \gamma_ 1 \)）。 检查目的 ：如果 z 的某些系数太大（绝对值 ≥ \( \beta \)），说明在这个特定位置， y 可能不够大，无法完全掩盖 \( c s \) 的特征，导致 z 的分布略微偏离理想的随机分布，从而可能通过统计分析泄露私钥 s 的信息。 如果检查失败（存在系数超过边界），签名者必须 丢弃 当前的 y 和计算出的 z ，然后 返回第一步 ，重新采样一个新的随机掩码 y‘ ，重新计算 \( w_ 1' \)，重新生成挑战 c' （因为 \( w_ 1 \) 变了），再计算 \( z' = y' + c' s \) 并再次进行边界检查。这个过程重复直到找到一组（ y , z ）使得 z 的系数都在安全边界内。 生成最终签名 一旦找到通过边界检查的 z ，签名就基本完成了。最终的签名通常是三元组 \( (\rho, z, h) \) 或类似形式，其中： \( \rho \) 是生成矩阵 A 的随机种子（通常公钥中包含或从公钥推导）。 \( z \) 是上面计算出的签名向量。 \( h \) 是一些辅助信息（在 Dilithium 优化版本中，是用于帮助验证时高效重建 \( w_ 1 \) 的“提示”，它是对原始承诺 \( w \) 与用公钥、 z 、 c 等计算出的值之间差异的压缩编码，用于验证时更精确地恢复 \( c \)）。 在某些简化描述中，签名就是 \( (z, c) \)，但标准 Dilithium 为了减小签名大小，不直接发送 \( c \)，而是发送提示 \( h \)，让验证者从 \( h, z, M, pk \) 中重新推导出 \( c \)。 验证侧的逻辑闭环 验证者收到签名 \( (\rho, z, h) \) 和消息 \( M \) 后，利用 \( \rho \) 重建矩阵 A ，利用公钥 t 和签名中的 \( h, z \) 等信息，可以重新计算出一个承诺的近似值 \( w_ 1' \)。 然后，验证者将自己计算出的 \( w_ 1' \)、收到的 \( M \) 以及公钥信息进行哈希，用同样的确定性过程 重新生成挑战多项式 \( c' \) 。 接着，验证者检查两件事：1) 签名向量 z 的系数是否确实小于安全边界 \( \beta \)。2) 利用公钥等式 \( A z - c' t \) 计算出的值与从签名中恢复出的承诺是否“足够接近”（在压缩误差范围内）。 如果 \( c' \) 与签名生成时使用的 \( c \) 一致（这是由哈希确定性保证的，前提是承诺正确），并且 z 是合法计算的（即 \( z = y + c s \)），那么验证等式就会成立。同时，边界检查保证了 z 不会泄露私钥。 总结 ： 挑战哈希过程（ c = Hash(\( w_ 1\), M, ...) ）将签名与特定的消息和承诺 唯一且确定性地 绑定，是安全性的基石。掩码 y 和拒绝采样技术共同作用，确保最终发布的签名部分 z 在数学上隐藏了私钥 s 的信息，使得即使攻击者收集大量签名，也无法推断出私钥，从而实现了基于格问题的数字签名安全。