与流行的迷信相反，AES 128 在后量子世界中依然很好

Source: Ars Technica

概览

周一，Filippo Valsorda 终于把多年对广泛误解的沮丧倾注到一篇博客文章中，标题为《量子计算机对 128 位对称密钥并不构成威胁》。

“人们常误以为量子计算机会‘把’对称密钥的安全性减半，因而需要 256 位密钥才能获得 128 位安全性。这并不是对量子算法加速的准确解释，也没有出现在任何合规要求中，而且会把精力从真正必要的后量子迁移工作上转移走。” – Filippo Valsorda

关于量子安全的误解

论点的容易部分是上面的陈述。更困难的部分是解释为何这种误解是错误的数学和物理原理。

经典 vs. 量子 暴力搜索

经典并行化

经典计算机可以同时执行多个搜索。这使得大型任务可以被拆分成更小的子任务并行运行，从而更快完成整体工作。

Grover 算法与并行化

相比之下，Grover 算法需要长时间的串行计算，每次搜索只能一次完成。正如 Valsorda 在一次访谈中解释的：

“Grover 的特别之处在于，当你对它进行并行化时，它相对于非量子算法的优势会变小。”

小密钥空间的示例

• 假设一个锁有 256 种可能的组合。
• 正常（经典）攻击需要 256 次尝试。
• 如果你找来三位朋友，每人尝试 64 次 → 256 / 4 = 64 次/人。这就是经典并行化。

使用 Grover 算法时：

• 理论上你可以顺序进行 √256 = 16 次尝试。
• 如果再次请三位朋友帮忙，每人必须做 √256 / 4 = 8 次尝试。
• 总工作量：8 × 4 = 32 次尝试，多于 你单独完成的 16 次。请求帮助并行化攻击实际上会让它更慢——这在经典攻击中从未发生过。

对 AES‑128 安全性的影响

在实际情境下，密钥空间天文般庞大。如果我们对攻击者施加合理约束（例如攻击必须在 10 年内完成），所需的总工作量远大于 2⁶⁴。此外，朴素的 2⁶⁴ 估计假设你可以把 AES 当作单个量子比特上的单次操作，而事实并非如此。

将这些观察结果结合起来，基于 Grover 的对 AES‑128 的攻击有效成本大约提升到 2¹⁰⁴ 次操作（前后略有浮动），远超任何实际安全阈值。

专家评论

Sophie Schmieg，Google 的高级密码学工程师，总结了现状：

[Insert Sophie Schmieg’s quoted explanation here if available]

专家们的共识是，AES‑128 在可预见的量子攻击下仍然安全，仅仅因为量子担忧而推动使用 256 位对称密钥是没有必要的。