单表替换密码量子密钥恢复攻击的效率建模与模拟——基于Grover算法的预言机成本解析与QUBO退火对比

《Scientific Reports》：Statistical-Plausibility Oracles for Quantum Key-Recovery: A Corpus-Driven Complexity Analysis

　　摘要基于Grover的量子密钥恢复攻击的效率不仅由密钥空间的大小决定，还取决于预言机将哪些密钥判定为合理的可能性比例。对于依据统计合理性判断密钥的密码，该比例反映了语言对允许字符序列的约束强度，以及正如我们通过实验所展示的，截获密文的长度。我们通过一项语料库驱动的关于单表替换密码的实验来研究这一问题，使用了在四篇文艺复兴时期意大利语文本上训练的字符三元组语言模型。预言机阈值被定义为最佳观测解密得分的一个标量分数（\(S_{\max}/\tau\)），从而产生一个随密码长度自然缩放的阈值。在一个21个字母的字母表上，我们估计了密文长度和严格性参数各种组合下的合理密钥比例，并解析地推导出Grover预言机成本。对两个缩减字母表大小下完全枚举的密钥空间进行完整的Grover态矢量模拟，证实了预言机的接受密度随密文长度而变化，这由评分分布集中度与最佳观测得分锚点\(S_{\max}\)之间的相互作用驱动，并且在整个过程中Boyer迭代公式都提供了一个可靠的近最优停止准则。在相同评分函数下进行的并行QUBO退火实验在字母表压缩下表现出截然不同的失败模式，确立了两种攻击范式作为互补景观特性的探测器。跨越不同字母表大小的解析投影显示，Grover预言机调用次数的增长远远慢于密钥空间，大约相差三个数量级——而密钥空间基数增长了16个数量级，因此相对于经典随机搜索的量子加速随着字母表大小的增加而增大，在完整的21个字母规模上达到数千倍。