0
$\begingroup$

What is the parameter for? I read that in XMSS it is a member of the set {4, 16}, but what does it exactly mean? I also read that the bigger the $w$ parameter, the shorter the signatures but the keygen, sign and vrfy become slower. How do I pick an optimal $w$ parameter? Is it the height of the Merkle tree?

$\endgroup$
1
$\begingroup$

This paper answers your question most succinctly:

The size of a Winternitz signature is roughly $mn/w$ bits and signing roughly requires $2^wm/w$ hash operations, where $m$ is the bit length of the hash value to be signed, $n$ is the output length of the hash function used in the scheme, and $w$ is the Winternitz parameter determining the tradeoff between signature size and signature generation time.

The reference paper here goes into detail on how the parameter $w$ is used in various algorithms. Per the paper:

The parameter $w$ can be chosen from the set {4, 16}. A larger value of $w$ results in shorter signatures but slower overall signing operations; it has little effect on security. Choices of $w$ are limited to the values 4 and 16 since these values yield optimal trade-offs and easy implementation.

An example of the parameter being used is in Algorithm 5: WOTS_sign - Generating a signature from a private key and a message.

Section 2.2 of this paper goes into further detail about time-memory tradeoff.

Additionally section 4 goes into further depth with performance comparisons of different parameters.

$\endgroup$
1
$\begingroup$

The height of the merkle tree is an independent parameter. The Winternitz parameter — $w$ — comes up because to sign or verify a WOTS+ signature the first step is to encode your message as a list of integers from $0$ to $w - 1$ (inclusive). For example the string "hello" is encoded in ascii as 01101000 01100101 01101100 01101100 01101111. If $w$ were $16$ then each integer would correspond to $4$ bits of the message. Like this:

0110 1000 0110 0101 0110 1100 0110 1100 0110 1111
   6    8    6    5    6   12    6   12    6   15

If $w$ were $4$ then each integer would correspond to $2$ bits and the sequence would be like that:

01 10 10 00 01 10 01 01 01 10 11 00 01 10 11 00 01 10 11 11
 1  2  2  0  1  2  1  1  1  2  3  0  1  2  3  0  1  2  3  3

So $4$ and $16$ are just values that make conversion simple and efficient. A big $w$ makes for a small sequence of big numbers, a small $w$ makes a big sequence of small numbers. Bigger sequences tend to result in bigger signatures. Bigger numbers increase the amount of hashes you need to calculate.

If your hashes have $n$ bytes and you're signing a message of $m$ bytes then the length of your signature will be

$$n\cdot\left(\left\lceil \frac{8\cdot m}{\log_2(w)} \right\rceil + \left\lfloor \frac{\log_2\left(\left\lceil \frac{8\cdot m}{\log_2(w)} \right\rceil \cdot (w - 1)\right)}{\log_2(w)} \right\rfloor + 1 \right)$$

bytes. So you could try plugging some values of $w$ to see which ones give you a reasonable size.

$\endgroup$

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.