Cryptography Reference
In-Depth Information
H
(
u
i
) values. Let
L
∗
Let
L
=
((
u
1
,
h
1
)
,...,
(
u
n
,
h
n
)) be the list of all known
h
i
=
be the event that
h
i
=
H
(
u
i
) for
i
=
1
,...,
n
for the random oracle
H
. Obviously
L
∗
] when we query
H
with
u
in the simulator. It is not
Pr[output
h
|
L
]
=
Pr[
H
(
u
)
=
h
|
more difficult to realize that
L
∗
]
Pr[output (
h
,
r
,
s
)
|
L
]
=
Pr[Sig(
M
)
=
(
r
,
s
) and
H
(
r
||
M
)
=
h
|
(assuming that no
u
i
is equal to
r
M
) when we query Sig with
M
in the simulator.
Therefore we deduce that except when the simulator aborts, it perfectly simulates the
two oracles. Since
r
is generated with probability up to
||
O
(
/
q
), the
r
||
M
is equal to some
u
i
with probability up to
O
(
n
(log
q
)
q
). The cases which are not simulated thus happen
with probability less than
O
(
Q
2
(log
q
)
/
q
), which can be neglected. We conclude this
first step of our proof by saying that the adversary
/
A
running with the simulator will
O
(
Q
2
(log
q
)
output a valid (
M
,
h
,
r
,
s
) quadruplet with probability at least
ε
−
/
q
). By
Q
2
(log
q
)
assuming that
ε
/
q
we can simply say that it succeeds with probability at
least
ε
.
The second step is known as the “forking lemma.” We assume that every time the
simulator for
H
wishes to pick a random value, it sequentially reads it from a tape
ρ
which is set up at the beginning. What we will do is run
A
with the simulator several
times with some modified tape. More precisely, we re-run
with a tape which starts
by the same numbers, but whose content has been overwritten starting from the value
which is read at some crucial point. Indeed, for any initial random tape
A
ρ
which leads to
a valid forgery, there is one crucial moment in the simulator when
r
M
was a query to
the
H
oracle. (Note that it cannot come from the query to the signing oracle, otherwise
it would mean that
M
was queried to this oracle, which is forbidden.) We number the
oracle calls from 1 to
Q
. Given a random tape
||
ρ
, for any
i
we let
ρ
i
be the prefix of
ρ
which consists of all values which have been used before the
i
-th query. We let
c
(
ρ
)
be the number of the oracle call when
r
||
M
is queried to
H
. We let dist(
ρ
)be
ρ
c
(
ρ
)
.
||
ρ
where
ρ
is a new random sequence.
We intend to re-run
A
with a new tape dist(
ρ
)
Given a tape
ρ
we let succ(
ρ
) be the event that
A
succeeds when initialized with
ρ
,
and succ
c
(
ρ
) be the event that both succ(
ρ
) and
c
(
ρ
)
=
c
occur. Note that cutting all
possible
sequences at the oracle query times leads to a tree structure of depth
Q
.
Given a truncated random tape
ρ
ν
, we can consider the probability
f
(
ν
) that a random
ρ
=
ν
||
ρ
leads to a successful run such that dist(
tape
ρ
)
=
ν
. By using Lemma 10.3
we show that
f
(dist(
)
2
Q
1
2
.
Pr
ρ
ρ
))
>
succ(
ρ
≥
In other words,
Pr
ρ
)
succ
c
(
ρ
)
(dist(
||
ρ
)
>
2
Q
1
2
.
Pr
ρ
ρ
)
succ(
ρ
≥
Search WWH ::
Custom Search