假设量子计算机签名后，基于散列的签名方案有多安全？

Question

考虑一个基于散列的签名方案，它需要接受要签名的任意长度消息的k-bit哈希(例如Lamport一次性签名方案)。我的理解是，假设此步骤是签名方案的最弱环节，并且所使用的哈希函数具有抗冲突性，则该签名方案提供了签名前的k-bit安全性和签名后的k/2-bit安全性(因为任何试图伪造签名的人在试图签名的任何消息的散列时，平均都可以免费获得一半的比特)。

那么，我的问题是，如果一个对手试图用目前已知的寻找哈希冲突的最佳量子算法来寻找与量子计算机的哈希冲突，那么这种签名方案的安全性又是什么呢？

这个问题的答案是：

基于散列的签名方案LMS/LMS易受预图像/第二预图像攻击？

提供有用的信息，并暗示此方案仍将提供k/2-bit安全性，如

“Grover的算法允许我们在量子世界中找到具有Θ(2^{/2})复杂性的前置图像，然而，生日悖论已经限制了经典世界中碰撞抵抗的复杂性。(在量子世界中，我们不知道有更好的方法来解决这个问题。”

引用这份文件：

1

这似乎揭穿了本文的说法：

2

这就提出了一种更有效地发现碰撞的量子算法。

所提出的论点似乎是有意义的(即所提出的工作使人认为交流基本上是自由的这一不现实的假设)，但我在这方面的知识还不足以更彻底地分析它。对于那些人来说:这个论点有效吗？量子密码学研究者的普遍共识是什么？

最后，提交人还声明如下：

“事实上，时间2b/3已经是由尺寸为2b/6的非量子机器实现的，而小时间的2b/4已经由尺寸为2b/4的非量子机器实现了。任何害怕量子哈希碰撞算法的人都对非量子哈希碰撞算法有更多的恐惧。”

作者在这里指的是什么算法？这是否意味着即使没有量子计算机，使用k位哈希函数的签名方案的后签名安全性已经低于k/2位？

Answer 1

有两件事：

• “基于甲骨文的碰撞发现问题对于量子计算机来说有多难”这个问题是一个悬而未决的问题；我们知道它介于O(\sqrt[3]{n})和O(\sqrt{n})之间(我记得有一篇文章显示O(\sqrt[3]{n})的查询是下限，但我忘了那是什么纸)--我们不知道它的实际范围在哪里。Brassard等人展示了一种发现与O(\sqrt[3]{n})甲骨文查询冲突的算法；但是Dan指出，与该算法相关的其他成本实际上比并行运行大量的二次预图像查找器更昂贵。目前尚不清楚是否存在另一种使用o(\sqrt{n}) Oracle查询的算法，并且没有Brassard算法所具有的其他开销。
• 当前的三种“基于哈希的签名标准”，即LMS、XMSS和Sphincs+实际上并不依赖于冲突抵抗，即使在进行消息的初始哈希时也是如此。这三个步骤都是，当给签名者一个消息M时，签名者选择一个不可预测的R，然后计算\text{Hash}(R + M) (然后将该哈希用于签名操作的其余部分)。如果对手提交了要签名的消息，则他不知道签名者将选择的值R；相反，要执行碰撞攻击，他需要选择具有非平凡概率(考虑到R的概率分布)的\text{Hash}(R + M) = \text{Hash}(R + M')的两种不同的消息，这似乎比找到冲突要困难得多。

Brassard算法本质上是一种大规模的多目标二次预图像攻击，Dan的抱怨是，在一个大的稀疏非结构化空间上进行识别的量子逻辑是相当昂贵的。在一本未发表的著作中，我研究了Brassard算法，并在“每个搜索者的目标数”和“搜索者的数量”之间搜索“甜蜜点”--基于已发布的SHA-256量子电路和我绘制的目标识别电路，我得出的结论是，这使得问题的攻击成本比单个预图像问题低了大约1000倍(而且每个搜索者的目标约为100万个目标)。

对于那些不熟悉小符号的人来说，o(\sqrt{n})的意思是“小于c\sqrt{n}查询，对于任何c > 0 (只要n足够大，而”足够大“的含义取决于c)。