1
$\begingroup$

I'm doing some comparison on hash-based signature schemes. I am reading about one of the most recent schemes, XMSS^MT, and trying to figure out its actual public and private key sizes for concrete parameters.

I found this paper which has some numbers for a variety of parameters, however it does not say what's the size of the private key (even in terms of XMSS parameters). Has anyone figured this out?

$\endgroup$
2
$\begingroup$

The problem with talking about XMSS private key size is that there is a fairly large number of size/performance trade-offs, and so there's no one answer.

At the minimum, the private key needs to have the value used to generate the WOTS+ private keys ($n$ bits), the $n$ bit public seed, and current leaf index (20, 40 or 60 bits, depending on the parameter set). In addition, if you follow the recommendations of the RFC, you also have an $n$ bit SK_PRF value (to do randomized hashing), as well as the $n$ bit root (although you could recompute that on the fly if you had to).

If you do this (including the recommendations), this translates to a private key (for $n=32$) of 136 bytes (assuming a parameter set with a hypertree of 60 levels).

On the other hand, if you just did this, this would imply that, with every signature you generated, you would need to reconstruct every XMSS tree involved; that's not cheap.

Now, the obvious thing to do is also include the internal contents of each XMSS tree; this makes things fast, but vastly increases the size of the private key.

As a compromise, you can save a handful of internal Merkle tree elements, and use a tree walking algorithm, such a BDS to generate the next authentication path incrementally (and don't forget, if you're doing XMSS^MT, to start work on building the next Merkle tree while you're traversing this one, if you want to avoid having to build the entire next XMSS tree when you exhaust this one. There are a number of tree walking algorithms known, with various trade-offs (and tweakable parameters).

In addition, you may also want to include other things in your private key. For example, if you are interested in detecting fault attacks (where a miscomputation of a lower level XMSS public key causes the next higher WOTS+ signature to sign two different messages over two different signature operations), you may want to store the signature (or public key) of the current lower level tree (or, alternatively, the hash of the signature); that way, either you never actually sign with the same WOTS+ private key twice (or, alternatively, you catch it if a miscompute causes you to generate two different signatures).

All this leads to the fact that there are a number of different trade-offs you can make, and hence, no simple answer to 'how big is the private key is'


You asked for an example using BDS; lets lay out some assumptions:

  • We'll assume that the private key contains the various central information I listed above, a BDS tree for each Merkle tree in the hierarchy, a place to construct the next Merkle tree (for all Merkle tree levels except the top), and nothing else

  • We'll use the BDS algorithm with the internal variable $k=2$ (note: the BDS paper stated that the algorithm works only if $H-B$ was even; a simple modification to the algorithm makes it work in all cases).

Then, the central information takes $4n+h$ bits.

And, if we denote $H=h/d$ as the height of each Merkle tree, each BSDS tree (both the current and the next one being constructed; total of $2d-1$) takes up no more than $n(\lfloor 3.5H \rfloor - 4)$ memory (actually, it uses a bit less, however a characterization of how much less is nontrivial).

In addition, each of the active BDS structures (total of $d$ of them) need some auxiliary information to track what's stored in their stacks (we don't need to store auxiliary information for Merkle trees we are in the process of building). I don't feel up to examining precisely how much memory this takes up; I'll just estimate it as $8H$ bits.

This gives a total of $n(4+(2d+1)(\lfloor 3.5h/d \rfloor - 4)) + 9h$ bits

Different assumptions give different numbers (and could be higher, could be lower...)

$\endgroup$
  • $\begingroup$ Yes I understand that there can't be a straight answer since it involves many parameters. So assuming we do the BDS approach, what's the key size in terms of XMSS parameters n, h, d, w and length? (not sure if all those parameters affect its size) $\endgroup$ – bomberb17 Jan 29 at 5:02

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.