Cryptography Reference
In-Depth Information
invokes the
F
-inverter (polynomially) many times, each time feeding it
with a sequence of random
f
-images that contains
y
at a random loca-
tion. (Indeed such a sequence corresponds to a random image of
F
.)
The analysis of this reduction, presented in (65, Sec. 2.3), demonstrates
that dealing with computational diculty is much more involved than
the analogous combinatorial question. An alternative demonstration of
the diculty of reasoning about computational diculty (in compar-
ison to an analogous purely probabilistic situation) is provided in the
proof of Theorem 2.5.
2.2
Hard-core predicates
Loosely speaking, saying that a function
f
is one-way implies that given
y
(in the range of
f
) it is infeasible to find a preimage of
y
under
f
.
This does not mean that it is infeasible to find out partial informa-
tion about the preimage(s) of
y
under
f
. Specifically it may be easy
to retrieve half of the bits of the preimage (e.g., given a one-way func-
tion
f
consider the function
g
defined by
g
(
x, r
)
de
=(
f
(
x
)
,r
), for every
|x|
=
|r|
). As will become clear in subsequent sections, hiding partial
information (about the function's preimage) plays an important role
in more advanced constructs (e.g., secure encryption). Thus, we will
first show how to transform any one-way function into a one-way func-
tion that hides specific partial information about its preimage, where
this partial information is easy to compute from the preimage itself.
This partial information can be considered as a “hard core” of the dif-
ficulty of inverting
f
. Loosely speaking, a
polynomial-time computable
(Boolean) predicate
b
, is called a hard-core of a function
f
if no feasible
algorithm, given
f
(
x
), can guess
b
(
x
) with success probability that is
non-negligibly better than one half.
Definition 2.4.
(hard-core predicates (31)):
A polynomial-time com-
putable predicate
b
:
}
∗
→{
is called a
hard-core
of a function
f
if for every probabilistic polynomial-time algorithm
A
, every positive
{
0
,
1
0
,
1
}
