Cryptography Reference
In-Depth Information
of pairs, and
H
n
(
X
n
)
H
n
∈
B
def
=
Pr
δ
,
Then
U
k
,
H
n
∈
B
>
δ
4
Pr
O
(
k
)
Using the definition of
A
and applying Claim 3.5.9.1 to Eq. (3.14), it follows
that the probability that
A
inverts
f
on
y
equals
(
y
)
4
(
y
)
4
O
(
n
)
A
y
H
n
∈
F
−
1
y
H
n
>
δ
O
(
k
)
>
δ
Pr
,
U
k
,
,
U
k
,
(3.15)
Thus,
Pr
[
A
(
f
(
U
n
))
∈
f
−
1
(
f
(
U
n
))]
f
−
1
(
f
(
U
n
))
δ
A
(
f
(
U
n
))
>
ε
(
n
)
2
>
ε
(
n
)
2
≥
Pr
δ
(
f
(
U
n
))
·
Pr
∈
(
f
(
U
n
))
2)
4
O
(
n
)
We reach a contradiction (to the hypothesis that
f
is strongly one-way), and the
proposition follows.
5
All that is left is to prove Claim 3.5.9.1. The proof, which
follows, is rather technical.
>
ε
ε
/
(
n
)
2
·
(
(
y
)
We stress that the fact that
m
(
n
) can be computed from
n
does not play an essential
role in the reducibility argument (as it is possible to try all possible values of
m
(
n
)).
Claim 3.5.9.1 is of interest for its own sake. However, its proof provides no significant
insights and can be skipped without significant damage (especially by readers who are
more interested in cryptography than in “probabilistic analysis”).
Proof of Claim 3.5.9.1:
We first use Lemma 3.5.1 to show that only a “tiny” fraction
of the hashing functions in
S
n
can map a “large” probability mass into “small” subsets.
Once this is done, the claim is proved by dismissing those few bad functions and relating
the two probabilities, appearing in the statement of the claim, conditioned on the function
not being bad. Details follow.
We begin by bounding the fraction of the hashing functions that map a “large” prob-
ability mass into “small” subsets. We say that a function
h
S
n
is (
T
∈
,
)
-expanding
if
k
of cardinality
2
k
such that
there exists a set
R
⊂{
,
}
·
Pr
∈
R
]
≥
(
T
+
·
0
1
[
h
(
X
n
)
1)
.
5
In case
f
is weakly one-way, the argument is slightly modified. Specifically, suppose that for some positive
polynomial, any probabilistic polynomial-time algorithm that tries to invert
f
on
f
(
U
n
) fails with probability at
least 1
/
p
(
n
). We claim that any probabilistic polynomial-time algorithm that tries to invert
F
on
F
(
U
n
,
H
n
) fails
with probability at least 1
4
p
(
n
). Suppose, toward the contradiction, that there exists a probabilistic polynomial-
time algorithm that inverts
F
on
F
(
U
n
,
H
n
) with probability at least 1
−
ε
(
n
), where
ε
(
n
)
≤
1
/
4
p
(
n
). Then, for
δ
/
1
2
p
(
n
)
(
·
), as before, it holds that
E
[
δ
(
f
(
U
n
))]
=
1
−
ε
(
n
), and
Pr
[
δ
(
f
(
U
n
))
≥
1
−
2
p
(
n
)
ε
(
n
)]
≥
1
−
follows.
1
2
p
(
n
)
fraction of the
n
-bit-long strings
x
, it holds that
Using
ε
(
n
)
≤
1
/
4
p
(
n
), we infer that for at least a 1
−
1
2
. Applying Claim 3.5.9.1, it follows that (for these
x
's) the probability that
A
inverts
f
on
f
(
x
)
δ
(
f
(
x
))
≥
n
). Considering an algorithm that iterates
A
for
O
(
n
2
) times, we obtain a probabilistic polynomial-
time algorithm that inverts
f
on
f
(
U
n
) with success probability at least (1
−
is
(1
/
1
2
p
(
n
)
)
·
(1
−
2
−
n
)
>
1
−
1
p
(
n
)
,in
contradiction to our hypothesis concerning
f
.
