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?


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 2n/2. E.g. with SHA-256 (a 256-bit output), the best quantum computer would still need 2128 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.)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.