[cryptography] Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use

Nicolas Williams Nicolas.Williams at oracle.com
Fri Jul 9 18:17:17 EDT 2010

On Sat, Jun 12, 2010 at 10:21:51PM -0600, Zooko O'Whielacronx wrote:
> http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004439.html

There you ask how the Merkle Signature Scheme depends on collision
resistance.  The authors of the paper you link to say that signature
itself depends only on second-pre-image resistance, but that the Merkle
hash tree used to cope with the one-time-use signature (by letting you
group many one-time-use public keys) depends on collision resistance.

I believe it's fairly obvious that the hash tree part of MSS does depend
on collision resistance: the tree node values are hashes of private keys
(leaf nodes) or interior nodes in the tree (hashes of sequences of
hashes of .. hashes of private keys), and the peer verifying a signature
cannot validate those tree node values.  A collision attack on the hash
tree's hash function would allow you to take a signature and claim it
was made with someone else's key -- all you have to do is find one
collision for a public key and its leaf node sibling(s).

Whereas you need pre-images in order to attack the Lamport one-time
signatures: the signature includes the hash function inputs for half of
the public key (the other half is then ignored), and the peer need only
verify that the hashes of those inputs match the corresponding hashes in
the public key.  The attacker must have pre-images in order to forge

At least that's my impression on a cursory check.

Caveat emptor: IANAC.


More information about the cryptography mailing list