Cryptography Reference
In-Depth Information
We first observe that for
n
's satisfying the foregoing inequality we can easily find
a set
I
satisfying
1
2
+
1
2
p
(
n
)
def
=
Pr
[
A
(
I
,
g
2
(
U
3
n
))
=
b
I
(
U
3
n
)]
≥
p
I
Specifically, we can try all possible
I
's and estimate
p
I
for each of them (via
random experiments), picking an
I
for which the estimate is highest. (Note
that using poly(
n
) many experiments, we can approximate each of the possi-
ble 2
l
(
n
)
−
1
=
poly(
n
) different
p
I
's up to an additive deviation of 1
/
4
p
(
n
) and
error probability of 2
−
n
.)
We now present an algorithm for approximating
b
(
x
,
r
) from
y
def
=
f
(
x
) and
r
. On input
y
and
r
, the algorithm first finds a set
I
as described earlier (this
stage depends only on
n
def
=|
x
|
, which equals
|
r
|
). Once
I
is found, the algorithm
uniformly selects a string
s
such that
⊕
i
∈
I
sub
i
(
s
)
=
r
and returns
A
(
I
,
(
y
,
s
)).
Note that for uniformly distributed
r
∈{
0
,
1
}
n
, the string
s
selected by our
algorithm is uniformly distributed in
s
). Evaluation
of the success probability of this algorithm is left as an exercise.
{
0
,
1
}
2
n
and
b
(
x
,
r
)
=
b
I
(
x
,
The following lemma provides a generic transformation of algorithms distinguish-
ing between (
f
(
X
n
)
,
h
(
X
n
)) and (
f
(
X
n
)
,
R
l
(
n
)
) to algorithms that, given
f
(
X
n
) and
a random non-empty subset
I
of
{
1
,...,
l
(
n
)
}
, predict the XOR of the bits of
X
n
at
locations
I
.
Lemma 2.5.8 (Computational XOR Lemma):
Let f and h be arbitrary length-
regular functions, and let l
(
n
)
def
h
(1
n
)
=|
|
. Let D be any algorithm, and denote
D
f
(
X
n
)
R
l
(
n
)
=
1
def
=
Pr
def
=
Pr
p
[
D
(
f
(
X
n
)
,
h
(
X
n
))
=
1]
and
q
,
where X
n
and R
l
(
n
)
are independent random variables uniformly distributed
over
{
0
,
1
}
n
l
(
n
)
, respectively. We consider a specific algorithm, de-
and
{
0
,
1
}
def
=
G
D
, that uses D as a subroutine. Specifically, on input and y, and
noted G
S
⊆{
1
,...,
l
(
n
)
}
(
and l
(
n
))
, algorithm G selects r
=
r
1
···
r
l
(
n
)
uniformly in
{
0
,
1
}
l
(
n
)
and outputs D
(
y
,
r
)
⊕
1
⊕
(
⊕
i
∈
S
r
i
)
. Then,
1
2
+
p
−
q
Pr
[
G
(
f
(
X
n
)
,
I
l
,
l
(
n
))
=⊕
i
∈
I
l
(
h
i
(
X
n
))]
=
1
where I
l
is a randomly chosen non-empty subset of
{
1
,...,
l
(
n
)
}
, and h
i
(
x
)
denotes
the i th bit of h
(
x
)
.
2
l
(
n
)
−
It follows that for logarithmically shrinking
h
's, the existence of an efficient algo-
rithm that distinguishes (with a gap that is not negligible in
n
) the random variables
(
f
(
X
n
)
,
R
l
(
n
)
) implies the existence of an efficient algorithm that
approximates the XOR of a random non-empty subset of the bits of
h
(
X
n
) from the
value of
f
(
X
n
) with an advantage that is not negligible. On the other hand, it is clear that
any efficient algorithm that approximates an XOR of a random non-empty subset of the
,
h
(
X
n
)) and (
f
(
X
n
)
