Cryptography Reference
In-Depth Information
The proof of the theorem follows by combining a
proposition that capitalizes on the
structure of the specific function h
and a
general lemma
concerning hard-core functions.
Loosely speaking, the proposition “reduces” the problem of approximating
b
(
x
,
r
)
given
g
(
x
,
r
) to the problem of approximating the XOR of any non-empty set of the
bits of
h
(
x
s
), where
b
and
g
are the hard-core and the one-way function
presented in the preceding subsection. Since we know that the predicate
b
(
x
,
s
)given
g
2
(
x
,
,
r
) cannot
be approximated from
g
(
x
,
r
), we conclude that no XOR of the bits of
h
(
x
,
s
) can be
approximated from
g
2
(
x
s
). The general lemma implies that for every “logarithmically
shrinking” function
h
(i.e.,
h
satisfying
,
)), the function
h
is a hard-
core of a function
f
if and only if the XOR of any non-empty subset of the bits of
h
cannot be approximated from the value of
f
. Following are the formal statements and
proofs of both claims.
h
(
x
)
|
|=
O
(log
|
x
|
Proposition 2.5.7:
Let f , g
2
, l, and the b
i
's be as in Theorem 2.5.6. Let
{
I
n
⊆{
1
,
2
,...,
l
(
n
)
}}
n
∈N
be an arbitrary sequence of non-empty sets, and let
b
I
|
x
|
(
x
s
)
def
s
)
. Then for every probabilistic polynomial-time algo-
rithm A
, every positive polynomial p
(
,
=⊕
i
∈
I
|
x
|
b
i
(
x
,
·
)
, and all sufficiently large n's,
1
2
+
1
p
(
n
)
[
A
(
I
n
,
g
2
(
U
3
n
))
Pr
=
b
I
n
(
U
3
n
)]
<
where U
3
n
is a random variable uniformly distributed over
{
0
,
1
}
3
n
.
Proof:
The proof is by a reducibility argument. Let
X
n
,
R
n
, and
S
2
n
be indepen-
dent random variables uniformly distributed over
{
0
,
1
}
2
n
, re-
spectively. We show that the problem of approximating
b
(
X
n
,
R
n
)given
(
f
(
X
n
)
,
R
n
) is reducible to the problem of approximating
b
I
n
(
X
n
,
S
2
n
)given
(
f
(
X
n
)
,
S
2
n
). The underlying observation is that for every
|
s
|=
2
·|
x
|
and every
I
⊆{
1
,...,
l
(
n
)
}
,
n
,
{
0
,
1
}
n
, and
{
0
,
1
}
b
I
(
x
,
s
)
=⊕
i
∈
I
b
i
(
x
,
s
)
=
b
(
x
,
⊕
i
∈
I
sub
i
(
s
))
where sub
i
(
s
1
,...,
s
2
n
)
def
(
s
i
+
1
,...,
s
i
+
n
). Furthermore, the reader can verify that
for every non-empty
I
⊆{
=
1
,...,
l
(
n
)
}
, the random variable
⊕
i
∈
I
sub
i
(
S
2
n
) is uni-
formly distributed over
{
0
,
1
}
n
, and that given a string
r
∈{
0
,
1
}
n
and such a set
I
, one can efficiently select a string uniformly in the set
{
s
:
⊕
i
∈
I
sub
i
(
s
)
=
r
}
.
Verification of both claims is left as an exercise.
13
Now assume, to the contrary, that there exists an efficient algorithm
A
,a
polynomial
p
(
·
), and an infinite sequence of sets (i.e.,
I
n
's) and
n
's such that
1
2
+
1
p
(
n
)
[
A
(
I
n
,
g
2
(
U
3
n
))
=
b
I
n
(
U
3
n
)]
≥
Pr
13
Given any non-empty
I
and any
r
=
r
1
···
r
n
∈{
0
,
1
}
n
, consider the following procedure, where
k
is the
largest element in
I
. First, uniformly select
s
1
,...,
n
,
determine
s
k
+
i
so that
⊕
j
∈
I
s
i
+
j
=
r
i
(i.e.,
s
k
+
i
←
r
i
⊕
(
⊕
j
∈
I
\{
k
}
s
j
+
i
), where the relevant
s
i
+
j
's are already
determined, since
j
<
k
). This process determines a string
s
1
···
s
2
n
uniformly among 2
n
s
k
,
s
k
+
n
+
1
,...,
s
2
n
∈{
0
,
1
}
. Next, going from
i
=
1to
i
=
strings
s
that satisfy
⊕
i
∈
I
sub
i
(
s
)
=
r
. Since there are 2
n
possible
r
's, both claims follow.
