Cryptography Reference
In-Depth Information
def
=
Definition 3.2.5 (Efficiently Constructible Ensembles):
An ensemble X
{
X
n
}
n
∈N
is said to be
polynomial-time-constructible
if there exists a proba-
bilistic polynomial-time algorithm S such that for every n, the random variables
S
(1
n
)
and X
n
are identically distributed.
def
={
def
={
Theorem 3.2.6:
Let X
Y
n
}
n
∈N
be two polynomial-time-
constructible ensembles, and suppose that X and Y are indistinguishable in
polynomial time (as in Definition 3.2.2). Then X and Y are indistinguishable
by polynomial-time sampling (as in Definition 3.2.4).
X
n
}
n
∈N
and Y
An alternative formulation of Theorem 3.2.6 proceeds as follows. For every ensemble
Z
def
={
Z
n
}
n
∈N
and every polynomial
m
(
·
), define the
m
(
·
)-
product
of
Z
as the ensemble
{
(
Z
(1)
n
,...,
Z
(
m
(
n
)
n
)
}
n
∈N
, where the
Z
(
i
n
's are independent copies of
Z
n
. Theorem 3.2.6
asserts that
if the ensembles X and Y are polynomial-time-indistinguishable and each
is polynomial-time-constructible, then for every polynomial m
(
·
)
the m
(
·
)
-product of X
and the m
(
·
)
-product of Y are polynomial-time-indistinguishable
.
The information-theoretic analogue of the foregoing theorem is quite obvious: If
two ensembles are statistically close, then their polynomial-products are statistically
close (see Exercise 7). Adapting the proof to the computational setting requires, as
usual, a reducibility argument. This argument uses, for the first time in this topic,
the
hybrid technique
. The hybrid technique plays a central role in demonstrating the
computational indistinguishability of complex ensembles, constructed on the basis of
simpler (computationally indistinguishable) ensembles. Subsequent applications of the
hybrid technique will involve more technicalities. Hence the reader is urged not to skip
the following proof.
Proof:
The proof is by a reducibility argument. We show that the existence of an
efficient algorithm that distinguishes the ensembles
X
and
Y
using several samples
implies the existence of an efficient algorithm that distinguishes the ensembles
X
and
Y
using a single sample. The implication is proved using the following
argument, which will later be called a “hybrid argument.”
Suppose, to the contrary, that there is a probabilistic polynomial-time algorithm
D
, as well as polynomials
m
(
·
) and
p
(
·
), such that for infinitely many
n
's it holds
that
Pr
1
D
X
(1)
n
X
(
m
n
=
1
−
Pr
D
Y
(1)
n
Y
(
m
n
=
(
n
)
def
=
,...,
,...,
(3.4)
1
p
(
n
)
>
where
m
def
=
m
(
n
), and the
X
(
i
n
's and
Y
(
i
n
's are as in Definition 3.2.4. In the se-
quel, we shall derive a contradiction by presenting a probabilistic polynomial-
time algorithm
D
that distinguishes the ensembles
X
and
Y
(in the sense of
Definition 3.2.2).
For every
k
, with 0
m
, we define the
hybrid
random variable
H
n
as a
(
m
-long) sequence consisting of
k
independent copies of
X
n
followed by
m
≤
k
≤
−
k
