Cryptography Reference
In-Depth Information
bits of
h
from the value of
f
can be easily modified to distinguish (
f
(
X
n
)
,
h
(
X
n
)) from
(
f
(
X
n
)
,
R
l
(
n
)
). Hence, for logarithmically shrinking
h
's, 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
.
Proof:
All that is required is to evaluate the success probability of algorithm
G
(as a function of
p
−
q
). We start by fixing an
x
∈{
0
,
1
}
n
and evaluating
Pr
[
G
(
f
(
x
)
,
I
l
,
l
)
=⊕
i
∈
I
l
(
h
i
(
x
))], where
I
l
is a uniformly chosen non-empty sub-
set of
{
1
,...,
l
}
and
l
def
=
l
(
n
). The rest is an easy averaging (over the
x
's).
C
denote the set (or class) of all non-empty subsets of
{
1
,...,
l
}
. Define,
for every
S
∈
C
Let
, a relation
≡
S
such that
y
≡
S
z
if and only if
⊕
i
∈
S
y
i
=⊕
i
∈
S
z
i
,
where
y
=
y
1
···
y
l
and
z
=
z
1
···
z
l
. Note that for every
S
∈
C
l
,
the relation
y
≡
S
z
holds for exactly 2
l
−
1
of the
y
's. Recall that by definition of
G
, on input (
f
(
x
)
,
S
,
l
) and random choice
r
=
r
1
···
r
l
∈{
0
,
1
}
and
z
∈{
0
,
1
}
l
, algorithm
G
outputs
D
(
f
(
x
)
,
r
)
⊕
1
⊕
(
⊕
i
∈
S
r
i
). The latter equals
⊕
i
∈
S
(
h
i
(
x
)) if and only if
one of the following two disjoint events occurs:
event 1:
D
(
f
(
x
)
,
r
)
=
1 and
r
≡
S
h
(
x
).
event 2:
D
(
f
(
x
)
≡
S
h
(
x
).
By the preceding discussion and elementary manipulations, we get
,
r
)
=
0 and
r
s
(
x
)
def
=
Pr
[
G
(
f
(
x
)
,
I
l
,
l
)
=⊕
i
∈
I
l
(
h
i
(
x
))]
1
|
C
|
·
=
Pr
,
S
,
l
)
=⊕
i
∈
S
(
h
i
(
x
)]
[
G
(
f
(
x
)
S
∈
C
1
|
C
|
·
=
(
Pr
[event 1]
+
Pr
[event 2])
S
∈
C
1
Pr
[
(
R
l
)
=
1
|
R
l
≡
S
h
(
x
)]
+
Pr
=
·|
C
|
·
(
[
(
R
l
)
=
0
|
R
l
≡
S
h
(
x
)])
2
S
∈
C
where
R
l
is uniformly distributed over
{
0
,
1
}
l
(representing the random choice of
algorithm
G
), and
r
). The rest
of the analysis is straightforward but tedious and can be skipped with little loss.
(
r
) is shorthand for the random variable
D
(
f
(
x
)
,
1
2
+
1
2
|
C
|
·
s
(
x
)
=
(
Pr
[
(
R
l
)
=
1
|
R
l
≡
S
h
(
x
)]
−
Pr
[
(
R
l
)
S
∈
C
=
|
R
l
≡
S
h
(
x
)])
1
S
1
2
+
1
2
|
C
|
·
1
2
l
−
1
·
=
≡
S
h
(
x
)
Pr
[
(
r
)
=
1]
−
≡
S
h
(
x
)
Pr
[
(
r
)
=
1]
∈
C
r
S
∈
C
r
1
2
+
1
EQ(
r
,
h
(
x
))
Pr
=
·|
C
|
·
[
(
r
)
=
1]
2
l
r
S
∈
1]
−
h
(
x
))
Pr
[
(
r
)
=
r
S
∈
NE(
r
,
