[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz] Re: One-time signature possibilities
From: |
Tuomas Lukka |
Subject: |
[Gzz] Re: One-time signature possibilities |
Date: |
Mon, 12 May 2003 16:05:19 +0300 |
User-agent: |
Mutt/1.4.1i |
On Mon, May 12, 2003 at 01:26:33PM +0200, Benja Fallenstein wrote:
> I'm starting to be quite convinced that one-time signatures are the
> way to go with pointers. One-time signatures are signatures where the
> key can only be used to sign n messages for small n (so actually
> they're n-time) (you can get around the problem by signing as one of
> the n messages the next public key to be used).
How does this BTW impact the chain length? If you need to check
1000 signatures in order to see that a key is valid, that's not really
nice...
> - safer than e.g. DSA: less algorithms in Storm that can be broken (if
> we use e.g. DSA, we still need cryptographic hashes)
> - more durable: DSA signatures are only considered safe for about two
> years; no such problem with the hash functions we use
However, we of course still need all revocation and re-signing
methods because a cracker might steal your keys.
> - faster: factoring large integers is very costly compared to hashing.
??? ;)
> On the downside, one-time signatures are *large*. Remember that for
> every save we want to keep, we have to keep the signatures. The
> storage space per signature is O(b*b) with b the number of bits in the
> hash, a problem if we want to use SHA-1 + Tiger. To some degree, we
> can trade off running time against signature storage space; we need to
> decide what is reasonable.
Do you have the numbers for e.g. DSA? How many bits more will
we have for this?
> I've benchmarked, and on my machine, a DSA verification takes 30ms, a
> SHA-1 hash 5/1000 ms and a Tiger hash 6/1000 ms. The time estimates
> below are based on this.
>
> 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 don't quite understand how you get these tradeoffs...
> If, in addition to the above, you store another 20c or 44c bytes (for
> SHA-1 and SHA-1+Tiger, respectively), you can sign 2^c messages with
> the same public key. (Generation of the public key takes 2*(2^c) times
> the verification time for a single hash.)
How does this work?
> Discussion, please: What (if any) of this do you think is reasonable?
This might be reasonable.
Note of course that you can sign a group of blocks, you don't need
to sign each block separately.
Tuomas