# Leighton-Micali Hash-Based Signatures

Pages: 61
Informational

```5.  Leighton-Micali Signatures

The Leighton-Micali Signature (LMS) method can sign a potentially
large but fixed number of messages.  An LMS system uses two
cryptographic components: a one-time signature method and a hash
function.  Each LMS public/private key pair is associated with a
perfect binary tree, each node of which contains an m-byte value,
where m is the output length of the hash function.  Each leaf of the
tree contains the value of the public key of an LM-OTS public/private
key pair.  The value contained by the root of the tree is the LMS
public key.  Each interior node is computed by applying the hash
function to the concatenation of the values of its children nodes.

Each node of the tree is associated with a node number, an unsigned
integer that is denoted as node_num in the algorithms below, which is
computed as follows.  The root node has node number 1; for each node
with node number N < 2^h (where h is the height of the tree), its
left child has node number 2*N, while its right child has node number
2*N + 1.  The result of this is that each node within the tree will
have a unique node number, and the leaves will have node numbers 2^h,
(2^h)+1, (2^h)+2, ..., (2^h)+(2^h)-1.  In general, the j-th node at
level i has node number 2^i + j.  The node number can conveniently be
computed when it is needed in the LMS algorithms, as described in
those algorithms.

5.1.  Parameters

An LMS system has the following parameters:

h : the height of the tree

m : the number of bytes associated with each node

H : a second-preimage-resistant cryptographic hash function that
accepts byte strings of any length and returns an m-byte string.

There are 2^h leaves in the tree.

The overall strength of LMS signatures is governed by the weaker of
the hash function used within the LM-OTS and the hash function used
within the LMS system.  In order to minimize the risk, these two hash
functions SHOULD be the same (so that an attacker could not take
advantage of the weaker hash function choice).
```
```                 +--------------------+--------+----+----+
| Name               | H      | m  | h  |
+--------------------+--------+----+----+
| LMS_SHA256_M32_H5  | SHA256 | 32 | 5  |
|                    |        |    |    |
| LMS_SHA256_M32_H10 | SHA256 | 32 | 10 |
|                    |        |    |    |
| LMS_SHA256_M32_H15 | SHA256 | 32 | 15 |
|                    |        |    |    |
| LMS_SHA256_M32_H20 | SHA256 | 32 | 20 |
|                    |        |    |    |
| LMS_SHA256_M32_H25 | SHA256 | 32 | 25 |
+--------------------+--------+----+----+

Table 2

5.2.  LMS Private Key

The format of the LMS private key is an internal matter to the
implementation, and this document does not attempt to define it.  One
possibility is that it may consist of an array OTS_PRIV[] of 2^h
LM-OTS private keys and the leaf number q of the next LM-OTS private
key that has not yet been used.  The q-th element of OTS_PRIV[] is
generated using Algorithm 0 with the identifiers I, q.  The leaf
number q is initialized to zero when the LMS private key is created.
The process is as follows:

Algorithm 5: Computing an LMS Private Key.

1. Determine h and m from the typecode and Table 2.

2. Set I to a uniformly random 16-byte string.

3. Compute the array OTS_PRIV[] as follows:
for ( q = 0; q < 2^h; q = q + 1) {
OTS_PRIV[q] = LM-OTS private key with identifiers I, q
}

4. q = 0

An LMS private key MAY be generated pseudorandomly from a secret
value; in this case, the secret value MUST be at least m bytes long
and uniformly random and MUST NOT be used for any other purpose than
the generation of the LMS private key.  The details of how this
process is done do not affect interoperability; that is, the public
key verification operation is independent of these details.
Appendix A provides an example of a pseudorandom method for computing
an LMS private key.
```
```   The signature-generation logic uses q as the next leaf to use; hence,
step 4 starts it off at the leftmost leaf.  Because the signature
process increments q after the signature operation, the first
signature will have q=0.

5.3.  LMS Public Key

An LMS public key is defined as follows, where we denote the public
key final hash value (namely, the K value computed in Algorithm 1)
associated with the i-th LM-OTS private key as OTS_PUB_HASH[i], with
i ranging from 0 to (2^h)-1.  Each instance of an LMS public/private
key pair is associated with a balanced binary tree, and the nodes of
that tree are indexed from 1 to 2^(h+1)-1.  Each node is associated
with an m-byte string.  The string for the r-th node is denoted as
T[r] and defined as

if r >= 2^h:
H(I||u32str(r)||u16str(D_LEAF)||OTS_PUB_HASH[r-2^h])
else
H(I||u32str(r)||u16str(D_INTR)||T[2*r]||T[2*r+1])

where D_LEAF is the fixed two-byte value 0x8282 and D_INTR is the
fixed two-byte value 0x8383, both of which are used to distinguish
this hash from every other hash in this system.

When we have r >= 2^h, then we are processing a leaf node (and thus
hashing only a single LM-OTS public key).  When we have r < 2^h, then
we are processing an internal node -- that is, a node with two child
nodes that we need to combine.

The LMS public key can be represented as the byte string

u32str(type) || u32str(otstype) || I || T

Section 3.3 specifies the format of the type variable.  The value
otstype is the parameter set for the LM-OTS public/private key pairs
used.  The value I is the private key identifier and is the value
used for all computations for the same LMS tree.  The value T can
be computed via recursive application of the above equation or by any
equivalent method.  An iterative procedure is outlined in Appendix C.
```
```5.4.  LMS Signature

An LMS signature consists of

the number q of the leaf associated with the LM-OTS signature, as
a four-byte unsigned integer in network byte order, an LM-OTS
signature,

a typecode indicating the particular LMS algorithm,

an array of h m-byte values that is associated with the path
through the tree from the leaf associated with the LM-OTS
signature to the root.

Symbolically, the signature can be represented as

u32str(q) || lmots_signature || u32str(type) ||
path || path || path || ... || path[h-1]

Section 3.3 formally defines the format of the signature as the
lms_signature structure.  The array for a tree with height h will
have h values and contains the values of the siblings of (that is, is
adjacent to) the nodes on the path from the leaf to the root, where
the sibling to node A is the other node that shares node A's parent.
In the signature, 0 is counted from the bottom level of the tree, and
so path is the value of the node adjacent to leaf node q; path
is the second-level node that is adjacent to leaf node q's parent,
and so on up the tree until we get to path[h-1], which is the value
of the next-to-the-top-level node whose branch the leaf node q does
not reside in.

Below is a simple example of the authentication path for h=3 and q=2.
The leaf marked OTS is the one-time signature that is used to sign
the actual message.  The nodes on the path from the OTS public key to
the root are marked with a *, while the nodes that are used within
the path array are marked with **.  The values in the path array are
those nodes that are siblings of the nodes on the path; path is
the leaf** node that is adjacent to the OTS public key (which is the
start of the path); path is the T** node that is the sibling of
the second node T* on the path, and path is the T** node
that is the sibling of the third node T* on the path.
```
```                                Root
|
---------------------------------
|                               |
T*                          T**
|                               |
------------------            -----------------
|                |            |               |
T**           T*         T            T
|                |            |               |
---------       ----------     --------       ---------
|       |       |        |     |      |       |       |
leaf    leaf    OTS  leaf**   leaf   leaf    leaf    leaf

The idea behind this authentication path is that it allows us to
validate the OTS hash with using h path array values and hash
computations.  What the verifier does is recompute the hashes up the
path; first, it hashes the given OTS and path value, giving a
tentative T' value.  Then, it hashes its path and tentative
T' value to get a tentative T' value.  Then, it hashes that and
the path value to get a tentative Root' value.  If that value is
the known public key of the Merkle tree, then we can assume that the
value T' it got was the correct T value in the original tree,
and so the T' value it got was the correct T value in the
original tree, and so the OTS public key is the same as in the
original and, hence, is correct.

5.4.1.  LMS Signature Generation

To compute the LMS signature of a message with an LMS private key,
the signer first computes the LM-OTS signature of the message using
the leaf number of the next unused LM-OTS private key.  The leaf
number q in the signature is set to the leaf number of the LMS
private key that was used in the signature.  Before releasing the
signature, the leaf number q in the LMS private key MUST be
incremented to prevent the LM-OTS private key from being used again.
If the LMS private key is maintained in nonvolatile memory, then the
implementation MUST ensure that the incremented value has been stored
before releasing the signature.  The issue this tries to prevent is a
scenario where a) we generate a signature using one LM-OTS private
key and release it to the application, b) before we update the
nonvolatile memory, we crash, and c) we reboot and generate a second
signature using the same LM-OTS private key.  With two different
signatures using the same LM-OTS private key, an attacker could
potentially generate a forged signature of a third message.
```
```   The array of node values in the signature MAY be computed in any way.
There are many potential time/storage trade-offs that can be applied.
The fastest alternative is to store all of the nodes of the tree and
set the array in the signature by copying them; pseudocode to do so
appears in Appendix D.  The least storage-intensive alternative is to
recompute all of the nodes for each signature.  Note that the details
of this procedure are not important for interoperability; it is not
necessary to know any of these details in order to perform the
signature-verification operation.  The internal nodes of the tree
need not be kept secret, and thus a node-caching scheme that stores
only internal nodes can sidestep the need for strong protections.

Several useful time/storage trade-offs are described in the "Small-
Memory LM Schemes" section of [USPTO5432852].

5.4.2.  LMS Signature Verification

An LMS signature is verified by first using the LM-OTS signature
verification algorithm (Algorithm 4b) to compute the LM-OTS public
key from the LM-OTS signature and the message.  The value of that
public key is then assigned to the associated leaf of the LMS tree,
and then the root of the tree is computed from the leaf value and the
array path[] as described in Algorithm 6 below.  If the root value
matches the public key, then the signature is valid; otherwise, the
signature verification fails.

Algorithm 6: LMS Signature Verification

1. If the public key is not at least eight bytes long, return
INVALID.

2. Parse pubtype, I, and T from the public key as follows:

a. pubtype = strTou32(first 4 bytes of public key)

b. ots_typecode = strTou32(next 4 bytes of public key)

c. Set m according to pubtype, based on Table 2.

d. If the public key is not exactly 24 + m bytes
long, return INVALID.

e. I = next 16 bytes of the public key

f. T = next m bytes of the public key
```
```     3. Compute the LMS Public Key Candidate Tc from the signature,
message, identifier, pubtype, and ots_typecode, using
Algorithm 6a.

4. If Tc is equal to T, return VALID; otherwise, return INVALID.

Algorithm 6a: Computing an LMS Public Key Candidate from a Signature,
Message, Identifier, and Algorithm Typecodes

1. If the signature is not at least eight bytes long,
return INVALID.

2. Parse sigtype, q, lmots_signature, and path from the signature
as follows:

a. q = strTou32(first 4 bytes of signature)

b. otssigtype = strTou32(next 4 bytes of signature)

c. If otssigtype is not the OTS typecode from the public key,
return INVALID.

d. Set n, p according to otssigtype and Table 1; if the
signature is not at least 12 + n * (p + 1) bytes long,
return INVALID.

e. lmots_signature = bytes 4 through 7 + n * (p + 1)
of signature

f. sigtype = strTou32(bytes 8 + n * (p + 1)) through
11 + n * (p + 1) of signature)

g. If sigtype is not the LM typecode from the public key,
return INVALID.

h. Set m, h according to sigtype and Table 2.

i. If q >= 2^h or the signature is not exactly
12 + n * (p + 1) + m * h bytes long,
return INVALID.

j. Set path as follows:
path = next m bytes of signature
path = next m bytes of signature
...
path[h-1] = next m bytes of signature
```
```     3. Kc = candidate public key computed by applying Algorithm 4b
to the signature lmots_signature, the message, and the
identifiers I, q

4. Compute the candidate LMS root value Tc as follows:
node_num = 2^h + q
tmp = H(I || u32str(node_num) || u16str(D_LEAF) || Kc)
i = 0
while (node_num > 1) {
if (node_num is odd):
tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||path[i]||tmp)
else:
tmp = H(I||u32str(node_num/2)||u16str(D_INTR)||tmp||path[i])
node_num = node_num/2
i = i + 1
}
Tc = tmp

5. Return Tc.

6.  Hierarchical Signatures

In scenarios where it is necessary to minimize the time taken by the
public key generation process, the Hierarchical Signature System
(HSS) can be used.  This hierarchical scheme, which we describe in
this section, uses the LMS scheme as a component.  In HSS, we have a
sequence of L LMS trees, where the public key for the first LMS tree
is included in the public key of the HSS system, each LMS private key
signs the next LMS public key, and the last LMS private key signs the
actual message.  For example, if we have a three-level hierarchy
(L=3), then to sign a message, we would have:

The first LMS private key (level 0) signs a level 1 LMS public
key.

The second LMS private key (level 1) signs a level 2 LMS public
key.

The third LMS private key (level 2) signs the message.

The root of the level 0 LMS tree is contained in the HSS public key.

To verify the LMS signature, we would verify all the signatures:

We would verify that the level 1 LMS public key is correctly
signed by the level 0 signature.
```
```      We would verify that the level 2 LMS public key is correctly
signed by the level 1 signature.

We would verify that the message is correctly signed by the level
2 signature.

We would accept the HSS signature only if all the signatures
validated.

During the signature-generation process, we sign messages with the
lowest (level L-1) LMS tree.  Once we have used all the leafs in that
tree to sign messages, we would discard it, generate a fresh LMS
tree, and sign it with the next (level L-2) LMS tree (and when that
is used up, recursively generate and sign a fresh level L-2 LMS
tree).

HSS, in essence, utilizes a tree of LMS trees.  There is a single LMS
tree at level 0 (the root).  Each LMS tree (actually, the private key
corresponding to the LMS tree) at level i is used to sign 2^h objects
(where h is the height of trees at level i).  If i < L-1, then each
object will be another LMS tree (actually, the public key) at level
i+1; if i = L-1, we've reached the bottom of the HSS tree, and so
each object will be a message from the application.  The HSS public
key contains the public key of the LMS tree at the root, and an HSS
signature is associated with a path from the root of the HSS tree to
the leaf.

Compared to LMS, HSS has a much reduced public key generation time,
as only the root tree needs to be generated prior to the distribution
of the HSS public key.  For example, an L=3 tree (with h=10 at each
level) would have one level 0 LMS tree, 2^10 level 1 LMS trees (with
each such level 1 public key signed by one of the 1024 level 0 OTS
public keys), and 2^20 level 2 LMS trees.  Only 1024 OTS public keys
need to be computed to generate the HSS public key (as you need to
compute only the level 0 LMS tree to compute that value; you can, of
course, decide to compute the initial level 1 and level 2 LMS trees).
In addition, the 2^20 level 2 LMS trees can jointly sign a total of
over a billion messages.  In contrast, a single LMS tree that could
sign a billion messages would require a billion OTS public keys to be
computed first (if h=30 were allowed in a supported parameter set).

Each LMS tree within the hierarchy is associated with a distinct LMS
public key, private key, signature, and identifier.  The number of
levels is denoted as L and is between one and eight, inclusive.  The
following notation is used, where i is an integer between 0 and L-1
inclusive, and the root of the hierarchy is level 0:

prv[i] is the current LMS private key of the i-th level.
```
```      pub[i] is the current LMS public key of the i-th level, as
described in Section 5.3.

sig[i] is the LMS signature of public key pub[i+1] generated using
the private key prv[i].

It is expected that the above arrays are maintained for the course of
the HSS key.  The contents of the prv[] array MUST be kept private;
the pub[] and sig[] array may be revealed should the implementation
find that convenient.

In this section, we say that an N-time private key is exhausted when
it has generated N signatures; thus, it can no longer be used for
signing.

For i > 0, the values prv[i], pub[i], and (for all values of i)
sig[i] will be updated over time as private keys are exhausted and

When these key pairs are updated (or initially generated before the
first message is signed), then the LMS key generation processes
outlined in Sections 5.2 and 5.3 are performed.  If the generated key
pairs are for level i of the HSS hierarchy, then we store the public
key in pub[i] and the private key in prv[i].  In addition, if i > 0,
then we sign the generated public key with the LMS private key at
level i-1, placing the signature into sig[i-1].  When the LMS key
pair is generated, the key pair and the corresponding identifier MUST
be generated independently of all other key pairs.

HSS allows L=1, in which case the HSS public key and signature
formats are essentially the LMS public key and signature formats,
prepended by a fixed field.  Since HSS with L=1 has very little
overhead compared to LMS, all implementations MUST support HSS in
order to maximize interoperability.

We specifically allow different LMS levels to use different parameter
sets.  For example, the 0-th LMS public key (the root) may use the
LMS_SHA256_M32_H15 parameter set, while the 1-th public key may use
LMS_SHA256_M32_H10.  There are practical reasons to allow this; for
one, the signer may decide to store parts of the 0-th LMS tree (that
it needs to construct while computing the public key) to accelerate
later operations.  As the 0-th tree is never updated, these internal
nodes will never need to be recomputed.  In addition, during the
signature-generation operation, almost all the operations involved
with updating the authentication path occur with the bottom (L-1th)
LMS public key; hence, it may be useful to select the parameter set
for that public key to have a shorter LMS tree.
```
```   A close reading of the HSS verification pseudocode shows that it
would allow the parameters of the nontop LMS public keys to change
over time; for example, the signer might initially have the 1-th LMS
public key use the LMS_SHA256_M32_H10 parameter set, but when that
tree is exhausted, the signer might replace it with an LMS public key
that uses the LMS_SHA256_M32_H15 parameter set.  While this would
work with the example verification pseudocode, the signer MUST NOT
change the parameter sets for a specific level.  This prohibition is
to support verifiers that may keep state over the course of several
signature verifications.

6.1.  Key Generation

The public key of the HSS scheme consists of the number of levels L,
followed by pub, the public key of the top level.

The HSS private key consists of prv, ... , prv[L-1], along with
the associated pub, ... pub[L-1] and sig, ..., sig[L-2] values.
As stated earlier, the values of the pub[] and sig[] arrays need not
be kept secret and may be revealed.  The value of pub does not
change (and, except for the index q, the value of prv need not
change); however, the values of pub[i] and prv[i] are dynamic for i >
0 and are changed by the signature-generation algorithm.

During the key generation, the public and private keys are
initialized.  Here is some pseudocode that explains the key-
generation logic:

Algorithm 7: Generating an HSS Key Pair

1. Generate an LMS key pair, as specified in Sections 5.2 and 5.3,
placing the private key into priv, and the public key into
pub

2. For i = 1 to L-1 do {
generate an LMS key pair, placing the private key into priv[i]
and the public key into pub[i]

sig[i-1] = lms_signature( pub[i], priv[i-1] )
}

3. Return u32str(L) || pub as the public key and the priv[],
pub[], and sig[] arrays as the private key

In the above algorithm, each LMS public/private key pair generated
MUST be generated independently.
```
```   Note that the value of the public key does not depend on the
execution of step 2.  As a result, an implementation may decide to
delay step 2 until later -- for example, during the initial
signature-generation operation.

6.2.  Signature Generation

To sign a message using an HSS key pair, the following steps are
performed:

If prv[L-1] is exhausted, then determine the smallest integer d
such that all of the private keys prv[d], prv[d+1], ... , prv[L-1]
are exhausted.  If d is equal to zero, then the HSS key pair is
exhausted, and it MUST NOT generate any more signatures.
Otherwise, the key pairs for levels d through L-1 must be
regenerated during the signature-generation process, as follows.
For i from d to L-1, a new LMS public and private key pair with a
new identifier is generated, pub[i] and prv[i] are set to those
values, then the public key pub[i] is signed with prv[i-1], and
sig[i-1] is set to the resulting value.

The message is signed with prv[L-1], and the value sig[L-1] is set
to that result.

The value of the HSS signature is set as follows.  We let
signed_pub_key denote an array of octet strings, where
signed_pub_key[i] = sig[i] || pub[i+1], for i between 0 and
Nspk-1, inclusive, where Nspk = L-1 denotes the number of signed
public keys.  Then the HSS signature is u32str(Nspk) ||
signed_pub_key || ... || signed_pub_key[Nspk-1] || sig[Nspk].

Note that the number of signed_pub_key elements in the signature
is indicated by the value Nspk that appears in the initial four
bytes of the signature.

Here is some pseudocode of the above logic:

Algorithm 8: Generating an HSS signature

1. If the message-signing key prv[L-1] is exhausted, regenerate
that key pair, together with any parent key pairs that might
be necessary.

If the root key pair is exhausted, then the HSS key pair is
exhausted and MUST NOT generate any more signatures.
```
```        d = L
while (prv[d-1].q == 2^(prv[d-1].h)) {
d = d - 1
if (d == 0)
return FAILURE
}
while (d < L) {
create lms key pair pub[d], prv[d]
sig[d-1] = lms_signature( pub[d], prv[d-1] )
d = d + 1
}

2. Sign the message.
sig[L-1] = lms_signature( msg, prv[L-1] )

3. Create the list of signed public keys.
i = 0;
while (i < L-1) {
signed_pub_key[i] = sig[i] || pub[i+1]
i = i + 1
}

4. Return u32str(L-1) || signed_pub_key || ...
|| signed_pub_key[L-2] || sig[L-1]

In the specific case of L=1, the format of an HSS signature is

u32str(0) || sig

In the general case, the format of an HSS signature is

u32str(Nspk) || signed_pub_key || ...
|| signed_pub_key[Nspk-1] || sig[Nspk]

which is equivalent to

u32str(Nspk) || sig || pub || ...
|| sig[Nspk-1] || pub[Nspk] || sig[Nspk]
```
```6.3.  Signature Verification

To verify a signature S and message using the public key pub, perform
the following steps:

The signature S is parsed into its components as follows:

Nspk = strTou32(first four bytes of S)
if Nspk+1 is not equal to the number of levels L in pub:
return INVALID
for (i = 0; i < Nspk; i = i + 1) {
siglist[i] = next LMS signature parsed from S
publist[i] = next LMS public key parsed from S
}
siglist[Nspk] = next LMS signature parsed from S

key = pub
for (i = 0; i < Nspk; i = i + 1) {
sig = siglist[i]
msg = publist[i]
if (lms_verify(msg, key, sig) != VALID):
return INVALID
key = msg
}
return lms_verify(message, key, siglist[Nspk])

Since the length of an LMS signature cannot be known without parsing
it, the HSS signature verification algorithm makes use of an LMS
signature parsing routine that takes as input a string consisting of
an LMS signature with an arbitrary string appended to it and returns
both the LMS signature and the appended string.  The latter is passed
on for further processing.

6.4.  Parameter Set Recommendations

As for guidance as to the number of LMS levels and the size of each,
any discussion of performance is implementation specific.  In
general, the sole drawback for a single LMS tree is the time it takes
to generate the public key; as every LM-OTS public key needs to be
generated, the time this takes can be substantial.  For a two-level
tree, only the top-level LMS tree and the initial bottom-level LMS
tree need to be generated initially (before the first signature is
generated); this will in general be significantly quicker.

To give a general idea of the trade-offs available, we include some
measurements taken with the LMS implementation available at
<https://github.com/cisco/hash-sigs>, taken on a 3.3 GHz Xeon
processor with threading enabled.  We tried various parameter sets,
```
```   all with W=8 (which minimizes signature size, while increasing time).
These are here to give a guideline as to what's possible; for the
computational time, your mileage may vary, depending on the computing
resources you have.  The machine these tests were performed on does
not have the SHA-256 extensions; you could possibly do significantly
better.

+---------+------------+---------+-------------+
| ParmSet | KeyGenTime | SigSize | KeyLifetime |
+---------+------------+---------+-------------+
| 15      | 6 sec      | 1616    | 30 seconds  |
|         |            |         |             |
| 20      | 3 min      | 1776    | 16 minutes  |
|         |            |         |             |
| 25      | 1.5 hour   | 1936    | 9 hours     |
|         |            |         |             |
| 15/10   | 6 sec      | 3172    | 9 hours     |
|         |            |         |             |
| 15/15   | 6 sec      | 3332    | 12 days     |
|         |            |         |             |
| 20/10   | 3 min      | 3332    | 12 days     |
|         |            |         |             |
| 20/15   | 3 min      | 3492    | 1 year      |
|         |            |         |             |
| 25/10   | 1.5 hour   | 3492    | 1 year      |
|         |            |         |             |
| 25/15   | 1.5 hour   | 3652    | 34 years    |
+---------+------------+---------+-------------+

Table 3

ParmSet:  this is the height of the Merkle tree(s); parameter sets
listed as a single integer have L=1 and consist of a single Merkle
tree of that height; parameter sets with L=2 are listed as x/y,
with x being the height of the top-level Merkle tree and y being
the bottom level.

KeyGenTime:  the measured key-generation time; that is, the time
needed to generate the public/private key pair.

SigSize:  the size of a signature (in bytes)

signatures per second.  In practice, we're not likely to get
anywhere close to 1000 signatures per second sustained; if you
have a more appropriate figure for your scenario, this column is
easy to recompute.
```
```   As for signature generation or verification times, those are
moderately insensitive to the above parameter settings (except for
the Winternitz setting and the number of Merkle trees for
verification).  Tests on the same machine (without multithreading)
gave approximately 4 msec to sign a short message, 2.6 msec to
verify; these tests used a two-level ParmSet; a single level would
approximately halve the verification time.  All times can be
significantly improved (by perhaps a factor of 8) by using a
parameter set with W=4; however, that also about doubles the
signature size.

```