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

[Stephen Farrell]

As an FYI: I started generating a 20-deep key on a (fairly old)
server yesterday during the meeting. It's still working away at
that (using the python code).

S.

On 21/09/17 22:23, Russ Housley wrote:
> 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
> 
> _______________________________________________
> Tech mailing list
> Tech at cryptech.is
> https://lists.cryptech.is/listinfo/tech
> 

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: OpenPGP digital signature
URL: <https://lists.cryptech.is/archives/tech/attachments/20170922/3ce119e2/attachment.sig>