Hash-based signatures

[Daira Hopwood]

This is a transcript of an IRC conversation I had with Zooko, about a potential
improvement to the "Merkle-Winternitz-HORS" hash-based signature scheme I
originally described in [Hopwood2010]:
<https://tahoe-lafs.org/pipermail/tahoe-dev/2010-July/004587.html>

We'll be discussing it in today's "Tesla Coils and Corpses" meeting
<https://tahoe-lafs.org/trac/tahoe-lafs/wiki/WeeklyMeeting>.

-----
(2014-03-14 17:57:16)
daira: BTW, I had an idea today (on the train, literally on the back of an
       envelope), about hash-based signatures.
daira: I need to do some simulations to see whether it actually helps.
daira: You know how in Merkle-Winternitz-HORS, you have a chain of WOTS
       signatures leading to a HORS leaf signature (ignore the partly
       stateful optimization for now)?

[The "partly stateful optimization" is point 4 in [Hopwood2010].
WOTS stands for "Winternitz one-time signature". HORS is described
in <http://eprint.iacr.org/2002/014>.]

zooko: daira: um, hold on. I'm not sure I know about that.
zooko: Sorry, could you remind me in 1 sentence what's the idea of HORS?
daira: HORS is the one where you reveal q out of K hashes for each signature
daira: and an attacker can only forge if they can find a message that indexes
       q hashes that have already been revealed
***zooko nods
daira: so, the forgery probability decreases with K
***daira checks the original post for the details
daira: "If we model the hash as a random oracle (for simplicity), then each
        query will choose a random bucket, and so the probability of
        a query to the hash oracle allowing a forgery is:
          Pr(forgery) = sum_{x = 1..j}(Pr(X = x) * (q*x / K2)^q) + Pr(x > j)
                        where j = floor(K2/q)"
daira: here K2 is K
daira: so we want K to be as large as possible, so that the forgery
       probability is minimized and we can use a smaller overall tree,
       with fewer layers
daira: but the signer must recompute all K keys in order to find the
       public key for the HORS signature
***zooko nods
daira: so here's the idea: in the next-higher layer of the tree, sign
       several different HORS public keys, and include one HORS signature
       for each
daira: the overall stateless signature is only valid if it contains the
       required number of HORS signatures
daira: but the signer only needs to compute the HORS signatures that are
       actually used, not all those that could have been selected at that
       level
daira: since this is only done at the immediately-higher level of the tree,
       most of the chain of signatures is the same, so only the additional
       HORS signatures and the signatures of the HORS public keys contribute
       to increasing the overall signature size
daira: and we hope that the forgery probability is reduced enough that this
       is better than just choosing different parameters for the original
       scheme (that's what I need to simulate)
daira: actually now that I've explained it, I can see there's another thing
       to consider tweaking...
daira: that explanation keeps all-but-one layers in the signature chain the
       same between the HORS signatures
daira: we can instead do all-but-z for some z
daira: (which increases the number of HORS keys from which we choose in
       each signature exponentially in z, while only increasing signature
       size linearly in z)
daira: ok, that's it

-- 
Daira Hopwood ⚥

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 555 bytes
Desc: OpenPGP digital signature
URL: <http://tahoe-lafs.org/pipermail/tahoe-dev/attachments/20140424/016f6c6c/attachment.pgp>