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

[Ben Laurie]

On 13/06/2010 05:21, Zooko O'Whielacronx wrote:
> Folks:
> 
> Regarding earlier discussion on these lists about "the difficulty of
> factoring" and "post-quantum cryptography" and so on, you might be
> interested in this note that I just posted to the tahoe-dev list:
> 
> "100-year digital signatures"
> 
> http://tahoe-lafs.org/pipermail/tahoe-dev/2010-June/004439.html
> 
> Here is an excerpt:
> 
> """
> As David-Sarah [Hopwood] has pointed out, a Merkle Signature Scheme is at least
> as secure as *any* other digital signature scheme, even in the
> long-term—even if attackers have quantum computers and the knowledge
> of how to solve math problems that we don't know how to solve today.
> 
> If you had some other digital signature scheme (even, for the sake of
> argument, a post-quantum digital signature scheme with some sort of
> beautiful reduction from some classic math problem), then you would
> probably start wanting to digitally sign messages larger than the few
> hundreds of bits that the digital signature algorithm natively
> handles. Therefore, you would end up hashing your messages with a
> secure hash function to generate "message representatives" short
> enough to sign. Therefore, your system will actually depend on both
> the security of the digital signature scheme *and* the security of a
> hash function. With a Merkle Signature Scheme you rely on just the
> security of a hash function, so there is one less thing that can go
> wrong. That's why a Merkle Signature Scheme is at least as secure as
> the best digital signature scheme that you can imagine. :-)
> """

Way behind the curve here, but this argument seems incorrect. Merkle
signatures rely on the properties of chained hash functions, whereas
RSA, for example, only needs a single iteration of the hash function to
be good.

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).

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