Cryptography Reference
In-Depth Information
3.2.2. Relation to Statistical Closeness
Computational indistinguishability is a coarsening of a traditional notion from proba-
bility theory. We call two ensembles
X
def
={
X
n
}
n
∈N
and
Y
def
={
Y
n
}
n
∈N
statistically close
if their statistical difference is negligible, where the
statistical difference
(also known
as
variation distance
) between
X
and
Y
is defined as the function
1
2
·
(
n
)
def
=
|
Pr
[
X
n
=
α
]
−
Pr
[
Y
n
=
α
]
|
(3.1)
α
Clearly, if the ensembles
X
and
Y
are statistically close, then they are also polynomial-
time-indistinguishable (see Exercise 6). The converse, however, is not true. In particular:
Proposition 3.2.3:
There exists an ensemble X
={
X
n
}
n
∈N
such that X is not
statistically close to the uniform ensemble U
def
={
U
n
}
n
∈N
, and yet X and U are
polynomial-time-indistinguishable. Furthermore, X
n
assigns all its probability
mass to at most
2
n
/
2
strings (of length n).
Recall that
U
n
is uniformly distributed over strings of length
n
. Although
X
and
U
are
polynomial-time-indistinguishable, one can define a function
f
:
{
0
,
1
}
∗
→{
0
,
1
}
such
that
f
has average 1 over
X
while having average almost 0 over
U
(e.g.,
f
(
x
)
=
1if
and only if
Pr
[
X
=
x
]
>
0). Hence,
X
and
U
have different “profiles” with respect to
the function
f
, yet it is (necessarily) impossible to compute
f
in polynomial time.
Proof:
We claim that for all sufficiently large
n
, there exists a random variable
X
n
, distributed over some set of at most 2
n
/
2
strings (each of length
n
), such that
for every circuit
C
n
of size (i.e., number of gates) 2
n
/
8
, it holds that
[
C
n
(
X
n
)
=
1]
|
<
2
−
n
/
8
|
Pr
[
C
n
(
U
n
)
=
1]
−
Pr
(3.2)
The proposition follows from this claim, because polynomial-time-distinguishers
(even probabilistic ones; see Exercise 10 (Part 1)) yield polynomial-size circuits
with at least as large a distinguishing gap.
The foregoing claim is proved using a probabilistic argument. That is, we
actually show that most distributions of a certain class can “fool” all circuits of
size 2
n
/
8
. Specifically, we show that if we select uniformly a multi-set of 2
n
/
2
strings in
n
and let
X
n
be uniform over this multi-set, then Eq. (3.2) holds
with overwhelmingly high probability (over the choices of the multi-set).
Let
C
n
be some fixed circuit with
n
inputs, and let
p
n
{
,
}
0
1
def
=
Pr
[
C
n
(
U
n
)
=
1]. We
select, independently and uniformly, 2
n
/
2
strings, denoted
s
1
,...,
s
2
n
/
2
,in
{
0
,
1
}
n
.
We define random variables
C
n
(
s
i
); that is, these random
variables depend on the random choices of the corresponding
s
i
's. Using the
Chernoff bound, we get that
ζ
i
's such that
ζ
i
=
1
ζ
i
≥
2
−
n
/
8
2
n
/
2
1
2
n
/
2
·
2
e
−
2
·
2
n
/
2
(2
−
n
/
8
)
2
2
−
2
n
/
4
·
Pr
p
n
−
≤
<
(3.3)
i
=
