[Cryptech Tech] Private Key Size in Hash-based Signatures

[Russ Housley]

Table 2 in https://eprint.iacr.org/2017/349.pdf has the formulas for the public key and sig sizes of LMS and HSS and their XMSS equivalents. These are based on the -07 version of the Internet-Draft. For actual example numbers you can use Table 3.

As for the private key, the Internet-Draft (purposely) does not specify a unique format for the private key.

There are some time/memory trade-offs available.  At one extreme, you could just store a (a truly random) seed, the current position within the HSS tree, and possibly the parameter set; this would make the private key less than 64 bytes, but at the cost of having to rebuild the Merkle trees each time, which is computationally expensive.

At the other extreme, you could explicitly store the contents of the current Merkle trees and next for the non-topmost HSS levels; this makes it much cheaper, but also makes the private key much larger.

In the middle, you could store parts of the Merkle tree, and use a Merkle walking algorithm (Fractal or BDS) to recreate the parts of tree that you need to generate the authentication path.  This doesn't require that much memory, and is efficient; however it is also somewhat more programmatically complex than the previous options.

As for the current open source implementations, the Python code uses the first alternative; the C implementation uses the first alternative for the persistent (on-disk) state, and the third alternative for the in-memory copy, making the generation of the next signature fairly cheap.  It also allows a number of time/memory trade-offs internally, which does increase the complexity.

Implementers will have to decide where Cryptech fits in this spectrum.

Russ