Difference between XMSS and MSS-SPR

Question

I am currently studying stateful hash based signatures. In the XMSS paper the authors claim that XMSS signatures are 4 times smaller than those of MSS-SPR. However I do not get how it is possible, because I do not understand the differences between both of them.

As the paper of MSS-SPR does not contain any One Time Signature scheme, a fair comparison should use the same OTS in both schemes. The only other difference I get is pseudo-random versus true random but it is unsufficient because it should not affect signature size:

• pseudo-random generation of secret keys must not change the signature at all

• pseudo-random generation of salt is helpful to reduce the public key size, but should not change the signature size either

So can someone explain to me where does this factor 4 come from?

Answer 1

As the paper of MSS-SPR does not contain any One Time Signature scheme

Actually, that's not true; they assume Lamport signatures (specifically, a version they call LD-OTS).

When using the LD–OTS, the one-time signature of the message consists of
n bit strings of length n. The verification key also consists of n bit
strings of length n, since half of the verification key can be computed
from the signature.

Hence, the OTS signature is $2n^2$ bits long; in contrast, a WOTS+ signature (which XMSS uses) is $(n/4+3)n$ bits long, considerably shorter.

Now, the difference is actually larger than a factor of 4 - I believe that, if we take account of the fixed overhead of the authentication path (which is the same in both cases), and MSS-SPR's use of a somewhat smaller $n$, the two are closer.

a fair comparison should use the same OTS in both schemes.

True; however as specified, the comparison isn't fair.

As for why MSS-SPR uses LD-OTS (rather than some Winternitz-based scheme), I'm not one of the designers, and so I can't be certain. My best guess is that they couldn't come up with a shorter scheme that preserves the "not relying on collision resistance" property (which WOTS+ does).