Cryptography Reference
In-Depth Information
j=H
j=
0
i
Fig. 2.
The authentication path for leaf
i
the authentication path for leaf
i
. To compute the authentication path we use
the tree traversal algorithm from [11] as it allows for optimal balanced runtimes
using very little memory.
To verify the signature
SIG
=(
i, σ,
Auth
), the string (
b
0
,...,b
) is computed
as described in the W-OTS signature generation. Then the
i
ith verification key
is computed using the formula
(
pk
1
,...,
pk
)=(
f
w−
1
−b
1
(
x
)
,...,f
w−
1
−b
σ
(
x
))
.
σ
1
The corresponding leaf
Node
0
,i
oftheXMSStreeisconstructed using the L-tree.
This leaf and the authentication path are used to compute the path (
p
0
,...,p
H
)
to the root of the XMSS tree, where
p
0
=
Node
0
,i
and
p
j
=
h
K
((
p
j−
1
⊕
if
i/
2
j
≡
b
l,j
)
||
(
Auth
j−
1
⊕
b
r,j
))
,
0mod2
if
i/
2
j
≡
h
K
((
Auth
j−
1
⊕
b
l,j
)
||
(
p
j−
1
⊕
b
r,j
))
,
1mod2
for 0
H
.If
p
H
is equal to the root of the XMSS tree in the public key, the
signature is accepted. Otherwise, it is rejected.
≤
j
≤
Signature key generation
The W-OTS secret signature keys are computed us-
n
, the pseudorandom function family
F
(
n
), and the
pseudorandom generator
GEN
which for
λ, μ
ingaseed
Seed
∈{
0
,
1
}
n
yields
∈{
0
,
1
}
GEN
λ
(
μ
)=
f
μ
(1)
||
...
||
f
μ
(
λ
)
.
1
,...,
2
H
For
i
∈{
}
the
i
i-th W-OTS signature key is
sk
i
←
GEN
(
f
Seed
(
i
))
.
The XMSS secret key contains
Seed
and the index of the last signature
i
.
The bit length of the XMSS public key is (2(
H
+
)+1)
n
,anXMSSsig-
nature has length (
+
H
)
n
, and the length of the XMSS secret signature key is
<
2
n
.
log
