# Difference between XMSS and MSS-SPR

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?

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 veriﬁcation key also consists of n bit
strings of length n, since half of the veriﬁcation 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).

• I missed that claim. For the "why" question, the WOTS paper used in XMSS has been published later than the MSS-SPR, so it is quite clear. It's quite sad such an unfair comparison has been published without modification. – Distic Jul 4 '19 at 7:03