Cryptography Reference
In-Depth Information
z
)
def
z
)
def
where EQ(
r
,
={
S
∈
C
:
r
≡
S
z
}
and NE(
r
,
={
S
∈
C
:
r
≡
S
z
}
. Observe
that for every
r
=
z
, it holds that
|
NE(
r
,
z
)
|=
2
l
−
1
(and
|
EQ(
r
,
z
)
|=
2
l
−
1
−
1).
On the other hand, EQ(
z
,
z
)
=
C
(and NE(
z
,
z
)
=∅
) holds for every
z
. Hence,
we get
1
2
+
1
((2
l
−
1
2
l
−
1
s
(
x
)
=
−
1)
·
Pr
[
(
r
)
=
1]
−
·
Pr
[
(
r
)
=
1])
|
C
|
2
l
r
=
h
(
x
)
1
+
|
C
|
·|
C
|·
Pr
[
(
h
(
x
))
=
1]
2
l
1
|
C
|
−
1
2
−
1
1
=
h
(
x
)
Pr
[
(
r
)
=
1]
+
·
Pr
[
(
h
(
x
))
=
1]
|
C
|
|
C
|
2
l
2
l
r
=
where the last equality uses
|
C
|=
2
l
1
2
l
1
1
−
1 (i.e.,
=
|
C
|
−
). Rearranging the
2
l
|
C
|
terms and substituting for
,weget
r
Pr
1
2
+
1
|
C
|
·
Pr
1
s
(
x
)
=
[
(
h
(
x
))
=
1]
−
[
(
r
)
=
1]
2
l
|
C
|
1
2
+
1
|
C
|
·
Pr
−
Pr
=
(
[
D
(
f
(
x
)
,
h
(
x
))
=
1]
[
D
(
f
(
x
)
,
R
l
)
=
1])
Finally, taking the expectation over the
x
's,weget
1
2
+
1
|
C
|
·
E
[
s
(
X
n
)]
=
(
Pr
[
D
(
f
(
X
n
)
,
h
(
X
n
))
=
1]
−
Pr
[
D
(
f
(
X
n
)
,
R
l
)
=
1])
1
2
+
1
=
−
1
·
(
p
−
q
)
2
l
and the lemma follows.
2.6.
∗
Efficient Amplification of One-Way Functions
The
amplification
of weak one-way functions into strong ones, presented in
Theorem 2.3.2, has no practical value. Recall that this amplification transforms a func-
tion
f
that is hard to invert on a noticeable fraction (i.e.,
1
p
(
n
)
) of the strings of length
n
into a function
g
that is hard to invert on all but a negligible fraction of the strings
of length
n
2
p
(
n
). Specifically, it is shown that an algorithm running in time
T
(
n
) that
inverts
g
on a
ε
(
n
) fraction of the strings of length
n
2
p
(
n
) yields an algorithm running
in time poly(
p
(
n
)
,
n
,
1
1
p
(
n
)
fraction of the strings of
length
n
. Hence, if
f is hard to invert in practice on 1% of the strings of length 1000,
then all we can say is that
g is hard to invert in practice on almost all strings of length
100,000,000
. In contrast, an efficient amplification of one-way functions, as given later,
should relate the difficulty of inverting the (weak one-way) function
f
on strings of
length
n
to the difficulty of inverting the (strong one-way) function
g
on the strings
of length
O
(
n
), rather than relating it to the difficulty of inverting the function
g
on
the strings of length poly(
n
). Consequently, we may get assertions such as this: If
fis
ε
(
n
)
)
·
T
(
n
) that inverts
f
ona1
−
