[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Julian Wälde]

> Great! I would love help. Have you seen these docs?
> 
> http:/3/tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography#Signatures



> 2. Help us figure out in theory how efficient it can be while still
> having 128-bit security and allowing at least 2^53 signatures before
> losing security. 

Thats one point that has me somewhat confused. As I took it you were
planing to do some randomized hashing with the message to get TCR and
then sign the randomized hash (I presume 128 bit here) with a Merkle key
in the following way:

The merkle key has 2^256 onetime keys and the signer chooses one of
those keys at random. To be able to generate such a huge tree you would
create small trees(e.g. height = 2) and sign the root of each tree on
each layer with a onetime key in a tree in the layer above. That way one
can generate the needed part of the tree out of a secret seed (one tree
with min 2 leafs per layer). And the problem would be that you risk to
use a key twice with a different message ...

I don't see the reason not to use the randomized hash that will be
signed as path in a tree over 2^128 onetime keys. that way you can do as
many signatures you like and never reuse a key with a different message.

> (See the docs above for details about how far we've
> gotten so far.) The simulation results posted on the wiki are rather
> discouraging -- the best parameters found so far have signatures of
> size 10 to 20 Kbytes, take 170 to 466 Mcycles to sign and around 29 to
> 39 Mcycles to verify. 

There is no way in hell that these stateless merkle schemes can compete
with ecdsa or rsa in terms of speed/signature size ... the fastest
stateless scheme (meaning that the privatekey does not change with every
signature) was still 5 times slower than rsa4k and had ~40kb per signature.

> I don't know how long key generation takes.

The enormous signature sizes and bad timings aside ... key generation
should be rather fast.

-Julian

PS: The problem with 128 bit security is that Grovers Algorithm will
take only 2^64 steps to break it on a quantum computer.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20110216/63aa1a4c/attachment.pgp>