Cryptography Reference
In-Depth Information
XMSS Tree
The XMSS tree is a modification of the Merkle Hash Tree proposed
in [14]. It utilizes the hash function
h
K
. The XMSS tree is a binary tree. Denote
its height by
H
.Ithas
H
+ 1 levels. The leaves are on level 0. The root is on level
H
. The nodes on level
j
,0
≤
i<
2
H−j
.The
≤
j
≤
H
, are denoted by
Node
i,j
,0
construction of the leaves is explained below. Level
j
,0
<j
≤
H
, is constructed
2
n
using a bitmask (
b
l,j
||
b
r,j
)
∈{
0
,
1
}
chosen uniformly at random. The nodes
are computed as
Node
i,j
=
h
K
((
Node
2
i,j−
1
⊕
b
l,j
)
||
(
Node
2
i
+1
,j−
1
⊕
b
r,j
))
for 0
<j
H
. The usage of the bitmasks is the main difference to the other
Merkle tree constructions. It is borrowed from [5] and allows to replace the
collision resistant hash function family. Figure 1 shows the construction of the
XMSS tree.
≤
N
ODE
i,j
j = H
h
b
r,j
b
l,j
XOR
XOR
N
ODE
2
i,j-1
N
ODE
2
i+1,j-1
j =
0
Fig. 1.
TheXMSStreeconstruction
We explain the computation of the leaves of the XMSS tree. The XMSS tree
is used to authenticate 2
H
W-OTS verification keys, each of which is used to
construct one leaf of the XMSS tree. The construction of the keys is explained at
the end of this section. In the construction of a leaf another XMSS tree is used. It
is called L-tree. The first
leaves of an L-tree are the
bit strings (
pk
0
,...,
pk
)
from the corresponding verification key. As
might not be a power of 2 there
are not suciently many leaves. Therefore the construction is modified. A node
that has no right sibling is lifted to a higher level of the L-tree until it becomes
the right sibling of another node. In this construction, the same hash function as
above but new bitmasks are used. The bitmasks are the same for each of those
trees. As L-trees have height
bitmasks are required.
The XMSS public key PK contains the bitmasks and the root of the XMSS tree.
To sign the
i
th message, the
i
ith W-OTS key pair is used. The signature
SIG
=
(
i, σ,
Auth
) contains the index
i
, the W-OTS signature
σ
, and the authentica-
tion path for the leaf
Node
0
,i
. It is the sequence
Auth
=(
Auth
0
,...,
Auth
H−
1
)
of the siblings of all nodes on the path from
Node
0
,i
to the root. Figure 2 shows
log
, additional
log
