Cryptography Reference
In-Depth Information
3S cu y
In this section we discuss the security of XMSS. We use the notations of Section
2 and sketch the proof of the following theorem.
Theorem 1.
(
n
)
is a second preimage resistant hash function family and
F
(
n
)
a pseudorandom function family, then XMSS is existentially unforgeable
under chosen message attacks.
Before sketching the proof of Theorem 1 we show that it implies the minimality of
the security requirements of XMSS. For this purpose, we show how to construct
second preimage resistant hash function families and pseudorandom function fam-
ilies from secure signature schemes. Those constructions imply that there is a se-
cure instance of XMSS if there is a secure signature scheme. This implies that the
security requirements for XMSS are minimal. Now we present the constructions.
In [27] it is shown that a one-way function can be constructed from any secure
signature scheme. Also the construction of a target collision resistant hash func-
tion family from a one-way function is presented. Since target collision resistant
hash function families are second preimage resistant (see [26]), this implies that
second preimage resistant hash function families can be constructed from secure
digital signature schemes. In [19] the construction of a pseudorandom generator
from a one-way function is presented. In [17] pseudorandom function families
are obtained from pseudorandom generators. It follows that secure signature
schemes yield pseudorandom function families.
Next, we sketch the proof of Theorem 1. First the notion of existentially
unforgeability under chosen message attacks (
EU-CMA
) [18] has to be adapted
to the given setting. XMSS is a signature scheme where the private signature
key is not constant as in RSA, but changes over time, whereas the definition of
EU-CMA
assumes a constant signature key. The definition of
EU-CMA
security
can be described by an experiment, where the adversary has access to a signature
oracle, initialized with the constant signature key. The adversary is allowed to
send messages to the oracle. The oracle returns the corresponding signatures
under the secret signature key. At the end of the experiment, the adversary has
to come up with a signature for a message she did not send to the oracle before.
For one-time signature schemes like W-OTS the number of queries is limited to
one. In the XMSS-experiment the adversary is given access to an XMSS oracle
which changes the secret signature key after each signature according to the
XMSS construction. The adversary may query this oracle 2
H
times.
The proof of Theorem 1 proceeds in two steps. First, it is shown that W-OTS,
which is known to be
EU-CMA
-secure from [9] remains
EU-CMA
secure in the
XMSS construction, where the secret key is generated using a pseudorandom
function family.
Second, we modify the security proof in [14]. This is necessary since in contrast
to the signature scheme in [14] XMSS generates its signature keys pseudoran-
domly.
In fact, both steps use the following result. Denote by
Dss
one of the signature
schemes XMSS and W-OTS. In both schemes the key generation algorithm uses
n
bits of random input and expands them to the
λn
bits using the pseudorandom
If
H
