Cryptography Reference
In-Depth Information
sufficiently large n's,
1
p
(
n
)
1
n
)
1
n
)
|Pr
[
D
(
X
n
,
=
− Pr
[
D
(
Y
n
,
=
|
<
1]
1]
def
={
2.
Variant for ensembles indexed by a set of strings
S
:
Two ensembles, X
X
w
}
w
∈
S
def
={
Y
w
}
w
∈
S
,are
indistinguishable in polynomial time
if for every prob-
abilistic polynomial-time algorithm D, every positive polynomial p
(
and Y
·
)
, and all
sufficiently long
w
∈
S,
1
|Pr
[
D
(
X
w
,w
)
=
1]
− Pr
[
D
(
Y
w
,w
)
=
1]
|
<
p
(
|
w
|
)
We often say
computational indistinguishability
instead of indistinguishability in
polynomial time.
The probabilities in the foregoing definition are taken over the corresponding random
variables
X
i
(or
Y
i
) and the internal coin tosses of algorithm
D
(which is allowed
to be a probabilistic algorithm). The second variant of this definition will play a key
role in subsequent chapters, and further discussion of it is postponed to those places. In
the rest of this chapter, we refer to only the first variant of the foregoing definition. The
string 1
n
is given as auxiliary input to algorithm
D
in order to make the first variant
consistent with the second one. We comment that
in typical cases
, the length of
X
n
(resp.,
Y
n
) and
n
are polynomially related (i.e.,
|
X
n
|
<
poly(
n
) and
n
<
poly(
|
X
n
|
)) and
furthermore can be computed one from the other in poly(
n
) time. In such cases,
giving
1
n
as auxiliary input is redundant
. Indeed, throughout this chapter we typically omit
this auxiliary input and assume that
n
can be efficiently determined from
X
n
.
The following mental experiment may be instructive. For each
α
∈{
0
,
1
}
∗
, consider
the probability, hereafter denoted
d
(
α
), that algorithm
D
outputs 1 on input
α
. Consider
the expectation of
d
taken over each of the two ensembles: That is, let
d
X
(
n
)
=
E
[
d
(X
n
)]
and
d
Y
(
n
)
[
d
(
Y
n
)]. Then
X
and
Y
are said to be indistinguishable by
D
if the
difference (function)
=
E
(
n
)
def
δ
=|
d
X
(
n
)
−
d
Y
(
n
)
|
is negligible in
n
. Recall that a function
µ
:
N →
[0
,
1] is called
negligible
if for every positive polynomial
p
and all sufficiently
large
n
's,
p
(
n
).
A couple of examples may help to clarify the definition. Consider an algorithm
D
1
that, obliviously of the input, flips a (0-1-valued) coin and outputs its outcome. Clearly,
on every input, algorithm
D
1
outputs 1 with probability exactly
µ
(
n
)
<
1
/
1
2
and hence does not
distinguish any pair of ensembles. Next, consider an algorithm
D
2
that outputs 1 if and
only if the input string contains more zeros than ones. Because
D
2
can be implemented
in polynomial time, it follows that if
X
and
Y
are polynomial-time-indistinguishable,
then the difference
|
Pr
n
2
]
−
Pr
n
2
]
|
is negligible (in
n
), where wt(
α
)
denotes the number of ones in the string
α
. Similarly, polynomial-time-indistinguishable
ensembles must exhibit the same “profile” (up to negligible error) with respect to any
“string statistics” that can be computed in polynomial time. However, it is not required
that polynomial-time-indistinguishable ensembles have similar “profiles” with respect
to quantities that cannot be computed in polynomial time (e.g., Kolmogorov complexity,
or the function presented immediately after Proposition 3.2.3).
[wt(
X
n
)
<
[wt(
Y
n
)
<
