Re: Merkle-Winternitz-HORS signature scheme for Tahoe-LAFS [correction]

[David-Sarah Hopwood]

David-Sarah Hopwood wrote:
[snip]
> There could also be a concern that point 4 above is similar to
> on-line/off-line signatures as patented by Even, Goldreich and Micali
> (U.S. patent 5016274, filed in 1988; expires on 14 May 2011).

Ah, I calculated the expiration date incorrectly. It was filed before the
rules changed in June 1995, so it's the later of 20 years after filing
(8 November 2008) or 17 years after issue (14 May 2008). So it has already
expired.

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



signature.asc
Description: OpenPGP digital signature

Merkle-Winternitz-HORS signature scheme for Tahoe-LAFS

[David-Sarah Hopwood]

[cc:d to cryptography list from the tahoe-dev list.
See ,
 and
http://allmydata.org/pipermail/tahoe-dev/2010-June/004496.html> for context.]

Brian Warner wrote:
> On 6/23/10 7:18 AM, David-Sarah Hopwood wrote:
>
>> 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.
>
> Right, exactly. The basic scheme would look something like this:
>
>  * set K=1024
>  * build a K-ary tree with 2^M=2^256 leaves. Each leaf corresponds to a
>possible message.
>  * define a deterministic keyed function from leaf number to keypair
>  * define a deterministic keyed function from node number to keypair
>  * publish the root pubkey as the readcap. Retain the secret key (used
>as an input to the above deterministic functions) as the writecap.
>  * to sign a given message:
>* identify the DEPTH=ln(base=K, 2^256) =26ish tree nodes along the
>  path from root to leaf
>* generate the one privkey for the message leaf, use it to sign the
>  message itself
>* for all nodes on the path, from bottom to top:
>[
> * generate all K pubkeys for the node's children, concatenate them
>   into a string, treat that as a message
> * sign the message with the parent node's privkey
>]
>
> As zooko pointed out, the leaf signature can be optimized away: since
> each message gets a unique pubkey, it suffices to reveal the
> preimage/privkey for that pubkey. This reduces the size of the leaf
> signature down to a single hash.
>
> Assuming a 256-bit Merkle-signature scheme (with a "0" and a "1"
> preimage for each bit), it takes 512 hashes to build all the
> privkey/preimages, and then 512 hashes to build the pubkeys.
> Each signature requires computing and publishing (revealing) 256 preimage
> hashes.

Note that this is a Lamport-Diffie signature, not a Merkle one-time
signature. The Merkle one-time signature scheme (described in the second
paragraph under "Signing a several bit message" in [Merkle1987]) publishes
only preimage hashes corresponding to "1" bits, and uses a checksum.

> Generating the readcap is pretty easy: you build the K pubkeys for the
> top node (4*256 small hashes each), hash each one down (K large hashes
> of 512*32 bytes each), then hash those lists into a single value (one
> large hash of K*32 bytes). So 1M small hashes, 1024 hashes of 16KiB
> each, and one hash of 32KiB bytes.
>
> For K=1024 and M=256, the message signature consists of the leaf
> signature (one hash), and 26 nodes. Each node contains one signature
> (256 preimages), one pubkey (512 hashes), and 1023 hashes-of-pubkeys.
>
> So the overall message signature requires you publish about 46567 hashes,
> or 1.5MB.

The scheme that I'm currently considering has the following five
improvements over the one above:


1. For the signatures on non-leaf public keys, use the Winternitz one-time
   signature scheme. This was first publically described in [Merkle1987],
   but a clearer description is given in [BDS2008].

   The Winternitz scheme (unlike the Lamport-Diffie or Merkle schemes) has
   the property that the full public key can be derived from a signature.
   Therefore it's not necessary to explicitly include the pubkey that is
   being signed at each node, since it can be derived from the signature
   on the next-lower node. More precisely, the lower signature gives a
   claimed public key, which can be authenticated using the upper signature.

   Winternitz signatures also allow a trade-off between signature size and
   the number of hash computations needed to sign, depending on the base.

   (Typically the scheme is described with a base that is a power of 2,
   i.e. the message representative and checksum are expressed as base
   2^w numbers. Actually it works for an arbitrary base >= 2, and using
   a base that is not a power of two can sometimes save an extra few
   percent in signature cost for a given signing size.)

   The signing cost is linear in the base B, while the size of the
   signature is only divided by lg(B). Nevertheless, choices of B from
   4 up to about 32 are useful.

   In the example above, the 256 + 512 = 768 hashes for the signature and
   pubkey, are reduced to 133 hashes for base 4; 90 hashes for base 8; and
   67 hashes for base 16.

   Note that the optimal choices of K are typically smaller than 1024, so
   the one-time signature/pubkey makes up a greater proportion of the
   published size for each layer than in the example above. For instance,
   if K = 16, B = 16, and M = 256, then the number of hashes published per
   layer drops to 67 + K-1 = 82. Without any of the other improvements
   below, at least 64 layers would be needed, so that would be 5248 hashes