doc: Add RFC documents

1 files changed, 4147 insertions, 0 deletions

diff --git a/doc/rfc/rfc8391.txt b/doc/rfc/rfc8391.txt
new file mode 100644
index 0000000..1768857
--- /dev/null
+++ b/doc/rfc/rfc8391.txt
@@ -0,0 +1,4147 @@
+
+
+
+
+
+
+Internet Research Task Force (IRTF)                          A. Huelsing
+Request for Comments: 8391                                  TU Eindhoven
+Category: Informational                                         D. Butin
+ISSN: 2070-1721                                             TU Darmstadt
+                                                               S. Gazdag
+                                                              genua GmbH
+                                                            J. Rijneveld
+                                                      Radboud University
+                                                             A. Mohaisen
+                                           University of Central Florida
+                                                                May 2018
+
+
+                 XMSS: eXtended Merkle Signature Scheme
+
+Abstract
+
+   This note describes the eXtended Merkle Signature Scheme (XMSS), a
+   hash-based digital signature system that is based on existing
+   descriptions in scientific literature.  This note specifies
+   Winternitz One-Time Signature Plus (WOTS+), a one-time signature
+   scheme; XMSS, a single-tree scheme; and XMSS^MT, a multi-tree variant
+   of XMSS.  Both XMSS and XMSS^MT use WOTS+ as a main building block.
+   XMSS provides cryptographic digital signatures without relying on the
+   conjectured hardness of mathematical problems.  Instead, it is proven
+   that it only relies on the properties of cryptographic hash
+   functions.  XMSS provides strong security guarantees and is even
+   secure when the collision resistance of the underlying hash function
+   is broken.  It is suitable for compact implementations, is relatively
+   simple to implement, and naturally resists side-channel attacks.
+   Unlike most other signature systems, hash-based signatures can so far
+   withstand known attacks using quantum computers.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 1]
+
+RFC 8391                          XMSS                          May 2018
+
+
+Status of This Memo
+
+   This document is not an Internet Standards Track specification; it is
+   published for informational purposes.
+
+   This document is a product of the Internet Research Task Force
+   (IRTF).  The IRTF publishes the results of Internet-related research
+   and development activities.  These results might not be suitable for
+   deployment.  This RFC represents the consensus of the Crypto Forum
+   Research Group of the Internet Research Task Force (IRTF).  Documents
+   approved for publication by the IRSG are not candidates for any level
+   of Internet Standard; see Section 2 of RFC 7841.
+
+   Information about the current status of this document, any errata,
+   and how to provide feedback on it may be obtained at
+   https://www.rfc-editor.org/info/rfc8391.
+
+Copyright Notice
+
+   Copyright (c) 2018 IETF Trust and the persons identified as the
+   document authors.  All rights reserved.
+
+   This document is subject to BCP 78 and the IETF Trust's Legal
+   Provisions Relating to IETF Documents
+   (https://trustee.ietf.org/license-info) in effect on the date of
+   publication of this document.  Please review these documents
+   carefully, as they describe your rights and restrictions with respect
+   to this document.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 2]
+
+RFC 8391                          XMSS                          May 2018
+
+
+Table of Contents
+
+   1. Introduction ....................................................5
+      1.1. CFRG Note on Post-Quantum Cryptography .....................6
+      1.2. Conventions Used in This Document ..........................7
+   2. Notation ........................................................7
+      2.1. Data Types .................................................7
+      2.2. Functions ..................................................7
+      2.3. Operators ..................................................8
+      2.4. Integer-to-Byte Conversion .................................9
+      2.5. Hash Function Address Scheme ...............................9
+      2.6. Strings of Base w Numbers .................................12
+      2.7. Member Functions ..........................................13
+   3. Primitives .....................................................14
+      3.1. WOTS+: One-Time Signatures ................................14
+           3.1.1. WOTS+ Parameters ...................................14
+                  3.1.1.1. WOTS+ Functions ...........................15
+           3.1.2. WOTS+ Chaining Function ............................15
+           3.1.3. WOTS+ Private Key ..................................16
+           3.1.4. WOTS+ Public Key ...................................17
+           3.1.5. WOTS+ Signature Generation .........................17
+           3.1.6. WOTS+ Signature Verification .......................19
+           3.1.7. Pseudorandom Key Generation ........................20
+   4. Schemes ........................................................20
+      4.1. XMSS: eXtended Merkle Signature Scheme ....................20
+           4.1.1. XMSS Parameters ....................................21
+           4.1.2. XMSS Hash Functions ................................22
+           4.1.3. XMSS Private Key ...................................22
+           4.1.4. Randomized Tree Hashing ............................23
+           4.1.5. L-Trees ............................................23
+           4.1.6. TreeHash ...........................................24
+           4.1.7. XMSS Key Generation ................................25
+           4.1.8. XMSS Signature .....................................27
+           4.1.9. XMSS Signature Generation ..........................28
+           4.1.10. XMSS Signature Verification .......................30
+           4.1.11. Pseudorandom Key Generation .......................32
+           4.1.12. Free Index Handling and Partial Private Keys ......33
+      4.2. XMSS^MT: Multi-Tree XMSS ..................................33
+           4.2.1. XMSS^MT Parameters .................................33
+           4.2.2. XMSS^MT Key Generation .............................33
+           4.2.3. XMSS^MT Signature ..................................36
+           4.2.4. XMSS^MT Signature Generation .......................37
+           4.2.5. XMSS^MT Signature Verification .....................39
+           4.2.6. Pseudorandom Key Generation ........................40
+           4.2.7. Free Index Handling and Partial Private Keys .......40
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 3]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   5. Parameter Sets .................................................40
+      5.1. Implementing the Functions ................................41
+      5.2. WOTS+ Parameters ..........................................43
+      5.3. XMSS Parameters ...........................................43
+           5.3.1. Parameter Guide ....................................44
+      5.4. XMSS^MT Parameters ........................................45
+           5.4.1. Parameter Guide ....................................47
+   6. Rationale ......................................................49
+   7. Reference Code .................................................50
+   8. IANA Considerations ............................................50
+   9. Security Considerations ........................................54
+      9.1. Security Proofs ...........................................55
+      9.2. Minimal Security Assumptions ..............................56
+      9.3. Post-Quantum Security .....................................56
+   10. References ....................................................57
+      10.1. Normative References .....................................57
+      10.2. Informative References ...................................58
+   Appendix A.  WOTS+ XDR Formats ....................................60
+     A.1.  WOTS+ Parameter Sets ......................................60
+     A.2.  WOTS+ Signatures ..........................................60
+     A.3.  WOTS+ Public Keys .........................................61
+   Appendix B.  XMSS XDR Formats .....................................61
+     B.1.  XMSS Parameter Sets .......................................61
+     B.2.  XMSS Signatures ...........................................62
+     B.3.  XMSS Public Keys ..........................................64
+   Appendix C.  XMSS^MT XDR Formats ..................................65
+     C.1.  XMSS^MT Parameter Sets ....................................65
+     C.2.  XMSS^MT Signatures ........................................67
+     C.3.  XMSS^MT Public Keys .......................................71
+   Acknowledgements ..................................................73
+   Authors' Addresses ................................................74
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 4]
+
+RFC 8391                          XMSS                          May 2018
+
+
+1.  Introduction
+
+   A (cryptographic) digital signature scheme provides asymmetric
+   message authentication.  The key generation algorithm produces a key
+   pair consisting of a private and a public key.  A message is signed
+   using a private key to produce a signature.  A message/signature pair
+   can be verified using a public key.  A One-Time Signature (OTS)
+   scheme allows using a key pair to sign exactly one message securely.
+   A Many-Time Signature (MTS) system can be used to sign multiple
+   messages.
+
+   OTS schemes, and MTS schemes composed from them, were proposed by
+   Merkle in 1979 [Merkle83].  They were well-studied in the 1990s and
+   have regained interest from the mid 2000s onwards because of their
+   resistance against quantum-computer-aided attacks.  These kinds of
+   signature schemes are called hash-based signature schemes as they are
+   built out of a cryptographic hash function.  Hash-based signature
+   schemes generally feature small private and public keys as well as
+   fast signature generation and verification; however, they also
+   feature large signatures and relatively slow key generation.  In
+   addition, they are suitable for compact implementations that benefit
+   various applications and are naturally resistant to most kinds of
+   side-channel attacks.
+
+   Some progress has already been made toward introducing and
+   standardizing hash-based signatures.  Buchmann, Dahmen, and Huelsing
+   proposed the eXtended Merkle Signature Scheme (XMSS) [BDH11], which
+   offers better efficiency than Merkle's original scheme and a modern
+   security proof in the standard model.  McGrew, Curcio, and Fluhrer
+   authored an Internet-Draft [MCF18] specifying the Leighton-Micali
+   Signature (LMS) scheme, which builds on the seminal works by Lamport,
+   Diffie, Winternitz, and Merkle, taking a different approach than XMSS
+   and relying entirely on security arguments in the random oracle
+   model.  Very recently, the stateless hash-based signature scheme
+   SPHINCS was introduced [BHH15], with the intent of being easier to
+   deploy in current applications.  A reasonable next step toward
+   introducing hash-based signatures is to complete the specifications
+   of the basic algorithms -- LMS, XMSS, SPHINCS, and/or variants.
+
+   The eXtended Merkle Signature Scheme (XMSS) [BDH11] is the latest
+   stateful hash-based signature scheme.  It has the smallest signatures
+   out of such schemes and comes with a multi-tree variant that solves
+   the problem of slow key generation.  Moreover, it can be shown that
+   XMSS is secure, making only mild assumptions on the underlying hash
+   function.  In particular, it is not required that the cryptographic
+   hash function is collision-resistant for the security of XMSS.
+   Improvements upon XMSS, as described in [HRS16], are part of this
+   note.
+
+
+
+Huelsing, et al.              Informational                     [Page 5]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   This document describes a single-tree and a multi-tree variant of
+   XMSS.  It also describes WOTS+, a variant of the Winternitz OTS
+   scheme introduced in [Huelsing13] that is used by XMSS.  The schemes
+   are described with enough specificity to ensure interoperability
+   between implementations.
+
+   This document is structured as follows.  Notation is introduced in
+   Section 2.  Section 3 describes the WOTS+ signature system.  MTS
+   schemes are defined in Section 4: the eXtended Merkle Signature
+   Scheme (XMSS) in Section 4.1 and its multi-tree variant (XMSS^MT) in
+   Section 4.2.  Parameter sets are described in Section 5.  Section 6
+   describes the rationale behind choices in this note.  Section 7 gives
+   information about the reference code.  The IANA registry for these
+   signature systems is described in Section 8.  Finally, security
+   considerations are presented in Section 9.
+
+1.1.  CFRG Note on Post-Quantum Cryptography
+
+   All post-quantum algorithms documented by the Crypto Forum Research
+   Group (CFRG) are today considered ready for experimentation and
+   further engineering development (e.g., to establish the impact of
+   performance and sizes on IETF protocols).  However, at the time of
+   writing, we do not have significant deployment experience with such
+   algorithms.
+
+   Many of these algorithms come with specific restrictions, e.g.,
+   change of classical interface or less cryptanalysis of proposed
+   parameters than established schemes.  CFRG has consensus that all
+   documents describing post-quantum technologies include the above
+   paragraph and a clear additional warning about any specific
+   restrictions, especially as those might affect use or deployment of
+   the specific scheme.  That guidance may be changed over time via
+   document updates.
+
+   Additionally, for XMSS:
+
+   CFRG consensus is that we are confident in the cryptographic security
+   of the signature schemes described in this document against quantum
+   computers, given the current state of the research community's
+   knowledge about quantum algorithms.  Indeed, we are confident that
+   the security of a significant part of the Internet could be made
+   dependent on the signature schemes defined in this document, if
+   developers take care of the following.
+
+   In contrast to traditional signature schemes, the signature schemes
+   described in this document are stateful, meaning the secret key
+   changes over time.  If a secret key state is used twice, no
+   cryptographic security guarantees remain.  In consequence, it becomes
+
+
+
+Huelsing, et al.              Informational                     [Page 6]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   feasible to forge a signature on a new message.  This is a new
+   property that most developers will not be familiar with and requires
+   careful handling of secret keys.  Developers should not use the
+   schemes described here except in systems that prevent the reuse of
+   secret key states.
+
+   Note that the fact that the schemes described in this document are
+   stateful also implies that classical APIs for digital signatures
+   cannot be used without modification.  The API MUST be able to handle
+   a secret key state; in particular, this means that the API MUST allow
+   to return an updated secret key state.
+
+1.2.  Conventions Used in This Document
+
+   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
+   "OPTIONAL" in this document are to be interpreted as described in
+   BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
+   capitals, as shown here.
+
+2.  Notation
+
+2.1.  Data Types
+
+   Bytes and byte strings are the fundamental data types.  A byte is a
+   sequence of eight bits.  A single byte is denoted as a pair of
+   hexadecimal digits with a leading "0x".  A byte string is an ordered
+   sequence of zero or more bytes and is denoted as an ordered sequence
+   of hexadecimal characters with a leading "0x".  For example, 0xe534f0
+   is a byte string of length 3.  An array of byte strings is an
+   ordered, indexed set starting with index 0 in which all byte strings
+   have identical length.  We assume big-endian representation for any
+   data types or structures.
+
+2.2.  Functions
+
+   If x is a non-negative real number, then we define the following
+   functions:
+
+      ceil(x): returns the smallest integer greater than or equal to x.
+
+      floor(x): returns the largest integer less than or equal to x.
+
+      lg(x): returns the logarithm to base 2 of x.
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 7]
+
+RFC 8391                          XMSS                          May 2018
+
+
+2.3.  Operators
+
+   When a and b are integers, mathematical operators are defined as
+   follows:
+
+      ^ : a ^ b denotes the result of a raised to the power of b.
+
+      * : a * b denotes the product of a and b.  This operator is
+      sometimes omitted in the absence of ambiguity, as in usual
+      mathematical notation.
+
+      / : a / b denotes the quotient of a by non-zero b.
+
+      % : a % b denotes the non-negative remainder of the integer
+      division of a by b.
+
+      + : a + b denotes the sum of a and b.
+
+      - : a - b denotes the difference of a and b.
+
+      ++ : a++ denotes incrementing a by 1, i.e., a = a + 1.
+
+      << : a << b denotes a logical left shift with b being non-
+      negative, i.e., a * 2^b.
+
+      >> : a >> b denotes a logical right shift with b being non-
+      negative, i.e., floor(a / 2^b).
+
+   The standard order of operations is used when evaluating arithmetic
+   expressions.
+
+   Arrays are used in the common way, where the i^th element of an array
+   A is denoted A[i].  Byte strings are treated as arrays of bytes where
+   necessary: if X is a byte string, then X[i] denotes its i^th byte,
+   where X[0] is the leftmost byte.
+
+   If A and B are byte strings of equal length, then:
+
+   o  A AND B denotes the bitwise logical conjunction operation.
+
+   o  A XOR B denotes the bitwise logical exclusive disjunction
+      operation.
+
+   When B is a byte and i is an integer, then B >> i denotes the logical
+   right-shift operation.
+
+
+
+
+
+
+Huelsing, et al.              Informational                     [Page 8]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   If X is an x-byte string and Y a y-byte string, then X || Y denotes
+   the concatenation of X and Y, with X || Y = X[0] ... X[x-1] Y[0] ...
+   Y[y-1].
+
+2.4.  Integer-to-Byte Conversion
+
+   If x and y are non-negative integers, we define Z = toByte(x, y) to
+   be the y-byte string containing the binary representation of x in
+   big-endian byte order.
+
+2.5.  Hash Function Address Scheme
+
+   The schemes described in this document randomize each hash function
+   call.  This means that aside from the initial message digest, a
+   different key and different bitmask is used for each hash function
+   call.  These values are pseudorandomly generated using a pseudorandom
+   function that takes a key SEED and a 32-byte address ADRS as input
+   and outputs an n-byte value, where n is the security parameter.  Here
+   we explain the structure of address ADRS and propose setter methods
+   to manipulate the address.  We explain the generation of the
+   addresses in the following sections where they are used.
+
+   The schemes in the next two sections use two kinds of hash functions
+   parameterized by security parameter n.  For the hash tree
+   constructions, a hash function that maps an n-byte key and 2n-byte
+   inputs to n-byte outputs is used.  To randomize this function, 3n
+   bytes are needed -- n bytes for the key and 2n bytes for a bitmask.
+   For the OTS scheme constructions, a hash function that maps n-byte
+   keys and n-byte inputs to n-byte outputs is used.  To randomize this
+   function, 2n bytes are needed -- n bytes for the key and n bytes for
+   a bitmask.  Consequently, three addresses are needed for the first
+   function and two addresses for the second one.
+
+   There are three different types of addresses for the different use
+   cases.  One type is used for the hashes in OTS schemes, one is used
+   for hashes within the main Merkle tree construction, and one is used
+   for hashes in the L-trees.  The latter is used to compress one-time
+   public keys.  All these types share as much format as possible.  In
+   the remainder of this section, we describe these types in detail.
+
+   The structure of an address complies with word borders, with a word
+   being 32 bits long in this context.  Only the tree address is too
+   long to fit a single word, but it can fit a double word.  An address
+   is structured as follows.  It always starts with a layer address of
+   one word in the most significant bits, followed by a tree address of
+   two words.  Both addresses are needed for the multi-tree variant (see
+   Section 4.2) and describe the position of a tree within a multi-tree.
+   They are therefore set to zero in single-tree applications.  For
+
+
+
+Huelsing, et al.              Informational                     [Page 9]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   multi-tree hash-based signatures, the layer address describes the
+   height of a tree within the multi-tree, starting from height zero for
+   trees at the bottom layer.  The tree address describes the position
+   of a tree within a layer of a multi-tree starting with index zero for
+   the leftmost tree.  The next word defines the type of the address.
+   It is set to 0 for an OTS address, to 1 for an L-tree address, and to
+   2 for a hash tree address.  Whenever the type word of an address is
+   changed, all following words should be initialized with 0 to prevent
+   non-zero values in unused padding words.
+
+   We first describe the OTS address case.  In this case, the type word
+   is followed by an OTS address word that encodes the index of the OTS
+   key pair within the tree.  The next word encodes the chain address
+   followed by a word that encodes the address of the hash function call
+   within the chain.  The last word, called keyAndMask, is used to
+   generate two different addresses for one hash function call.  The
+   word is set to zero to generate the key.  To generate the n-byte
+   bitmask, the word is set to one.
+
+                     +-------------------------+
+                     | layer address  (32 bits)|
+                     +-------------------------+
+                     | tree address   (64 bits)|
+                     +-------------------------+
+                     | type = 0       (32 bits)|
+                     +-------------------------+
+                     | OTS address    (32 bits)|
+                     +-------------------------+
+                     | chain address  (32 bits)|
+                     +-------------------------+
+                     | hash address   (32 bits)|
+                     +-------------------------+
+                     | keyAndMask     (32 bits)|
+                     +-------------------------+
+
+                            An OTS Hash Address
+
+   We now discuss the L-tree case, which means that the type word is set
+   to one.  In that case, the type word is followed by an L-tree address
+   word that encodes the index of the leaf computed with this L-tree.
+   The next word encodes the height of the node being input for the next
+   computation inside the L-tree.  The following word encodes the index
+   of the node at that height, inside the L-tree.  This time, the last
+   word, keyAndMask, is used to generate three different addresses for
+   one function call.  The word is set to zero to generate the key.  To
+   generate the most significant n bytes of the 2n-byte bitmask, the
+   word is set to one.  The least significant bytes are generated using
+   the address with the word set to two.
+
+
+
+Huelsing, et al.              Informational                    [Page 10]
+
+RFC 8391                          XMSS                          May 2018
+
+
+                     +-------------------------+
+                     | layer address  (32 bits)|
+                     +-------------------------+
+                     | tree address   (64 bits)|
+                     +-------------------------+
+                     | type = 1       (32 bits)|
+                     +-------------------------+
+                     | L-tree address (32 bits)|
+                     +-------------------------+
+                     | tree height    (32 bits)|
+                     +-------------------------+
+                     | tree index     (32 bits)|
+                     +-------------------------+
+                     | keyAndMask     (32 bits)|
+                     +-------------------------+
+
+                             An L-tree Address
+
+   We now describe the remaining type for the main tree hash addresses.
+   In this case, the type word is set to two, followed by a zero padding
+   of one word.  The next word encodes the height of the tree node being
+   input for the next computation, followed by a word that encodes the
+   index of this node at that height.  As for the L-tree addresses, the
+   last word, keyAndMask, is used to generate three different addresses
+   for one function call.  The word is set to zero to generate the key.
+   To generate the most significant n bytes of the 2n-byte bitmask, the
+   word is set to one.  The least significant bytes are generated using
+   the address with the word set to two.
+
+                     +-------------------------+
+                     | layer address  (32 bits)|
+                     +-------------------------+
+                     | tree address   (64 bits)|
+                     +-------------------------+
+                     | type = 2       (32 bits)|
+                     +-------------------------+
+                     | Padding = 0    (32 bits)|
+                     +-------------------------+
+                     | tree height    (32 bits)|
+                     +-------------------------+
+                     | tree index     (32 bits)|
+                     +-------------------------+
+                     | keyAndMask     (32 bits)|
+                     +-------------------------+
+
+                            A Hash Tree Address
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 11]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   All fields within these addresses encode unsigned integers.  When
+   describing the generation of addresses we use setter methods that
+   take positive integers and set the bits of a field to the binary
+   representation of that integer of the length of the field.  We
+   furthermore assume that the setType() method sets the four words
+   following the type word to zero.
+
+2.6.  Strings of Base w Numbers
+
+   A byte string can be considered as a string of base w numbers, i.e.,
+   integers in the set {0, ... , w - 1}.  The correspondence is defined
+   by the function base_w(X, w, out_len) (Algorithm 1) as follows.  If X
+   is a len_X-byte string, and w is a member of the set {4, 16}, then
+   base_w(X, w, out_len) outputs an array of out_len integers between 0
+   and w - 1.  The length out_len is REQUIRED to be less than or equal
+   to 8 * len_X / lg(w).
+
+   Algorithm 1: base_w
+
+     Input: len_X-byte string X, int w, output length out_len
+     Output: out_len int array basew
+
+       int in = 0;
+       int out = 0;
+       unsigned int total = 0;
+       int bits = 0;
+       int consumed;
+
+       for ( consumed = 0; consumed < out_len; consumed++ ) {
+           if ( bits == 0 ) {
+               total = X[in];
+               in++;
+               bits += 8;
+           }
+           bits -= lg(w);
+           basew[out] = (total >> bits) AND (w - 1);
+           out++;
+       }
+       return basew;
+
+   For example, if X is the (big-endian) byte string 0x1234, then
+   base_w(X, 16, 4) returns the array a = {1, 2, 3, 4}.
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 12]
+
+RFC 8391                          XMSS                          May 2018
+
+
+                      X (represented as bits)
+         +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+         | 0| 0| 0| 1| 0| 0| 1| 0| 0| 0| 1| 1| 0| 1| 0| 0|
+         +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+                    X[0]         |         X[1]
+
+                 X (represented as base 16 numbers)
+         +-----------+-----------+-----------+-----------+
+         |     1     |     2     |     3     |     4     |
+         +-----------+-----------+-----------+-----------+
+
+                          base_w(X, 16, 4)
+         +-----------+-----------+-----------+-----------+
+         |     1     |     2     |     3     |     4     |
+         +-----------+-----------+-----------+-----------+
+             a[0]        a[1]        a[2]        a[3]
+
+                          base_w(X, 16, 3)
+         +-----------+-----------+-----------+
+         |     1     |     2     |     3     |
+         +-----------+-----------+-----------+
+             a[0]        a[1]        a[2]
+
+                          base_w(X, 16, 2)
+         +-----------+-----------+
+         |     1     |     2     |
+         +-----------+-----------+
+             a[0]        a[1]
+
+                                  Example
+
+2.7.  Member Functions
+
+   To simplify algorithm descriptions, we assume the existence of member
+   functions.  If a complex data structure like a public key PK contains
+   a value X, then getX(PK) returns the value of X for this public key.
+   Accordingly, setX(PK, X, Y) sets value X in PK to the value held by
+   Y.  Since camelCase is used for member function names, a value z may
+   be referred to as Z in the function name, e.g., getZ.
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 13]
+
+RFC 8391                          XMSS                          May 2018
+
+
+3.  Primitives
+
+3.1.  WOTS+: One-Time Signatures
+
+   This section describes the WOTS+ system in a manner similar to that
+   in [Huelsing13].  WOTS+ is an OTS scheme; while a private key can be
+   used to sign any message, each private key MUST be used only once to
+   sign a single message.  In particular, if a private key is used to
+   sign two different messages, the scheme becomes insecure.
+
+   This section starts with an explanation of parameters.  Afterwards,
+   the so-called chaining function, which forms the main building block
+   of the WOTS+ scheme, is explained.  A description of the algorithms
+   for key generation, signing, and verification follows.  Finally,
+   pseudorandom key generation is discussed.
+
+3.1.1.  WOTS+ Parameters
+
+   WOTS+ uses the parameters n and w; they both take positive integer
+   values.  These parameters are summarized as follows:
+
+      n: the message length as well as the length of a private key,
+      public key, or signature element in bytes.
+
+      w: the Winternitz parameter; it is a member of the set {4, 16}.
+
+   The parameters are used to compute values len, len_1, and len_2:
+
+      len: the number of n-byte string elements in a WOTS+ private key,
+      public key, and signature.  It is computed as len = len_1 + len_2,
+      with len_1 = ceil(8n / lg(w)) and len_2 = floor(lg(len_1 *
+      (w - 1)) / lg(w)) + 1.
+
+   The value of n is determined by the cryptographic hash function used
+   for WOTS+.  The hash function is chosen to ensure an appropriate
+   level of security.  The value of n is the input length that can be
+   processed by the signing algorithm.  It is often the length of a
+   message digest.  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.
+
+   WOTS+ parameters are implicitly included in algorithm inputs as
+   needed.
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 14]
+
+RFC 8391                          XMSS                          May 2018
+
+
+3.1.1.1.  WOTS+ Functions
+
+   The WOTS+ algorithm uses a keyed cryptographic hash function F.  F
+   accepts and returns byte strings of length n using keys of length n.
+   More detail on specific instantiations can be found in Section 5.
+   Security requirements on F are discussed in Section 9.  In addition,
+   WOTS+ uses a pseudorandom function PRF.  PRF takes as input an n-byte
+   key and a 32-byte index and generates pseudorandom outputs of length
+   n.  More detail on specific instantiations can be found in Section 5.
+   Security requirements on PRF are discussed in Section 9.
+
+3.1.2.  WOTS+ Chaining Function
+
+   The chaining function (Algorithm 2) computes an iteration of F on an
+   n-byte input using outputs of PRF.  It takes an OTS hash address as
+   input.  This address will have the first six 32-bit words set to
+   encode the address of this chain.  In each iteration, PRF is used to
+   generate a key for F and a bitmask that is XORed to the intermediate
+   result before it is processed by F.  In the following, ADRS is a
+   32-byte OTS hash address as specified in Section 2.5 and SEED is an
+   n-byte string.  To generate the keys and bitmasks, PRF is called with
+   SEED as key and ADRS as input.  The chaining function takes as input
+   an n-byte string X, a start index i, a number of steps s, as well as
+   ADRS and SEED.  The chaining function returns as output the value
+   obtained by iterating F for s times on input X, using the outputs of
+   PRF.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 15]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 2: chain - Chaining Function
+
+     Input: Input string X, start index i, number of steps s,
+     seed SEED, address ADRS
+     Output: value of F iterated s times on X
+
+     if ( s == 0 ) {
+       return X;
+     }
+     if ( (i + s) > (w - 1) ) {
+       return NULL;
+     }
+     byte[n] tmp = chain(X, i, s - 1, SEED, ADRS);
+
+     ADRS.setHashAddress(i + s - 1);
+     ADRS.setKeyAndMask(0);
+     KEY = PRF(SEED, ADRS);
+     ADRS.setKeyAndMask(1);
+     BM = PRF(SEED, ADRS);
+
+     tmp = F(KEY, tmp XOR BM);
+     return tmp;
+
+3.1.3.  WOTS+ Private Key
+
+   The private key in WOTS+, denoted by sk (s for secret), is a length
+   len array of n-byte strings.  This private key MUST be only used to
+   sign at most one message.  Each n-byte string MUST either be selected
+   randomly from the uniform distribution or be selected using a
+   cryptographically secure pseudorandom procedure.  In the latter case,
+   the security of the used procedure MUST at least match that of the
+   WOTS+ parameters used.  For a further discussion on pseudorandom key
+   generation, see Section 3.1.7.  The following pseudocode (Algorithm
+   3) describes an algorithm for generating sk.
+
+   Algorithm 3: WOTS_genSK - Generating a WOTS+ Private Key
+
+     Input: No input
+     Output: WOTS+ private key sk
+
+     for ( i = 0; i < len; i++ ) {
+       initialize sk[i] with a uniformly random n-byte string;
+     }
+     return sk;
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 16]
+
+RFC 8391                          XMSS                          May 2018
+
+
+3.1.4.  WOTS+ Public Key
+
+   A WOTS+ key pair defines a virtual structure that consists of len
+   hash chains of length w.  The len n-byte strings in the private key
+   each define the start node for one hash chain.  The public key
+   consists of the end nodes of these hash chains.  Therefore, like the
+   private key, the public key is also a length len array of n-byte
+   strings.  To compute the hash chain, the chaining function (Algorithm
+   2) is used.  An OTS hash address ADRS and a seed SEED have to be
+   provided by the calling algorithm.  This address will encode the
+   address of the WOTS+ key pair within a greater structure.  Hence, a
+   WOTS+ algorithm MUST NOT manipulate any parts of ADRS except for the
+   last three 32-bit words.  Please note that the SEED used here is
+   public information also available to a verifier.  The following
+   pseudocode (Algorithm 4) describes an algorithm for generating the
+   public key pk, where sk is the private key.
+
+   Algorithm 4: WOTS_genPK - Generating a WOTS+ Public Key From a
+   Private Key
+
+     Input: WOTS+ private key sk, address ADRS, seed SEED
+     Output: WOTS+ public key pk
+
+     for ( i = 0; i < len; i++ ) {
+       ADRS.setChainAddress(i);
+       pk[i] = chain(sk[i], 0, w - 1, SEED, ADRS);
+     }
+     return pk;
+
+3.1.5.  WOTS+ Signature Generation
+
+   A WOTS+ signature is a length len array of n-byte strings.  The WOTS+
+   signature is generated by mapping a message to len integers between 0
+   and w - 1.  To this end, the message is transformed into len_1 base w
+   numbers using the base_w function defined in Section 2.6.  Next, a
+   checksum is computed and appended to the transformed message as len_2
+   base w numbers using the base_w function.  Note that the checksum may
+   reach a maximum integer value of len_1 * (w - 1) * 2^8 and therefore
+   depends on the parameters n and w.  For the parameter sets given in
+   Section 5, a 32-bit unsigned integer is sufficient to hold the
+   checksum.  If other parameter settings are used, the size of the
+   variable holding the integer value of the checksum MUST be
+   sufficiently large.  Each of the base w integers is used to select a
+   node from a different hash chain.  The signature is formed by
+   concatenating the selected nodes.  An OTS hash address ADRS and a
+   seed SEED have to be provided by the calling algorithm.  This address
+   will encode the address of the WOTS+ key pair within a greater
+   structure.  Hence, a WOTS+ algorithm MUST NOT manipulate any parts of
+
+
+
+Huelsing, et al.              Informational                    [Page 17]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   ADRS except for the last three 32-bit words.  Please note that the
+   SEED used here is public information also available to a verifier.
+   The pseudocode for signature generation is shown below (Algorithm 5),
+   where M is the message and sig is the resulting signature.
+
+   Algorithm 5: WOTS_sign - Generating a signature from a private key
+   and a message
+
+     Input: Message M, WOTS+ private key sk, address ADRS, seed SEED
+     Output: WOTS+ signature sig
+
+     csum = 0;
+
+     // Convert message to base w
+     msg = base_w(M, w, len_1);
+
+     // Compute checksum
+     for ( i = 0; i < len_1; i++ ) {
+           csum = csum + w - 1 - msg[i];
+     }
+
+     // Convert csum to base w
+     csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
+     len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
+     msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
+     for ( i = 0; i < len; i++ ) {
+          ADRS.setChainAddress(i);
+          sig[i] = chain(sk[i], 0, msg[i], SEED, ADRS);
+     }
+     return sig;
+
+   The data format for a signature is given below.
+
+             +---------------------------------+
+             |                                 |
+             |           sig_ots[0]            |    n bytes
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             ~              ....               ~
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             |          sig_ots[len - 1]       |    n bytes
+             |                                 |
+             +---------------------------------+
+
+                              WOTS+ Signature
+
+
+
+Huelsing, et al.              Informational                    [Page 18]
+
+RFC 8391                          XMSS                          May 2018
+
+
+3.1.6.  WOTS+ Signature Verification
+
+   In order to verify a signature sig on a message M, the verifier
+   computes a WOTS+ public key value from the signature.  This can be
+   done by "completing" the chain computations starting from the
+   signature values, using the base w values of the message hash and its
+   checksum.  This step, called WOTS_pkFromSig, is described below in
+   Algorithm 6.  The result of WOTS_pkFromSig is then compared to the
+   given public key.  If the values are equal, the signature is
+   accepted.  Otherwise, the signature MUST be rejected.  An OTS hash
+   address ADRS and a seed SEED have to be provided by the calling
+   algorithm.  This address will encode the address of the WOTS+ key
+   pair within a greater structure.  Hence, a WOTS+ algorithm MUST NOT
+   manipulate any parts of ADRS except for the last three 32-bit words.
+   Please note that the SEED used here is public information also
+   available to a verifier.
+
+   Algorithm 6: WOTS_pkFromSig - Computing a WOTS+ public key from a
+   message and its signature
+
+     Input: Message M, WOTS+ signature sig, address ADRS, seed SEED
+     Output: 'Temporary' WOTS+ public key tmp_pk
+
+     csum = 0;
+
+     // Convert message to base w
+     msg = base_w(M, w, len_1);
+
+     // Compute checksum
+     for ( i = 0; i < len_1; i++ ) {
+           csum = csum + w - 1 - msg[i];
+     }
+
+     // Convert csum to base w
+     csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
+     len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
+     msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
+     for ( i = 0; i < len; i++ ) {
+          ADRS.setChainAddress(i);
+          tmp_pk[i] = chain(sig[i], msg[i], w - 1 - msg[i], SEED, ADRS);
+     }
+     return tmp_pk;
+
+   Note: XMSS uses WOTS_pkFromSig to compute a public key value and
+   delays the comparison to a later point.
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 19]
+
+RFC 8391                          XMSS                          May 2018
+
+
+3.1.7.  Pseudorandom Key Generation
+
+   An implementation MAY use a cryptographically secure pseudorandom
+   method to generate the private key from a single n-byte value.  For
+   example, the method suggested in [BDH11] and explained below MAY be
+   used.  Other methods MAY be used.  The choice of a pseudorandom
+   method does not affect interoperability, but the cryptographic
+   strength MUST match that of the used WOTS+ parameters.
+
+   The advantage of generating the private key elements from a random
+   n-byte string is that only this n-byte string needs to be stored
+   instead of the full private key.  The key can be regenerated when
+   needed.  The suggested method from [BDH11] can be described using
+   PRF.  During key generation, a uniformly random n-byte string S is
+   sampled from a secure source of randomness.  This string S is stored
+   as private key.  The private key elements are computed as sk[i] =
+   PRF(S, toByte(i, 32)) whenever needed.  Please note that this seed S
+   MUST be different from the seed SEED used to randomize the hash
+   function calls.  Also, this seed S MUST be kept secret.  The seed S
+   MUST NOT be a low entropy, human-memorable value since private key
+   elements are derived from S deterministically and their
+   confidentiality is security-critical.
+
+4.  Schemes
+
+   In this section, the eXtended Merkle Signature Scheme (XMSS) is
+   described using WOTS+.  XMSS comes in two flavors: a single-tree
+   variant (XMSS) and a multi-tree variant (XMSS^MT).  Both allow
+   combining a large number of WOTS+ key pairs under a single small
+   public key.  The main ingredient added is a binary hash tree
+   construction.  XMSS uses a single hash tree while XMSS^MT uses a tree
+   of XMSS key pairs.
+
+4.1.  XMSS: eXtended Merkle Signature Scheme
+
+   XMSS is a method for signing a potentially large but fixed number of
+   messages.  It is based on the Merkle signature scheme.  XMSS uses
+   four cryptographic components: WOTS+ as OTS method, two additional
+   cryptographic hash functions H and H_msg, and a pseudorandom function
+   PRF.  One of the main advantages of XMSS with WOTS+ is that it does
+   not rely on the collision resistance of the used hash functions but
+   on weaker properties.  Each XMSS public/private key pair is
+   associated with a perfect binary tree, every node of which contains
+   an n-byte value.  Each tree leaf contains a special tree hash of a
+   WOTS+ public key value.  Each non-leaf tree node is computed by first
+   concatenating the values of its child nodes, computing the XOR with a
+   bitmask, and applying the keyed hash function H to the result.  The
+   bitmasks and the keys for the hash function H are generated from a
+
+
+
+Huelsing, et al.              Informational                    [Page 20]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   (public) seed that is part of the public key using the pseudorandom
+   function PRF.  The value corresponding to the root of the XMSS tree
+   forms the XMSS public key together with the seed.
+
+   To generate a key pair that can be used to sign 2^h messages, a tree
+   of height h is used.  XMSS is a stateful signature scheme, meaning
+   that the private key changes with every signature generation.  To
+   prevent one-time private keys from being used twice, the WOTS+ key
+   pairs are numbered from 0 to (2^h) - 1 according to the related leaf,
+   starting from index 0 for the leftmost leaf.  The private key
+   contains an index that is updated with every signature generation,
+   such that it contains the index of the next unused WOTS+ key pair.
+
+   A signature consists of the index of the used WOTS+ key pair, the
+   WOTS+ signature on the message, and the so-called authentication
+   path.  The latter is a vector of tree nodes that allow a verifier to
+   compute a value for the root of the tree starting from a WOTS+
+   signature.  A verifier computes the root value and compares it to the
+   respective value in the XMSS public key.  If they match, the
+   signature is declared valid.  The XMSS private key consists of all
+   WOTS+ private keys and the current index.  To reduce storage, a
+   pseudorandom key generation procedure, as described in [BDH11], MAY
+   be used.  The security of the used method MUST at least match the
+   security of the XMSS instance.
+
+4.1.1.  XMSS Parameters
+
+   XMSS has the following parameters:
+
+      h: the height (number of levels - 1) of the tree
+
+      n: the length in bytes of the message digest as well as each node
+
+      w: the Winternitz parameter as defined for WOTS+ in Section 3.1
+
+   There are 2^h leaves in the tree.
+
+   For XMSS and XMSS^MT, private and public keys are denoted by SK (S
+   for secret) and PK, respectively.  For WOTS+, private and public keys
+   are denoted by sk (s for secret) and pk, respectively.  XMSS and
+   XMSS^MT signatures are denoted by Sig.  WOTS+ signatures are denoted
+   by sig.
+
+   XMSS and XMSS^MT parameters are implicitly included in algorithm
+   inputs as needed.
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 21]
+
+RFC 8391                          XMSS                          May 2018
+
+
+4.1.2.  XMSS Hash Functions
+
+   Besides the cryptographic hash function F and the pseudorandom
+   function PRF required by WOTS+, XMSS uses two more functions:
+
+   o  A cryptographic hash function H.  H accepts n-byte keys and byte
+      strings of length 2n and returns an n-byte string.
+
+   o  A cryptographic hash function H_msg.  H_msg accepts 3n-byte keys
+      and byte strings of arbitrary length and returns an n-byte string.
+
+   More detail on specific instantiations can be found in Section 5.
+   Security requirements on H and H_msg are discussed in Section 9.
+
+4.1.3.  XMSS Private Key
+
+   An XMSS private key SK contains 2^h WOTS+ private keys, the leaf
+   index idx of the next WOTS+ private key that has not yet been used,
+   SK_PRF (an n-byte key to generate pseudorandom values for randomized
+   message hashing), the n-byte value root (which is the root node of
+   the tree and SEED), and the n-byte public seed used to pseudorandomly
+   generate bitmasks and hash function keys.  Although root and SEED
+   formally would be considered only part of the public key, they are
+   needed (e.g., for signature generation) and hence are also required
+   for functions that do not take the public key as input.
+
+   The leaf index idx is initialized to zero when the XMSS private key
+   is created.  The key SK_PRF MUST be sampled from a secure source of
+   randomness that follows the uniform distribution.  The WOTS+ private
+   keys MUST be generated as described in Section 3.1, or, to reduce the
+   private key size, a cryptographic pseudorandom method MUST be used as
+   discussed in Section 4.1.11.  SEED is generated as a uniformly random
+   n-byte string.  Although SEED is public, it is critical for security
+   that it is generated using a good entropy source.  The root node is
+   generated as described below in the section on key generation
+   (Section 4.1.7).  That section also contains an example algorithm for
+   combined private and public key generation.
+
+   For the following algorithm descriptions, the existence of a method
+   getWOTS_SK(SK, i) is assumed.  This method takes as input an XMSS
+   private key SK and an integer i and outputs the i^th WOTS+ private
+   key of SK.
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 22]
+
+RFC 8391                          XMSS                          May 2018
+
+
+4.1.4.  Randomized Tree Hashing
+
+   To improve readability, we introduce a function RAND_HASH(LEFT,
+   RIGHT, SEED, ADRS) (Algorithm 7) that does the randomized hashing in
+   the tree.  It takes as input two n-byte values LEFT and RIGHT that
+   represent the left and the right halves of the hash function input,
+   the seed SEED used as key for PRF, and the address ADRS of this hash
+   function call.  RAND_HASH first uses PRF with SEED and ADRS to
+   generate a key KEY and n-byte bitmasks BM_0, BM_1.  Then, it returns
+   the randomized hash H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1)).
+
+   Algorithm 7: RAND_HASH
+
+     Input:  n-byte value LEFT, n-byte value RIGHT, seed SEED,
+             address ADRS
+     Output: n-byte randomized hash
+
+     ADRS.setKeyAndMask(0);
+     KEY = PRF(SEED, ADRS);
+     ADRS.setKeyAndMask(1);
+     BM_0 = PRF(SEED, ADRS);
+     ADRS.setKeyAndMask(2);
+     BM_1 = PRF(SEED, ADRS);
+
+     return H(KEY, (LEFT XOR BM_0) || (RIGHT XOR BM_1));
+
+4.1.5.  L-Trees
+
+   To compute the leaves of the binary hash tree, a so-called L-tree is
+   used.  An L-tree is an unbalanced binary hash tree, distinct but
+   similar to the main XMSS binary hash tree.  The algorithm ltree
+   (Algorithm 8) takes as input a WOTS+ public key pk and compresses it
+   to a single n-byte value pk[0].  It also takes as input an L-tree
+   address ADRS that encodes the address of the L-tree and the seed
+   SEED.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 23]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 8: ltree
+
+     Input: WOTS+ public key pk, address ADRS, seed SEED
+     Output: n-byte compressed public key value pk[0]
+
+     unsigned int len' = len;
+     ADRS.setTreeHeight(0);
+     while ( len' > 1 ) {
+       for ( i = 0; i < floor(len' / 2); i++ ) {
+         ADRS.setTreeIndex(i);
+         pk[i] = RAND_HASH(pk[2i], pk[2i + 1], SEED, ADRS);
+       }
+       if ( len' % 2 == 1 ) {
+         pk[floor(len' / 2)] = pk[len' - 1];
+       }
+       len' = ceil(len' / 2);
+       ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
+     }
+     return pk[0];
+
+4.1.6.  TreeHash
+
+   For the computation of the internal n-byte nodes of a Merkle tree,
+   the subroutine treeHash (Algorithm 9) accepts an XMSS private key SK
+   (including seed SEED), an unsigned integer s (the start index), an
+   unsigned integer t (the target node height), and an address ADRS that
+   encodes the address of the containing tree.  For the height of a node
+   within a tree, counting starts with the leaves at height zero.  The
+   treeHash algorithm returns the root node of a tree of height t with
+   the leftmost leaf being the hash of the WOTS+ pk with index s.  It is
+   REQUIRED that s % 2^t = 0, i.e., that the leaf at index s is a
+   leftmost leaf of a sub-tree of height t.  Otherwise, the hash-
+   addressing scheme fails.  The treeHash algorithm described here uses
+   a stack holding up to (t - 1) nodes, with the usual stack functions
+   push() and pop().  We furthermore assume that the height of a node
+   (an unsigned integer) is stored alongside a node's value (an n-byte
+   string) on the stack.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 24]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 9: treeHash
+
+     Input: XMSS private key SK, start index s, target node height t,
+            address ADRS
+     Output: n-byte root node - top node on Stack
+
+     if( s % (1 << t) != 0 ) return -1;
+     for ( i = 0; i < 2^t; i++ ) {
+       SEED = getSEED(SK);
+       ADRS.setType(0);   // Type = OTS hash address
+       ADRS.setOTSAddress(s + i);
+       pk = WOTS_genPK (getWOTS_SK(SK, s + i), SEED, ADRS);
+       ADRS.setType(1);   // Type = L-tree address
+       ADRS.setLTreeAddress(s + i);
+       node = ltree(pk, SEED, ADRS);
+       ADRS.setType(2);   // Type = hash tree address
+       ADRS.setTreeHeight(0);
+       ADRS.setTreeIndex(i + s);
+       while ( Top node on Stack has same height t' as node ) {
+          ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
+          node = RAND_HASH(Stack.pop(), node, SEED, ADRS);
+          ADRS.setTreeHeight(ADRS.getTreeHeight() + 1);
+       }
+       Stack.push(node);
+     }
+     return Stack.pop();
+
+4.1.7.  XMSS Key Generation
+
+   The XMSS key pair is computed as described in XMSS_keyGen (Algorithm
+   10).  The XMSS public key PK consists of the root of the binary hash
+   tree and the seed SEED, both also stored in SK.  The root is computed
+   using treeHash.  For XMSS, there is only a single main tree.  Hence,
+   the used address is set to the all-zero string in the beginning.
+   Note that we do not define any specific format or handling for the
+   XMSS private key SK by introducing this algorithm.  It relates to
+   requirements described earlier and simply shows a basic but very
+   inefficient example to initialize a private key.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 25]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 10: XMSS_keyGen - Generate an XMSS key pair
+
+     Input: No input
+     Output: XMSS private key SK, XMSS public key PK
+
+     // Example initialization for SK-specific contents
+     idx = 0;
+     for ( i = 0; i < 2^h; i++ ) {
+       wots_sk[i] = WOTS_genSK();
+     }
+     initialize SK_PRF with a uniformly random n-byte string;
+     setSK_PRF(SK, SK_PRF);
+
+     // Initialization for common contents
+     initialize SEED with a uniformly random n-byte string;
+     setSEED(SK, SEED);
+     setWOTS_SK(SK, wots_sk));
+     ADRS = toByte(0, 32);
+     root = treeHash(SK, 0, h, ADRS);
+
+     SK = idx || wots_sk || SK_PRF || root || SEED;
+     PK = OID || root || SEED;
+     return (SK || PK);
+
+   The above is just an example algorithm.  It is strongly RECOMMENDED
+   to use pseudorandom key generation to reduce the private key size.
+   Public and private key generation MAY be interleaved to save space.
+   Particularly, when a pseudorandom method is used to generate the
+   private key, generation MAY be done when the respective WOTS+ key
+   pair is needed by treeHash.
+
+   The format of an XMSS public key is given below.
+
+            +---------------------------------+
+            |          algorithm OID          |
+            +---------------------------------+
+            |                                 |
+            |            root node            |     n bytes
+            |                                 |
+            +---------------------------------+
+            |                                 |
+            |              SEED               |     n bytes
+            |                                 |
+            +---------------------------------+
+
+                              XMSS Public Key
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 26]
+
+RFC 8391                          XMSS                          May 2018
+
+
+4.1.8.  XMSS Signature
+
+   An XMSS signature is a (4 + n + (len + h) * n)-byte string consisting
+   of:
+
+   o  the index idx_sig of the used WOTS+ key pair (4 bytes),
+
+   o  a byte string r used for randomized message hashing (n bytes),
+
+   o  a WOTS+ signature sig_ots (len * n bytes), and
+
+   o  the so-called authentication path 'auth' for the leaf associated
+      with the used WOTS+ key pair (h * n bytes).
+
+   The authentication path is an array of h n-byte strings.  It contains
+   the siblings of the nodes on the path from the used leaf to the root.
+   It does not contain the nodes on the path itself.  A verifier needs
+   these nodes to compute a root node for the tree from the WOTS+ public
+   key.  A node Node is addressed by its position in the tree.  Node(x,
+   y) denotes the y^th node on level x with y = 0 being the leftmost
+   node on a level.  The leaves are on level 0; the root is on level h.
+   An authentication path contains exactly one node on every layer 0 <=
+   x <= (h - 1).  For the i^th WOTS+ key pair, counting from zero, the
+   j^th authentication path node is:
+
+      Node(j, floor(i / (2^j)) XOR 1)
+
+   The computation of the authentication path is discussed in
+   Section 4.1.9.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 27]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The data format for a signature is given below.
+
+             +---------------------------------+
+             |                                 |
+             |          index idx_sig          |    4 bytes
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             |          randomness r           |    n bytes
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             |     WOTS+ signature sig_ots     |    len * n bytes
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             |             auth[0]             |    n bytes
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             ~              ....               ~
+             |                                 |
+             +---------------------------------+
+             |                                 |
+             |           auth[h - 1]           |    n bytes
+             |                                 |
+             +---------------------------------+
+
+                              XMSS Signature
+
+4.1.9.  XMSS Signature Generation
+
+   To compute the XMSS signature of a message M with an XMSS private
+   key, the signer first computes a randomized message digest using a
+   random value r, idx_sig, the index of the WOTS+ key pair to be used,
+   and the root value from the public key as key.  Then, a WOTS+
+   signature of the message digest is computed using the next unused
+   WOTS+ private key.  Next, the authentication path is computed.
+   Finally, the private key is updated, i.e., idx is incremented.  An
+   implementation MUST NOT output the signature before the private key
+   is updated.
+
+   The node values of the authentication path MAY be computed in any
+   way.  This computation is assumed to be performed by the subroutine
+   buildAuth for the function XMSS_sign (Algorithm 12).  The fastest
+   alternative is to store all tree nodes and set the array in the
+   signature by copying the respective nodes.  The least storage-
+   intensive alternative is to recompute all nodes for each signature
+
+
+
+Huelsing, et al.              Informational                    [Page 28]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   online using the treeHash algorithm (Algorithm 9).  Several
+   algorithms exist in between, with different time/storage trade-offs.
+   For an overview, see [BDS09].  A further approach can be found in
+   [KMN14].  Note that the details of this procedure are not relevant to
+   interoperability; it is not necessary to know any of these details in
+   order to perform the signature verification operation.  The following
+   version of buildAuth is given for completeness.  It is a simple
+   example for understanding, but extremely inefficient.  The use of one
+   of the alternative algorithms is strongly RECOMMENDED.
+
+   Given an XMSS private key SK, all nodes in a tree are determined.
+   Their values are defined in terms of treeHash (Algorithm 9).  Hence,
+   one can compute the authentication path as follows:
+
+   (Example) buildAuth - Compute the authentication path for the i^th
+   WOTS+ key pair
+
+     Input: XMSS private key SK, WOTS+ key pair index i, ADRS
+     Output: Authentication path auth
+
+     for ( j = 0; j < h; j++ ) {
+       k = floor(i / (2^j)) XOR 1;
+       auth[j] = treeHash(SK, k * 2^j, j, ADRS);
+     }
+
+   We split the description of the signature generation into two main
+   algorithms.  The first one, treeSig (Algorithm 11), generates the
+   main part of an XMSS signature and is also used by the multi-tree
+   variant XMSS^MT.  XMSS_sign (Algorithm 12) calls treeSig but handles
+   message compression before and the private key update afterwards.
+
+   The algorithm treeSig (Algorithm 11) described below calculates the
+   WOTS+ signature on an n-byte message and the corresponding
+   authentication path.  treeSig takes as input an n-byte message M', an
+   XMSS private key SK, a signature index idx_sig, and an address ADRS.
+   It returns the concatenation of the WOTS+ signature sig_ots and
+   authentication path auth.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 29]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 11: treeSig - Generate a WOTS+ signature on a message with
+   corresponding authentication path
+
+     Input: n-byte message M', XMSS private key SK,
+            signature index idx_sig, ADRS
+     Output: Concatenation of WOTS+ signature sig_ots and
+             authentication path auth
+
+     auth = buildAuth(SK, idx_sig, ADRS);
+     ADRS.setType(0);   // Type = OTS hash address
+     ADRS.setOTSAddress(idx_sig);
+     sig_ots = WOTS_sign(getWOTS_SK(SK, idx_sig),
+                         M', getSEED(SK), ADRS);
+     Sig = sig_ots || auth;
+     return Sig;
+
+   The algorithm XMSS_sign (Algorithm 12) described below calculates an
+   updated private key SK and a signature on a message M.  XMSS_sign
+   takes as input a message M of arbitrary length and an XMSS private
+   key SK.  It returns the byte string containing the concatenation of
+   the updated private key SK and the signature Sig.
+
+   Algorithm 12: XMSS_sign - Generate an XMSS signature and update the
+   XMSS private key
+
+     Input: Message M, XMSS private key SK
+     Output: Updated SK, XMSS signature Sig
+
+     idx_sig = getIdx(SK);
+     setIdx(SK, idx_sig + 1);
+     ADRS = toByte(0, 32);
+     byte[n] r = PRF(getSK_PRF(SK), toByte(idx_sig, 32));
+     byte[n] M' = H_msg(r || getRoot(SK) || (toByte(idx_sig, n)), M);
+     Sig = idx_sig || r || treeSig(M', SK, idx_sig, ADRS);
+     return (SK || Sig);
+
+4.1.10.  XMSS Signature Verification
+
+   An XMSS signature is verified by first computing the message digest
+   using randomness r, index idx_sig, the root from PK and message M.
+   Then the used WOTS+ public key pk_ots is computed from the WOTS+
+   signature using WOTS_pkFromSig.  The WOTS+ public key in turn is used
+   to compute the corresponding leaf using an L-tree.  The leaf,
+   together with index idx_sig and authentication path auth is used to
+   compute an alternative root value for the tree.  The verification
+   succeeds if and only if the computed root value matches the one in
+   the XMSS public key.  In any other case, it MUST return fail.
+
+
+
+
+Huelsing, et al.              Informational                    [Page 30]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   As for signature generation, we split verification into two parts to
+   allow for reuse in the XMSS^MT description.  The steps also needed
+   for XMSS^MT are done by the function XMSS_rootFromSig (Algorithm 13).
+   XMSS_verify (Algorithm 14) calls XMSS_rootFromSig as a subroutine and
+   handles the XMSS-specific steps.
+
+   The main part of XMSS signature verification is done by the function
+   XMSS_rootFromSig (Algorithm 13) described below.  XMSS_rootFromSig
+   takes as input an index idx_sig, a WOTS+ signature sig_ots, an
+   authentication path auth, an n-byte message M', seed SEED, and
+   address ADRS.  XMSS_rootFromSig returns an n-byte string holding the
+   value of the root of a tree defined by the input data.
+
+   Algorithm 13: XMSS_rootFromSig - Compute a root node from a tree
+   signature
+
+     Input: index idx_sig, WOTS+ signature sig_ots, authentication path
+            auth, n-byte message M', seed SEED, address ADRS
+     Output: n-byte root value node[0]
+
+     ADRS.setType(0);   // Type = OTS hash address
+     ADRS.setOTSAddress(idx_sig);
+     pk_ots = WOTS_pkFromSig(sig_ots, M', SEED, ADRS);
+     ADRS.setType(1);   // Type = L-tree address
+     ADRS.setLTreeAddress(idx_sig);
+     byte[n][2] node;
+     node[0] = ltree(pk_ots, SEED, ADRS);
+     ADRS.setType(2);   // Type = hash tree address
+     ADRS.setTreeIndex(idx_sig);
+     for ( k = 0; k < h; k++ ) {
+       ADRS.setTreeHeight(k);
+       if ( (floor(idx_sig / (2^k)) % 2) == 0 ) {
+         ADRS.setTreeIndex(ADRS.getTreeIndex() / 2);
+         node[1] = RAND_HASH(node[0], auth[k], SEED, ADRS);
+       } else {
+         ADRS.setTreeIndex((ADRS.getTreeIndex() - 1) / 2);
+         node[1] = RAND_HASH(auth[k], node[0], SEED, ADRS);
+       }
+       node[0] = node[1];
+     }
+     return node[0];
+
+   The full XMSS signature verification is depicted below (Algorithm
+   14).  It handles message compression, delegates the root computation
+   to XMSS_rootFromSig, and compares the result to the value in the
+   public key.  XMSS_verify takes as input an XMSS signature Sig, a
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 31]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   message M, and an XMSS public key PK.  XMSS_verify returns true if
+   and only if Sig is a valid signature on M under public key PK.
+   Otherwise, it returns false.
+
+   Algorithm 14: XMSS_verify - Verify an XMSS signature using the
+   corresponding XMSS public key and a message
+
+     Input: XMSS signature Sig, message M, XMSS public key PK
+     Output: Boolean
+
+     ADRS = toByte(0, 32);
+     byte[n] M' = H_msg(r || getRoot(PK) || (toByte(idx_sig, n)), M);
+
+     byte[n] node = XMSS_rootFromSig(idx_sig, sig_ots, auth, M',
+                                     getSEED(PK), ADRS);
+     if ( node == getRoot(PK) ) {
+       return true;
+     } else {
+       return false;
+     }
+
+4.1.11.  Pseudorandom Key Generation
+
+   An implementation MAY use a cryptographically secure pseudorandom
+   method to generate the XMSS private key from a single n-byte value.
+   For example, the method suggested in [BDH11] and explained below MAY
+   be used.  Other methods, such as the one in [HRS16], MAY be used.
+   The choice of a pseudorandom method does not affect interoperability,
+   but the cryptographic strength MUST match that of the used XMSS
+   parameters.
+
+   For XMSS, a method similar to that for WOTS+ can be used.  The
+   suggested method from [BDH11] can be described using PRF.  During key
+   generation, a uniformly random n-byte string S is sampled from a
+   secure source of randomness.  This seed S MUST NOT be confused with
+   the public seed SEED.  The seed S MUST be independent of SEED, and
+   because it is the main secret, it MUST be kept secret.  This seed S
+   is used to generate an n-byte value S_ots for each WOTS+ key pair.
+   The n-byte value S_ots can then be used to compute the respective
+   WOTS+ private key using the method described in Section 3.1.7.  The
+   seeds for the WOTS+ key pairs are computed as S_ots[i] = PRF(S,
+   toByte(i, 32)) where i is the index of the WOTS+ key pair.  An
+   advantage of this method is that a WOTS+ key can be computed using
+   only len + 1 evaluations of PRF when S is given.
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 32]
+
+RFC 8391                          XMSS                          May 2018
+
+
+4.1.12.  Free Index Handling and Partial Private Keys
+
+   Some applications might require working with partial private keys or
+   copies of private keys.  Examples include load balancing and
+   delegation of signing rights or proxy signatures.  Such applications
+   MAY use their own key format and MAY use a signing algorithm
+   different from the one described above.  The index in partial private
+   keys or copies of a private key MAY be manipulated as required by the
+   applications.  However, applications MUST establish means that
+   guarantee that each index, and thereby each WOTS+ key pair, is used
+   to sign only a single message.
+
+4.2.  XMSS^MT: Multi-Tree XMSS
+
+   XMSS^MT is a method for signing a large but fixed number of messages.
+   It was first described in [HRB13].  It builds on XMSS.  XMSS^MT uses
+   a tree of several layers of XMSS trees, a so-called hypertree.  The
+   trees on top and intermediate layers are used to sign the root nodes
+   of the trees on the respective layer below.  Trees on the lowest
+   layer are used to sign the actual messages.  All XMSS trees have
+   equal height.
+
+   Consider an XMSS^MT tree of total height h that has d layers of XMSS
+   trees of height h / d.  Then, layer d - 1 contains one XMSS tree,
+   layer d - 2 contains 2^(h / d) XMSS trees, and so on.  Finally, layer
+   0 contains 2^(h - h / d) XMSS trees.
+
+4.2.1.  XMSS^MT Parameters
+
+   In addition to all XMSS parameters, an XMSS^MT system requires the
+   number of tree layers d, specified as an integer value that divides h
+   without remainder.  The same tree height h / d and the same
+   Winternitz parameter w are used for all tree layers.
+
+   All the trees on higher layers sign root nodes of other trees, with
+   the root nodes being n-byte strings.  Hence, no message compression
+   is needed, and WOTS+ is used to sign the root nodes themselves
+   instead of their hash values.
+
+4.2.2.  XMSS^MT Key Generation
+
+   An XMSS^MT private key SK_MT (S for secret) consists of one reduced
+   XMSS private key for each XMSS tree.  These reduced XMSS private keys
+   just contain the WOTS+ private keys corresponding to that XMSS key
+   pair; they do not contain a pseudorandom function key, index, public
+   seed, or root node.  Instead, SK_MT contains a single n-byte
+   pseudorandom function key SK_PRF, a single (ceil(h / 8))-byte index
+   idx_MT, a single n-byte seed SEED, and a single root value root
+
+
+
+Huelsing, et al.              Informational                    [Page 33]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   (which is the root of the single tree on the top layer).  The index
+   is a global index over all WOTS+ key pairs of all XMSS trees on layer
+   0.  It is initialized with 0.  It stores the index of the last used
+   WOTS+ key pair on the bottom layer, i.e., a number between 0 and 2^h
+   - 1.
+
+   The reduced XMSS private keys MUST either be generated as described
+   in Section 4.1.3 or be generated using a cryptographic pseudorandom
+   method as discussed in Section 4.2.6.  As for XMSS, the PRF key
+   SK_PRF MUST be sampled from a secure source of randomness that
+   follows the uniform distribution.  SEED is generated as a uniformly
+   random n-byte string.  Although SEED is public, it is critical for
+   security that it is generated using a good entropy source.  The root
+   is the root node of the single XMSS tree on the top layer.  Its
+   computation is explained below.  As for XMSS, root and SEED are
+   public information and would classically be considered part of the
+   public key.  However, as both are needed for signing, which only
+   takes the private key, they are also part of SK_MT.
+
+   This document does not define any specific format for the XMSS^MT
+   private key SK_MT as it is not required for interoperability.
+   Algorithms 15 and 16 use a function getXMSS_SK(SK, x, y) that outputs
+   the reduced private key of the x^th XMSS tree on the y^th layer.
+
+   The XMSS^MT public key PK_MT contains the root of the single XMSS
+   tree on layer d - 1 and the seed SEED.  These are the same values as
+   in the private key SK_MT.  The pseudorandom function PRF keyed with
+   SEED is used to generate the bitmasks and keys for all XMSS trees.
+   XMSSMT_keyGen (Algorithm 15) shows example pseudocode to generate
+   SK_MT and PK_MT.  The n-byte root node of the top-layer tree is
+   computed using treeHash.  The algorithm XMSSMT_keyGen outputs an
+   XMSS^MT private key SK_MT and an XMSS^MT public key PK_MT.  The
+   algorithm below gives an example of how the reduced XMSS private keys
+   can be generated.  However, any of the above mentioned ways is
+   acceptable as long as the cryptographic strength of the used method
+   matches or supersedes that of the used XMSS^MT parameter set.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 34]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 15: XMSSMT_keyGen - Generate an XMSS^MT key pair
+
+     Input: No input
+     Output: XMSS^MT private key SK_MT, XMSS^MT public key PK_MT
+
+     // Example initialization
+     idx_MT = 0;
+     setIdx(SK_MT, idx_MT);
+     initialize SK_PRF with a uniformly random n-byte string;
+     setSK_PRF(SK_MT, SK_PRF);
+     initialize SEED with a uniformly random n-byte string;
+     setSEED(SK_MT, SEED);
+
+     // Generate reduced XMSS private keys
+     ADRS = toByte(0, 32);
+     for ( layer = 0; layer < d; layer++ ) {
+        ADRS.setLayerAddress(layer);
+        for ( tree = 0; tree <
+              (1 << ((d - 1 - layer) * (h / d)));
+              tree++ ) {
+           ADRS.setTreeAddress(tree);
+           for ( i = 0; i < 2^(h / d); i++ ) {
+             wots_sk[i] = WOTS_genSK();
+           }
+           setXMSS_SK(SK_MT, wots_sk, tree, layer);
+        }
+     }
+
+     SK = getXMSS_SK(SK_MT, 0, d - 1);
+     setSEED(SK, SEED);
+     root = treeHash(SK, 0, h / d, ADRS);
+     setRoot(SK_MT, root);
+
+     PK_MT = OID || root || SEED;
+     return (SK_MT || PK_MT);
+
+   The above is just an example algorithm.  It is strongly RECOMMENDED
+   to use pseudorandom key generation to reduce the private key size.
+   Public and private key generation MAY be interleaved to save space.
+   In particular, when a pseudorandom method is used to generate the
+   private key, generation MAY be delayed to the point that the
+   respective WOTS+ key pair is needed by another algorithm.
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 35]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The format of an XMSS^MT public key is given below.
+
+            +---------------------------------+
+            |          algorithm OID          |
+            +---------------------------------+
+            |                                 |
+            |            root node            |     n bytes
+            |                                 |
+            +---------------------------------+
+            |                                 |
+            |              SEED               |     n bytes
+            |                                 |
+            +---------------------------------+
+
+                            XMSS^MT Public Key
+
+4.2.3.  XMSS^MT Signature
+
+   An XMSS^MT signature Sig_MT is a byte string of length (ceil(h / 8) +
+   n + (h + d * len) * n).  It consists of:
+
+   o  the index idx_sig of the used WOTS+ key pair on the bottom layer
+      (ceil(h / 8) bytes),
+
+   o  a byte string r used for randomized message hashing (n bytes), and
+
+   o  d reduced XMSS signatures ((h / d + len) * n bytes each).
+
+   The reduced XMSS signatures only contain a WOTS+ signature sig_ots
+   and an authentication path auth.  They contain no index idx and no
+   byte string r.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 36]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The data format for a signature is given below.
+
+           +---------------------------------+
+           |                                 |
+           |          index idx_sig          |   ceil(h / 8) bytes
+           |                                 |
+           +---------------------------------+
+           |                                 |
+           |          randomness r           |   n bytes
+           |                                 |
+           +---------------------------------+
+           |                                 |
+           |  (reduced) XMSS signature Sig   |   (h / d + len) * n bytes
+           |        (bottom layer 0)         |
+           |                                 |
+           +---------------------------------+
+           |                                 |
+           |  (reduced) XMSS signature Sig   |   (h / d + len) * n bytes
+           |            (layer 1)            |
+           |                                 |
+           +---------------------------------+
+           |                                 |
+           ~              ....               ~
+           |                                 |
+           +---------------------------------+
+           |                                 |
+           |  (reduced) XMSS signature Sig   |   (h / d + len) * n bytes
+           |          (layer d - 1)          |
+           |                                 |
+           +---------------------------------+
+
+                             XMSS^MT Signature
+
+4.2.4.  XMSS^MT Signature Generation
+
+   To compute the XMSS^MT signature Sig_MT of a message M using an
+   XMSS^MT private key SK_MT, XMSSMT_sign (Algorithm 16) described below
+   uses treeSig as defined in Section 4.1.9.  First, the signature index
+   is set to idx_sig.  Next, PRF is used to compute a pseudorandom
+   n-byte string r.  This n-byte string, idx_sig, and the root node from
+   PK_MT are then used to compute a randomized message digest of length
+   n.  The message digest is signed using the WOTS+ key pair on the
+   bottom layer with absolute index idx.  The authentication path for
+   the WOTS+ key pair and the root of the containing XMSS tree are
+   computed.  The root is signed by the parent XMSS tree.  This is
+   repeated until the top tree is reached.
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 37]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 16: XMSSMT_sign - Generate an XMSS^MT signature and update
+   the XMSS^MT private key
+
+     Input: Message M, XMSS^MT private key SK_MT
+     Output: Updated SK_MT, signature Sig_MT
+
+     // Init
+     ADRS = toByte(0, 32);
+     SEED = getSEED(SK_MT);
+     SK_PRF = getSK_PRF(SK_MT);
+     idx_sig = getIdx(SK_MT);
+
+     // Update SK_MT
+     setIdx(SK_MT, idx_sig + 1);
+
+     // Message compression
+     byte[n] r = PRF(SK_PRF, toByte(idx_sig, 32));
+     byte[n] M' = H_msg(r || getRoot(SK_MT) || (toByte(idx_sig, n)), M);
+
+     // Sign
+     Sig_MT = idx_sig;
+     unsigned int idx_tree
+                   = (h - h / d) most significant bits of idx_sig;
+     unsigned int idx_leaf = (h / d) least significant bits of idx_sig;
+     SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, 0) || SK_PRF
+           || toByte(0, n) || SEED;
+     ADRS.setLayerAddress(0);
+     ADRS.setTreeAddress(idx_tree);
+     Sig_tmp = treeSig(M', SK, idx_leaf, ADRS);
+     Sig_MT = Sig_MT || r || Sig_tmp;
+     for ( j = 1; j < d; j++ ) {
+        root = treeHash(SK, 0, h / d, ADRS);
+        idx_leaf = (h / d) least significant bits of idx_tree;
+        idx_tree = (h - j * (h / d)) most significant bits of idx_tree;
+        SK = idx_leaf || getXMSS_SK(SK_MT, idx_tree, j) || SK_PRF
+               || toByte(0, n) || SEED;
+        ADRS.setLayerAddress(j);
+        ADRS.setTreeAddress(idx_tree);
+        Sig_tmp = treeSig(root, SK, idx_leaf, ADRS);
+        Sig_MT = Sig_MT || Sig_tmp;
+     }
+     return SK_MT || Sig_MT;
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 38]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Algorithm 16 is only one method to compute XMSS^MT signatures.  Time-
+   memory trade-offs exist that allow reduction of the signing time to
+   less than the signing time of an XMSS scheme with tree height h / d.
+   These trade-offs 1) prevent certain values from being recomputed
+   several times by keeping a state and 2) distribute all computations
+   over all signature generations.  Details can be found in
+   [Huelsing13a].
+
+4.2.5.  XMSS^MT Signature Verification
+
+   XMSS^MT signature verification (Algorithm 17) can be summarized as d
+   XMSS signature verifications with small changes.  First, the message
+   is hashed.  The XMSS signatures are then all on n-byte values.
+   Second, instead of comparing the computed root node to a given value,
+   a signature on this root node is verified.  Only the root node of the
+   top tree is compared to the value in the XMSS^MT public key.
+   XMSSMT_verify uses XMSS_rootFromSig.  The function
+   getXMSSSignature(Sig_MT, i) returns the ith reduced XMSS signature
+   from the XMSS^MT signature Sig_MT.  XMSSMT_verify takes as input an
+   XMSS^MT signature Sig_MT, a message M, and a public key PK_MT.
+   XMSSMT_verify returns true if and only if Sig_MT is a valid signature
+   on M under public key PK_MT.  Otherwise, it returns false.
+
+   Algorithm 17: XMSSMT_verify - Verify an XMSS^MT signature Sig_MT on a
+   message M using an XMSS^MT public key PK_MT
+
+     Input: XMSS^MT signature Sig_MT, message M,
+            XMSS^MT public key PK_MT
+     Output: Boolean
+
+     idx_sig = getIdx(Sig_MT);
+     SEED = getSEED(PK_MT);
+     ADRS = toByte(0, 32);
+
+     byte[n] M' = H_msg(getR(Sig_MT) || getRoot(PK_MT)
+                        || (toByte(idx_sig, n)), M);
+
+     unsigned int idx_leaf
+                   = (h / d) least significant bits of idx_sig;
+     unsigned int idx_tree
+                   = (h - h / d) most significant bits of idx_sig;
+     Sig' = getXMSSSignature(Sig_MT, 0);
+     ADRS.setLayerAddress(0);
+     ADRS.setTreeAddress(idx_tree);
+     byte[n] node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
+                                      getAuth(Sig'), M', SEED, ADRS);
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 39]
+
+RFC 8391                          XMSS                          May 2018
+
+
+     for ( j = 1; j < d; j++ ) {
+        idx_leaf = (h / d) least significant bits of idx_tree;
+        idx_tree = (h - j * h / d) most significant bits of idx_tree;
+        Sig' = getXMSSSignature(Sig_MT, j);
+        ADRS.setLayerAddress(j);
+        ADRS.setTreeAddress(idx_tree);
+        node = XMSS_rootFromSig(idx_leaf, getSig_ots(Sig'),
+                              getAuth(Sig'), node, SEED, ADRS);
+     }
+     if ( node == getRoot(PK_MT) ) {
+       return true;
+     } else {
+       return false;
+     }
+
+4.2.6.  Pseudorandom Key Generation
+
+   Like for XMSS, an implementation MAY use a cryptographically secure
+   pseudorandom method to generate the XMSS^MT private key from a single
+   n-byte value.  For example, the method explained below MAY be used.
+   Other methods, such as the one in [HRS16], MAY be used.  The choice
+   of a pseudorandom method does not affect interoperability, but the
+   cryptographic strength MUST match that of the used XMSS^MT
+   parameters.
+
+   For XMSS^MT, a method similar to that for XMSS and WOTS+ can be used.
+   The method uses PRF.  During key generation, a uniformly random
+   n-byte string S_MT is sampled from a secure source of randomness.
+   This seed S_MT is used to generate one n-byte value S for each XMSS
+   key pair.  This n-byte value can be used to compute the respective
+   XMSS private key using the method described in Section 4.1.11.  Let
+   S[x][y] be the seed for the x^th XMSS private key on layer y.  The
+   seeds are computed as S[x][y] = PRF(PRF(S, toByte(y, 32)), toByte(x,
+   32)).
+
+4.2.7.  Free Index Handling and Partial Private Keys
+
+   The content of Section 4.1.12 also applies to XMSS^MT.
+
+5.  Parameter Sets
+
+   This section provides basic parameter sets that are assumed to cover
+   most relevant applications.  Parameter sets for two classical
+   security levels are defined.  Parameters with n = 32 provide a
+   classical security level of 256 bits.  Parameters with n = 64 provide
+   a classical security level of 512 bits.  Considering quantum-
+   computer-aided attacks, these output sizes yield post-quantum
+   security of 128 and 256 bits, respectively.
+
+
+
+Huelsing, et al.              Informational                    [Page 40]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   While this document specifies several parameter sets, an
+   implementation is only REQUIRED to provide support for verification
+   of all REQUIRED parameter sets.  The REQUIRED parameter sets all use
+   SHA2-256 to instantiate all functions.  The REQUIRED parameter sets
+   are only distinguished by the tree height parameter h (which
+   determines the number of signatures that can be done with a single
+   key pair) and the number of layers d (which defines a trade-off
+   between speed and signature size).  An implementation MAY provide
+   support for signature generation using any of the proposed parameter
+   sets.  For convenience, this document defines a default option for
+   XMSS (XMSS_SHA2_20_256) and XMSS^MT (XMSSMT-SHA2_60/3_256).  These
+   are supposed to match the most generic requirements.
+
+5.1.  Implementing the Functions
+
+   For the n = 32 setting, we give parameters that use SHA2-256 as
+   defined in [FIPS180] and other parameters that use the SHA3/Keccak-
+   based extendable-output function SHAKE-128 as defined in [FIPS202].
+   For the n = 64 setting, we give parameters that use SHA2-512 as
+   defined in [FIPS180] and other parameters that use the SHA3/Keccak-
+   based extendable-output functions SHAKE-256 as defined in [FIPS202].
+   The parameter sets using SHA2-256 are mandatory for deployment and
+   therefore MUST be provided by any implementation.  The remaining
+   parameter sets specified in this document are OPTIONAL.
+
+   SHA2 does not provide a keyed-mode itself.  To implement the keyed
+   hash functions, the following is used for SHA2 with n = 32:
+
+      F: SHA2-256(toByte(0, 32) || KEY || M),
+
+      H: SHA2-256(toByte(1, 32) || KEY || M),
+
+      H_msg: SHA2-256(toByte(2, 32) || KEY || M), and
+
+      PRF: SHA2-256(toByte(3, 32) || KEY || M).
+
+   Accordingly, for SHA2 with n = 64 we use:
+
+      F: SHA2-512(toByte(0, 64) || KEY || M),
+
+      H: SHA2-512(toByte(1, 64) || KEY || M),
+
+      H_msg: SHA2-512(toByte(2, 64) || KEY || M), and
+
+      PRF: SHA2-512(toByte(3, 64) || KEY || M).
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 41]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The n-byte padding is used for two reasons.  First, it is necessary
+   that the internal compression function takes 2n-byte blocks, but keys
+   are n and 3n bytes long.  Second, the padding is used to achieve
+   independence of the different function families.  Finally, for the
+   PRF, no full-fledged Hash-Based Message Authentication Code (HMAC) is
+   needed as the message length is fixed, meaning that standard length
+   extension attacks are not a concern here.  For that reason, the
+   simpler construction above suffices.
+
+   Similar constructions are used with SHA3.  To implement the keyed
+   hash functions, the following is used for SHA3 with n = 32:
+
+      F: SHAKE128(toByte(0, 32) || KEY || M, 256),
+
+      H: SHAKE128(toByte(1, 32) || KEY || M, 256),
+
+      H_msg: SHAKE128(toByte(2, 32) || KEY || M, 256),
+
+      PRF: SHAKE128(toByte(3, 32) || KEY || M, 256).
+
+   Accordingly, for SHA3 with n = 64, we use:
+
+      F: SHAKE256(toByte(0, 64) || KEY || M, 512),
+
+      H: SHAKE256(toByte(1, 64) || KEY || M, 512),
+
+      H_msg: SHAKE256(toByte(2, 64) || KEY || M, 512),
+
+      PRF: SHAKE256(toByte(3, 64) || KEY || M, 512).
+
+   As for SHA2, an initial n-byte identifier is used to achieve
+   independence of the different function families.  While a shorter
+   identifier could be used in case of SHA3, we use n bytes for
+   consistency with the SHA2 implementations.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 42]
+
+RFC 8391                          XMSS                          May 2018
+
+
+5.2.  WOTS+ Parameters
+
+   To fully describe a WOTS+ signature method, the parameters n and w,
+   as well as the functions F and PRF, MUST be specified.  The following
+   table defines several WOTS+ signature systems, each of which is
+   identified by a name.  Naming follows this convention:
+   WOTSP-[Hashfamily]_[n in bits].  Naming does not include w as all
+   parameter sets in this document use w=16.  Values for len are
+   provided for convenience.
+
+              +-----------------+----------+----+----+-----+
+              | Name            | F / PRF  |  n |  w | len |
+              +-----------------+----------+----+----+-----+
+              | REQUIRED:       |          |    |    |     |
+              |                 |          |    |    |     |
+              | WOTSP-SHA2_256  | SHA2-256 | 32 | 16 |  67 |
+              |                 |          |    |    |     |
+              | OPTIONAL:       |          |    |    |     |
+              |                 |          |    |    |     |
+              | WOTSP-SHA2_512  | SHA2-512 | 64 | 16 | 131 |
+              |                 |          |    |    |     |
+              | WOTSP-SHAKE_256 | SHAKE128 | 32 | 16 |  67 |
+              |                 |          |    |    |     |
+              | WOTSP-SHAKE_512 | SHAKE256 | 64 | 16 | 131 |
+              +-----------------+----------+----+----+-----+
+
+                                  Table 1
+
+   The implementation of the single functions is done as described
+   above.  External Data Representation (XDR) formats for WOTS+ are
+   listed in Appendix A.
+
+5.3.  XMSS Parameters
+
+   To fully describe an XMSS signature method, the parameters n, w, and
+   h, as well as the functions F, H, H_msg, and PRF, MUST be specified.
+   The following table defines different XMSS signature systems, each of
+   which is identified by a name.  Naming follows this convention:
+   XMSS-[Hashfamily]_[h]_[n in bits].  Naming does not include w as all
+   parameter sets in this document use w=16.
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 43]
+
+RFC 8391                          XMSS                          May 2018
+
+
+          +-------------------+-----------+----+----+-----+----+
+          | Name              | Functions |  n |  w | len |  h |
+          +-------------------+-----------+----+----+-----+----+
+          | REQUIRED:         |           |    |    |     |    |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_10_256  | SHA2-256  | 32 | 16 |  67 | 10 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_16_256  | SHA2-256  | 32 | 16 |  67 | 16 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_20_256  | SHA2-256  | 32 | 16 |  67 | 20 |
+          |                   |           |    |    |     |    |
+          | OPTIONAL:         |           |    |    |     |    |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_10_512  | SHA2-512  | 64 | 16 | 131 | 10 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_16_512  | SHA2-512  | 64 | 16 | 131 | 16 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHA2_20_512  | SHA2-512  | 64 | 16 | 131 | 20 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_10_256 | SHAKE128  | 32 | 16 |  67 | 10 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_16_256 | SHAKE128  | 32 | 16 |  67 | 16 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_20_256 | SHAKE128  | 32 | 16 |  67 | 20 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_10_512 | SHAKE256  | 64 | 16 | 131 | 10 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_16_512 | SHAKE256  | 64 | 16 | 131 | 16 |
+          |                   |           |    |    |     |    |
+          | XMSS-SHAKE_20_512 | SHAKE256  | 64 | 16 | 131 | 20 |
+          +-------------------+-----------+----+----+-----+----+
+
+                                  Table 2
+
+   The XDR formats for XMSS are listed in Appendix B.
+
+5.3.1.  Parameter Guide
+
+   In contrast to traditional signature schemes like RSA or Digital
+   Signature Algorithm (DSA), XMSS has a tree height parameter h that
+   determines the number of messages that can be signed with one key
+   pair.  Increasing the height allows using a key pair for more
+   signatures, but it also increases the signature size and slows down
+   key generation, signing, and verification.  To demonstrate the impact
+   of different values of h, the following table shows signature size
+   and runtimes.  Runtimes are given as the number of calls to F and H
+   when the BDS algorithm is used to compute authentication paths for
+
+
+
+
+Huelsing, et al.              Informational                    [Page 44]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   the worst case.  The last column shows the number of messages that
+   can be signed with one key pair.  The numbers are the same for the
+   XMSS-SHAKE instances with same parameters h and n.
+
+    +------------------+-------+------------+--------+--------+-------+
+    | Name             | |Sig| |     KeyGen |   Sign | Verify | #Sigs |
+    +------------------+-------+------------+--------+--------+-------+
+    | REQUIRED:        |       |            |        |        |       |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_10_256 | 2,500 |  1,238,016 |  5,725 |  1,149 |  2^10 |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_16_256 | 2,692 |    79*10^6 |  9,163 |  1,155 |  2^16 |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_20_256 | 2,820 | 1,268*10^6 | 11,455 |  1,159 |  2^20 |
+    |                  |       |            |        |        |       |
+    | OPTIONAL:        |       |            |        |        |       |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_10_512 | 9,092 |  2,417,664 | 11,165 |  2,237 |  2^10 |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_16_512 | 9,476 |   155*10^6 | 17,867 |  2,243 |  2^16 |
+    |                  |       |            |        |        |       |
+    | XMSS-SHA2_20_512 | 9,732 | 2,476*10^6 | 22,335 |  2,247 |  2^20 |
+    +------------------+-------+------------+--------+--------+-------+
+
+                                  Table 3
+
+   As a default, users without special requirements should use option
+   XMSS-SHA2_20_256, which allows signing of 2^20 messages with one key
+   pair and provides reasonable speed and signature size.  Users that
+   require more signatures per key pair or faster key generation should
+   consider XMSS^MT.
+
+5.4.  XMSS^MT Parameters
+
+   To fully describe an XMSS^MT signature method, the parameters n, w,
+   h, and d, as well as the functions F, H, H_msg, and PRF, MUST be
+   specified.  The following table defines different XMSS^MT signature
+   systems, each of which is identified by a name.  Naming follows this
+   convention: XMSSMT-[Hashfamily]_[h]/[d]_[n in bits].  Naming does not
+   include w as all parameter sets in this document use w=16.
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 45]
+
+RFC 8391                          XMSS                          May 2018
+
+
+     +------------------------+-----------+----+----+-----+----+----+
+     | Name                   | Functions |  n |  w | len |  h |  d |
+     +------------------------+-----------+----+----+-----+----+----+
+     | REQUIRED:              |           |    |    |     |    |    |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_20/2_256   | SHA2-256  | 32 | 16 |  67 | 20 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_20/4_256   | SHA2-256  | 32 | 16 |  67 | 20 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/2_256   | SHA2-256  | 32 | 16 |  67 | 40 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/4_256   | SHA2-256  | 32 | 16 |  67 | 40 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/8_256   | SHA2-256  | 32 | 16 |  67 | 40 |  8 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/3_256   | SHA2-256  | 32 | 16 |  67 | 60 |  3 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/6_256   | SHA2-256  | 32 | 16 |  67 | 60 |  6 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/12_256  | SHA2-256  | 32 | 16 |  67 | 60 | 12 |
+     |                        |           |    |    |     |    |    |
+     | OPTIONAL:              |           |    |    |     |    |    |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_20/2_512   | SHA2-512  | 64 | 16 | 131 | 20 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_20/4_512   | SHA2-512  | 64 | 16 | 131 | 20 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/2_512   | SHA2-512  | 64 | 16 | 131 | 40 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/4_512   | SHA2-512  | 64 | 16 | 131 | 40 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_40/8_512   | SHA2-512  | 64 | 16 | 131 | 40 |  8 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/3_512   | SHA2-512  | 64 | 16 | 131 | 60 |  3 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/6_512   | SHA2-512  | 64 | 16 | 131 | 60 |  6 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHA2_60/12_512  | SHA2-512  | 64 | 16 | 131 | 60 | 12 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_20/2_256  | SHAKE128  | 32 | 16 |  67 | 20 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_20/4_256  | SHAKE128  | 32 | 16 |  67 | 20 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/2_256  | SHAKE128  | 32 | 16 |  67 | 40 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/4_256  | SHAKE128  | 32 | 16 |  67 | 40 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/8_256  | SHAKE128  | 32 | 16 |  67 | 40 |  8 |
+
+
+
+Huelsing, et al.              Informational                    [Page 46]
+
+RFC 8391                          XMSS                          May 2018
+
+
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/3_256  | SHAKE128  | 32 | 16 |  67 | 60 |  3 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/6_256  | SHAKE128  | 32 | 16 |  67 | 60 |  6 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/12_256 | SHAKE128  | 32 | 16 |  67 | 60 | 12 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_20/2_512  | SHAKE256  | 64 | 16 | 131 | 20 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_20/4_512  | SHAKE256  | 64 | 16 | 131 | 20 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/2_512  | SHAKE256  | 64 | 16 | 131 | 40 |  2 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/4_512  | SHAKE256  | 64 | 16 | 131 | 40 |  4 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_40/8_512  | SHAKE256  | 64 | 16 | 131 | 40 |  8 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/3_512  | SHAKE256  | 64 | 16 | 131 | 60 |  3 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/6_512  | SHAKE256  | 64 | 16 | 131 | 60 |  6 |
+     |                        |           |    |    |     |    |    |
+     | XMSSMT-SHAKE_60/12_512 | SHAKE256  | 64 | 16 | 131 | 60 | 12 |
+     +------------------------+-----------+----+----+-----+----+----+
+
+                                  Table 4
+
+   XDR formats for XMSS^MT are listed in Appendix C.
+
+5.4.1.  Parameter Guide
+
+   In addition to the tree height parameter already used for XMSS,
+   XMSS^MT has the parameter d that determines the number of tree
+   layers.  XMSS can be understood as XMSS^MT with a single layer, i.e.,
+   d=1.  Hence, the choice of h has the same effect as for XMSS.  The
+   number of tree layers provides a trade-off between signature size on
+   the one side and key generation and signing speed on the other side.
+   Increasing the number of layers reduces key generation time
+   exponentially and signing time linearly at the cost of increasing the
+   signature size linearly.  Essentially, an XMSS^MT signature contains
+   one WOTSP signature per layer.  Speed roughly corresponds to d-times
+   the speed for XMSS with trees of height h/d.
+
+   To demonstrate the impact of different values of h and d, the
+   following table shows signature size and runtimes.  Runtimes are
+   given as the number of calls to F and H when the BDS algorithm and
+   distributed signature generation are used.  Timings are worst-case
+   times.  The last column shows the number of messages that can be
+   signed with one key pair.  The numbers are the same for the XMSS-
+
+
+
+Huelsing, et al.              Informational                    [Page 47]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   SHAKE instances with same parameters h and n.  Due to formatting
+   limitations, only the parameter part of the parameter set names are
+   given, omitting the name "XMSSMT".
+
+    +----------------+---------+------------+--------+--------+-------+
+    | Name           |   |Sig| |     KeyGen |   Sign | Verify | #Sigs |
+    +----------------+---------+------------+--------+--------+-------+
+    | REQUIRED:      |         |            |        |        |       |
+    |                |         |            |        |        |       |
+    | SHA2_20/2_256  |   4,963 |  2,476,032 |  7,227 |  2,298 |  2^20 |
+    |                |         |            |        |        |       |
+    | SHA2_20/4_256  |   9,251 |    154,752 |  4,170 |  4,576 |  2^20 |
+    |                |         |            |        |        |       |
+    | SHA2_40/2_256  |   5,605 | 2,535*10^6 | 13,417 |  2,318 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_40/4_256  |   9,893 |  4,952,064 |  7,227 |  4,596 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_40/8_256  |  18,469 |    309,504 |  4,170 |  9,152 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_60/3_256  |   8,392 | 3,803*10^6 | 13,417 |  3,477 |  2^60 |
+    |                |         |            |        |        |       |
+    | SHA2_60/6_256  |  14,824 |  7,428,096 |  7,227 |  6,894 |  2^60 |
+    |                |         |            |        |        |       |
+    | SHA2_60/12_256 |  27,688 |    464,256 |  4,170 | 13,728 |  2^60 |
+    |                |         |            |        |        |       |
+    | OPTIONAL:      |         |            |        |        |       |
+    |                |         |            |        |        |       |
+    | SHA2_20/2_512  |  18,115 |  4,835,328 | 14,075 |  4,474 |  2^20 |
+    |                |         |            |        |        |       |
+    | SHA2_20/4_512  |  34,883 |    302,208 |  8,138 |  8,928 |  2^20 |
+    |                |         |            |        |        |       |
+    | SHA2_40/2_512  |  19,397 | 4,951*10^6 | 26,025 |  4,494 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_40/4_512  |  36,165 |  9,670,656 | 14,075 |  8,948 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_40/8_512  |  69,701 |    604,416 |  8,138 | 17,856 |  2^40 |
+    |                |         |            |        |        |       |
+    | SHA2_60/3_512  |  29,064 | 7,427*10^6 | 26,025 |  6,741 |  2^60 |
+    |                |         |            |        |        |       |
+    | SHA2_60/6_512  |  54,216 | 14,505,984 | 14,075 | 13,422 |  2^60 |
+    |                |         |            |        |        |       |
+    | SHA2_60/12_512 | 104,520 |    906,624 |  8,138 | 26,784 |  2^60 |
+    +----------------+---------+------------+--------+--------+-------+
+
+                                  Table 5
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 48]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   As a default, users without special requirements should use option
+   XMSSMT-SHA2_60/3_256, which allows signing of 2^60 messages with one
+   key pair (this is a virtually unbounded number of signatures).  At
+   the same time, signature size and speed are well balanced.
+
+6.  Rationale
+
+   The goal of this note is to describe the WOTS+, XMSS, and XMSS^MT
+   algorithms based on the scientific literature.  The description is
+   done in a modular way that allows basing a description of stateless
+   hash-based signature algorithms like SPHINCS [BHH15] on it.
+
+   This note slightly deviates from the scientific literature by using a
+   tweak that prevents multi-user and multi-target attacks against
+   H_msg.  To this end, the public key as well as the index of the used
+   one-time key pair become part of the hash function key.  Thereby, we
+   achieve a domain separation that forces an attacker to decide which
+   hash value to attack.
+
+   For the generation of the randomness used for randomized message
+   hashing, we apply a PRF, keyed with a secret value, to the index of
+   the used one-time key pair instead of the message.  The reason is
+   that this requires processing the message only once instead of twice.
+   For long messages, this improves speed and simplifies implementations
+   on resource-constrained devices that cannot hold the entire message
+   in storage.
+
+   We give one mandatory set of parameters using SHA2-256.  The reasons
+   are twofold.  On the one hand, SHA2-256 is part of most cryptographic
+   libraries.  On the other hand, a 256-bit hash function leads to
+   parameters that provide 128 bits of security even against quantum-
+   computer-aided attacks.  A post-quantum security level of 256 bits
+   seems overly conservative.  However, to prepare for possible
+   cryptanalytic breakthroughs, we also provide OPTIONAL parameter sets
+   using the less widely supported SHA2-512, SHAKE-256, and SHAKE-512
+   functions.
+
+   We suggest the value w = 16 for the Winternitz parameter.  No bigger
+   values are included since the decrease in signature size then becomes
+   less significant.  Furthermore, the value w = 16 considerably
+   simplifies the implementations of some of the algorithms.  Please
+   note that we do allow w = 4 but limit the specified parameter sets to
+   w = 16 for efficiency reasons.
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 49]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The signature and public key formats are designed so that they are
+   easy to parse.  Each format starts with a 32-bit enumeration value
+   that indicates all of the details of the signature algorithm and
+   hence defines all of the information that is needed in order to parse
+   the format.
+
+7.  Reference Code
+
+   For testing purposes, a reference implementation in C is available.
+   The code contains a basic implementation that closely follows the
+   pseudocode in this document and an optimized implementation that uses
+   the BDS algorithm [BDS08] to compute authentication paths and
+   distributed signature generation as described in [HRB13] for XMSS^MT.
+
+   The code is permanently available at
+   <https://github.com/joostrijneveld/xmss-reference>.
+
+8.  IANA Considerations
+
+   The Internet Assigned Numbers Authority (IANA) has created three
+   registries: one for WOTS+ signatures (as defined in Section 3), one
+   for XMSS signatures (as defined in Section 4), and one for XMSS^MT
+   signatures (as defined in Section 4).  For the sake of clarity and
+   convenience, the first collection of WOTS+, XMSS, and XMSS^MT
+   parameter sets is defined in Section 5.  Additions to these
+   registries require that a specification be documented in an RFC or
+   another permanent and readily available reference in sufficient
+   detail as defined by the "Specification Required" policy described in
+   [RFC8126] to make interoperability between independent
+   implementations possible.  Each entry in these registries contains
+   the following elements:
+
+   o  a short name, such as "XMSS_SHA2_20_256",
+
+   o  a positive number, and
+
+   o  a reference to a specification that completely defines the
+      signature method test cases or provides a reference implementation
+      that can be used to verify the correctness of an implementation
+      (or a reference to such an implementation).
+
+   Requests to add an entry to these registries MUST include the name
+   and the reference.  The number is assigned by IANA.  These number
+   assignments SHOULD use the smallest available positive number.
+   Submitters MUST have their requests reviewed and approved.
+   Designated Experts for this task as requested by the "Specification
+   Required" policy defined by [RFC8126] will be assigned by the
+
+
+
+
+Huelsing, et al.              Informational                    [Page 50]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   Internet Engineering Steering Group (IESG).  The IESG can be
+   contacted at iesg@ietf.org.  Interested applicants that are
+   unfamiliar with IANA processes should visit <http://www.iana.org>.
+
+   The number 0x00000000 (decimal 0) is Reserved.  The numbers between
+   0xDDDDDDDD (decimal 3,722,304,989) and 0xFFFFFFFF (decimal
+   4,294,967,295) inclusive will not be assigned by IANA and are
+   Reserved for Private Use; no attempt will be made to prevent multiple
+   sites from using the same value in different (and incompatible) ways
+   [RFC8126].
+
+   The "WOTS+ Signatures" registry is as follows.
+
+          +--------------------+-----------------+-------------+
+          | Numeric Identifier | Name            |  Reference  |
+          +--------------------+-----------------+-------------+
+          |     0x00000000     | Reserved        |   this RFC  |
+          |                    |                 |             |
+          |     0x00000001     | WOTSP-SHA2_256  | Section 5.2 |
+          |                    |                 |             |
+          |     0x00000002     | WOTSP-SHA2_512  | Section 5.2 |
+          |                    |                 |             |
+          |     0x00000003     | WOTSP-SHAKE_256 | Section 5.2 |
+          |                    |                 |             |
+          |     0x00000004     | WOTSP-SHAKE_512 | Section 5.2 |
+          +--------------------+-----------------+-------------+
+
+                                  Table 6
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 51]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The "XMSS Signatures" registry is as follows.
+
+         +--------------------+-------------------+-------------+
+         | Numeric Identifier | Name              |  Reference  |
+         +--------------------+-------------------+-------------+
+         |     0x00000000     | Reserved          |   this RFC  |
+         |                    |                   |             |
+         |     0x00000001     | XMSS-SHA2_10_256  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000002     | XMSS-SHA2_16_256  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000003     | XMSS-SHA2_20_256  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000004     | XMSS-SHA2_10_512  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000005     | XMSS-SHA2_16_512  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000006     | XMSS-SHA2_20_512  | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000007     | XMSS-SHAKE_10_256 | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000008     | XMSS-SHAKE_16_256 | Section 5.3 |
+         |                    |                   |             |
+         |     0x00000009     | XMSS-SHAKE_20_256 | Section 5.3 |
+         |                    |                   |             |
+         |     0x0000000A     | XMSS-SHAKE_10_512 | Section 5.3 |
+         |                    |                   |             |
+         |     0x0000000B     | XMSS-SHAKE_16_512 | Section 5.3 |
+         |                    |                   |             |
+         |     0x0000000C     | XMSS-SHAKE_20_512 | Section 5.3 |
+         +--------------------+-------------------+-------------+
+
+                                  Table 7
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 52]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   The "XMSS^MT Signatures" registry is as follows.
+
+       +--------------------+------------------------+-------------+
+       | Numeric Identifier | Name                   |  Reference  |
+       +--------------------+------------------------+-------------+
+       |     0x00000000     | Reserved               |   this RFC  |
+       |                    |                        |             |
+       |     0x00000001     | XMSSMT-SHA2_20/2_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000002     | XMSSMT-SHA2_20/4_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000003     | XMSSMT-SHA2_40/2_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000004     | XMSSMT-SHA2_40/4_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000005     | XMSSMT-SHA2_40/8_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000006     | XMSSMT-SHA2_60/3_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000007     | XMSSMT-SHA2_60/6_256   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000008     | XMSSMT-SHA2_60/12_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000009     | XMSSMT-SHA2_20/2_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000A     | XMSSMT-SHA2_20/4_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000B     | XMSSMT-SHA2_40/2_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000C     | XMSSMT-SHA2_40/4_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000D     | XMSSMT-SHA2_40/8_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000E     | XMSSMT-SHA2_60/3_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000000F     | XMSSMT-SHA2_60/6_512   | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000010     | XMSSMT-SHA2_60/12_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000011     | XMSSMT-SHAKE_20/2_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000012     | XMSSMT-SHAKE_20/4_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000013     | XMSSMT-SHAKE_40/2_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000014     | XMSSMT-SHAKE_40/4_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000015     | XMSSMT-SHAKE_40/8_256  | Section 5.4 |
+
+
+
+Huelsing, et al.              Informational                    [Page 53]
+
+RFC 8391                          XMSS                          May 2018
+
+
+       |                    |                        |             |
+       |     0x00000016     | XMSSMT-SHAKE_60/3_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000017     | XMSSMT-SHAKE_60/6_256  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000018     | XMSSMT-SHAKE_60/12_256 | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000019     | XMSSMT-SHAKE_20/2_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001A     | XMSSMT-SHAKE_20/4_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001B     | XMSSMT-SHAKE_40/2_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001C     | XMSSMT-SHAKE_40/4_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001D     | XMSSMT-SHAKE_40/8_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001E     | XMSSMT-SHAKE_60/3_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x0000001F     | XMSSMT-SHAKE_60/6_512  | Section 5.4 |
+       |                    |                        |             |
+       |     0x00000020     | XMSSMT-SHAKE_60/12_512 | Section 5.4 |
+       +--------------------+------------------------+-------------+
+
+                                  Table 8
+
+   An IANA registration of a signature system does not constitute an
+   endorsement of that system or its security.
+
+9.  Security Considerations
+
+   A signature system is considered secure if it prevents an attacker
+   from forging a valid signature.  More specifically, consider a
+   setting in which an attacker gets a public key and can learn
+   signatures on arbitrary messages of its choice.  A signature system
+   is secure if, even in this setting, the attacker cannot produce a new
+   message/signature pair of his choosing such that the verification
+   algorithm accepts.
+
+   Preventing an attacker from mounting an attack means that the attack
+   is computationally too expensive to be carried out.  There are
+   various estimates for when a computation is too expensive to be done.
+   For that reason, this note only describes how expensive it is for an
+   attacker to generate a forgery.  Parameters are accompanied by a bit
+   security value.  The meaning of bit security is as follows.  A
+   parameter set grants b bits of security if the best attack takes at
+   least 2^(b - 1) bit operations to achieve a success probability of
+
+
+
+
+Huelsing, et al.              Informational                    [Page 54]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   1/2.  Hence, to mount a successful attack, an attacker needs to
+   perform 2^b bit operations on average.  The given values for bit
+   security were estimated according to [HRS16].
+
+9.1.  Security Proofs
+
+   A full security proof for all schemes described in this document can
+   be found in [HRS16].  This proof shows that an attacker has to break
+   at least one out of certain security properties of the used hash
+   functions and PRFs to forge a signature in any of the described
+   schemes.  The proof in [HRS16] considers an initial message
+   compression different from the randomized hashing used here.  We
+   comment on this below.  For the original schemes, these proofs show
+   that an attacker has to break certain minimal security properties.
+   In particular, it is not sufficient to break the collision resistance
+   of the hash functions to generate a forgery.
+
+   More specifically, the requirements on the used functions are that F
+   and H are post-quantum multi-function multi-target second-preimage
+   resistant keyed functions, F fulfills an additional statistical
+   requirement that roughly says that most images have at least two
+   preimages, PRF is a post-quantum pseudorandom function, and H_msg is
+   a post-quantum multi-target extended target collision-resistant keyed
+   hash function.  For detailed definitions of these properties see
+   [HRS16].  To give some intuition: multi-function multi-target second-
+   preimage resistance is an extension of second-preimage resistance to
+   keyed hash functions, covering the case where an adversary succeeds
+   if it finds a second preimage for one out of many values.  The same
+   holds for multi-target extended target collision resistance, which
+   just lacks the multi-function identifier as target collision
+   resistance already considers keyed hash functions.  The proof in
+   [HRS16] splits PRF into two functions.  When PRF is used for
+   pseudorandom key generation or generation of randomness for
+   randomized message hashing, it is still considered a pseudorandom
+   function.  Whenever PRF is used to generate bitmasks and hash
+   function keys, it is modeled as a random oracle.  This is due to
+   technical reasons in the proof, and an implementation using a
+   pseudorandom function is secure.
+
+   The proof in [HRS16] considers classical randomized hashing for the
+   initial message compression, i.e., H(r, M) instead of H(r ||
+   getRoot(PK) || index, M).  This classical randomized hashing allows
+   getting a security reduction from extended target collision
+   resistance [HRS16], a property that is conjectured to be strictly
+   weaker than collision resistance.  However, it turns out that in this
+   case, an attacker could still launch a multi-target attack even
+   against multiple users at the same time.  The reason is that the
+   adversary attacking u users at the same time learns u * 2^h
+
+
+
+Huelsing, et al.              Informational                    [Page 55]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   randomized hashes H(r_i_j || M_i_j) with signature index i in [0, 2^h
+   - 1] and user index j in [0, u].  It suffices to find a single pair
+   (r*, M*) such that H(r* || M*) = H(r_i_u || M_i_u) for one out of the
+   u * 2^h learned hashes.  Hence, an attacker can do a brute-force
+   search in time 2^n / u * 2^h instead of 2^n.
+
+   The indexed randomized hashing H(r || getRoot(PK) || toByte(idx, n),
+   M) used in this work makes the hash function calls position- and
+   user-dependent.  This thwarts the above attack because each hash
+   function evaluation during an attack can only target one of the
+   learned randomized hash values.  More specifically, an attacker now
+   has to decide which index idx and which root value to use for each
+   query.  If one assumes that the used hash function is a random
+   function, it can be shown that a multi-user existential forgery
+   attack that targets this message compression has a complexity of 2^n
+   hash function calls.
+
+   The given bit security values were estimated based on the complexity
+   of the best-known generic attacks against the required security
+   properties of the used hash and pseudorandom functions, assuming
+   conventional and quantum adversaries.  At the time of writing,
+   generic attacks are the best-known attacks for the parameters
+   suggested in the classical setting.  Also, in the quantum setting,
+   there are no dedicated attacks known that perform better than generic
+   attacks.  Nevertheless, the topic of quantum cryptanalysis of hash
+   functions is not as well understood as in the classical setting.
+
+9.2.  Minimal Security Assumptions
+
+   The assumptions one has to make to prove security of the described
+   schemes are minimal in the following sense.  Any signature algorithm
+   that allows arbitrary size messages relies on the security of a
+   cryptographic hash function, either on collision resistance or on
+   extended target collision resistance if randomized hashing is used
+   for message compression.  For the schemes described here, this is
+   already sufficient to be secure.  In contrast, common signature
+   schemes like RSA, DSA, and Elliptic Curve Digital Signature Algorithm
+   (ECDSA) additionally rely on the conjectured hardness of certain
+   mathematical problems.
+
+9.3.  Post-Quantum Security
+
+   A post-quantum cryptosystem is a system that is secure against
+   attackers with access to a reasonably sized quantum computer.  At the
+   time of writing this note, whether or not it is feasible to build
+   such a machine is an open conjecture.  However, significant progress
+   was made over the last few years in this regard.  Hence, we consider
+   it a matter of risk assessment to prepare for this case.
+
+
+
+Huelsing, et al.              Informational                    [Page 56]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   In contrast to RSA, DSA, and ECDSA, the described signature systems
+   are post-quantum-secure if they are used with an appropriate
+   cryptographic hash function.  In particular, for post-quantum
+   security, the size of n must be twice the size required for classical
+   security.  This is in order to protect against quantum square-root
+   attacks due to Grover's algorithm.  [HRS16] shows that variants of
+   Grover's algorithm are the optimal generic attacks against the
+   security properties of hash functions required for the described
+   schemes.
+
+   As stated above, we only consider generic attacks here, as
+   cryptographic hash functions should be deprecated as soon as
+   dedicated attacks that perform significantly better exist.  This also
+   applies to the quantum setting.  As soon as dedicated quantum attacks
+   against the used hash function that can perform significantly better
+   than the described generic attacks exist, these hash functions should
+   not be used anymore for the described schemes, or the computation of
+   the security level has to be redone.
+
+10.  References
+
+10.1.  Normative References
+
+   [FIPS180]  National Institute of Standards and Technology, "Secure
+              Hash Standard (SHS)", FIPS PUB 180-4,
+              DOI 10.6028/NIST.FIPS.180-4, August 2015.
+
+   [FIPS202]  National Institute of Standards and Technology, "SHA-3
+              Standard: Permutation-Based Hash and Extendable-Output
+              Functions", FIPS PUB 202, DOI 10.6028/NIST.FIPS.202,
+              August 2015.
+
+   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
+              Requirement Levels", BCP 14, RFC 2119,
+              DOI 10.17487/RFC2119, March 1997,
+              <https://www.rfc-editor.org/info/rfc2119>.
+
+   [RFC4506]  Eisler, M., Ed., "XDR: External Data Representation
+              Standard", STD 67, RFC 4506, DOI 10.17487/RFC4506, May
+              2006, <https://www.rfc-editor.org/info/rfc4506>.
+
+   [RFC8126]  Cotton, M., Leiba, B., and T. Narten, "Guidelines for
+              Writing an IANA Considerations Section in RFCs", BCP 26,
+              RFC 8126, DOI 10.17487/RFC8126, June 2017,
+              <https://www.rfc-editor.org/info/rfc8126>.
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 57]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   [RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
+              2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
+              May 2017, <https://www.rfc-editor.org/info/rfc8174>.
+
+10.2.  Informative References
+
+   [BDH11]    Buchmann, J., Dahmen, E., and A. Huelsing, "XMSS - A
+              Practical Forward Secure Signature Scheme Based on Minimal
+              Security Assumptions", Lecture Notes in Computer Science,
+              Volume 7071, Post-Quantum Cryptography,
+              DOI 10.1007/978-3-642-25405-5_8, 2011.
+
+   [BDS08]    Buchmann, J., Dahmen, E., and M. Schneider, "Merkle Tree
+              Traversal Revisited", Lecture Notes in Computer Science,
+              Volume 5299, Post-Quantum Cryptography,
+              DOI 10.1007/978-3-540-88403-3_5, 2008.
+
+   [BDS09]    Buchmann, J., Dahmen, E., and M. Szydlo, "Hash-based
+              Digital Signature Schemes", Book chapter, Post-Quantum
+              Cryptography, DOI 10.1007/978-3-540-88702-7_3, 2009.
+
+   [BHH15]    Bernstein, D., Hopwood, D., Huelsing, A., Lange, T.,
+              Niederhagen, R., Papachristodoulou, L., Schneider, M.,
+              Schwabe, P., and Z. Wilcox-O'Hearn, "SPHINCS: Practical
+              Stateless Hash-Based Signatures", Lecture Notes in
+              Computer Science, Volume 9056, Advances in Cryptology -
+              EUROCRYPT, DOI 10.1007/978-3-662-46800-5_15, 2015.
+
+   [HRB13]    Huelsing, A., Rausch, L., and J. Buchmann, "Optimal
+              Parameters for XMSS^MT", Lecture Notes in Computer
+              Science, Volume 8128, CD-ARES,
+              DOI 10.1007/978-3-642-40588-4_14, 2013.
+
+   [HRS16]    Huelsing, A., Rijneveld, J., and F. Song, "Mitigating
+              Multi-Target Attacks in Hash-based Signatures", Lecture
+              Notes in Computer Science, Volume 9614, Public-Key
+              Cryptography - PKC, DOI 10.1007/978-3-662-49384-7_15,
+              2016.
+
+   [Huelsing13]
+              Huelsing, A., "W-OTS+ - Shorter Signatures for Hash-Based
+              Signature Schemes", Lecture Notes in Computer Science,
+              Volume 7918, Progress in Cryptology - AFRICACRYPT,
+              DOI 10.1007/978-3-642-38553-7_10, 2013.
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 58]
+
+RFC 8391                          XMSS                          May 2018
+
+
+   [Huelsing13a]
+              Huelsing, A., "Practical Forward Secure Signatures using
+              Minimal Security Assumptions", PhD thesis TU Darmstadt,
+              2013,
+              <http://tuprints.ulb.tu-darmstadt.de/3651/1/Thesis.pdf>.
+
+   [KMN14]    Knecht, M., Meier, W., and C. Nicola, "A space- and time-
+              efficient Implementation of the Merkle Tree Traversal
+              Algorithm", Computing Research Repository
+              (CoRR), arXiv:1409.4081, 2014.
+
+   [MCF18]    McGrew, D., Curcio, M., and S. Fluhrer, "Hash-Based
+              Signatures", Work in Progress, draft-mcgrew-hash-sigs-11,
+              April 2018.
+
+   [Merkle83] Merkle, R., "Secrecy, Authentication, and Public Key
+              Systems", Computer Science Series, UMI Research Press,
+              ISBN: 9780835713849, 1983.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 59]
+
+RFC 8391                          XMSS                          May 2018
+
+
+Appendix A.  WOTS+ XDR Formats
+
+   The WOTS+ signature and public key formats are formally defined using
+   XDR [RFC4506] in order to provide an unambiguous, machine readable
+   definition.  Though XDR is used, these formats are simple and easy to
+   parse without any special tools.  Note that this representation
+   includes all optional parameter sets.  The same applies for the XMSS
+   and XMSS^MT formats below.
+
+A.1.  WOTS+ Parameter Sets
+
+   WOTS+ parameter sets are defined using XDR syntax as follows:
+
+      /* ots_algorithm_type identifies a particular
+         signature algorithm */
+
+      enum ots_algorithm_type {
+        wotsp_reserved  = 0x00000000,
+        wotsp-sha2_256  = 0x00000001,
+        wotsp-sha2_512  = 0x00000002,
+        wotsp-shake_256 = 0x00000003,
+        wotsp-shake_512 = 0x00000004,
+      };
+
+A.2.  WOTS+ Signatures
+
+   WOTS+ signatures are defined using XDR syntax as follows:
+
+      /* Byte strings */
+
+      typedef opaque bytestring32[32];
+      typedef opaque bytestring64[64];
+
+      union ots_signature switch (ots_algorithm_type type) {
+        case wotsp-sha2_256:
+        case wotsp-shake_256:
+          bytestring32 ots_sig_n32_len67[67];
+
+        case wotsp-sha2_512:
+        case wotsp-shake_512:
+          bytestring64 ots_sig_n64_len18[131];
+
+        default:
+          void;   /* error condition */
+      };
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 60]
+
+RFC 8391                          XMSS                          May 2018
+
+
+A.3.  WOTS+ Public Keys
+
+   WOTS+ public keys are defined using XDR syntax as follows:
+
+      union ots_pubkey switch (ots_algorithm_type type) {
+        case wotsp-sha2_256:
+        case wotsp-shake_256:
+          bytestring32 ots_pubk_n32_len67[67];
+
+        case wotsp-sha2_512:
+        case wotsp-shake_512:
+          bytestring64 ots_pubk_n64_len18[131];
+
+        default:
+          void;   /* error condition */
+      };
+
+Appendix B.  XMSS XDR Formats
+
+B.1.  XMSS Parameter Sets
+
+   XMSS parameter sets are defined using XDR syntax as follows:
+
+      /* Byte strings */
+
+      typedef opaque bytestring4[4];
+
+      /* Definition of parameter sets */
+
+      enum xmss_algorithm_type {
+        xmss_reserved     = 0x00000000,
+
+        /* 256 bit classical security, 128 bit post-quantum security */
+
+        xmss-sha2_10_256  = 0x00000001,
+        xmss-sha2_16_256  = 0x00000002,
+        xmss-sha2_20_256  = 0x00000003,
+
+        /* 512 bit classical security, 256 bit post-quantum security */
+
+        xmss-sha2_10_512  = 0x00000004,
+        xmss-sha2_16_512  = 0x00000005,
+        xmss-sha2_20_512  = 0x00000006,
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 61]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        /* 256 bit classical security, 128 bit post-quantum security */
+
+        xmss-shake_10_256 = 0x00000007,
+        xmss-shake_16_256 = 0x00000008,
+        xmss-shake_20_256 = 0x00000009,
+
+        /* 512 bit classical security, 256 bit post-quantum security */
+
+        xmss-shake_10_512 = 0x0000000A,
+        xmss-shake_16_512 = 0x0000000B,
+        xmss-shake_20_512 = 0x0000000C,
+      };
+
+B.2.  XMSS Signatures
+
+   XMSS signatures are defined using XDR syntax as follows:
+
+      /* Authentication path types */
+
+      union xmss_path switch (xmss_algorithm_type type) {
+        case xmss-sha2_10_256:
+        case xmss-shake_10_256:
+          bytestring32 path_n32_t10[10];
+
+        case xmss-sha2_16_256:
+        case xmss-shake_16_256:
+          bytestring32 path_n32_t16[16];
+
+        case xmss-sha2_20_256:
+        case xmss-shake_20_256:
+          bytestring32 path_n32_t20[20];
+
+        case xmss-sha2_10_512:
+        case xmss-shake_10_512:
+          bytestring64 path_n64_t10[10];
+
+        case xmss-sha2_16_512:
+        case xmss-shake_16_512:
+          bytestring64 path_n64_t16[16];
+
+        case xmss-sha2_20_512:
+        case xmss-shake_20_512:
+          bytestring64 path_n64_t20[20];
+
+        default:
+          void;     /* error condition */
+      };
+
+
+
+
+Huelsing, et al.              Informational                    [Page 62]
+
+RFC 8391                          XMSS                          May 2018
+
+
+      /* Types for XMSS random strings */
+
+      union random_string_xmss switch (xmss_algorithm_type type) {
+        case xmss-sha2_10_256:
+        case xmss-sha2_16_256:
+        case xmss-sha2_20_256:
+        case xmss-shake_10_256:
+        case xmss-shake_16_256:
+        case xmss-shake_20_256:
+          bytestring32 rand_n32;
+
+        case xmss-sha2_10_512:
+        case xmss-sha2_16_512:
+        case xmss-sha2_20_512:
+        case xmss-shake_10_512:
+        case xmss-shake_16_512:
+        case xmss-shake_20_512:
+          bytestring64 rand_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* Corresponding WOTS+ type for given XMSS type */
+
+      union xmss_ots_signature switch (xmss_algorithm_type type) {
+        case xmss-sha2_10_256:
+        case xmss-sha2_16_256:
+        case xmss-sha2_20_256:
+          wotsp-sha2_256;
+
+        case xmss-sha2_10_512:
+        case xmss-sha2_16_512:
+        case xmss-sha2_20_512:
+          wotsp-sha2_512;
+
+        case xmss-shake_10_256:
+        case xmss-shake_16_256:
+        case xmss-shake_20_256:
+          wotsp-shake_256;
+
+        case xmss-shake_10_512:
+        case xmss-shake_16_512:
+        case xmss-shake_20_512:
+          wotsp-shake_512;
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 63]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* XMSS signature structure */
+
+      struct xmss_signature {
+        /* WOTS+ key pair index */
+        bytestring4 idx_sig;
+        /* Random string for randomized hashing */
+        random_string_xmss rand_string;
+        /* WOTS+ signature */
+        xmss_ots_signature sig_ots;
+        /* authentication path */
+        xmss_path nodes;
+      };
+
+B.3.  XMSS Public Keys
+
+   XMSS public keys are defined using XDR syntax as follows:
+
+      /* Types for bitmask seed */
+
+      union seed switch (xmss_algorithm_type type) {
+        case xmss-sha2_10_256:
+        case xmss-sha2_16_256:
+        case xmss-sha2_20_256:
+        case xmss-shake_10_256:
+        case xmss-shake_16_256:
+        case xmss-shake_20_256:
+          bytestring32 seed_n32;
+
+        case xmss-sha2_10_512:
+        case xmss-sha2_16_512:
+        case xmss-sha2_20_512:
+        case xmss-shake_10_512:
+        case xmss-shake_16_512:
+        case xmss-shake_20_512:
+          bytestring64 seed_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 64]
+
+RFC 8391                          XMSS                          May 2018
+
+
+      /* Types for XMSS root node */
+
+      union xmss_root switch (xmss_algorithm_type type) {
+        case xmss-sha2_10_256:
+        case xmss-sha2_16_256:
+        case xmss-sha2_20_256:
+        case xmss-shake_10_256:
+        case xmss-shake_16_256:
+        case xmss-shake_20_256:
+          bytestring32 root_n32;
+
+        case xmss-sha2_10_512:
+        case xmss-sha2_16_512:
+        case xmss-sha2_20_512:
+        case xmss-shake_10_512:
+        case xmss-shake_16_512:
+        case xmss-shake_20_512:
+          bytestring64 root_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* XMSS public key structure */
+
+      struct xmss_public_key {
+        xmss_root root;  /* Root node */
+        seed SEED;  /* Seed for bitmasks */
+      };
+
+Appendix C.  XMSS^MT XDR Formats
+
+C.1.  XMSS^MT Parameter Sets
+
+   XMSS^MT parameter sets are defined using XDR syntax as follows:
+
+      /* Byte strings */
+
+      typedef opaque bytestring3[3];
+      typedef opaque bytestring5[5];
+      typedef opaque bytestring8[8];
+
+      /* Definition of parameter sets */
+
+      enum xmssmt_algorithm_type {
+        xmssmt_reserved        = 0x00000000,
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 65]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        /* 256 bit classical security, 128 bit post-quantum security */
+
+        xmssmt-sha2_20/2_256   = 0x00000001,
+        xmssmt-sha2_20/4_256   = 0x00000002,
+        xmssmt-sha2_40/2_256   = 0x00000003,
+        xmssmt-sha2_40/4_256   = 0x00000004,
+        xmssmt-sha2_40/8_256   = 0x00000005,
+        xmssmt-sha2_60/3_256   = 0x00000006,
+        xmssmt-sha2_60/6_256   = 0x00000007,
+        xmssmt-sha2_60/12_256  = 0x00000008,
+
+        /* 512 bit classical security, 256 bit post-quantum security */
+
+        xmssmt-sha2_20/2_512   = 0x00000009,
+        xmssmt-sha2_20/4_512   = 0x0000000A,
+        xmssmt-sha2_40/2_512   = 0x0000000B,
+        xmssmt-sha2_40/4_512   = 0x0000000C,
+        xmssmt-sha2_40/8_512   = 0x0000000D,
+        xmssmt-sha2_60/3_512   = 0x0000000E,
+        xmssmt-sha2_60/6_512   = 0x0000000F,
+        xmssmt-sha2_60/12_512  = 0x00000010,
+
+        /* 256 bit classical security, 128 bit post-quantum security */
+
+        xmssmt-shake_20/2_256  = 0x00000011,
+        xmssmt-shake_20/4_256  = 0x00000012,
+        xmssmt-shake_40/2_256  = 0x00000013,
+        xmssmt-shake_40/4_256  = 0x00000014,
+        xmssmt-shake_40/8_256  = 0x00000015,
+        xmssmt-shake_60/3_256  = 0x00000016,
+        xmssmt-shake_60/6_256  = 0x00000017,
+        xmssmt-shake_60/12_256 = 0x00000018,
+
+        /* 512 bit classical security, 256 bit post-quantum security */
+
+        xmssmt-shake_20/2_512  = 0x00000019,
+        xmssmt-shake_20/4_512  = 0x0000001A,
+        xmssmt-shake_40/2_512  = 0x0000001B,
+        xmssmt-shake_40/4_512  = 0x0000001C,
+        xmssmt-shake_40/8_512  = 0x0000001D,
+        xmssmt-shake_60/3_512  = 0x0000001E,
+        xmssmt-shake_60/6_512  = 0x0000001F,
+        xmssmt-shake_60/12_512 = 0x00000020,
+      };
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 66]
+
+RFC 8391                          XMSS                          May 2018
+
+
+C.2.  XMSS^MT Signatures
+
+   XMSS^MT signatures are defined using XDR syntax as follows:
+
+      /* Type for XMSS^MT key pair index */
+      /* Depends solely on h */
+
+      union idx_sig_xmssmt switch (xmss_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_20/4_512:
+          bytestring3 idx3;
+
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-sha2_40/8_512:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_40/2_512:
+        case xmssmt-shake_40/4_512:
+        case xmssmt-shake_40/8_512:
+          bytestring5 idx5;
+
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-shake_60/3_256:
+        case xmssmt-shake_60/6_256:
+        case xmssmt-shake_60/12_256:
+        case xmssmt-shake_60/3_512:
+        case xmssmt-shake_60/6_512:
+        case xmssmt-shake_60/12_512:
+          bytestring8 idx8;
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 67]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        default:
+          void;     /* error condition */
+      };
+
+      union random_string_xmssmt switch (xmssmt_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_60/3_256:
+        case xmssmt-shake_60/6_256:
+        case xmssmt-shake_60/12_256:
+          bytestring32 rand_n32;
+
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-sha2_40/8_512:
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_20/4_512:
+        case xmssmt-shake_40/2_512:
+        case xmssmt-shake_40/4_512:
+        case xmssmt-shake_40/8_512:
+        case xmssmt-shake_60/3_512:
+        case xmssmt-shake_60/6_512:
+        case xmssmt-shake_60/12_512:
+          bytestring64 rand_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* Type for reduced XMSS signatures */
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 68]
+
+RFC 8391                          XMSS                          May 2018
+
+
+      union xmss_reduced (xmss_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_60/6_256:
+          bytestring32 xmss_reduced_n32_t77[77];
+
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_60/12_256:
+          bytestring32 xmss_reduced_n32_t72[72];
+
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_60/3_256:
+          bytestring32 xmss_reduced_n32_t87[87];
+
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_40/4_512:
+        case xmssmt-shake_60/6_512:
+          bytestring64 xmss_reduced_n32_t141[141];
+
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-sha2_40/8_512:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-shake_20/4_512:
+        case xmssmt-shake_40/8_512:
+        case xmssmt-shake_60/12_512:
+          bytestring64 xmss_reduced_n32_t136[136];
+
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-shake_40/2_512:
+        case xmssmt-shake_60/3_512:
+          bytestring64 xmss_reduced_n32_t151[151];
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 69]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* xmss_reduced_array depends on d */
+
+      union xmss_reduced_array (xmss_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_40/2_512:
+          xmss_reduced xmss_red_arr_d2[2];
+
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-shake_60/3_256:
+        case xmssmt-shake_60/3_512:
+          xmss_reduced xmss_red_arr_d3[3];
+
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_20/4_512:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_40/4_512:
+          xmss_reduced xmss_red_arr_d4[4];
+
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-shake_60/6_256:
+        case xmssmt-shake_60/6_512:
+          xmss_reduced xmss_red_arr_d6[6];
+
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_40/8_512:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_40/8_512:
+          xmss_reduced xmss_red_arr_d8[8];
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 70]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-shake_60/12_256:
+        case xmssmt-shake_60/12_512:
+          xmss_reduced xmss_red_arr_d12[12];
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* XMSS^MT signature structure */
+
+      struct xmssmt_signature {
+        /* WOTS+ key pair index */
+        idx_sig_xmssmt idx_sig;
+        /* Random string for randomized hashing */
+        random_string_xmssmt randomness;
+        /* Array of d reduced XMSS signatures */
+        xmss_reduced_array;
+      };
+
+C.3.  XMSS^MT Public Keys
+
+   XMSS^MT public keys are defined using XDR syntax as follows:
+
+      /* Types for bitmask seed */
+
+      union seed switch (xmssmt_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_60/6_256:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_60/12_256:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_60/3_256:
+          bytestring32 seed_n32;
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 71]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-sha2_40/8_512:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_40/4_512:
+        case xmssmt-shake_60/6_512:
+        case xmssmt-shake_20/4_512:
+        case xmssmt-shake_40/8_512:
+        case xmssmt-shake_60/12_512:
+        case xmssmt-shake_40/2_512:
+        case xmssmt-shake_60/3_512:
+          bytestring64 seed_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* Types for XMSS^MT root node */
+
+      union xmssmt_root switch (xmssmt_algorithm_type type) {
+        case xmssmt-sha2_20/2_256:
+        case xmssmt-sha2_20/4_256:
+        case xmssmt-sha2_40/2_256:
+        case xmssmt-sha2_40/4_256:
+        case xmssmt-sha2_40/8_256:
+        case xmssmt-sha2_60/3_256:
+        case xmssmt-sha2_60/6_256:
+        case xmssmt-sha2_60/12_256:
+        case xmssmt-shake_20/2_256:
+        case xmssmt-shake_20/4_256:
+        case xmssmt-shake_40/2_256:
+        case xmssmt-shake_40/4_256:
+        case xmssmt-shake_40/8_256:
+        case xmssmt-shake_60/3_256:
+        case xmssmt-shake_60/6_256:
+        case xmssmt-shake_60/12_256:
+          bytestring32 root_n32;
+
+        case xmssmt-sha2_20/2_512:
+        case xmssmt-sha2_20/4_512:
+        case xmssmt-sha2_40/2_512:
+        case xmssmt-sha2_40/4_512:
+        case xmssmt-sha2_40/8_512:
+
+
+
+Huelsing, et al.              Informational                    [Page 72]
+
+RFC 8391                          XMSS                          May 2018
+
+
+        case xmssmt-sha2_60/3_512:
+        case xmssmt-sha2_60/6_512:
+        case xmssmt-sha2_60/12_512:
+        case xmssmt-shake_20/2_512:
+        case xmssmt-shake_20/4_512:
+        case xmssmt-shake_40/2_512:
+        case xmssmt-shake_40/4_512:
+        case xmssmt-shake_40/8_512:
+        case xmssmt-shake_60/3_512:
+        case xmssmt-shake_60/6_512:
+        case xmssmt-shake_60/12_512:
+          bytestring64 root_n64;
+
+        default:
+          void;     /* error condition */
+      };
+
+      /* XMSS^MT public key structure */
+
+      struct xmssmt_public_key {
+        xmssmt_root root;  /* Root node */
+        seed SEED;  /* Seed for bitmasks */
+      };
+
+Acknowledgements
+
+   We would like to thank Johannes Braun, Peter Campbell, Florian
+   Caullery, Stephen Farrell, Scott Fluhrer, Burt Kaliski, Adam Langley,
+   Marcos Manzano, David McGrew, Rafael Misoczki, Sean Parkinson,
+   Sebastian Roland, and the Keccak team for their help and comments.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 73]
+
+RFC 8391                          XMSS                          May 2018
+
+
+Authors' Addresses
+
+   Andreas Huelsing
+   TU Eindhoven
+   P.O. Box 513
+   Eindhoven  5600 MB
+   The Netherlands
+
+   Email: ietf@huelsing.net
+
+
+   Denis Butin
+   TU Darmstadt
+   Hochschulstrasse 10
+   Darmstadt  64289
+   Germany
+
+   Email: dbutin@cdc.informatik.tu-darmstadt.de
+
+
+   Stefan-Lukas Gazdag
+   genua GmbH
+   Domagkstrasse 7
+   Kirchheim bei Muenchen  85551
+   Germany
+
+   Email: ietf@gazdag.de
+
+
+   Joost Rijneveld
+   Radboud University
+   Toernooiveld 212
+   Nijmegen  6525 EC
+   The Netherlands
+
+   Email: ietf@joostrijneveld.nl
+
+
+   Aziz Mohaisen
+   University of Central Florida
+   4000 Central Florida Blvd
+   Orlando, FL  32816
+   United States of America
+
+   Phone: +1 407 823-1294
+   Email: mohaisen@ieee.org
+
+
+
+
+
+Huelsing, et al.              Informational                    [Page 74]
+