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 signatures. At least that's my impression on a cursory check. Caveat emptor: IANAC. Nico -- _______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
