RFC 8391
XMSS: eXtended Merkle Signature Scheme
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
(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.
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.
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.
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.
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.
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
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.
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
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.
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.
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
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.
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
(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.
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.
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.
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.
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;
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);
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.
(page 40 continued on part 3)
