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

Question

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?

The answer to this question:

Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

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:

[1] https://cr.yp.to/hash/collisioncost-20090517.pdf

which appears to debunk the claims of this paper:

[2] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.5265&rep=rep1&type=pdf

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?

Answer 1

Two things:

• 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.

---

[1] The Brassard algorithm is essentially a large multi-target second preimage attack, and Dan's complaint is that the quantum logic to do a recognization over a large sparse unstructured space is quite expensive. In an unpublished work, I looked at the Brassard algorithm, and searched for the 'sweet spot' between 'number of targets per searcher' and 'number of searchers' - based on the published SHA-256 Quantum circuit, and a sketched out target recognizer circuit I drew, I came to the conclusion that this made the problem circa a factor of 1000 cheaper to attack than a single preimage problem (and the sweet spot was circa a million targets per searcher).

[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 $c$). More colloquially, $o(\sqrt{n})$ means 'grows slower than $\sqrt{n}$'