Note on speed of verification in SLH-DSA
Here I’ll compare on the verification functionality of LMS and SLH-DSA. The XMSS is not mentioned, but as both LMS and XMSS are quite similar in this sense, we probably can observe similar results (XMSS is slightly slower than LMS).
When comparing stateful and stateless hash-based signature schemes, the main benefit of the former is significantly shorter signature sizes and much faster verification. The difference in signature size is significant. I summarised differences in a table below, but in brief, an LMS signature is around 4KB, while a signature with SLH-DSA at a similar security level is closer to <50KB, hence ~10x bigger.
| SLH-DSA param | PubKey | Signature | Security | LMS param | SK | PK | Sig |
|---|---|---|---|---|---|---|---|
| SLH-DSA-SHA2-128s | 32 | 7856 | 128 | - | - | - | - |
| SLH-DSA-SHA2-128f | 32 | 17088 | 128 | - | - | - | - |
| SLH-DSA-SHA2-192s | 48 | 16224 | 192 | LMS-SHA2-M24-H25-W8 | 44 | 48 | 1260 |
| SLH-DSA-SHA2-192f | 48 | 35664 | 192 | LMS-SHA2-M24-H25-W1 | 44 | 48 | 5436 |
| SLH-DSA-SHA2-256s | 64 | 29792 | 256 | LMS-SHA2-M32-H25-W8 | 52 | 56 | 1932 |
| SLH-DSA-SHA2-128f | 64 | 49856 | 256 | LMS-SHA2-M32-H25-W1 | 52 | 56 | 9324 |
For SHA2-based LMS, there are 40 different parameterizations possible. In the table above we used extreme values. Parameterization with the W1 postfix indicates large, but fast verification and the one with W8 postfix is a parameterization that provides small signatures, but slow verification.
When it comes to SLH-DSA – the s postfix indicates small parameter sets and f indicates the fast one. But, contrary to LMS, the verification procedure of s parameterization is faster than f. That is related to the design of the verification algorithm – namely, a shorter signature implies fewer evaluations of the hash function.
To give some numbers, the runtime of function F() dominates the runtime of SLH-DSA. We calculated (average) the number of calls to that function as well as the percentage of time the verification algorithm spends in the F() function. The results are presented in the table below. One should notice that there are much fewer calls to the F() in the case of s variant.
| 128f | 192f | 256f | 128s | 192s | 256s | |
|---|---|---|---|---|---|---|
No of invocations of function F() |
5908 | 8620 | 8633 | 1886 | 2751 | 4067 |
% time spent in F() |
94.8% | 95.7% | 95.2% | 88.1% | 89.3% | 90.9% |