CRYSTALS-Dilithium 后量子数字签名算法中的拒绝采样技术 题目描述： 在CRYSTALS-Dilithium后量子数字签名算法中，拒绝采样（Rejection Sampling）是签名生成过程的关键步骤。其核心问题是如何通过拒绝采样技术，确保签名向量的分布与密钥无关，从而避免私钥信息通过签名向量泄露。请详细解释Dilithium中拒绝采样的具体目标、实现步骤及其数学原理。 解题过程： 背景与目标 Dilithium基于模数学习问题（MLWE/LWE），签名时需生成一个向量z = y + c·s1（其中y是临时噪声，c是挑战哈希值，s1是私钥部分）。直接发布z会泄露s1的分布信息，因为z的分布会因s1而异。拒绝采样的目标是：通过设定阈值β，仅当z的所有系数均满足|z_ i| ≤ β - U（U为安全参数）时才接受该签名，使得输出签名z的统计分布近似与s1无关（即呈均匀分布）。 拒绝采样参数设置 设定阈值β：根据方案安全参数，β通常取γ1 - U（γ1为y的系数范围边界，U为缓冲值） 目标分布：理想情况下，z应服从均匀分布D_ σ（离散高斯分布或均匀分布），但实际分布受s1影响。拒绝采样通过概率性丢弃某些z，使输出分布被"修正"为目标分布。 具体采样步骤 a. 生成临时噪声 ：签名者首先生成临时向量y，其系数从均匀分布[ -γ1, γ1 ]中随机采样。 b. 计算候选签名 ：计算z = y + c·s1，其中c为挑战值（由消息和公钥哈希生成），s1为私钥的小多项式向量。 c. 系数范围检查 ：对z的每个系数z_ i，检查是否满足|z_ i| ≤ β - U。若任一系数不满足，则返回步骤a重新生成y。 d. 高比特验证 ：计算w1 = HighBits(A·z - c·t, 2γ2)（A为公钥矩阵，t为公钥向量），验证w1是否与承诺值w1'一致。若不一致，也拒绝。 数学原理：分布修正 设实际分布为P_ z(z) = P_ y(z - c·s1)，目标分布为Q(z) = 1/(2β)^n（均匀分布）。 接受概率为min(1, Q(z)/M·P_ z(z))，其中M为放大因子。Dilithium通过设定β使得P_ z(z) ≤ M·Q(z)恒成立，此时接受概率简化为Q(z)/P_ z(z) ∝ 1/P_ z(z)。 最终输出分布为P_ acc(z) = P_ z(z) · (Q(z)/P_ z(z)) = Q(z)，即与s1无关的均匀分布。 安全性与效率平衡 阈值β需足够大以确保接受概率不过低（避免签名时间过长），但也不能过大以免签名向量泄露私钥信息。 实际参数中，通过调整U和γ1，使接受概率约1/2至2/3，保证实用性的同时满足零知识性。 通过以上步骤，Dilithium的签名在统计上隐藏了私钥信息，即使攻击者获得大量签名，也无法推断出s1的分布特征。