Cryptography Reference
In-Depth Information
Theorem 2.5.2:
Let f be an arbitrary strong one-way function, and let g be de-
fined by g
(
x
r
)
def
r
)
denote the inner product
mod 2
of the binary vectors x and r . Then the predicate b is a hard-core of the
function g.
,
=
(
f
(
x
)
,
r
)
, where
|
x
|=|
r
|
. Let b
(
x
,
In other words, the theorem states that if
f
is strongly one-way, then it is infeasible
to guess the exclusive-OR (XOR) of a random subset of the bits of
x
when given
f
(
x
)
and the subset itself. We stress that the theorem requires that
f
be strongly one-way
and that the conclusion is false if
f
is only weakly one-way (see Exercise 25). Clearly,
g
is also strongly one-way. We point out that
g
maintains other properties of
f
,
such
as being length-preserving and being one-to-one. Furthermore, an analogous statement
holds for collections of one-way functions with/without trapdoor, etc.
The rest of this section is devoted to proving Theorem 2.5.2. Again we use a re-
ducibility argument: Here, inverting the function
f
is reduced to guessing
b
(
x
,
r
) from
(
f
(
x
)
,
r
). Hence, we assume (for contradiction) the existence of an efficient algorithm
guessing the inner product with an advantage that is non-negligible, and we derive
an algorithm that inverts
f
with related (i.e., non-negligible) success probability. This
contradicts the hypothesis that
f
is a one-way function.
We start with some preliminary observations and a motivating discussion and then
turn to the main part of the actual proof. We conclude with more efficient implementa-
tions of the reducibility argument that assert “higher levels of security.”
2.5.2.1. Preliminaries
Let
G
be a (probabilistic polynomial-time) algorithm that on input
f
(
x
) and
r
tries to
guess the inner product (mod 2) of
x
and
r
. Denote by
ε
G
(
n
) the (overall) advantage of
algorithm
G
in guessing
b
(
x
,
r
) from
f
(
x
) and
r
, where
x
and
r
are uniformly chosen
n
. Namely,
in
{
0
,
1
}
1
2
ε
G
(
n
)
def
=
Pr
[
G
(
f
(
X
n
)
,
R
n
)
=
b
(
X
n
,
R
n
)]
−
(2.15)
where here and in the sequel
X
n
and
R
n
denote two independent random variables, each
uniformly distributed over
{
0
,
1
}
n
. Assuming, to the contrary, that
b
is not a hard-core
of
g
means that there exists an efficient algorithm
G
, a polynomial
p
(
·
), and an infinite
1
set
N
such that for every
n
∈
N
, it holds that
p
(
n
)
. We restrict our attention to
this algorithm
G
and to
n
's in this set
N
. In the sequel, we shorthand
ε
G
(
n
)
>
ε
G
by
ε
.
Our first observation is that on at least an
ε
(
n
)
2
fraction of the
x
's of length
n
, al-
gorithm
G
has at least an
ε
(
n
)
2
advantage in guessing
b
(
x
,
R
n
) from
f
(
x
) and
R
n
.
Namely:
n
of cardinality at least
ε
(
n
)
2
Claim 2.5.2.1:
There exists a set
S
n
⊆{
0
,
1
}
·
2
n
such
that for every
x
∈
S
n
, it holds that
1
2
+
ε
(
n
)
s
(
x
)
def
=
Pr
[
G
(
f
(
x
)
,
R
n
)
=
b
(
x
,
R
n
)]
≥
2
66
