基于格的数字签名算法：Dilithium 的签名生成与验证过程
字数 1729 2025-11-01 09:19:03

基于格的数字签名算法：Dilithium 的签名生成与验证过程

题目描述
Dilithium 是一种基于格上困难问题（模块学习错误问题，MLWE 和模块短整数解问题，MSIS）的后量子数字签名算法。其核心操作包括多项式环上的乘法和向量运算。本题要求详细解释 Dilithium 的签名生成与验证步骤，包括参数定义、密钥生成、签名过程（含拒绝采样）和验证逻辑。

解题过程

1. 算法背景与参数设置
Dilithium 在多项式环 \(R_q = \mathbb{Z}_q[X]/(X^n + 1)\) 上操作，其中常见参数为 \(n=256\), \(q=8380417\)（质数）。其他关键参数包括：

  • \(\ell, k\)：控制矩阵维度，例如 \((k, \ell) = (4,4)\) 或 \((6,5)\)。
  • \(\eta\)：拒绝采样边界，用于隐藏敏感随机性。
  • \(\gamma_1, \gamma_2\)：签名向量的数值边界。

2. 密钥生成过程

  • 生成随机种子 \(\rho\)，用于派生矩阵 \(A \in R_q^{k \times \ell}\)（公开参数）。
  • 生成秘密向量 \(s_1 \in R_q^\ell\)，其系数在 \([-\eta, \eta]\) 内均匀随机采样。
  • 生成噪声向量 \(s_2 \in R_q^k\)，系数同样在 \([-\eta, \eta]\) 内随机。
  • 计算 \(t = A s_1 + s_2 \in R_q^k\)。
  • 公钥：\(pk = (\rho, t)\)；私钥：\(sk = (\rho, s_1, s_2)\)。

3. 签名生成（含拒绝采样）
假设待签名消息为 \(M\)：

  1. 生成随机掩码：
    使用随机种子 \(r\) 计算 \(y \in R_q^\ell\)，其系数在 \([-\gamma_1, \gamma_1]\) 内均匀采样。
  2. 计算承诺：
    \(w = A y \in R_q^k\)，然后将其压缩为低精度向量 \(w_1 = \text{HighBits}(w, 2\gamma_2)\)。
  3. 生成挑战：
    计算 \(c = H(\mu \parallel w_1)\)，其中 \(\mu = H(pk) \parallel M\)，\(H\) 为哈希函数，\(c\) 被映射为稀疏多项式（少量非零系数）。
  4. 计算候选签名：
    \(z = y + c s_1\)。若 \(z\) 的系数超出 \(\gamma_1 - \beta\)（\(\beta\) 为 \(c s_1\) 的系数界），则返回步骤1重试（拒绝采样）。
  5. 防止信息泄露：
    计算 \(h = c s_2\)，然后检查 \(\text{LowBits}(w - c s_2, 2\gamma_2)\) 是否小于 \(\gamma_2 - \beta\)。若不满足，重试。
  6. 输出签名：
    \(\sigma = (z, c, \text{提示位})\)，其中提示位用于辅助验证时恢复 \(w_1\)。

4. 签名验证

  1. 恢复承诺：
    计算 \(w_1' = \text{HighBits}(A z - c t, 2\gamma_2)\)（利用提示位修正舍入误差）。
  2. 重新计算挑战：
    验证 \(c \stackrel{?}{=} H(\mu \parallel w_1')\)。
  3. 检查范数边界：
    确保 \(z\) 的系数在 \([-\gamma_1 + \beta, \gamma_1 - \beta]\) 内，防止伪造。

5. 安全性关键点

  • 拒绝采样确保 \(z\) 的分布与私钥 \(s_1\) 无关，避免信息泄露。
  • 提示位机制解决验证时因取整导致的误差，保证 \(w_1\) 可准确还原。
  • 安全性归约于 MLWE 和 MSIS 问题的难解性。
基于格的数字签名算法：Dilithium 的签名生成与验证过程 题目描述 Dilithium 是一种基于格上困难问题（模块学习错误问题，MLWE 和模块短整数解问题，MSIS）的后量子数字签名算法。其核心操作包括多项式环上的乘法和向量运算。本题要求详细解释 Dilithium 的签名生成与验证步骤，包括参数定义、密钥生成、签名过程（含拒绝采样）和验证逻辑。 解题过程 1. 算法背景与参数设置 Dilithium 在多项式环 \( R_ q = \mathbb{Z}_ q[ X ]/(X^n + 1) \) 上操作，其中常见参数为 \( n=256 \), \( q=8380417 \)（质数）。其他关键参数包括： \( \ell, k \)：控制矩阵维度，例如 \( (k, \ell) = (4,4) \) 或 \( (6,5) \)。 \( \eta \)：拒绝采样边界，用于隐藏敏感随机性。 \( \gamma_ 1, \gamma_ 2 \)：签名向量的数值边界。 2. 密钥生成过程 生成随机种子 \( \rho \)，用于派生矩阵 \( A \in R_ q^{k \times \ell} \)（公开参数）。 生成秘密向量 \( s_ 1 \in R_ q^\ell \)，其系数在 \( [ -\eta, \eta ] \) 内均匀随机采样。 生成噪声向量 \( s_ 2 \in R_ q^k \)，系数同样在 \( [ -\eta, \eta ] \) 内随机。 计算 \( t = A s_ 1 + s_ 2 \in R_ q^k \)。 公钥：\( pk = (\rho, t) \)；私钥：\( sk = (\rho, s_ 1, s_ 2) \)。 3. 签名生成（含拒绝采样） 假设待签名消息为 \( M \)： 生成随机掩码 ： 使用随机种子 \( r \) 计算 \( y \in R_ q^\ell \)，其系数在 \( [ -\gamma_ 1, \gamma_ 1 ] \) 内均匀采样。 计算承诺 ： \( w = A y \in R_ q^k \)，然后将其压缩为低精度向量 \( w_ 1 = \text{HighBits}(w, 2\gamma_ 2) \)。 生成挑战 ： 计算 \( c = H(\mu \parallel w_ 1) \)，其中 \( \mu = H(pk) \parallel M \)，\( H \) 为哈希函数，\( c \) 被映射为稀疏多项式（少量非零系数）。 计算候选签名 ： \( z = y + c s_ 1 \)。若 \( z \) 的系数超出 \( \gamma_ 1 - \beta \)（\( \beta \) 为 \( c s_ 1 \) 的系数界），则返回步骤1重试（拒绝采样）。 防止信息泄露 ： 计算 \( h = c s_ 2 \)，然后检查 \( \text{LowBits}(w - c s_ 2, 2\gamma_ 2) \) 是否小于 \( \gamma_ 2 - \beta \)。若不满足，重试。 输出签名 ： \( \sigma = (z, c, \text{提示位}) \)，其中提示位用于辅助验证时恢复 \( w_ 1 \)。 4. 签名验证 恢复承诺 ： 计算 \( w_ 1' = \text{HighBits}(A z - c t, 2\gamma_ 2) \)（利用提示位修正舍入误差）。 重新计算挑战 ： 验证 \( c \stackrel{?}{=} H(\mu \parallel w_ 1') \)。 检查范数边界 ： 确保 \( z \) 的系数在 \( [ -\gamma_ 1 + \beta, \gamma_ 1 - \beta ] \) 内，防止伪造。 5. 安全性关键点 拒绝采样确保 \( z \) 的分布与私钥 \( s_ 1 \) 无关，避免信息泄露。 提示位机制解决验证时因取整导致的误差，保证 \( w_ 1 \) 可准确还原。 安全性归约于 MLWE 和 MSIS 问题的难解性。