引用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].”
举它作例子:量子计算对对称密码的攻击分析进展很快
用 Simon 算法在量子查询模型下攻破 CBC-MAC、GCM 等对称密码模式
考虑攻击者能以量子叠加态查询密码原语的模型,用 Simon 算法(最简单的量子周期查找算法)加速基于碰撞的经典攻击:存在隐含周期时,找碰撞只需 O(n) 次查询,而经典需要 Ω(2^{n/2}) 次。结果表明 CBC-MAC、PMAC、GMAC、GCM、OCB 等常用的认证与认证加密模式在该模型下被完全攻破,许多 CAESAR 候选方案也受影响,Simon 算法还能对滑动攻击实现指数级加速。
评论者把它作为一个近期进展很快的例子,说明量子计算对对称密码的威胁正被理论计算机科学界积极分析。
先了解量子计算的能力边界与查询模型,再读 Shor 算法的周期查找思想,最后看如何把类似技巧用于攻破对称密码。
说明量子计算在黑盒查询下的能力与局限,是量子查询模型的背景
读抓住量子查询复杂度和黑盒下能做什么、不能做什么的结论
周期查找思想的源头,目标论文用 Simon 算法做类似的周期查找
读看量子傅里叶变换如何提取周期,不必深究数论部分
把量子周期查找用到对称密码的叠加态查询攻击
读看攻击模型(叠加态访问预言机)以及对 CBC-MAC、GCM 的具体攻击
“Some good examples are the recent (quite rapid) progress in analyzing symmetric cryptography schemes' vulnerability to attacks by a quantum computers[1].”