Cryptography Reference
In-Depth Information
worst-case analysis) is extremely sensitive to the instance-distribution. Hence, one
has to be extremely careful in deducing average-case complexity with respect to one
distribution from the average-case complexity with respect to another distribution. The
short history of the field contains several cases in which this point has been ignored,
and consequently bad suggestions have been made.
Consider, for example, the following (bad) suggestion to base one-way functions
on the conjectured difficulty of the Graph Isomorphism problem. Let
F
GI
(
G
,π
)
=
(
G
,π
G
), where
G
is an undirected graph,
π
is a permutation on its vertex set, and
π
G
denotes the graph resulting by renaming the vertices of
G
using
π
(i.e., (
π
(
u
)
,π
(
v
))
is an edge in
) is an edge in
G
). Although it is indeed believed
that Graph Isomorphism cannot be solved in polynomial time, it is easy to see that
F
GI
is easy to invert in most instances (e.g., use vertex-degree statistics to determine the
isomorphism). That is, the conjectured worst-case hardness does not imply an average-
case hardness for the uniform distribution. Furthermore, even if the problem is hard on
the average with respect to
some
distribution, one has to specify this distribution and
propose an efficient algorithm for sampling according to it.
π
G
if and only if (
u
,v
2.5. Hard-Core Predicates
Loosely speaking, saying that a function
f
is one-way implies that given
y
, it is infea-
sible to find a pre-image of
y
under
f
. This does not mean that it is infeasible to find
some partial information about the pre-image of
y
under
f
. Specifically, it may be easy
to retrieve half of the bits of the pre-image (e.g., given a one-way function
f
, consider
the function
g
defined by
g
(
x
r
)
def
). The fact that one-
way functions do not necessarily hide partial information about their pre-images limits
their “direct applicability” to tasks such as secure encryption. Fortunately, assuming
the existence of one-way functions, it is possible to construct one-way functions that
hide specific partial information about their pre-images (which is easy to compute from
the pre-image itself). This partial information can be considered as a “hard-core” of the
difficulty of inverting
f
.
,
=
(
f
(
x
)
,
r
) for every
|
x
|=|
r
|
2.5.1. Definition
Loosely speaking, a
polynomial-time
predicate
b
is called a hard-core of a function
f
if every efficient algorithm, given
f
(
x
), can guess
b
(
x
) with success probability that is
only negligibly better than one-half.
Definition 2.5.1 (Hard-Core Predicate):
A polynomial-time-computable predi-
cate b
:
}
∗
→{
is called a
hard-core
of a function f if for every prob-
abilistic polynomial-time algorithm A
, every positive polynomial p
(
{
0
,
1
0
,
1
}
·
)
, and all
sufficiently large n's,
1
2
+
1
p
(
n
)
Pr
[
A
(
f
(
U
n
))
=
b
(
U
n
)]
<
