布莱克家族的后量子安全

Question

有没有证据证明布莱克(包括2和3)是量子后安全的？我们知道，作为默克-达莫德(适当的填充)保存塌陷，sha2是后量子安全。我知道，基于海绵的sha3竞赛冠军没有这样的证据。既然布雷克没有使用这两种构造，就没有任何关于它的构造是否是量子后安全的研究？

Answer 1

没有证据，只有进步。BLAKE2不是完全MD，而是扩展MD以消除问题的海法，BLAKE3是一个并行散列。

Quamtum碰撞攻击费用

最著名的一般量子碰撞是由于\mathcal{O}(2^{n/3})时间的布拉萨德-霍耶-塔普 (BHT)。它通常是广告(即使是由NIST)的时间，但我们也有其他费用。BHT构建了一个庞大的大小\mathcal{O}(2^{n/3})表，然后使用成本\mathcal{O}(2^{n/3})运行Grover的算法，从而使总成本\mathcal{O}(2^{2n/3})

所有的变体，包括仍然围绕着安贝尼斯( Ambainis算法)的\mathcal{O}(2^{2n/3})，都没有降低经典攻击成本\mathcal{O}(2^{n/2})的成本壁垒

我们已经知道有一个查询的数的下界，一个通用的算法mus采取\Omega(2^{n/3})。

所以我们看不到QC的威胁。

量子预图像攻击代价

Grover的算法是\mathcal{O}-time的最佳通用算法，不像BHT或其他算法那样占用太多空间。但是散列函数的顺序求值是其中的一个问题。即使你评估一个纳米秒，你最多可以在一年内得到2^{54}，你需要2^{64}-year来找到预图像。其他费用不包括在内。但是，我们可以运行Grover并行算法，但其优势与传统的不一样，您将从k机器上获得更快的\sqrt k速度。

因此，如果您有256位的输出，您将是安全的量子攻击哈希函数。

Collapsibility

Unruh将可折叠性定义为哈希函数的抗碰撞能力的量子等效。

• 2016年，计算约束量子承诺

非正式地说，对于密码散列函数，可折叠性要求输出散列值的对手和相应的预图像的叠加不能判断是否测量到了叠加。

Unruh的结果是

证明了存在一个抗冲突的散列函数，因此可以在经典的承诺方案中安全地使用，但是当在量子设置中使用该承诺方案时，它是不安全的。

所以我们有单向关系；

-Collapsability意味着抗碰撞能力。

Fer显示

他将该方法应用于Merkle̊rd和海绵散列结构，证明了如果底层压缩函数是，则它们正在崩溃。

冈斯和曼宁表明

1. 固定长度的二叉树散列正在折叠。
2. 带域分离的变长树散列是折叠的。