1
$\begingroup$

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
$\endgroup$
0

1 Answer 1

1
$\begingroup$

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

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.


[1]: Actually, because these hashes involve 2 SHA-256 compression operations, it is more precise to consider them two hashes; on the other hand, compared to the time taking to compute the Winternitz chains, the Merkle tree hashes can mostly be ignored)

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – radix
    May 1 at 14:56
  • 1
    $\begingroup$ @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... $\endgroup$
    – poncho
    May 1 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.