摘要
拒绝采样是基于格密码的签名方案（如遵循Fiat-Shamir中止范式的ML-DSA/CRYSTALS-Dilithium）中的关键安全机制。该技术将秘密相关的签名样本转换为统计上接近秘密无关分布的样本（在随机预言机模型中）。虽然许多侧信道攻击直接针对敏感数据（如随机数、密钥和解密承诺），但针对拒绝采样相关潜在泄漏的研究较少。值得注意的是，Karabulut等人在HOST 2021会议上证明，拒绝签名的挑战泄漏会削弱但无法完全破坏Dilithium方案的安全性。

受此启发，我们将密钥恢复问题（从拒绝采样泄漏中）转化为整数线性规划问题，其中唯一汉明权重的拒绝响应设置了挑战与私钥乘积的上下界约束。我们正式研究了该问题的最坏情况复杂度，并通过实验验证了拒绝签名挑战攻击的实用性。对于Dilithium-2/3/5的所有三个安全级别，我们的攻击在秒或分钟级别内以100%的成功率恢复私钥。

本攻击利用拒绝签名的挑战和响应信息，因此我们提出通过利用数论变换操作和响应生成过程相关函数的单条迹侧信道泄漏来提取这些信息。通过在ARM Cortex-M4微控制器上的实际功耗测试，我们证明了这种拒绝签名挑战攻击的实用性。据我们所知，这是首个针对ML-DSA/Dilithium拒绝采样过程的实用高效侧信道密钥恢复攻击。此外，我们还讨论了缓解此安全问题的对策。