Re: [Gzz] Re: One-time signature possibilities

[Benja Fallenstein]

Tuomas Lukka wrote:
> 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...

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

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

section 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 
> > 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?

Generate 2^c private keys and the public key for each (a single hash); 
create a c-level 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