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

[Zooko O'Whielacronx]

Ugh. Sorry about that. Here is the message that I intended to post.  --Zooko

On Tue, Jun 22, 2010 at 7:54 PM, Jack Lloyd <lloyd at randombit.net> wrote:
> 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).

Yeah!  Also the SIMD part of it hardly even depends on the algorithm,
does it? If you're doing a computation with multiple parallel hash
instances then you should be able to take almost any hash algorithm
and compute it in parallel, right? Thomas Pornin recently did this
with his SHA-3 candidate, Shabal, which doesn't have a structure that
lends itself to SIMD parallelism "internally" in one instance of
Shabal, but he arranged to compute four instances of Shabal in
parallel using SSE2, computing each instance half as fast.

I believe Wei Dai once mentioned the possibility of a similar hack for SHA-256.

> 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.

Hee hee!

> 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:

Hopefully you will use your Sandy Bridge chip to install mutt version
1.4, which was released May 29, 2002 with utf-8 support. Until then,
here is the translation:

> 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
                            2^256
> "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
                     2^160
> write 10????? times to your file while still incurring less than a 10????????
       10^16                                                        10^-15
> chance of an accidental collision which would let people forge new
> writes to your file.
> """
>
> ?????????? yours,
 faithfully

Zooko