0
$\begingroup$

This is a follow-up to a recent question of mine.

I am looking to find the public key and signature sizes for the XMSS signature scheme, in terms of the XMSS parameters (length $\ell$, height $h$ and security parameter $n$). I found the following 2 papers that have contradictory answers and I'm confused.

The original XMSS paper on pg.5 says:

The bit length of the XMSS public key is $(2(h+ \left \lceil log \ell \right \rceil) + 1)n$, an XMSS signature has length $(\ell+h)n$ (...)

and a more recent paper on pg.6 says that the public key has length of $4 + 2n$ and the signature size is $4+n(\ell+h+1)$

Can someone explain me which of the two is true and why?

$\endgroup$
2
$\begingroup$

The original XMSS paper (eprint 2011/484) discusses an older version of XMSS, which does use rather larger public keys (and I suspect they got the signature size slightly wrong - they forget the idx_sig part of the signature which specifies which WOTS+ leaf they're using).

The XMSS RFC defines a newer version, with considerably smaller public keys (and slightly larger signatures). The more recent XMSS/LMS comparison paper which you cited (eprint 2017/349) uses the RFC version of XMSS for the comparison.

I believe that the version defined in the RFC is what people generally use, and so the values in the comparison paper are the ones which are accurate.

As for the differences between the original version of XMSS and the RFC, well, here's the main difference: in the original paper used masks stored in the public keys to provide randomization; the problem with this is, because they use the same masks in different parts of the Merkle tree, this opens them up to multitarget preimage attacks. In the RFC version, they compute the masks dynamically (and hence they don't need to be in the public key). Because each mask is now different, multitarget preimage attacks don't apply (at the cost of the computation needed to generate the masks dynamically).

A more minor difference is that the RFC version includes a randomizer 'r' in with the signature (which is hashed along with the message); making this randomizer be unpredictable means that we don't depend on the collision resistance of the hash function (given that we rely on preimage or second preimage resistance everywhere else, this is a win).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, still however I see a minor difference in RFC par. 4.1.8 which says the signature size is $(4 + n + (\ell + h) * n)$. $\endgroup$ – bomberb17 Feb 4 at 0:53
  • $\begingroup$ @bomberb17: I believe I mentioned the differences; the 4 is the idx_sig value (which I believe they forgot to account for in the original XMSS paper, and the $n$ is the randomizer 'r' which I mentioned in the last paragraph $\endgroup$ – poncho Feb 4 at 1:36

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.