[tahoe-dev] note about hash-based digital signatures

[David-Sarah Hopwood]

Zooko wrote:
> So, I was about to give up on the idea of hash-based signatures, but
> then I thought that you could instead have a giant space of one-time
> keys, say 2²⁵⁶ one-time keys, and pick one at random to use for each
> signature! (This sounds crazy, but it turns out that you don't have to
> actually pre-generate all of the one-time keys in these sorts of
> schemes, so the giant space of 2²⁵⁶ one-time keys is actually "a
> virtual space of one-time keys" where every key has a unique sequence
> number assigned to it but not every key has actually been generated
> yet.)

That won't work, at least not for a conventional Merkle-tree scheme,
because the public key has to be dependent on all the private keys.

> Then Brian pointed out that the only security problem with re-using a
> one-time key is if you re-use the same one-time key with a *different*
> plaintext that you are signing. That suggests an easy way out of the
> statefulness mess: uses the one-time key whose index is determined by
> the message representative that you are about to sign.

This also won't work for the same reason; you would have to expend
effort proportional to the number of possible hashes in order to generate
the public key.

> Now *that* suggested, to me, another optimization, which is if you are
> going to use a one-time key out of a giant virtual space of one-time
> keys (say 2²⁵⁶ in size) then you don't need to actually *perform* the
> one-time signature with that key! You can just reveal the secret key.
> :-)

I don't understand this optimization. Please describe in more detail the
protocol you were thinking of (even if it is impractical).


PS. I'm atill having to read tahoe-dev from the archives, because the
mailing list emails are getting blocked. I think this is most likely due
to the outgoing MTA not reporting its actual domain name. Can that be fixed?

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://allmydata.org/pipermail/tahoe-dev/attachments/20100623/d4a25c62/attachment.pgp>