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 .
 
Search WWH ::




Custom Search