像Ambainis这样的量子碰撞搜索算法对抗碰撞哈希函数有什么影响？

Question

我刚刚偶然发现了一系列2017年的论文，关于如何将Ambainis量子碰撞发现算法应用于散列函数。(免责声明:我尚未全部阅读)：

• 海绵结构的后量子安全性
• 非均匀随机函数中的量子碰撞发现
• 一种有效的量子碰撞搜索算法及其对对称密码的启示

从后者：

与经典的$O(2^{n/2})$O(2^{n/2})$相比，量子碰撞搜索具有较高的查询复杂度(2^{n/3})。..。我们的算法是第一个在单处理器的简单设置下，提出一种改进$O(2^{n/2})$的时间复杂度的算法。

My问题：关注这项研究的人能否讨论：

1. 对安全从业者的影响..。我们需要三倍的哈希长度而不是加倍吗？
2. 这类量子碰撞发现攻击只对海绵结构和SHA-3有效，还是更广泛地适用于哈希函数？

在这些2017年论文之前提出和回答的相关问题：

• 2014年年
• 2011年年

Answer 1

查询复杂性(即机器将函数计算为黑匣子的次数)可能是O(2^{n/3})，但这并不是算法的唯一成本:机器的大小和运行它的时间也要计算在内。

So目前还存在 no含义用于抗碰撞哈希函数的安全参数的of量子算法。经典的算法仍然是最便宜的 <#>algorithms，即使具有Grover能力的量子计算机仅仅存在，也仍然是如此。

最初的Brassard算法[1]预先计算了H(x_1), H(x_2), \dots, H(x_{2^{n/3}})并将它们存储在一个表C中；然后它应用Grover在f(y) = [H(y) \in C]函数下找到1的预映像，这揭示了H中的冲突。

即使查找表的通信开销为零(这似乎是不现实的)，但这需要花费O(2^{n/3})空间，并且该算法在f下查找1的预图像之前，需要进行O(2^{n/3})甲骨文评估，对H进行的O(2^{n/3})评估，以及O(2^{2n/3})-far的总面积*时间开销大于O(2^{n/2})区域*标准经典算法(如van cost和基于并行\rho[2]的Wiener碰撞搜索算法)的时间开销。

该算法的变体已经被提出，但到目前为止，它们中没有一个能超过任何看似合理的代价模型中最好的经典算法的O(2^{n/2})成本，即使量子比特运算并不比比特运算更昂贵--而且在任何看似合理的成本模型[3]中，它们中的大多数都要昂贵得多。有关成本模型中的一些拟议算法和问题的概述，以及更广泛的上下文，请参见这里。

Ambainis算法[4]采用一种稍微不同的量子随机游走方法，如果O(M^{2/3})时间中的M元素序列中存在重复，则该算法可以转换为在O(2^{m/3})查询中的m位到n-bit函数中寻找碰撞的算法。但是，它还需要维护一个数据结构，在整个算法中保存所有O(M^{2/3})查询。因此，基于它的碰撞搜索的面积*时间代价是O(2^{2m/3})，它仍然远远超过传统的碰撞搜索的O(2^{n/2})代价，对于任何输入大小的m，在n-bit输出中产生碰撞的概率都是不可忽略的。查卡科夫斯基等人。描述[5]是一种通用的方法，可以将其应用到具有c-bit容量的海绵上，从而生成n-bit输出成本O(\min\{2^{2c/3}, 2^{2n/3}\})，这在本质上是您所期望的。

而且，由于一般量子碰撞搜索的查询复杂性有一个下界[6] of \Omega((2^n/r)^{1/3})，如果r是碰撞前图像数量的上限，除非存储成本有显著突破，否则这种情况似乎不太可能很快改变。