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

[Stephen Farrell]

On 22/09/17 12:55, Stephen Farrell wrote:
> 
> 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).

And after 25 hours...

"Command terminated by signal 11"

Ah well. More work needed I guess somewhere.

S.

> 
> 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
>>
> 
> 
> 
> _______________________________________________
> 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/20170923/659d6418/attachment.sig>