0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Distic Jul 4 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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