|
From: | Benja Fallenstein |
Subject: | Re: [Gzz] One-time signature possibilities |
Date: | Mon, 12 May 2003 18:55:16 +0200 |
User-agent: | Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.3) Gecko/20030430 Debian/1.3-5 |
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
[Prev in Thread] | Current Thread | [Next in Thread] |