Cryptography Reference
In-Depth Information
Because there are at most 2
2
n
/
4
different circuits of size (number of gates) 2
n
/
8
,
it follows that there exists a sequence
s
1
,...,
s
2
n
/
2
n
∈{
0
,
1
}
such that for every
circuit
C
n
of size 2
n
/
8
it holds that
Pr
<
2
−
n
/
8
2
n
/
2
i
1
C
n
(
s
i
)
2
n
/
2
=
[
C
n
(
U
n
)
=
1]
−
Fixing such a sequence of
s
i
's, and letting
X
n
be distributed uniformly over the
elements in the sequence, the claim follows.
High-Level Comment.
Proposition 3.2.3 presents a pair of ensembles that are com-
putationally indistinguishable, although they are statistically far apart. One of the two
ensembles is not constructible in polynomial time (see Definition 3.2.5). Interestingly,
a pair of polynomial-time-constructible ensembles that are both computationally indis-
tinguishable and have a noticeable statistical difference can exist only if pseudorandom
generators exist. Jumping ahead, we note that this necessary condition is also sufficient.
(The latter observation follows from the fact that pseudorandom generators give rise
to a polynomial-time-constructible ensemble that is computationally indistinguishable
from the uniform ensemble and yet statistically far from it.)
Low-Level Comment.
A closer examination of the foregoing proof reveals that all but
a negligible fraction of the sequences of length 2
n
/
2
can be used to define the random
variable
X
n
. Specifically, the second inequality in Eq. (3.3) is a gross overestimate, and
an upper bound of 2
−
2
(
n
)
2
−
2
n
/
4
actually holds. Observing that most sequences contain
no repetitions, we can fix such a sequence. Consequently,
X
n
will be uniform over the
2
n
/
2
distinct elements of the sequence.
·
3.2.3. Indistinguishability by Repeated Experiments
By Definition 3.2.2, two ensembles are considered computationally indistinguishable
if no efficient procedure can tell them apart based on a single sample. We now show that
for “efficiently constructible” ensembles, computational indistinguishability (based on
a single sample) implies computational indistinguishability based on multiple samples.
We start by presenting definitions of “indistinguishability by multiple samples” and
“efficiently constructible ensembles.”
Definition 3.2.4 (Indistinguishability by Repeated Sampling):
Two ensem-
bles, X
def
={
X
n
}
n
∈N
and Y
def
={
Y
n
}
n
∈N
,are
indistinguishable by polynomial-time
sampling
if for every probabilistic polynomial-time algorithm D, every two posi-
tive polynomials m
(
·
)
and p
(
·
)
, and all sufficiently large n's,
Pr
D
X
(1)
n
,...,
X
(
m
(
n
)
n
=
1
−
Pr
D
Y
(1)
n
,...,
Y
(
m
(
n
)
n
=
1
<
1
p
(
n
)
where X
(1)
n
through X
(
m
(
n
))
n
and Y
(1)
n
through Y
(
m
(
n
))
n
are independent random
variables, with each X
(
i
)
n
identical to X
n
and each Y
(
i
)
identical to Y
n
.
n
