[Suit] Notes on your usage of HSS-LMS

["Scott Fluhrer (sfluhrer)" <[e-mail]>]

Hi,

   I saw that you were using HSS-LMS as one of your signature algorithms; I thought it would be appropriate if I were to make comments on the slides that Brandon presented:


  *   Fixed number of signatures possible
This is true; however when you generate the HSS-LMS private key, you select the number of signatures possible.  It is usually fairly easy to set the limit to something considerably more than you'll ever need.  For example, if you believe you'll never sign more than a billion updates (enough for one per second for 30 years), then you can set the limit that high (perhaps with a two level HSS structure consisting of two LMS trees of height 15 each).

  *   Signatures are >1kB.
This is true for the parameter sets defined in the RFC.  On the other hand, the draft draft-fluhrer-lms-more-parm-sets (which will hopefully become an RFC soon) defines parameter sets with signatures about half as long as what you use now - still not anywhere close to what ECDSA can do, but it's better than what you have now (cost: those parameter sets do have reduced security; however that security reduction is from "insane overkill" to "quite conservative", and yes, it's still postquantum)

  *   Verification time

I suspect you did your performance testing with "W=8" (which is the "reduce signature size at the cost of computation" option); if you need to speed up the verification, you can select a parameter set with "W=4"; verification with that should be about 8 times faster (at the cost of having signatures which are about twice as large; no security change).  Going even further we have "W=2", which is about twice as fast as "W=4" (with about another doubling of the signature size).


And, if you have any further questions about HSS-LMS, or you need some help, feel free to ask - I've been working on it for an embarrassingly long time, and I'm glad to see it being used.

Thanks!