按年被提到
20162016 · 3 次2026
物理与量子›量子计算·arXiv:1602.05973 · quant-ph

Breaking Symmetric Cryptosystems using Quantum Period Finding

用量子周期查找攻破对称密码系统
Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia · 2016

用 Simon 算法在量子查询模型下攻破 CBC-MAC、GCM 等对称密码模式

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2016-02-22 · 最近 2016-06-16
3不同的人
3活跃月份
3讨论串
347被引(OpenAlex)

考虑攻击者能以量子叠加态查询密码原语的模型,用 Simon 算法(最简单的量子周期查找算法)加速基于碰撞的经典攻击:存在隐含周期时,找碰撞只需 O(n) 次查询,而经典需要 Ω(2^{n/2}) 次。结果表明 CBC-MAC、PMAC、GMAC、GCM、OCB 等常用的认证与认证加密模式在该模型下被完全攻破,许多 CAESAR 候选方案也受影响,Simon 算法还能对滑动攻击实现指数级加速。

HN 为什么提它

评论者把它作为一个近期进展很快的例子,说明量子计算对对称密码的威胁正被理论计算机科学界积极分析。

方法难度 5 / 5约 60 分钟经得起时间
读之前最好知道
1对称密码与认证加密模式
2量子计算基础
3Simon 算法
4伪随机函数(PRF)
5滑动攻击(slide attack)

学习路径

读这篇之前,按顺序读书架上的 2 篇 · 参考文献来自 OpenAlex,顺序和要点由 Claude Code 排出

先了解量子计算的能力边界与查询模型,再读 Shor 算法的周期查找思想,最后看如何把类似技巧用于攻破对称密码。

  1. 1

    说明量子计算在黑盒查询下的能力与局限,是量子查询模型的背景

    读抓住量子查询复杂度和黑盒下能做什么、不能做什么的结论

  2. 2
    Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer量子计算机上素因数分解与离散对数的多项式时间算法 · 1995

    周期查找思想的源头,目标论文用 Simon 算法做类似的周期查找

    读看量子傅里叶变换如何提取周期,不必深究数论部分

  3. 3
    Breaking Symmetric Cryptosystems using Quantum Period Finding用量子周期查找攻破对称密码系统 · 2016 · 就是这篇

    把量子周期查找用到对称密码的叠加态查询攻击

    读看攻击模型(叠加态访问预言机)以及对 CBC-MAC、GCM 的具体攻击

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用johncolanduoni · 2016-06

“Some good examples are the recent (quite rapid) progress in analyzing symmetric cryptography schemes' vulnerability to attacks by a quantum computers[1].”

举它作例子:量子计算对对称密码的攻击分析进展很快
Why Philosophers Should Care About Computational Complexity (2011) [pdf]原评论 ↗
被提交为 story · 2 次