[tahoe-dev] note about hash-based digital signatures

Jack Lloyd lloyd at randombit.net
Tue Jun 22 19:54:32 PDT 2010


On Tue, Jun 22, 2010 at 07:01:07PM -0700, Zooko O'Whielacronx wrote:

> Note that "tens of thousands of hashes" is not necessarily a
> show-stopper! Depending on a large number of details, we might be able
> to compute a secure hash in as little as 1000 CPU cycles. So to do
> 10,000 of them would take (with ideal CPU utilization) 10,000,000
> cycles. On a 1 GHz machine, this would take 10 milliseconds. (WARNING:
> all of these numbers are *very* rough estimates for the purposes of
> deciding if it is worth figuring out more accurate numbers.)

One other interesting aspect to a hash-based signature is that if you
are using a tree-like scheme, you could parallelize it quite well,
making good use of dozens of available cores (and, depending on the
algorithm, the parallelism avilable in vector units like SSE/AVX,
AltiVec, or NEON). In comparison RSA and ECDSA have a hard time making
use of more than 2 or 3 processors.

For instance Intel's upcoming Sandy Bridge will have a 256 bit wide
vector unit (AVX), and up to 8 cores with hyperthreading. Using the
AVX unit to compute 8 SHA-256 compression functions in parallel, plus
threads to access each core/HT, you can compute 128 compression
functions in parallel. Assuming 10K hashes at 1K cycles per hash,
that's less than a millisecond total. Obviously from our perspective
now, a Sandy Bridge processor that hasn't even been released yet seems
like the high end, but in 10 years it will be considered seriously
outdated and long replaced by more powerful chips, in 20 years things
like it will be used in your toaster (perhaps doubling as the heating
element?), and in 100 a chip of these specs will perhaps best be used
broken into pieces and used for speartips to hunt antelope.

BTW, could you post a translation guide for those of us without a
sufficiently Unicoded MUA? Here is what mutt shows me for the final
paragraph of your mail:

"""
Oh, one more detail: the "giant virtual space of one-time keys" might
not need to be as large as 2????????. That's because an attacker can't
"brute force attack" this space. The resistance against brute force
attack is provided by other parts of the system. This space needs to
be large only in order to avoid accidental collision. It could be
perhaps as small as 2????????, which if I calculate correctly would let you
write 10????? times to your file while still incurring less than a 10????????
chance of an accidental collision which would let people forge new
writes to your file.
"""

?????????? yours,

Jack


More information about the tahoe-dev mailing list