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

[Ben Laurie]

On 01/09/2010 22:45, Zooko O'Whielacronx wrote:
> On Wed, Sep 1, 2010 at 2:55 PM, Ben Laurie <ben at links.org> wrote:
>> Or, to put it another way, in order to show that a Merkle signature is
>> at least as good as any other, then you'll first have to show that an
>> iterated hash is at least as secure as a non-iterated hash (which seems
>> like a hard problem, since it isn't).
> 
> I'm not sure that I agree with you that security of a hash function
> used once on an arbitrarily large message is likely to be better than
> security of a hash function used a few times iteratively on its own
> outputs.

That's the whole point - a hash function used on an arbitrary message
produces one of its possible outputs. Feed that hash back in and it
produces one of a subset of its possible outputs. Each time you do this,
you lose a little entropy (I can't remember how much, but I do remember
David Wagner explaining it to me when I discovered this for myself quite
a few years ago).

So, on that basis alone, I reject the "most secure possible" argument.

> But regardless of that, I think the fair comparison here is:
> 
> ... show that an iterated hash is more likely to have preimage
> resistance than a non-iterated hash is to have collision-resistance.
> 
> And I think it is quite clear that for any real hash function such as
> MD5, SHA-1, Tiger, Ripemd, SHA-2, and the SHA-3 candidates that this
> does hold!
> 
> What do you think of that argument?

I think I've failed to understand why you thing collisions are not a
problem for Merkle trees.

Also, regardless, you are now talking probabilities and so a claim of
"most secure possible" still doesn't apply.

Merkle trees, probably the best signature in the world? :-)

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com