Re: [Gzz] One-time signature possibilities

[Benja Fallenstein]

Benja Fallenstein wrote:
> If we use only SHA-1, not Tiger, some of our options are:
>
> - Store ~3KB, verify ~160 hashes, ~.8 ms
> - Store ~1.5KB, verify ~240 hashes, ~1.2ms
> - Store ~840 bytes, verify ~600 hashes, ~3ms
> - Store ~440 bytes, verify ~5100 hashes, ~25.5ms
>
> Using SHA-1 + Tiger, we have:
>
> - Store ~15KB, verify ~350 hashes, ~4ms
> - Store ~8KB, verify ~530 hashes, ~6ms
> - Store ~4KB, verify ~1320 hashes, ~15ms
> - Store ~2KB, verify ~11000 hashes, ~120ms

I put in a thinko here: I treated SHA-1 + Tiger as a new hash function, 
and applied the algorithm to that. This works, but isn't efficient.

Instead, we can simply run the algorithm twice: Once with SHA-1, to sign 
the SHA-1 hash, and once with Tiger, to sign the Tiger/TreeTiger hash. 
Then we get:

- Store ~8KB, verify ~160+192 hashes, ~2ms
- Store ~4KB, verify ~240+290 hashes, ~3ms
- Store ~2KB, verify ~600+720 hashes, ~7ms
- Store ~1KB, verify ~5100+6100 hashes, ~62ms

The X+Y means X SHA-1 hashes plus Y Tiger hashes.

This makes sense because if SHA-1 gets broken, it doesn't help to have a 
secure Tiger hash signed by an insecure SHA-1-based signature, or to 
have a secure Tiger-based signature for an insecure SHA-1 hash. It 
suffices to sign the Tiger part using the Tiger signature, and to sign 
the SHA-1 part using the SHA-1 signature.

I think the 2KB, 7ms signature is probably our best bet...

- Benja