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 ⚥
signature.asc
Description: OpenPGP digital signature
_______________________________________________ tahoe-dev mailing list tahoe-dev@tahoe-lafs.org https://tahoe-lafs.org/cgi-bin/mailman/listinfo/tahoe-dev
