Cryptography Reference
In-Depth Information
satisfies
1
2
Below, we provide a more efficient implementation of
A
. Combining it with a more
refined averaging argument than the one used in Claim 2.5.2.1, we obtain the following:
[
A
(
f
(
U
n
))
=
U
n
]
≥
ε
G
(
n
)
Pr
2
·
Proposition 2.5.4:
Let G, t
G
:
N→N
, and
ε
G
:
N →
[0
,
1]
be as before, and de-
(
n
)
def
/ε
G
(
n
))
. Then there exists an algorithm A
that runs in
expected
fine
=
log
2
(1
time O
(
n
2
(
n
)
3
)
·
·
t
G
(
n
)
and satisfies
Pr
[
A
(
f
(
U
n
))
=
U
n
]
=
(
ε
G
(
n
)
2
)
Thus, the
time-versus-success ratio
of
A
is poly(
n
)
/ε
G
(
n
)
2
, which (in some sense) is
optimal up to a poly(
n
) factor; see Exercise 30.
(
n
)
def
def
=
E
Proof Sketch:
Let
ε
=
ε
G
(
n
), and
log
2
(1
/ε
(
n
)). Recall that
[
s
(
X
n
)]
=
0
.
5
+
ε
(
n
), where
s
(
x
)
def
[
G
(
f
(
x
)
,
R
n
)
=
b
(
x
,
R
n
)] (as in Claim 2.5.2.1). We
first replace Claim 2.5.2.1 by a more refined analysis.
=
Pr
n
of cardinality
Claim 2.5.4.1:
There exists an
i
∈{
1
,...,
}
and a set
S
n
⊆{
0
,
1
}
at least (2
i
−
1
·
ε
(
n
))
·
2
n
such that for every
x
∈
S
n
, it holds that
1
2
+
1
2
i
+
1
=
Pr
s
(
x
)
[
G
(
f
(
x
)
,
R
n
)
=
b
(
x
,
R
n
)]
≥
·
def
={
x
:
s
(
x
)
≥
1
1
2
i
+
1
n
,we
Proof:
Let
A
i
2
+
}
. For any non-empty set
S
⊆{
0
,
1
}
let
a
(
S
)
def
)
def
=
max
x
∈
S
{
s
(
x
)
−
.
}
∅
=
0
5
, and
a
(
0. Assuming, to the contrary, that the
|
A
i
|
<
(2
i
−
1
·
ε
·
2
n
for
i
=
,...,
claim does not hold (i.e.,
(
n
))
1
), we get
E
[
s
(
X
n
)
−
0
.
5]
≤
Pr
[
X
n
∈
A
1
]
·
a
(
A
1
)
2
Pr
+
[
X
n
∈
(
A
i
\
A
i
−
1
)]
·
a
(
A
i
\
A
i
−
1
)
i
=
n
n
+
Pr
[
X
n
∈
(
{
0
,
1
}
\
A
)]
·
a
(
{
0
,
1
}
\
A
)
1
2
+
1
2
i
1
2
+
1
(2
i
−
1
<ε
(
n
)
·
·
ε
(
n
))
·
+
1
·
i
=
2
=
ε
(
n
)
2
+
(
−
1)
·
ε
(
n
)
2
2
−
2
+
=
ε
(
n
)
E
which contradicts
[
s
(
X
n
)
−
0
.
5]
=
ε
(
n
).
def
=
Fixing any
i
that satisfies Claim 2.5.4.1, we let
ε
2
−
i
−
1
/
and consider the
def
={
x
:
s
(
x
)
corresponding set
S
n
≥
0
.
5
+
ε
}
. By suitable setting of parameters,
we obtain that for every
x
∈
S
n
, algorithm
A
runs in time
O
(
n
3
/ε
4
)
·
t
G
(
n
) and
1
retrieves
x
from
f
(
x
) with probability at least
2
. Our next goal is to provide a