Cryptography Reference
In-Depth Information
polynomial
p
(
·
), and all suciently large
n
's
Pr
A
(
f
(
x
))=
b
(
x
)
<
1
2
+
1
p
(
n
)
where the probability is taken uniformly over all the possible choices
of
x
n
and all the possible outcomes of the internal coin tosses
of algorithm
A
.
∈{
0
,
1
}
}
∗
,
there exist obvious algorithms that guess
b
(
x
)from
f
(
x
)withsuccess
probability at least one half (e.g., the algorithm that, obliviously of its
input, outputs a uniformly chosen bit). Also, if
b
is a hard-core predicate
(for any function) then it follows that
b
is almost unbiased (i.e., for a
uniformly chosen
x
, the difference
|
Pr[
b
(
x
)=0]
−
Pr[
b
(
x
)=1]
|
must be
a negligible function in
n
). Finally, if
b
is a hard-core of a 1-1 function
f
that is polynomial-time computable then
f
is a one-way function.
}
∗
→{
}
∗
→{
Note that for every
b
:
{
0
,
1
0
,
1
}
and
f
:
{
0
,
1
0
,
1
Theorem 2.5.
((72), see simpler proof in (65, Sec. 2.5.2)):
For any
one-way function
f
, the inner-product mod 2 of
x
and
r
is a hard-core
of
f
(
x, r
)=(
f
(
x
)
,r
).
The proof is by a so-called “reducibility argument” (which is used to
prove all conditional results in the area). Specifically, we reduce the task
of inverting
f
to the task of predicting the hard-core of
f
, while mak-
ing sure that the reduction (when applied to input distributed as in the
inverting task) generates a distribution as in the definition of the pre-
dicting task. Thus, a contradiction to the claim that
b
is a hard-core of
f
yields a contradiction to the hypothesis that
f
is hard to invert. We stress
that this argument is far more complex than analyzing the correspond-
ing “probabilistic” situation (i.e., the distribution of the inner-product
mod 2 of
X
and
r
, conditioned on a uniformly selected
r
n
,where
X
is a random variable with super-logarithmic min-entropy, which rep-
resents the “effective” knowledge of
x
,whengiven
f
(
x
)).
3
∈{
0
,
1
}
3
The
min-entropy of
X
is defined as min
v
{
log
2
(1
/
Pr[
X
=
v
])
}
;thatis,if
X
has min-entropy
m
then max
v
{
=2
−m
. The Leftover Hashing Lemma (120; 27; 87) implies that,
in this case, Pr[
b
(
X, U
n
)=1
Pr[
X
=
v
]
}
|U
n
]=
2
±
2
−
Ω(
m
)
,where
U
n
denotes the uniform distribution
n
,and
b
(
u, v
) denotes the inner-product mod 2 of
u
and
v
.
over
{
0
,
1
}
