Cryptography Reference
In-Depth Information
one-way function, then
F
is “hard to invert.” Furthermore, if
l
(
·
) is logarithmic, then
F
is “almost 1-1.”
Proposition 3.5.9:
Let f , m, l, and F be as in Construction 3.5.8. Suppose that
there exists an algorithm that on input n computes m
(
n
)
in
poly(
n
)
time. Then:
1.
F
is “almost” 1-1:
Pr
F
−
1
F
U
n
,
>
2
l
(
n
)
+
1
<
O
n
2
−
l
(
n
)
/
4
H
m
(
n
)
−
l
(
n
)
n
·
(Recall that
H
n
denotes a random variable uniformly distributed over
S
n
.)
2.
F
“preserves” the one-wayness of
f
:
If f is strongly (resp., weakly) one-way, then so is F .
Proof Sketch:
Part 1 is proved by applying Lemma 3.5.1, using the hypothe-
sis that
S
m
(
n
)
−
l
(
n
)
n
is a hashing family. Specifically, Lemma 3.5.1 implies that for
every
α
and all but a 2
−
l
(
n
)
fraction of
h
∈
S
m
(
n
)
−
l
(
n
)
n
Pr
, it holds that
[
h
(
U
n
)
=
α
]
≤
2
−
m
(
n
)
+
l
(
n
)
+
1
. Thus, for every
α
, it holds that
Pr
[
|
F
−
1
(
α,
H
m
(
n
)
−
l
(
n
)
n
)
|
>
2
l
(
n
)
+
1
]
<
def
={
2
−
l
(
n
)
.
Letting
B
(
α,
h
):
|
F
−
1
(
α,
h
)
|
>
2
l
(
n
)
+
1
}
,wehave
Pr
[(
U
m
(
n
)
−
l
(
n
)
,
H
m
(
n
)
−
l
(
n
)
n
)
∈
B
]
<
2
−
l
(
n
)
. Using Claim 3.5.9.1 (given later), it follows that
2
−
l
(
n
)
)
1
/
4
, as required in Part 1.
Part 2 is proved using a reducibility argument. Assuming, to the contradiction,
that there exists an efficient algorithm
A
that inverts
F
with unallowable success
probability, we construct an efficient algorithm
A
that inverts
f
with unallowable
success probability (reaching contradiction). For the sake of concreteness, we
consider the case in which
f
is strongly one-way and assume, to the contradiction,
that algorithm
A
inverts
F
on
F
(
U
n
,
H
m
(
n
)
−
l
(
n
)
[(
H
m
(
n
)
−
l
(
n
)
n
H
m
(
n
)
−
l
(
n
)
n
Pr
(
U
n
)
,
)
∈
B
]
<
O
(
m
(
n
)
·
) with success probability
ε
(
n
)
,
such
n
poly(
n
)
for infinitely many
n
's. Following is a description of
A
.
On input
y
(supposedly in the range of
f
(
U
n
)), algorithm
A
selects uniformly
h
∈
S
m
(
n
)
−
l
(
n
)
n
1
that
ε
(
n
)
>
m
(
n
)
−
l
(
n
)
and initiates
A
on input (
y
,α,
h
). Algorithm
A
sets
x
to be the
n
-bit-long prefix of
A
(
y
,α,
h
) and outputs
x
.
Clearly, algorithm
A
runs in polynomial time. We now evaluate the success
probability of
A
. For every possible input
y
to algorithm
A
, we consider a
random variable
X
n
uniformly distributed in
f
−
1
(
y
) (i.e.,
and
α
∈{
0
,
1
}
Pr
[
X
n
=
α
=
2
−
m
(
n
)
]
if
α
∈
f
−
1
(
y
), and
Pr
[
X
n
=
α
]
=
0 otherwise). Let
δ
(
y
) denote the success
def
=|
H
n
(
X
n
)
H
n
), where
n
probability of algorithm
A
on input (
y
,
,
y
|
and
def
=
m
(
n
)
k
−
l
(
n
). That is,
A
y
H
n
∈
F
−
1
y
H
n
(
y
)
def
H
n
(
X
n
)
H
n
(
X
n
)
δ
=
Pr
,
,
,
,
(3.14)
By the contradiction hypothesis (and the definition of
δ
(
y
)), it holds that
E
[
δ
(
f
(
U
n
))
>
ε
(
n
2
]
>
ε
(
n
)
Pr
[
δ
(
f
(
U
n
))]
=
ε
(
n
), and
follows. We fix an arbitrary
2
such that
δ
(
y
)
>
ε
(
n
2
. We prove the following technical claim.
y
∈{
0
,
1
}
n
n
Claim 3.5.9.1:
Let
k
≤
n
be natural numbers, and let
X
n
∈{
0
,
1
}
be a random
Pr
[
X
n
=
x
]
≤
2
−
k
n
. Suppose that
B
is a set
variable satisfying
for all
x
∈{
0
,
1
}
