Speeding up XMSS

Question

To compute the XMSS Tree root, one needs to compute all the 2^h keys and hash them together. The higher the height of the tree, the more keys there are and the longer the KeyGen computation. The signing and verifing is quick, but every signature creation needs to compute the authentication path, thus it needs to recompute the root again. For h=10 or 16 it is not a problem, but for h=20 the times of signing key generation require about 20minutes, while h=10 needs only 2 seconds. Is there a way to speed up the h=20 KeyGeneration? I know an algorithm BDS exists, which speeds up the authentication path generation, but how big is the speedup compared to the standard implementation? The keys still need to be generated in order to produce the XMSS leaves, thus even if one would save all leaves, it still takes a lot of time to compute all 2^h leaves. How can one speed up the leaves generation?

Answer 1

I know an algorithm BDS exists, which speeds up the authentication path generation, but how big is the speedup compared to the standard implementation?

I assume by "standard implementation", you mean one that regenerates the entire tree on each signature.

When BDS outputs an authentication path, it needs to compute $O(h)$ WOTS+ public keys (to get ready for the next authentication path); what this translates in practice for $h=20$ is 10 public keys per signature (actually, it alternates between 9 and 10 between successive signatures); this compares to 1,048,575 public keys for the "standard implementation"; because the cost of computing these public keys is the bulk of the work when generating an authentication path, we're looking at a factor of 100,000 speed up (!).

And, if BDS isn't fast enough for you, there are other algorithms, such as Fractal or one I have dubbed BKN (the authors didn't give it an official name) that require even less computation (possibly at the cost of increased storage for holding intermediate Merkle tree nodes).

The keys still need to be generated in order to produce the XMSS leaves, thus even if one would save all leaves, it still takes a lot of time to compute all 2^h leaves. How can one speed up the leaves generation?

You are correct; fancy Merkle tree walking algorithms don't help during the initial key generation; here are some ideas that might give some speed-up (some of which are easier than others):

• Use an XMSS^MT parameter set instead; for example, XMSSMT-SHA2_20/2_256 also gives you 1+ million signatures, and it makes key generation much faster

• Are you using a SHAKE-based parameter set or a SHA-512 parameter set? Consider switching to the equivalent SHA-256 parameter set - in my experience, SHA-256 is considerably faster in this context (at least on the CPUs I've tried them out on).

• If you know that you really only need (say) 100,000 signatures to be generated with this private key, consider generating only the first 100,000 WOTS+ public keys, and use arbitrary values for the public keys past that. You wouldn't be able to sign with these arbitrary values - however if you're assumption about the number of signatures is correct, you will never need to.

• You can speed up the hash function using AVX instructions (or SHA-NI instructions in the case of SHA-256)

• You can build separate parts of the tree using different threads.

• You might consider using LMS rather than XMSS (LMS is several times faster for equivalent parameter sets)