Tech-invite3GPPspaceIETF RFCsSIP
929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 8554

Leighton-Micali Hash-Based Signatures

Pages: 61
Informational
Part 2 of 4 – Pages 19 to 34
First   Prev   Next

Top   ToC   RFC8554 - Page 19   prevText

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).
Top   ToC   RFC8554 - Page 20
                 +--------------------+--------+----+----+
                 | 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.
Top   ToC   RFC8554 - Page 21
   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[1] 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[1] can be computed via recursive application of the above equation or by any equivalent method. An iterative procedure is outlined in Appendix C.
Top   ToC   RFC8554 - Page 22

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[0] || path[1] || path[2] || ... || 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[0] is the value of the node adjacent to leaf node q; path[1] 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[0] is the leaf** node that is adjacent to the OTS public key (which is the start of the path); path[1] is the T[4]** node that is the sibling of the second node T[5]* on the path, and path[2] is the T[3]** node that is the sibling of the third node T[2]* on the path.
Top   ToC   RFC8554 - Page 23
                                Root
                                 |
                 ---------------------------------
                 |                               |
               T[2]*                          T[3]**
                 |                               |
          ------------------            -----------------
          |                |            |               |
       T[4]**           T[5]*         T[6]            T[7]
          |                |            |               |
      ---------       ----------     --------       ---------
      |       |       |        |     |      |       |       |
     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[0] value, giving a
   tentative T[5]' value.  Then, it hashes its path[1] and tentative
   T[5]' value to get a tentative T[2]' value.  Then, it hashes that and
   the path[2] 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[2]' it got was the correct T[2] value in the original tree,
   and so the T[5]' value it got was the correct T[5] 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.
Top   ToC   RFC8554 - Page 24
   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[1] 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[1] = next m bytes of the public key
Top   ToC   RFC8554 - Page 25
     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[1], 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[0] = next m bytes of signature
             path[1] = next m bytes of signature
                ...
           path[h-1] = next m bytes of signature
Top   ToC   RFC8554 - Page 26
     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.
Top   ToC   RFC8554 - Page 27
      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.
Top   ToC   RFC8554 - Page 28
      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
   replaced by newer keys.

   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.
Top   ToC   RFC8554 - Page 29
   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[0], the public key of the top level. The HSS private key consists of prv[0], ... , prv[L-1], along with the associated pub[0], ... pub[L-1] and sig[0], ..., 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[0] does not change (and, except for the index q, the value of prv[0] 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[0], and the public key into pub[0] 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[0] 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.
Top   ToC   RFC8554 - Page 30
   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[0] || ... || 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.
Top   ToC   RFC8554 - Page 31
        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[0] || ...
                                 || 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[0]

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

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

   which is equivalent to

     u32str(Nspk) || sig[0] || pub[1] || ...
                              || sig[Nspk-1] || pub[Nspk] || sig[Nspk]
Top   ToC   RFC8554 - Page 32

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,
Top   ToC   RFC8554 - Page 33
   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)

   KeyLifetime:  the lifetime of a key, assuming we generated 1000
      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.
Top   ToC   RFC8554 - Page 34
   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.



(page 34 continued on part 3)

Next Section