Cryptography Reference
In-Depth Information
where the
i
th term in the sum is an upper bound on the fraction of the
h
's that are
(
T
·
2
i
−
3
3
3
ck
, we conclude
k
·
2
i
+
1
)-overweighting. For
c
=
1536, setting
T
=
ck
δ
2
and
=
δ
,
3
3
ck
)-expanding.
Having established an upper bound on suitably expanding functions, we now turn to
the actual claim. Specifically, we call
h honest
if it is
not
(
1536
k
δ
128
k
/
3
ck
)
=
4
fraction of the
h
's are (
ck
,
δ
that at most a
(
ck
/δ
2
)
2
·
(
δ
3
δ
2
3
4608
k
)-expanding. There
δ
,
2
are two important facts about honest functions:
Fact 1
: All but at most a
4
fraction of the
h
's are honest.
Fact 2
:If
h
is honest and
Pr
[
h
(
X
n
)
∈
R
]
≥
2
, then
Pr
[
U
k
∈
R
]
≥
3
4608
k
. (Suppose that
h
δ
3
4608
k
δ
(
1536
k
δ
3
4608
k
=
δ
Pr
Pr
is honest and
[
U
k
∈
R
]
≤
holds. Then
[
h
(
X
n
)
∈
R
]
<
+
1)
·
2
3
4608
k
<
2
.)
Concentrating on the honest
h
's, we now evaluate the probability that (
3
+
δ
α,
h
) hits
B
when
≥
2
. Using the Markov
α
is uniformly chosen. We call
h good
if
Pr
[(
h
(
X
n
)
,
h
)
∈
B
]
inequality (and the definition of
), we get the following:
Fact 3:
The probability that
H
n
is good is at least
2
.
Denote by
P
(for “perfect”) the set of
h
's that are both good and honest. Combining
Facts 1 and 3, we have the following:
δ
[
H
n
∈
≥
2
−
4
=
4
.
Fact 4:
Pr
P
]
def
={
α
≥
2
Let
B
h
:(
α,
h
)
∈
B
}
. Clearly, for every
h
∈
P
we have
Pr
[
h
(
X
n
)
∈
B
h
]
(since
h
3
4608
k
δ
is good), and
Pr
[
U
k
∈
B
h
]
≥
(since
h
is honest and the hypothesis of Fact 2 applies
to
B
h
). Thus:
3
4608
k
.
δ
Fact 5
: For every
h
∈
P
, it holds that
Pr
[(
U
k
,
h
)
∈
B
]
≥
Combining Facts 4 and 5, we have
Pr
U
k
,
H
n
∈
B
≥
Pr
U
k
,
H
n
∈
B
H
n
∈
P
·
Pr
H
n
∈
P
3
4608
k
·
4
δ
≥
and the claim follows.
Applying Proposition 3.5.9
It is possible to apply Construction 3.5.2 to the function resulting from Construc-
tion 3.5.8 and have the statement of Proposition 3.5.3 still hold, with minor modifica-
tions. Specifically, the modified bound (analogous to Proposition 3.5.3) is 2
−
(
l
(
n
))
+
l
(
n
)
3
1
p
(
n
)
1
p
(
n
)
) for every positive polynomial
p
. The argument leading
to Theorem 3.5.6 remains valid as well. Furthermore, we can even waive the require-
ment that
m
(
n
) can be computed (since we can construct functions
F
m
for every possible
value of
m
(
n
)). Finally, we note that the entire argument holds even if the definition of
regular functions is relaxed as follows.
(instead of 2
·
2
−
+
Definition 3.5.10 (Regular Functions, Revised Definition):
A function f
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
is called
regular
if there exists an integer function m
:
146
