Cryptography Reference
In-Depth Information
For one call to the XMSS signature verification algorithm, the number of calls
to
H
(
n
)and
F
(
n
) is bounded by
#
call
H
≤
H
+
,
#
call
F
≤
w.
For one call to the XMSS key generation algorithm, the number of calls to
H
(
n
)
and
F
(
n
) is bounded by
2
H
(
+1)
,
2
H
(2 +
(
w
+1))
.
#
call
H
≤
#
call
F
≤
The space requirements for the internal state of
Sign
and
Kg
(including
sk
)
are at most 6
H
∗
n
bits.
Vf
needs no internal state. Hence, the space used by
XMSS is at most 6
H
∗
n
bits.
6
Implementation
We have implemented XMSS to evaluate its practical performance. The im-
plementation was done in C, using the AES and SHA-2 implementation of
OpenSSL
1
. The implementation is straightforward, except for the construction of
H
(
n
)and
F
(
n
) for which we implemented constructions based on hash functions
and block ciphers.
First we discuss the hash function based constructions. In our implementation
any hash function from the OpenSSL library can be used that uses the Merkle-
Darmgard (M-D) construction [25]. The family
F
(
n
) is constructed as follows.
Given a hash function
Hash
with block length
b
and output size
n
that uses
the M-D construction we build the function family
F
(
n
)as
f
K
(
M
)=
Hash
(
Pad
(
K
)
||
Pad
(
M
))
,
n
, message
M
n
10
b−|x|−
1
)for
for key
K
∈{
0
,
1
}
∈{
0
,
1
}
and
Pad
(
x
)=(
x
||
|
<b
.
We show that this is a pseudorandom function family if
Hash
is a good cryp-
tographic hash function. In [2] it is assumed, that the compression function of
a good M-D hash function is a pseudorandom function family if keyed using
the input. In [3], it is assumed, that the compression function of a good M-D
hash function is a pseudorandom function family if keyed on the chaining input.
Further it is shown, that a fixed input length M-D hash function, keyed using
the initialization vector (IV) is a pseudorandom function family for fixed length
inputs. In our construction the internal compression function of
hash
is evalu-
ated twice: First on the IV and the padded key, second on the resulting chaining
value and the padded message. Due to the pseudorandomness of the compres-
sion function when keyed on the message input, the first evaluation works as
a pseudorandom key generation. As we have a fixed message length the second
iteration is a pseudorandom function family keyed using the IV input.
x
|
1
http://www.openssl.org/
