Proof of quantum safety of the Merkle signature scheme

Question

The Wikipedia article about the Merkle signature scheme claims that it is

very adjustable and resistant against quantum computing.

What proof is there of this?

Answer 1

The Merkle signature scheme is based on a hash tree over one-time signatures, e.g. using Lamport's scheme.

Roughly speaking, both Lamport's scheme and the hash tree are secure as long as the hash function is resistant to preimages and second-preimages. There can be details because when using hash trees, preimage attacks are often multi-target, i.e. there are several values for which the attacker would like a preimage, and a preimage for any one of them would yield a success. Yet, preimage resistance still leads the scheme overall robustness.

Against quantum computing, a "perfect" hash function of output size n bits still offers resistance 2^n/2. E.g. with SHA-256 (a 256-bit output), the best quantum computer would still need 2¹²⁸ operations (i.e. way too many to be feasible, with a huge margin) to break preimage resistance.

(This also means that against classical computers, a 256-bit hash function is total overkill when used in Merkle scheme. But, against classical computers, we can also use RSA or ECDSA, which are way more efficient than Merkle's scheme.)