Hash-based signatures
Daira Hopwood
daira at jacaranda.org
Thu Apr 24 21:06:49 UTC 2014
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.asc>
More information about the tahoe-dev
mailing list