该论文研究量子黑盒搜索在带有概率性“先验建议”(advice)时的精确加速幅度问题。经典情况下 Grover 算法提供最优的平方加速,但在密码分析中搜索常附带关于候选者的额外概率信息,尤其是乘积形式的信息(例如对相互独立密钥坐标的侧信道泄漏)。经典最优策略是按似然顺序猜测,Montanaro 已证明量子情形下可达到最优期望查询复杂度,在任意非均匀建议分布上优于朴素 Grover(相差常数因子)。然而此前缺少一种有限规模(finite-size)方法,用于针对给定建议分布定量评估“量子-经典猜测矩分离”所带来的加速指数。本文针对乘积分布建议填补该空白,并细化了 Bashiri 等人此前基于熵的估计。核心方法是将经典与量子猜测矩归约为“一维 surprisal(惊奇度)分布”的泛函;对乘积建议,该分布可由各坐标 surprisal 规律卷积得到。当 surprisal 落在公共算术网格上(可通约情形),对数矩乃至加速指数可用有限求和精确计算而无离散化误差,并借助指数倾斜(exponential tilting)保证数值稳定。对一般乘积建议,则将 surprisal 离散化到公共网格,并给出由此产生的分箱误差的后验界。作者将框架应用于:种子与分组密码密钥的冷启动(cold-boot)泄漏、模板攻击后验,以及按 ML-KEM 与 ML-DSA 上 Keccak 侧信道攻击所报告残差秩校准的合成独立同分布伯努利后验。结果显示在多种偏斜建议场景下加速指数显著超过 2,在这些合成模型中最高达 3.97;并且包含此前熵界无法确立指数高于 2 的情形。该工作为量化“泄漏结构如何放大量子搜索优势”提供了可认证的评估工具,适合量子密码分析、侧信道与后量子迁移安全评估方向的研究者与安全工程师阅读。
💡 推荐理由: 侧信道泄漏常被默认为只影响经典安全;本文给出有限规模、可认证的方法量化泄漏如何把量子搜索加速从平方推到更高指数,直接影响后量子算法(ML-KEM/ML-DSA)实现侧信道防护的威胁建模与安全余量评估。
🎯 建议动作: 研究跟进:将论文的评估框架纳入内部后量子/侧信道威胁建模流程,重点关注 ML-KEM、ML-DSA 实现中 Keccak 泄漏模型的适用性。