# LMS hash calls formula?

If we consider LMS with (SHA256 and LMS-OTS as the OTS scheme) as defined in sections 5 and 4 here:

https://datatracker.ietf.org/doc/html/rfc8554#section-5, they provide the following formulas for LMS-OTS (section 4.4):

In general, the LM-OTS signature is 4+n*(p+1) bytes long, and public key generation will take p*(2^w - 1) + 1 hash computations (and signature generation and verification will take approximately half that on average)

So ~ (p*(2^w - 1) + 1)*(1/2) = total calls to SHA256 for sign and the same is true for verify.

For a given parameter set of LMS as defined in Section 5, making use of LMS-OTS, what would those above formulas be?

For LMS parameter set:

Name | H | message digest m | height h LMS_SHA256_M32_H15 | SHA256 | 32(bytes) | 15 |

with Winternitz w = 8 which would use this LMS-OTS set:

Parameter Set Name H n w p ls sig_len
LMOTS_SHA256_N32_W8 SHA256 32 (bytes) 8 34 0 1124

Well, for LMS verification, it would be the time taken for LMS-OTS verification, plus one hash [1] per Merkle tree height $$L$$ (which is either 5, 10, 15, 20 or 25).
On the other hand, for LMS signing, it's not as clear, as there are a number of possible ways to precompute Merkle tree state - the total time taken to generate the original public key is $$2^L( p \cdot(2^w - 1) + 1 ) - 1$$; however depending on how much state you save, it may be as small as $$p\cdot(2^w-1)/2$$ (assuming you save all the state), or as much as generating the original public key (assuming you don't save any of the state), or it might be circa $$p\cdot(2^w-1)(k + 1/2)$$ for some small $$k$$, assuming you use a Merkle tree walking algorithm.
• I came across this, and I think that the formula p*(2^w - 1) + 1) may not reflect the computational effort, because for the compression K = H(...), it does not consider how many blocks SHA-256 has to process. It may be one call of the hash function's API, but a big input would result in more compression operations (e.g. w=1 -> p=265: K = H(I || u32str(q) || u16str(D_PBLC) || y[0] || ... || y[p-1]) with each y[i] = 32 byte -> K = H(...) receives 8502 bytes input -> 133 compressions a 64 byte (SHA256 block size) only for the compression K. Maybe somebody can confirm that? May 1 at 14:56
• @radix: for $W=1$, yes, you have a point. Normally, we don't use a $W$ that small; instead, we use $W=4$ or $W=8$, and in that case, the top-level hash at the LMOTS level is a small effect... May 1 at 16:15