> ---------- Forwarded message ---------- > From: Jonathan Katz <[email protected]> > Date: Fri, May 29, 2015 at 7:17 AM > Subject: [Cfrg] Analysis of Hash-Based Signatures (draft-mcgrew-hash-sigs-02) > To: [email protected] > We analyze a signature scheme described in a recent Internet Draft, > and highlight a variant (based on prior work of Micali and Leighton) > that offers improved concrete security. > > The paper is available here: > http://www.cs.umd.edu/~jkatz/papers/HashBasedSigs.pdf
I thought this list might be interested, both because of the stated result w.r.t. hash-based signatures, as well as its direct application to hash-tree-based append-only logs. I don't think I ever posted here about it, but I suggested the precaution of using a MAC (for key-transparency tries) to some of the folks on this list a while back. Short summary: Suppose that you form a hash tree in the naive way, as, e.g., N_(..., 0, _) = Hash(N_(..., 0, 0) | N_(..., 0, 1)) where Hash has 's*2' bits of output, an adversary has a multitarget advantage of O(log(#N)). (If there are K independent hash trees, this increases the multitarget advantage similarly.) So, instead of hashing, do something like: N_(..., i, _) = Mac(k, encode_node_position(..., i) || N_(..., i, 0) | N_(..., i, 1)) where `k` is a random, per-tree key. This results in reasonably tight s-bit security. (Any admissible tree-hashing mode has some encode_node_position function that can be used for plain Merkle trees.) -- This doesn't really work for certificate transparency, because the append-only log is the Merkle tree itself. (But it remains useful for each log to choose a random key rigidly, e.g., as Hash(dnsname).) This does, however, work for key transparency proposals in the style of CONIKS. - David _______________________________________________ Messaging mailing list [email protected] https://moderncrypto.org/mailman/listinfo/messaging
