
From:  Benja Fallenstein 
Subject:  Re: [Gzz] Re: Onetime signature possibilities 
Date:  Mon, 12 May 2003 15:37:52 +0200 
Useragent:  Mozilla/5.0 (X11; U; Linux i686; enUS; rv:1.3) Gecko/20030430 Debian/1.35 
Tuomas Lukka wrote:
On Mon, May 12, 2003 at 01:26:33PM +0200, Benja Fallenstein wrote:I'm starting to be quite convinced that onetime signatures are the way to go with pointers. Onetime signatures are signatures where the key can only be used to sign n messages for small n (so actually they're ntime) (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 check1000 signatures in order to see that a key is valid, that's not really nice...
You make a tree, so than you need to verify the mth signature, you need to verify O(log m) signatures in whole.
If you choose n = 1024, so that you can sign 1024 messages with the same public key, then seed 128 new private keys from there with n = 1024 each, you could sign 128K messages; each of these 128K messages would require checking two signatures. So you can get to pretty large numbers pretty easily if you need to.
 faster: factoring large integers is very costly compared to hashing.??? ;)
Um, multiplying. Blah :)
On the downside, onetime 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 SHA1 + 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 think it's the same length as the key  something like 1024 bit recommended but I'm not sure.
I've benchmarked, and on my machine, a DSA verification takes 30ms, a SHA1 hash 5/1000 ms and a Tiger hash 6/1000 ms. The time estimates below are based on this.If we use only SHA1, 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 SHA1 + 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, ~120msI don't quite understand how you get these tradeoffs...
Not surprising since you don't know the algorithm :) It was AFAIK invented by Merkle/Winternitz. The description I found is in: http://citeseer.nj.nec.com/goldreich94lineoffline.htmlsection 4.2, Construction 1, article page 13. (The article explains this as work itself is based on.) The parameter varying in the tradeoff is t: it's {1,2,3,4} respectively.
If, in addition to the above, you store another 20c or 44c bytes (for SHA1 and SHA1+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?
Generate 2^c private keys and the public key for each (a single hash); create a clevel binary Merkle hash tree of these public keys; publish the root of the hash tree as the combined public key.
To verify that one leaf is part of a hash tree (given the hash tree's root), you need to give the other hash, at every branch; this needs to be included in the signature; therefore, the signature needs to contain c more hashes.
Discussion, please: What (if any) of this do you think is reasonable?This might be reasonable.
Which version?
Note of course that you can sign a group of blocks, you don't need to sign each block separately.
Of course. Thus, one block per save.  Benja
[Prev in Thread]  Current Thread  [Next in Thread] 