Cryptography Reference
In-Depth Information
2.5.3.
∗
Hard-Core Functions
We have just seen that every one-way function can be easily modified to have a hard-
core predicate. In other words, the result establishes one bit of information about the
pre-image that is hard to approximate from the value of the function. A stronger result
may say that several bits of information about the pre-image are hard to approximate.
For example, we may want to say that a specific pair of bits is hard to approximate, in the
sense that it is infeasible to guess this pair with probability non-negligibly larger than
1
4
. Actually, in general, we take a slightly different approach and require that the true
value of these bits be hard to distinguish from a random value. That is, a
polynomial-
time
function
h
is called a hard-core of a function
f
if no efficient algorithm can
distinguish (
f
(
x
)
.For
further discussion of the notion of efficient distinguishability, the reader is referred to
Section 3.2. We assume for simplicity that
h
is length-regular (see next).
,
h
(
x
)) from (
f
(
x
)
,
r
), where
r
is a random string of length
|
h
(
x
)
|
Definition
2.5.5
(Hard-Core
Function):
Let
h
:
{
0
,
1
}
∗
→{
0
,
1
}
∗
be
a
polynomial-time-computable function satisfying
|
h
(
x
)
|=|
h
(
y
)
|
for all
|
x
|=|
y
|
,
and let l
(
n
)
def
|
. The function h is called a
hard-core
of a function f if
for every probabilistic polynomial-time algorithm D
, every positive polynomial
p
(
=|
h
(1
n
)
·
)
, and all sufficiently large n's,
Pr
D
f
(
X
n
)
R
l
(
n
)
1
<
1
p
(
n
)
where X
n
and R
l
(
n
)
are two independent random variables, the first uniformly
distributed over
[
D
(
f
(
X
n
)
,
h
(
X
n
))
=
1]
−
Pr
,
=
{
0
,
1
}
n
and the second uniformly distributed over
{
0
,
1
}
l
(
n
)
.
For
l
1, Definition 2.5.5 is equivalent to Definition 2.5.1; see the discussion following
Lemma 2.5.8. See also Exercise 31.
Simple hard-core functions with logarithmic lengths (i.e.,
l
(
n
)
≡
O
(log
n
)) are
known for the RSA, Rabin, and DLP collections, provided that the corresponding col-
lections are one-way. For example, the function that outputs logarithmically many least
significant bits is a hard-core function for the RSA collection, provided that the RSA
collection is one-way. Namely, assuming that the RSA collection is one-way, it is in-
feasible to distinguish, given RSA
N
,
e
(
x
)
=
x
e
mod
N
, the
O
(log
|
N
|
) least significant
bit of
x
from a uniformly distributed
O
(log
|
N
|
)-bit-long string. (Similar statements
hold for the Rabin and DLP collections.) A general result of this type follows.
=
Theorem 2.5.6:
Let f be an arbitrary strong one-way function, and let g
2
be
defined by g
2
(
x
,
s
)
def
|
x
|
.
12
Let b
i
(
x
,
s
)
denote the in-
ner product
mod 2
of the binary vectors x and
(
s
i
+
1
,...,
=
(
f
(
x
)
,
s
)
, where
|
s
|=
2
s
i
+
n
)
, where s
=
s
)
def
(
s
1
,...,
s
2
n
)
. Then, for any constant c
>
0
, the function h
(
x
,
=
b
1
(
x
,
s
)
···
b
l
(
|
x
|
)
(
x
,
s
)
is a hard-core of the function g
2
, where l
(
n
)
def
=
min
{
n
,
c
log
2
n
}
.
12
In fact, we can use
|
s
|=|
x
|+
l
(
|
x
|
)
−
1, where
l
(
n
)
=
O
(log
n
). In the current description,
s
1
and
s
n
+
l
(
n
)
+
1
,...,
s
2
n
are not used. However, the current formulation makes it unnecessary to specify
l
when
defining
g
2
.
