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?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
