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

[Jack Lloyd]

On Tue, Jun 22, 2010 at 11:51:43PM -0700, Zooko O'Whielacronx wrote:

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

The only problem being if you can actually implement the algorithm in
the limited instruction set of SSE2/Altivec/etc. For instance, table
lookups are quite difficult, which could rule out hashes like Tiger,
Whirlpool, and the SHA-3 candidates that are based on AES variations.
You can emulate these lookups using bit operations, but often the
expressions are large enough that you lose more than you gain.

There are other limitations, usually idiosyncratic; for instance SSE2
has no 64 bit integer multiply, and no modulo operation.

TBH the really difficult part (at least I found when I tried doing
this for SHA-1 a while back) is not implementing the compression
function in SIMD, it's doing the message block scheduling so you can
keep the pipeline as full as possible when hashing arbitrary
messages. OTOH for a tree-hashing signature scheme probably all of
your inputs would be the same size and you could know in advance
exactly what you were going to hash and when.

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

It's probably something, but it's not that:

$ mutt -v
Mutt 1.5.20 (2009-06-14, Gentoo 1.5.20-r10)

I'll poke around my settings.

-Jack