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

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
> 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.

Ah, but it will work for a multi-layer Merkle tree scheme, such as GMSS:
if keys are generated deterministically from a seed, then the signatures
certifying keys at upper layers are also deterministic, so there's no
key-reuse problem for those. So you just lose the optimization given by
the authentication path algorithm.

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

Again this can work for a multi-layer scheme. The effort is proportional
to the number of keys generated at each layer, times the number of layers.

-- 
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/e6e739ae/attachment.pgp>