Cryptography Reference
In-Depth Information
The parameters of XMSS are the following:
-
n
∈
N
, the security parameter,
-
w
∈
N
,w >
1, the Winternitz parameter,
-
m
, the message length in bits,
-
F
(
n
)=
∈
N
n
n
n
{
f
K
:
{
0
,
1
}
→{
0
,
1
}
|
K
∈{
0
,
1
}
}
a function family,
, the tree height, XMSS allows to make 2
H
-
H
∈
N
signatures using one
keypair,
-
h
K
, a hash function, chosen randomly with the uniform distribution from
the family
2
n
n
n
H
(
n
)=
{
h
K
:
{
0
,
1
}
→{
0
,
1
}
|
K
∈{
0
,
1
}
}
,
n
, chosen randomly with the uniform distribution. The string
x
is
used to construct the one-time verification keys.
-
x
∈{
0
,
1
}
Those parameters are publicly known.
We keep the following description of XMSS and its components short by
including references to more detailed descriptions. We write log for log
2
.
Winternitz OTS
As OTS we use the Winternitz OTS (W-OTS) first mentioned
in [24]. We use a slightly modified version proposed in [9]. For
K, x
n
∈{
0
,
1
}
we define
f
K
(
x
) as follows. We set
f
K
(
x
)=
K
and for
e>
0we
define
K
=
f
e−
K
(
x
)and
f
K
(
x
)=
f
K
(
x
). In contrast to previous versions of W-
OTS this is a (random) walk through the function family instead of an iterated
evaluation of a hash function. This modification allows to eliminate the need for
a collision resistant hash function family.
Also, define
1
=
m
log(
w
)
and
e
∈
N
,
2
=
log(
1
(
w
+1
,
−
1))
=
1
+
2
.
log(
w
)
The secret signature key of W-OTS consists of
n
-bit strings
sk
i
,1
≤
i
≤
chosen uniformly at random. The public verification key is computed as
pk
=(
pk
1
,...,
pk
)=(
f
w−
1
(
x
)
,...,f
w−
1
sk
(
x
))
,
sk
1
with
f
w−
1
as defined above.
W-OTS signs messages of binary length
m
. They are processed in base
w
representation. They are of the form
M
=(
M
1
...M
1
),
M
i
∈{
0
,...,w
−
1
}
.
The checksum
C
=
1
M
i
)inbase
w
representation is appended to
M
.Itisoflength
2
. The result is (
b
1
,...,b
). The signature of
M
is
i
=1
(
w
−
1
−
σ
=(
σ
1
,...,σ
)=(
f
b
1
(
x
)
,...,f
b
sk
(
x
))
.
sk
1
It is verified by constructing (
b
1
...,b
) and checking
?
=(
pk
1
,...,
pk
)
.
(
f
w−
1
−b
1
σ
1
(
pk
0
)
,...,f
w−
1
−b
(
pk
0
))
σ
The sizes of signature, public, and secret key are
n
. For more detailed informa-
tion see [9].
