[tahoe-dev] Hash based Signatures for Tahoe LAFS

[Zooko O'Whielacronx]

> From: Julian Wälde <jwaelde at cdc.informatik.tu-darmstadt.de>
...
> What I'd like to know is whether there is a documentation for the exact
> scheme you are (planing on) implementing. Also, I want to offer my help
> to you (or who else is working on this).

Great! I would love help. Have you seen these docs?

http://tahoe-lafs.org/trac/tahoe-lafs/wiki/OneHundredYearCryptography#Signatures

There are two ways that we currently need help with hash-based digital sigs:

1. Concrete measurements of performance, especially on the ARM
architecture. Our simulator code currently has a hard-coded "15.8" as
the cycles per byte, but that is probably quite inaccurate for any
real ARM system and any real hash function that we might use, such as
blake32 or sha256. This measurement shows sha256 taking up to 68.69
cycles per byte to hash 64 bytes on Freescale i.MX515 (v7-A, Cortex
A8):

http://bench.cr.yp.to/results-sha3.html#armeabi-h1mx515

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. (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. I don't know how long key generation takes.
Compare to Crypto++'s version of ECDSA:
http://cryptopp.com/benchmarks-amd64.html -- 2.88 Mcycles to 8.94
Mcycles to verify, and signatures are around 64 bytes. :-) See also
other competitive digital signature schemes benchmarked here:
http://bench.cr.yp.to/results-sign.html

For an example of the many open issues, those benchmarks suggest that
if the Merkle Trees had a fan-out of 36 (576 bytes) instead of 4 (64
bytes) then sha256 would run at about 28.86 cpb instead of 68.69. Our
current simulator doesn't take into account the fact that a hash
function runs faster in terms of cpb if given larger inputs.

Regards,

Zooko