Cryptography Reference
In-Depth Information
function family
F
(
n
). Denote by
Dss
the modification of
Dss
, that is obtained
by choosing the
λn
bits randomly. Denote by InSec
eu-cma
(
Dss
;
t, q
)themaxi-
mum success probability over all adversaries running in time
t
and making at
most
q
Sign
oracle queries in the
EU-CMA
experiment. InSec
eu-cma
(
Dss
;
t, q
)is
defined analogously. Also, define by InSec
prf
(
F
(
n
);
t, q
) the maximum success
probability over all adversaries in distinguishing a random element from
F
(
n
)
from a random function, when the runtime is bounded by
t
andshecanquery
an oracle for up to
q
function values. Then the following is true
InSec
eu-cma
(
Dss
;
t, q
) = InSec
prf
(
F
(
n
); (
t
+
λ
)
,λ
)
+InSec
eu-cma
(
Dss
;
t, q
)
≤
t
=
t
+
t
Kg
+
q
t
Sign
+
t
Vf
.
This is shown by contradiction. Assume there exists an adversary
A
returning
a valid forgery for
Dss
with success probability
Succ
eu-cma
(
Dss
;
A
)
>
InSec
eu-cma
(
Dss
;
t, q
)
in time
t
. We build a distinguisher
Dis
for
F
(
n
) that runs
A
and outputs 1, if
A
returns a valid forgery. Then we show that either
Dis
can distinguish
F
(
n
)with
success probability
Succ
prf
(
F
(
n
);
Dis
)
>
InSec
prf
(
F
;
t
,q
)
or
A
is a forger for
Dss
with success probability
Succ
eu-cma
(
Dss
;
A
)
>
InSec
eu-cma
(
Dss
;
t, q
)
.
Both lead to a contradiction of the initial assumptions.
Applying this result to W-OTS shows that W-OTS as used in the XMSS con-
struction is
EU-CMA
-secure if
F
(
n
) is pseudorandom. Together with the as-
sumption that
(
n
) is second preimage resistant it follows from [14] that XMSS
is
EU-CMA
-secure if the seeds for the W-OTS signature keys are chosen at ran-
dom. Finally, applying the above result again, we obtain the following formula
which is an exact version of Theorem 1 and therefore concludes the proof.
Denote by InSec
spr
(
H
H
(
n
);
t
) the maximum success probability over all adver-
saries running in time
(
n
). Furthermore,
denote the number of key collisions of
F
(
n
)by
κ
according to [9]. Then the
maximum success probability over all adversaries running in time
≤
t
for finding a second preimage in
H
t
,making
at most 2
H
oracle queries, against the XMSS
EU-CMA
security is bounded by
InSec
eu-cma
XMSS
;
t, q
=2
H
≤
≤
InSec
prf
F
(
n
); (
t
+2
H
)
,q
=2
H
⎧
⎨
⎫
⎬
InSec
spr
(
(2
H
+log
(
n
);
t
)
,
−
1)
·
H
2
H
InSec
prf
(
F
(
n
); (
t
+
)
,q
=
)
+2
·
max
InSec
prf
(
F
(
n
); (
t
)
,q
=2)
⎩
⎭
+(
2
w
2
κ
w−
1
1
(
κ
−
2
n
)
)
·
where
t
=
t
+2
H
·
t
Sign
+
t
Vf
+
t
Kg
.