Cryptography Reference
In-Depth Information
hybrids. The reader may be annoyed by the fact that the algorithm “was not designed to
work on such hybrids” (but rather only on the extreme hybrids). However,
an algorithm
is an algorithm
: Once it exists, we can apply it to any input of our choice and analyze
its performance on arbitrary input distributions.
Advanced Comment on the Non-triviality of Theorem 3.2.6.
Additional indication
of the non-triviality of Theorem 3.2.6 is provided by the fact that the conclusion may
fail in case the individual ensembles are
not both
efficiently constructible. Indeed, the
hypothesis that both ensembles are efficiently constructible plays a central role in the
proof of Theorem 3.2.6. Contrast this fact with the fact that an information-theoretic
analogue of Theorem 3.2.6 asserts that for
any
two ensembles, statistical closeness
implies statistical closeness of multiple samples.
3.2.4.
∗
Indistinguishability by Circuits
A stronger notion of computational indistinguishability is the notion of computational
indistinguishability by non-uniform families of polynomial-size circuits. This notion
will be used in subsequent chapters.
Definition 3.2.7 (Indistinguishability by Polynomial-Size Circuits):
def
={
1.
Variant
for
ensembles
indexed
by
N
:
Two
ensembles,
X
X
n
}
n
∈N
and
def
={
Y
Y
n
}
n
∈N
,are
indistinguishable by polynomial-size circuits
if for every
family
{
C
n
}
n
∈N
of polynomial-size circuits, every positive polynomial
p
(
·
)
,
and all sufficiently large n's,
1
p
(
n
)
|Pr
[
C
n
(
X
n
)
=
1]
− Pr
[
C
n
(
Y
n
)
=
1]
|
<
def
={
2.
Variant for ensembles indexed by a set of strings
S
:
Two ensembles, X
X
w
}
w
∈
S
def
={
and Y
Y
w
}
w
∈
S
,are
indistinguishable by polynomial-size circuits
if for every
family
{
C
n
}
n
∈N
of polynomial-size circuits, every positive polynomial p
(
·
)
, and all
sufficiently long
's,
Pr
C
|
w
|
(
X
w
)
w
1
− Pr
C
|
w
|
(
Y
w
)
1
<
1
=
=
p
(
|
w
|
)
We comment that the variant for ensembles indexed by
S
is equivalent to the following
(seemingly stronger) condition:
For every polynomial s
(
·
)
, every collection
{
C
w
}
w
∈
S
of circuits such that C
w
has size at
most s
(
|
w
|
)
, every positive polynomial p
(
·
)
, and all sufficiently long
w
's
,
1
p
(
|
w
|
)
|
Pr
−
Pr
[
C
w
(
X
w
)
=
1]
[
C
w
(
Y
w
)
=
1]
|
<
(3.5)
We show that the second requirement is not stronger than the requirement in the defini-
tion: That is, we show that if the second requirement is not satisfied, then neither is the
