Cryptography Reference
In-Depth Information
Proof:
Using Claim 3.2.6.1 for the first equality, we get
m
−
1
1
m
·
D
H
k
+
n
=
1
−
Pr
D
H
n
=
1
[
D
(
X
n
)
[
D
(
Y
n
)
|
Pr
=
1]
−
Pr
=
1]
|=
0
Pr
k
=
m
·
Pr
D
H
n
=
1
−
Pr
D
H
n
=
1
1
=
=
(
n
)
m
where the last equality follows by recalling that
H
n
=
(
X
(1)
,...,
X
(
m
)
n
) and
H
n
=
n
(
Y
(1)
n
,...,
Y
(
m
)
n
) and using the definition of
(
n
).
1
Since by our hypothesis
p
(
n
)
for infinitely many
n
's, it follows that the
probabilistic polynomial-time algorithm
D
distinguishes
X
and
Y
in contradic-
tion to the hypothesis of the theorem. Hence, the theorem follows.
(
n
)
>
The Hybrid Technique: A Digest
It is worthwhile to give some thought to the
hybrid technique
(used for the first time in
the preceding proof). The hybrid technique constitutes a special type of a “reducibility
argument” in which the computational indistinguishability of
complex
ensembles is
proved using the computational indistinguishability of
basic
ensembles. The actual
reduction is in the other direction: Efficiently distinguishing the basic ensembles is
reduced to efficiently distinguishing the complex ensembles, and
hybrid
distributions
are used in the reduction in an essential way. The following properties of the construction
of the hybrids play an important role in the argument:
1.
Extreme hybrids collide with the complex ensembles
: This property is essential because
what we want to prove (i.e., indistinguishability of the complex ensembles) relates to
the complex ensembles.
2.
Neighboring hybrids are easily related to the basic ensembles
: This property is essential
because what we know (i.e., indistinguishability of the basic ensembles) relates to the
basic ensembles. We need to be able to translate our knowledge (i.e., computational
indistinguishability) of the basic ensembles to knowledge (i.e., computational indistin-
guishability) of any pair of neighboring hybrids. Typically it is required to efficiently
transform strings in the range of a basic distribution into strings in the range of a hy-
brid, so that the transformation maps the first basic distribution to one hybrid and the
second basic distribution to the neighboring hybrid. (In the proof of Theorem 3.2.6, the
hypothesis that both
X
and
Y
are polynomial-time-constructible is instrumental for such
an efficient transformation.)
3.
The number of hybrids is small
(i.e., polynomial): This property is essential in order
to deduce the computational indistinguishability of extreme hybrids from the computa-
tional indistinguishability of each pair of neighboring hybrids. Typically, the provable
“distinguishability gap” is inversely proportional to the number of hybrids.
We remark that during the course of a hybrid argument a distinguishing algorithm
referring to the complex ensembles is being analyzed and even executed on arbitrary
