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

Zooko O'Whielacronx zookog at gmail.com
Sun Jun 13 00:21:51 EDT 2010


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

In that note I go on to talk about more Tahoe-LAFS-specific
engineering considerations and expose my ignorance about exactly what
properties are required of the underlying secure hash functions.

Regards,

Zooko



More information about the cryptography mailing list