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 majord...@metzdowd.com