Cryptography Reference
In-Depth Information
Note that, assuming only generic attacks on
H
(
n
)and
F
(
n
) the symmetric
bit security of XMSS is
b
=log
t
InSec
EU-CMA
(
XMSS
;
t, q
=2
H
)
≤
min
{
n
−
1
,n
−
H
−
2
−
w
−
2 log(
w
)
}−
1
4
Forward Security
Given the above result we can go even further. In [1] Anderson introduced the
idea of forward security for signature schemes (
FSSIG
) which was later formal-
ized in [4]. It says that even after a key compromise all signatures created before
remain valid. Obviously, this notion is only meaningful for signature schemes
that change their secret signature key over time. From an attack based point of
view this translates to: If an attacker learns the actual secret key
sk
i
, she is still
not able to forge a signature under a secret key
sk
j
,
j<i
. This is a desirable
property, especially in the context of long term secure signatures, as it allows to
remove the need for timestamps and an online trusted third party.
In this section we show that XMSS is forward secure if we slightly modify
the key generation process based on an idea from [22]. We describe the modi-
fications. To make XMSS forward secure we use a forward secure PRG
FsGen
when generating the seeds for the W-OTS secret keys. A forward secure PRG is
a stateful PRG that starts from a random initial state. Given a state, it outputs
a new state and some output bits. Even if an adversary manages to learn the
secret state of a forward secure PRG, she is not able to distinguish the former
outputs from random bit strings. In the modified XMSS, the W-OTS seeds are
generated by
FsGen
. Starting from a random input
Seed
=
State
0
of length
n
,
FsGen
uses
F
(
n
) and the previous state
State
i−
1
to generate
n
bits of pseudo-
random output
Out
i
and a new state
State
i
of length
n
:
(
State
i
||
Out
i
)=(
f
State
i−
1
(0)
||
f
State
i−
1
(1))
The generation of the W-OTS secret keys from the seeds still utilizes
GEN
.
The secret key of the resulting forward secure XMSS contains the actual state
State
i
instead of
Seed
. In contrast to the construction from Section 2, the
seeds for the W-OTS signature keys are not easily accessible from
State
i
using
one evaluation of
F
(
n
). To compute the authentication path, the tree traversal
algorithm needs to compute several W-OTS keys before they are needed. This
is very expensive using
FsGen
. This problem is already addressed in [11]. We use
their solution that requires to store 2
H
states of
FsGen
. This results in a secret
signature key size of 2
Hn
.
For this modified XMSS we proof the following security theorem.
Theorem 2.
(
n
)
is a second preimage resistant hash function family and
F
(
n
)
a pseudorandom function family, then XMSS with a modified key genera-
tion described below is a forward secure digital signature scheme.
If
H
