[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Zooko O'Whielacronx]

2011/3/29 Julian Wälde <jwaelde at cdc.informatik.tu-darmstadt.de>:
>
> Wooo finally got me self some time to do fun stuff ... I started out
> with implementing a prototype for a merkle scheme that has a static
> private key that can do infinite number of signatures [1].
> [1] http://www.cdc.informatik.tu-darmstadt.de/~jwaelde/smss.tar.xz


Hi there Julian! I was just looking at this new stackexchange site for
crypto, and someone (named Anthony "ninefingers" Vennard) had asked
why McEliece wasn't more popular, since it is post-quantum, and they
wondered if it was because of the large public keys. Below is my
reply.

By the way, I notice that the "back of the envelope" performance
requirements that I sketched out in this thread
(http://tahoe-lafs.org/pipermail/tahoe-dev/2011-February/006133.html )
are actually met by your implementation!

Regards,

Zooko

http://crypto.stackexchange.com/questions/131/is-key-size-the-only-barrier-to-the-adoption-of-the-mceliece-cryptosystem-or-is/151#151

We looked into post-quantum digital signature schemes for the
Tahoe-LAFS ["100 Year Cryptography"
project](http://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography)
but I stopped looking at all but one of them when David-Sarah Hopwood
observed that they all rely on a secure hash function to generate a
message representative for the digital signature scheme to sign.
Therefore, all of them (except for that one) are vulnerable to either
a break of the digital signature scheme or a break of the secure hash
function. The one remaining one is [hash-based digital
signatures](http://www.cdc.informatik.tu-darmstadt.de/%7Edahmen/papers/hashbasedcrypto.pdf).

Hash-based digital signature schemes are secure if the underlying hash
function is secure (of course we can and should be more precise about
what we mean by "secure" here, but this is good enough for now).
Therefore, a hash-based digital signature scheme has one fewer ways to
break than any other scheme. That is: a hash-based digital signature
scheme can be broken if you can break the underlying secure hash
function. All other digital signature schemes can be broken if you can
break the secure hash function that they use for generating a message
representative, *or* if you can break the digital signature scheme
itself.

So, for Tahoe-LAFS's "100 Year Cryptography" project, we are looking
at using hash-based digital signatures. Unfortunately, the best
designs we've found or invented so far are still somewhat efficient in
both processing time and key size, compared to a high performance
quantum-vulnerable scheme like the new
[ed25519](http://ed25519.cr.yp.to) which can take maybe 88,000 cycles
to do a signature or around 280,000 cycles to do a verification (on
certain modern Intel chips), with a public key of size 32 bytes and a
signature size of 64 bytes.

Julian Wälde has implemented a hash-based digital signature scheme
(warning: the details of the scheme have not been widely vetted, so
this particular scheme might not retain the security guarantee,
predicated on the security of the underlying secure hash function,
that I alluded to above), and
[reported](http://tahoe-lafs.org/pipermail/tahoe-dev/2011-March/006237.html)
4 signatures per second, 1700 verifications per second, a public key
size of 32 bytes, and signature size of 11,000 bytes. If we assume
Julian's development machine is a modern Intel chip running at 2.4
GHz, then it took about 600,000,000 cycles to sign and about 1,400,000
cycles to verify.

On the other hand, it compares well in certain respects to other
post-quantum crypto schemes, like McEliece. The [Bernstein, Lange,
Peters paper](http://eprint.iacr.org/2008/318) you referenced proposes
parameters for 128-bit security McEliece signatures in which the
public key is 192,000 bytes. That makes the 11,000 byte public keys in
Julian's hack look not as terrible.