Cryptography Reference
In-Depth Information
||
ρ
This means that if we pick a successful
ρ
, there is a very high chance that dist(
ρ
)
2
Q
. Starting from such
succeeds on the same crucial oracle call with probability at least
2
Q
ε
ρ
, and the probability to get at least one dist(
||
ρ
a
ρ
, we can try
log
values of
ρ
)
||
ρ
) is at least 1
1
tape such that succ
c
(
ρ
)
(dist(
ρ
)
−
. So if we iterate
times, we obtain
tapes with the same crucial oracle call and the same prefix tape with probability at
least
e
−
1
. To recapitulate, the algorithm works as follows.
1: Pick a random tape
ρ
until
A
succeeds
2:
for
i
=
1to
do
2
Q
ε
ρ
until dist (
||
ρ
succeeds and
c
(dist(
||
ρ
)
3:
try
log
values
ρ
)
ρ
)
=
c
(
ρ
)
(if this does not work the algorithm fails)
4:
end for
5: yield the (
M
ρ
,
h
,
r
,
s
) quadruplets corresponding to the
found values
This algorithm succeeds with a constant probability and yields
quadruplets. We
notice that the crucial oracle call is the one where
r
||
M
is queried to
H
,soall
quadruplets have the same
r
and
M
.Sowehave
quadruplets (
M
,
h
i
,
r
,
s
i
) such
g
mod
p
mod
q
.
h
i
s
i
r
s
i
mod
q
y
mod
q
that
r
=
(
g
k
The third step uses the fact that
k
→
mod
p
) mod
q
has no preimage set of
size
. This implies that we must have
h
i
+
xr
h
j
+
xr
≡
(mod
q
)
s
i
s
j
for some 1
≤
i
<
j
≤
. This leads to
h
i
s
j
−
h
j
s
i
x
=
mod
q
.
r
(
s
i
−
s
j
)
We can try all combinations of (
i
,
j
) until this formula gives
x
.
Lemma 10.3.
We consider a finite tree and a mapping
dist
which maps any leaf
λ
to
one of its ancestors
dist(
)
. We call it a distinguished ancestor. We assume we are given
a distribution which defines a random descent from the root of the tree to a random
leaf
λ
λ
.Welet
visit(
ν
)
be the event that the descent goes through
ν
,
i.e
. that
ν
is an
ancestor of
λ
.Welet
succ(
λ
)
be an event related to a leaf
λ
of the tree. When it occurs
)]
and d
we say that
λ
is successful. We let p
=
Pr[succ(
λ
=
E
(depth(
λ
))
for a random
leaf
λ
. Finally, we let f
(
ν
)
=
Pr[succ(
λ
) and dist(
λ
)
=
ν
|
visit(
ν
)]
. For any real number
θ>
0
, we have
f
(dist(
)
)
p
d
λ
>
−
θ
λ
≥
θ.
Pr
λ
))
(1
succ(
Search WWH ::
Custom Search