[Gzz] One-time signature possibilities

[Benja Fallenstein]

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

One-time signatures use only cryptographic hashes and a random number 
generator, which means that they are--

- 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
- faster: factoring large integers is very costly compared to hashing.

We have goals in Storm that would be very difficult to realize together 
if we used e.g. DSA:

- Durability: Storm blocks should still be readable in, say, 20 years.
- Decentrality: No central registry or service.
- Off-line: Storm should be usable w/o a connection to the net.

To make DSA sigs durable, the usual approach is a trusted third party 
timestamping service-- which would be a central service. Perhaps a 
decentral timestamping mechanism could be implemented, but it would 
still be problematic because it would require being on-line. One-time 
signatures have durability without any of this.

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.

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

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

Discussion, please: What (if any) of this do you think is reasonable?

Note that all but the last option is faster than DSA, according to my 
benchmarks.

- Benja