本文档不符合“ Blue Midnight Wish”，
（强调我的）
最有趣的要点是……
特别地，这是针对224位Keccak的$ 2 ^ {224} $像前电阻的索赔。没有关于量子计算机的影响的警告：Keccak声称“预成像电阻”，而不仅仅是量子预成像电阻。
和
>每次攻击都使用大约$ 2 ^ {112} $次迭代，从而破坏了针对每个函数的$ 2 ^ {224} $个图像前电阻要求。每个迭代的确切复杂度以及所需的qubit数量因函数而异，但其范围要比$ 2 ^ {112} $复杂度差距小得多。
这与我在NIST验证并选择Keccak作为胜出的SHA3提案后的某些期望相矛盾。同样，这也突显了我怀疑与Keccak论文中错误的“量子后足够”主张有关的正确性。 （您可能还记得我以前的问题，我已经怀疑Keccak的另一种量子后说法是不正确的：KECCAK（SHA3）声称256位安全强度“量子后足够”的确切依据是什么？）
结果，我得到了两个相关但又有些不同的问题：
就目前而言，伯恩斯坦证明了格罗弗的算法可以成功地对SHA3候选对象（包括SHA3决赛入围者Keccak）进行像前攻击，据我从Crypto.SE的不同回复中了解到：如果被破坏，就被破坏了……不无论中断是理论上的还是牵强的，中断都是一个明显的警告信号。即使我忽略了这一点，仍然存在问题，即这些SHA3论文的主张是否可以完全可信。我的意思是，我做了相当多的研究，但我经常注意到无法证明索赔。特别是关于Keccak。 （请参阅我的问题和答案：是否可以实际验证“海绵功能”的安全要求？）
我是否应该知道哪些论文与伯恩斯坦论文的发现相矛盾？
为了产生疑问，我不会开始考虑NIST在他们的SHA3搜寻中是否会受到影响，因为类似的加密新闻已经引起媒体的广泛关注。但是，我想知道为什么伯恩斯坦的发现似乎被忽略了，我想理解为什么NIST选择忽略大多数SHA3提案可能遭受量子攻击的事实。
NIST是否真的验证了有关后量子安全性的任何建议（以及论文中的相关声明），还是在其SHA3安全性评估期间只是忽略了量子计算？如果忽略了量子，这样做的动机是什么？
（也许您可以指向我确认NIST是否验证了量子后方面的参考文献……我找不到任何东西。）
#1 楼
使用任何$ n $位哈希，可以：在经典计算机上用工作$ 2 ^ n $查找原像，在量子计算机上用工作$ 2 ^ {n / 2} $查找原像
在经典计算机上查找与工作$ 2 ^ {n / 2} $的冲突，并在量子计算机上查找与$ 2 ^ {n / 3} $的冲突
我想强调一下，这些是始终有效的通用攻击，使用哪种具体哈希函数的问题。 Grover的算法与经典蛮力在量子力学上等效。
对于海绵（包括keccak和cubehash），如果$ c $小于$ 2n $，还存在其他通用攻击：
在经典计算机上用工作$ 2 ^ {c / 2} $查找原像，在量子计算机上用$ 2 ^ {c / 3} $查找原像
用工作$ 2 ^ {c / 2} $查找碰撞现在在经典计算机上，使用量子计算机在$ 2 ^ {c / 3} $上运行
现在，SHA-3候选人的几位作者只是写了“带有工作$ 2 ^ n $的原像”和“与工作$ 2 ^ {n / 2} $”，而没有明确指出这些声明仅适用于经典计算机。这些声明的意图显然是“比蛮力攻击要快”，但它们只是明确地将其阐明为经典计算机。
一些作者（如DJB本人）分别为经典计算机和量子计算机，有人简单地写道“通常使用安全级别”。哈希。同样的攻击也适用于cubehash，只是它们不违反其安全性声明。
本文的简单观察是，有些论文没有提到通用量子计算机攻击，也没有提及明确将他们的主张限制为经典计算机。那是那些论文中很小的草率，我希望每个密码学家都知道这些主张不适用于量子计算机。
本文不包含任何新的攻击或发现，仅包含nitpicks。
评论
尽管结构化的前映像攻击结果很有趣，但我看不到2 ^ 112时间内对224位哈希函数进行常规的前映像攻击与常规的Grover算法和常规ol'有何不同。在我看来，DJB的论文对提交物中的内容不屑一顾，因为他们没有在安全声明中包括量子攻击……肯定是2.5页的本质上是复制/粘贴的材料使事情看起来像这样。它被忽略，因为它不是对算法本身的攻击。这是对描述这些算法的论文中草率的安全性声明的攻击。本质上，他们针对经典计算机写了安全声明，但没有说明这些声明仅适用于经典计算机（这对任何密码学家来说都是显而易见的）。我怀疑这只是DJB对NIST坚持$ 2 ^ n $的原像抵抗感到生气的产品，而cubehash不能提供令人满意的性能。具有讽刺意味的是，他们想在keccak获胜后取消这一要求。
@CodesInChaos那么，您是说从传统意义上讲还是可以的，但是鉴于没有提出量子论后的主张，我们应该忽略QC带来的漏洞？我想我问的是与电子寿司相同的问题，启用量子的攻击有效吗？
@CodesInChaos我明白你现在在说什么。他正在做数学运算，将$ 2 ^ n $经典值与$ 2 ^ {n / 2} $量子值进行比较...。这并不是说攻击无效，而是已经被理解了，对吧？
@floorcat您好！ SHA-3的安全性完全位于theta（）上，您可以将其带到银行。术语“海绵构造”完全没有意义，兜售FIPS-202的任何人都不知道。坦白地说，我为NIST感到尴尬。 <2 ^（n / 2）我可以证明。