[Gzz] Re: One-time signature possibilities

[Tuomas Lukka]

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