Leighton-Micali Hash-Based Signature key sizes I am working with the RFC for Leighton-Micali Hash-Based Signatures: RFC-8554.
The question is if I understood it correctly and my calculations of the key sizes are correct.
Basically, LMS uses several Winternitz-One-Time-Signature keys.

Winternitz-OTS
In chapter 4.1 of the RFC the parameter sets of the OTS keys are mentioned:
  |------------------------------------------------------------|
  | Parameter Set Name  | H      | n  | w | p   | ls | sig_len |
  |------------------------------------------------------------|
  | LMOTS_SHA256_N32_W1 | SHA256 | 32 | 1 | 265 | 7  | 8516    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W2 | SHA256 | 32 | 2 | 133 | 6  | 4292    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W4 | SHA256 | 32 | 4 | 67  | 4  | 2180    |
  |                     |        |    |   |     |    |         |
  | LMOTS_SHA256_N32_W8 | SHA256 | 32 | 8 | 34  | 0  | 1124    |
  |------------------------------------------------------------|

Where n is the number of bytes of the output of the hash function and p is the number of n-byte string elements. This means basically for the OTS private key we have n * p keys (+ 4 bytes for the typecode). This would also fit for the given signature length sig_len (n * p + 4 + 32 bytes for the checksum). The OTS public key is of equal length of the private key.
LMS
In chapter 5.1 of the RFC the parameter sets of the LMS keys are mentioned.
+--------------------+--------+----+----+
| Name               | H      | m  | h  |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5  | SHA256 | 32 | 5  |
|                    |        |    |    |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
|                    |        |    |    |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
|                    |        |    |    |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
|                    |        |    |    |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+

Where m is the number of bytes associated with each node and h is the height of the Merkle tree.
One LMS private key consists of 2^h OTS private keys.
Questions

Is it correct that any LMS parameter set can be used with any OTS parameter set?
e.g. LMS_SHA256_M32_H25 for the Merkle tree and LMOTS_SHA_256_N32_W2 for the OTS keys.

Are those calculations of LMS private key sizes correct:
Formula: 2^h * ((n * p) + 4)

LMS_SHA256_M32_H5 &amp; LMOTS_SHA256_N32_W8: 2^5 * ((32 * 34) + 4) = 34 944 bytes ~ 34 KB
LMS_SHA256_M32_H5 &amp; LMOTS_SHA256_N32_W1: 2^5 * ((32 * 265) + 4) = 271 488 bytes ~ 271 KB
LMS_SHA256_M32_H20 &amp; LMOTS_SHA256_N32_W8: 2^20 * ((32 * 34) + 4) ~ 1.1 GB
LMS_SHA256_M32_H20 &amp; LMOTS_SHA256_N32_W1: 2^20 * ((32 * 265) + 4) ~ 9 GB
LMS_SHA256_M32_H25 &amp; LMOTS_SHA256_N32_W8: 2^25 * ((32 * 34) + 4) ~ 37 GB
LMS_SHA256_M32_H25 &amp; LMOTS_SHA256_N32_W1: 2^25 * ((32 * 265) + 4) ~ 285 GB



If those key sizes are correct then how would someone store them securely? Are those deep Merkle trees realistic? I guess calculating the corresponding public key can be done on demand.
Yes, each LMS parameter sets can be used with any OTS parameter set.
In the final NIST Recommendation for Stateful Hash-Based Signature Schemes there are even more parameters defined.



Those calculations are correct but we do not need to store the entire LMS tree in memory. The solution is to store the seed for the RNG in the private key and calculate the tree on demand. Requires more work but requires much less memory.


Calculations
LMOTS private key:
Size = 4 byte LMOTS typecode + 16 byte identifier + 4 byte q + n byte seed
Example: LMOTS_SHA256_N32_W8 = 4 + 16 + 4 + 32 = 56 byte

LMS private key:
Size = 4 byte LMOTS typecode + 4 byte LMS typecode + 4 byte q + 16 byte identifier + 2^h LMOTS private key size
Examples:
LMS_SHA256_M32_H5 &amp; LMOTS_SHA256_N32_W8: 4 + 4 + 4 + 16 + 2^5 * 56 = 1 820 byte
LMS_SHA256_M32_H25 &amp; LMOTS_SHA256_N32_W1: 4 + 4 + 4 + 16 + 2^25 * 56 = 1 879 048 220 byte ~ 1.9 GB