Cryptography Reference
In-Depth Information
def
=
and pairwise independence of the
r
J
's follows. Let
m
2
l
−
1, and let
ζ
represent
a generic
ζ
J
(which are all identically distributed). Using Chebyshev's inequality
(and
m
≥
2
n
·
p
(
n
)
2
), we get
J
ζ
2
·
m
·
m
≥
2
p
(
n
)
·
m
1
2
+
J
ζ
1
1
2
p
(
n
)
1
Pr
J
≤
Pr
J
≤
−
m
·
Var
[
ζ
]
≤
1
2
p
(
n
)
m
2
·
Var
[
ζ
]
=
1
2
p
(
n
)
2
·
(2
n
·
p
(
n
)
2
)
1
4
<
1
2
p
(
n
)
2
·
(2
n
·
p
(
n
)
2
)
1
2
n
=
The claim follows.
=⊕
j
∈
J
b
(
x
,
s
j
)
=
b
(
x
,
r
J
) for all non-empty
J
's. In this case, with probability at least
j
=
b
(
x
,
s
j
) for all
j
's, then
ρ
J
j
Recall that if
σ
=⊕
j
∈
J
σ
1
2
, the string
j
=
b
(
x
,
s
j
)
z
output by algorithm
A
equals
x
. However, the first event (i.e.,
σ
for all
j
's) happens with probability 2
−
l
1
2
n
·
p
(
n
)
2
+
1
independently of the events
analyzed in Claim 2.5.2.2. Hence, in case
x
∈
S
n
, algorithm
A
inverts
=
f
on
1
2
·
2
−
l
=
1
f
(
x
) with probability at least
2
(whereas the alternative algo-
4
n
·
p
(
|
x
|
)
2
+
rithm
A
succeeds with probability at least
1
2
). Recalling that (by Claim 2.5.2.1)
|
S
n
|
>
·
2
n
, we conclude that for every
n
∈
N
, algorithm
A
inverts
f
on
f
(
U
n
) with probability at least
1
2
p
(
n
)
1
8
n
·
p
(
n
)
3
+
4
p
(
n
)
. Noting that
A
is polynomial-time
(i.e., it merely invokes
G
for 2
n
·
p
(
n
)
2
=
poly(
n
) times, in addition to making
a polynomial amount of other computations), a contradiction to our hypothesis
that
f
is strongly one-way follows.
2.5.2.4.
∗
More Efficient Reductions
The preceding proof actually establishes the following:
Proposition 2.5.3:
Let G be a probabilistic algorithm with running time t
G
:
N→N
1]
in guessing b (see
Eq. (2.15)
). Then there
exists an algorithm A that runs in time O
(
n
2
and advantage
ε
G
:
N →
[0
,
/ε
G
(
n
)
2
)
·
t
G
(
n
)
such that
[
A
(
f
(
U
n
))
=
U
n
]
≥
ε
G
(
n
)
2
·
ε
G
(
n
)
2
Pr
4
n
The alternative implementation,
A
, mentioned earlier (i.e., trying all possible values
of the
σ
j
's rather than guessing one of them), runs in time
O
(
n
3
/ε
G
(
n
)
4
)
·
t
G
(
n
) and
