[cryptography] Merkle Signature Scheme is the most secure signature scheme possible for general-purpose use
Ben Laurie
ben at links.org
Wed Sep 1 16:55:24 EDT 2010
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
More information about the cryptography
mailing list