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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\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$ Commented Jul 4, 2019 at 7:03

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.