Cryptography Reference
In-Depth Information
probability of
I
on pre-images out of
S
n
. On the other hand, the probability that
all
U
(
i
n
's reside in
S
n
is small. Specifically, we define
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
∧
∃
S
n
s
1
(
n
)
def
i
s.t.
U
(
i
)
n
=
Pr
∈
and
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
∧
∀
i
:
U
(
i
)
∈
S
n
s
2
(
n
)
def
=
Pr
n
+
s
2
(
n
) (as the events considered in the
s
i
's are disjoint).
We derive a contradiction to the lower bound on
s
(
n
) (given in Eq. (2.7)) by
presenting upper bounds for both
s
1
(
n
) and
s
2
(
n
) (which sum up to less).
First, we present an upper bound on
s
1
(
n
). The key observation is that algorithm
I
inverts
f
on input
f
(
x
) with probability that is related to the success of
B
to
invert
g
on a sequence of random
f
-images containing
f
(
x
). Specifically, for
every
x
=
s
1
(
n
)
Clearly,
s
(
n
)
p
(
n
), the probability that
I
inverts
f
on
f
(
x
) is greater than or equal to the probability that
B
inverts
g
on
g
(
U
n
2
p
(
n
)
)
conditioned on
U
(
i
)
n
∈{
0
,
1
}
n
and every 1
≤
i
≤
n
·
x
(since any success of
B
to invert
g
means that
f
was
inverted on the
i
th block, and thus contributes to the success probability of
I
). It
follows that, for every
x
=
n
∈{
0
,
1
}
and every 1
≤
i
≤
n
·
p
(
n
),
Pr
[
I
(
f
(
x
))
∈
f
−
1
(
f
(
x
))]
≥
Pr
B
g
U
n
2
p
(
n
)
g
−
1
g
U
n
2
p
(
n
)
U
(
i
)
x
∈
=
(2.8)
n
Since for
x
∈
S
n
the left-hand side (l.h.s.) cannot be large, we shall show that (the
r.h.s. and so)
s
1
(
n
) cannot be large. Specifically, using Eq. (2.8), it follows that
∃
i
s.t.
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
∧
U
(
i
)
∈
S
n
s
1
(
n
)
=
Pr
n
n
·
p
(
n
)
i
=
1
Pr
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
∧
U
(
i
)
∈
S
n
≤
n
n
·
p
(
n
)
x
∈
S
n
Pr
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
∧
U
(
i
)
=
x
≤
n
i
=
1
n
·
p
(
n
)
x
∈
S
n
Pr
U
(
i
)
n
=
x
·
Pr
B
g
U
n
2
p
(
n
)
∈
g
−
1
g
U
n
2
p
(
n
)
U
(
i
)
=
x
=
n
i
=
1
n
·
p
(
n
)
x
∈
S
n
B
g
U
n
2
p
(
n
)
g
−
1
g
U
n
2
p
(
n
)
U
(
i
)
x
≤
max
Pr
∈
=
n
i
=
1
n
·
p
(
n
)
S
n
{
Pr
[
I
(
f
(
x
))
∈
f
−
1
(
f
(
x
))]
}
≤
max
x
∈
i
=
1
n
2
·
p
(
n
)
a
(
n
)
n
a
(
n
)
=
≤
n
·
p
(
n
)
·
(The last inequality uses the definition of
S
n
, and the one before it uses Eq. (2.8).)
47
