Cryptography Reference
In-Depth Information
independent copies of
Y
n
. Namely,
=
X
(1)
n
,...,
Y
(
m
n
def
H
n
,...,
X
(
k
)
n
,
Y
(
k
+
1)
n
where
X
(1)
n
through
X
(
k
)
n
and
Y
(
k
+
1)
n
through
Y
(
m
)
n
are independent random vari-
ables, with each
X
(
i
)
n
identical to
X
n
and each
Y
(
i
)
identical to
Y
n
. Clearly,
n
,...,
Y
(
m
n
).
By our hypothesis, algorithm
D
can distinguish the extreme hybrids (i.e.,
H
n
and
H
n
). Because the total number of hybrids is polynomial in
n
, a non-negligible
gap between (the “accepting” probability of
D
on) the extreme hybrids translates
into a non-negligible gap between (the “accepting” probability of
D
on) a pair
of neighboring hybrids. It follows that
D
, although not “designed to work on
general hybrids,” can distinguish a pair of neighboring hybrids. The punch line is
that algorithm
D
can be easily modified into an algorithm
D
that distinguishes
X
and
Y
. Details follow.
We construct an algorithm
D
that uses algorithm
D
as a subroutine. On input
H
n
=
(
X
(1)
,...,
X
(
m
)
n
), whereas
H
n
=
(
Y
(1)
n
n
α
(supposedly in the range of either
X
n
or
Y
n
), algorithm
D
proceeds as fol-
lows. Algorithm
D
first selects
k
uniformly in the set
. Using
the efficient sampling algorithm for the ensemble
X
, algorithm
D
generates
k
independent samples of
X
n
. These samples are denoted
x
1
{
0
,
1
,...,
m
−
1
}
x
k
. Likewise, us-
ing the efficient sampling algorithm for the ensemble
Y
, algorithm
D
generates
m
,...,
1 independent samples of
Y
n
, denoted
y
k
+
2
−
k
−
,...,
y
m
. Finally, algorithm
y
m
).
Clearly,
D
can be implemented in probabilistic polynomial time. It is also
easy to verify the following claims.
D
invokes algorithm
D
and halts with output
D
(
x
1
x
k
y
k
+
2
,...,
,α,
,...,
Claim 3.2.6.1:
m
−
k
=
0
Pr
1
D
H
k
+
n
=
1
1
m
Pr
[
D
(
X
n
)
=
1]
=
and
m
−
1
D
H
n
=
1
1
m
[
D
(
Y
n
)
Pr
=
1]
=
0
Pr
k
=
Proof:
By construction of algorithm
D
,wehave
D
(
α
)
=
D
X
(1)
n
,...,
Y
(
m
n
,...,
X
(
k
)
n
,α,
Y
(
k
+
2)
n
where
k
is uniformly distributed in
{
0
,
1
,...,
m
−
1
}
. Using the definition of the
hybrids
H
n
, the claim follows.
Claim 3.2.6.2:
For
(
n
) as in Eq. (3.4),
|=
(
n
)
m
(
n
)
[
D
(
X
n
)
[
D
(
Y
n
)
|
Pr
=
1]
−
Pr
=
1]
