CRYSTALS-Dilithium 后量子数字签名算法中的拒绝采样技术 题目描述 CRYSTALS-Dilithium 是一种基于格的后量子数字签名算法，其安全性依赖于模块格上的短整数解问题（MLWE和MSIS）。在签名生成过程中，为了避免私钥信息通过签名值泄露，Dilithium 使用拒绝采样技术确保签名值的分布与私钥无关。本题要求详解拒绝采样技术的原理、在Dilithium 中的具体实现步骤及其安全性作用。 解题过程 拒绝采样的核心目标 在签名过程中，签名值可能包含私钥的线性信息（例如：\( z = y + c \cdot s \)，其中 \( s \) 是私钥，\( y \) 是临时随机值，\( c \) 是挑战哈希值）。 若直接输出 \( z \)，攻击者可能通过多次签名统计恢复私钥 \( s \)。 拒绝采样的目标：确保签名值 \( z \) 的分布与私钥 \( s \) 无关，仅依赖于公开参数。 Dilithium 中的签名生成流程（简化版） 设私钥为短向量 \( s \)，公钥为矩阵 \( A \) 和 \( t = A \cdot s \)。 签名步骤： 生成临时随机向量 \( y \)（服从均匀分布或高斯分布，范围受限）。 计算 \( w = A \cdot y \)，并哈希得到挑战值 \( c = H(w, \text{消息}) \)。 计算 \( z = y + c \cdot s \)。 关键步骤 ：检查 \( z \) 是否满足预设范数（如无穷范数 \( \|z\|_ \infty \leq \beta \)）。若满足，输出签名 \( (z, c) \)；否则重新生成 \( y \) 并重复流程。 拒绝采样的具体实现 参数设置 ：Dilithium 设定阈值 \( \beta \)，要求 \( \|z\|_ \infty \leq \beta \)。 为什么需要范数限制 ： 若 \( z \) 的范数过大，其分布可能泄露 \( s \) 的信息（因为 \( z \) 的分布与 \( s \) 相关）。 通过限制 \( z \) 的范数，可证明 \( z \) 的分布近似于 \( y \) 的分布（与私钥无关），从而避免信息泄露。 安全性证明 ： 理想情况下，\( z \) 应服从与 \( y \) 相同的分布（即均匀随机分布）。 由于 \( c \cdot s \) 的范数较小，通过合理选择 \( \beta \) 和 \( y \) 的范围，可确保 \( z \) 的分布与 \( y \) 的分布统计不可区分。 拒绝采样的效率与优化 重复采样概率 ：若 \( \beta \) 设置过小，拒绝概率高，导致签名效率低；若 \( \beta \) 过大，则安全性降低。 Dilithium 通过调整参数（如 \( y \) 的分布范围）平衡安全性与效率，通常重复采样概率控制在 2–3 次以内。 实际实现中，\( y \) 采用中心二项分布而非均匀分布，以减小范数并提高采样效率。 与侧信道攻击的关联 拒绝采样可抵抗定时攻击：无论签名是否被拒绝，算法均使用恒定时间操作，避免通过执行时间推断私钥信息。 若未使用拒绝采样，攻击者可能通过分析签名值的分布实施统计攻击（如“隐藏数字问题”攻击）。 总结 拒绝采样是 Dilithium 实现安全签名的核心技术，它通过约束中间值的范数，切断签名值与私钥的统计关联，同时兼顾效率与侧信道防护。理解这一技术需掌握范数控制、分布模拟和参数权衡三个关键点。