CRYSTALS-Dilithium 后量子数字签名算法中的拒绝采样技术 题目描述 CRYSTALS-Dilithium 是一种基于格理论的后量子数字签名算法，其安全性依赖于模块化格上的短整数解问题（MLWE 和 SelfTargetMSIS）。在签名生成过程中，为了避免私钥信息通过签名值泄露，Dilithium 使用了 拒绝采样技术 。本题要求详细解释拒绝采样的作用、原理及其在 Dilithium 签名生成中的具体实现步骤。 1. 拒绝采样的背景与目的 在基于格的签名算法中，签名通常由以下形式生成： \[ \sigma = (c, z) \] 其中 \(z\) 是由私钥和随机值组合生成的向量。若直接输出 \(z\)，攻击者可能通过多次签名统计推断私钥信息。拒绝采样的核心目的是 让签名值的分布与私钥无关 ，即确保 \(z\) 的分布看起来是均匀随机的，即使攻击者收集大量签名也无法破解私钥。 2. 拒绝采样的基本原理 拒绝采样是一种概率性技术：先生成一个候选签名，再以一定概率决定是否接受它。若拒绝，则重新生成随机数并重复流程。Dilithium 采用的具体策略是： 要求签名向量 \(z\) 的每个分量绝对值不超过某个阈值 \(\eta\)。 若 \(z\) 的任一分量超出 \(\eta\)，则丢弃此次尝试。 这种策略使得最终输出的 \(z\) 服从均匀分布（在有限区间内），从而隐藏私钥的分布特征。 3. Dilithium 签名生成中的拒绝采样步骤 以下是 Dilithium 签名生成的简化流程（聚焦拒绝采样部分）： 步骤 1：生成随机掩码 签名者生成一个随机向量 \(y\)，其分量从均匀分布 \([ -η, η ]\) 中抽取。 步骤 2：计算承诺 计算 \(w = \text{HighBits}(A \cdot y)\)，其中 \(A\) 是公钥矩阵。将 \(w\) 哈希后得到挑战值 \(c\)。 步骤 3：生成候选签名 计算 \(z = y + c \cdot s\)（\(s\) 是私钥向量）。此时 \(z\) 的分布受私钥 \(s\) 影响。 步骤 4：拒绝条件检查 Dilithium 的拒绝采样条件为： \[ \|z\|_ \infty \leq \eta - \beta \] 其中 \(\beta\) 是与挑战 \(c\) 的范数相关的常数。若条件不满足，则返回步骤 1 重新生成 \(y\)。 步骤 5：二次验证 即使 \(z\) 通过范数检查，还需验证 \(w\) 是否与 \(z\) 一致： \[ \text{HighBits}(A \cdot z - c \cdot t) = w \] （\(t\) 是公钥向量）。此步骤确保签名可被正确验证。若失败，同样返回步骤 1。 4. 拒绝采样的安全性与效率 安全性 ：通过限制 \(z\) 的范数，使其分布与随机向量 \(y\) 的分布统计不可区分，从而避免私钥泄露。 效率 ：拒绝概率需足够低，否则签名速度会下降。Dilithium 通过调整参数 \(\eta\) 和 \(\beta\)，将拒绝率控制在约 10%-25%，实现安全与效率的平衡。 5. 实例说明 假设私钥 \(s = (1, -2)\)，随机生成 \(y = (3, 0)\)，挑战 \(c=1\)，则候选签名 \(z = (4, -2)\)。若设定 \(\eta = 5, \beta=2\)，则检查： \[ \|z\|_ \infty = \max(|4|, |-2|) = 4 \leq \eta - \beta = 3 \] 条件不满足（4 > 3），因此拒绝此次签名，重新生成 \(y\)。 总结 拒绝采样是 Dilithium 签名算法的核心安全机制，通过概率性丢弃不符合规范的签名候选值，确保最终输出的签名不泄露私钥信息。其实现依赖于精心设计的参数阈值和多次尝试机制，在格基密码学中具有广泛应用。