# How secure is a hash based signature scheme after signing assuming quantum computers?

Consider a hash based signature scheme that requires taking the $$k$$-bit hash of an arbitrary length message to be signed (e.g. Lamport one-time signature scheme). My understanding is, assuming that this step is the weakest point of the signature scheme and that the hash function used is collision resistant, this signature scheme offers $$k$$-bit security before signing and $$k/2$$-bit security after signing (since anyone trying to forge a signature will on average get half the bits for free when taking the hash of any message they are trying to sign).

My question, then, is what is the security of such a signature scheme if an adversary is trying to find a hash collision with a quantum computer using the best quantum algorithm currently known for finding hash collisions?

provides helpful information and implies that this scheme would still offer $$k/2$$-bit security as

"Grover’s algorithm allows us to find preimages with a complexity of $$Θ(2^{𝑛/2})$$ in a quantum world, however the birthday paradox bounds the complexity of the collision-resistance in the classical world already. (And we don't know a better way to go around it in the quantum world..."

citing this paper:

which appears to debunk the claims of this paper:

that presents a quantum algorithm to find collisions more efficiently.

The argument presented by [1] seems to make sense (i.e. that the work presented in [2] makes the unrealistic assumption that communication is essentially free), but I am not knowledgeable enough in this area to analyze it more thoroughly. To those who are: is this argument valid? What is the general consensus of quantum cryptography researchers?

Finally, the author in [1] also states the following:

"In fact, time $$2b/3$$ had already been achieved by non-quantum machines of size just $$2b/6$$, and smaller time $$2b/4$$ had already been achieved by non-quantum machines of size $$2b/4$$. Anyone afraid of quantum hash-collision algorithms already has much more to fear from non-quantum hash-collision algorithms."

What algorithms is the author referring to here? Does this mean that the post-sigining security of signature schemes using a k-bit hash function is already less than $$k/2$$ bits even without quantum computers?

• The question "how hard is the oracle-based collision-finding problem be for a Quantum Computer" is an open question; we know that it is somewhere between $$O(\sqrt[3]{n})$$ and $$O(\sqrt{n})$$ effort (I recall a paper showing that $$O(\sqrt[3]{n})$$ Oracle queries is the lower bound, but I forget what paper that was) - we don't know where in the range it actually is. Brassard et al showed an algorithm that found collisions with $$O(\sqrt[3]{n})$$ Oracle queries; however Dan pointed out that the other costs associated with the algorithm made it actually more expensive than just running a large number of second-preimage finders in parallel [1]. What is currently unknown whether there exists another algorithm that uses $$o(\sqrt{n})$$ Oracle queries [2], and doesn't have the other expenses that the Brassard algorithm has...
• The three current 'hash based signature standards', namely, LMS, XMSS and Sphincs+ don't actually rely on collision resistance, even when doing the initial hash of the message. What all three do is, when the signer is given a message $$M$$, the signer selects an unpredictable $$R$$ and then computes $$\text{Hash}(R + M)$$ (and then uses that hash for the rest of the signature operation). If the adversary submits a message to be signed, he doesn't know what the value $$R$$ that the signer will select; instead, to perform a collision attack, he would need to select two distinct messages $$M, M'$$ for which $$\text{Hash}(R + M) = \text{Hash}(R + M')$$ with nontrivial probability (given the probability distribution of $$R$$), and that would appear to be far more difficult than finding a collision.
[2] For those who are unfamiliar with little-oh notation, $$o(\sqrt{n})$$ means 'fewer than $$c\sqrt{n}$$ queries, for any $$c > 0$$ (as long as $$n$$ is large enough, and the meaning of "large enough" depends on $$n$$). More colloquially, $$o(\sqrt{n})$$ means 'grows slower than $$\sqrt{n}$$'