Cryptography Reference
InDepth Information
3.1
Computational indistinguishability
Indistinguishable things are identical
(or should be considered as identical).
The Principle of Identity of Indiscernibles
G.W. Leibniz (16461714)
(Leibniz admits that counterexamples to this principle are conceivable,
but will not occur in real life because God is much too benevolent.)
A central notion in modern cryptography is that of “effective sim
ilarity” (introduced by Goldwasser, Micali and Yao (80; 123)). The
underlying thesis is that we do not care whether or not objects are
equal, all we care about is whether or not a difference between the
objects can be observed by a feasible computation. In case the answer
is negative, the two objects are equivalent as far as any practical appli
cation is concerned. Indeed, in the sequel we will often interchange
such (computationally indistinguishable) objects. Let
X
=
X
n
}
n∈
N
and
Y
=
{Y
n
}
n∈
N
be probability ensembles such that each
X
n
and
Y
n
is a distribution that ranges over strings of length
n
(or polyno
mial in
n
). We say that
X
and
Y
are
computationally indistinguishable
if for every feasible algorithm
A
the difference
d
A
(
n
)
de
=
{

Pr[
A
(
X
n
)=
1]
−
Pr[
A
(
Y
n
)=1]

is a negligible function in
n
.Thatis:
Definition 3.1.
(computational indistinguishability (80; 123)):
We
say that
X
=
Y
n
}
n∈
N
are
computationally indistin
guishable
if for every probabilistic polynomialtime algorithm
D
every
polynomial
p
, and all suciently large
n
,
{
X
n
}
n∈
N
and
Y
=
{
<
1
p
(
n
)
where the probabilities are taken over the relevant distribution
(i.e.,
either
X
n
or
Y
n
)
and over the internal coin tosses of algorithm
D
.

Pr[
D
(
X
n
)=1]
−
Pr[
D
(
Y
n
)=1]

That is, we can think of
D
as somebody who wishes to distinguish two
distributions (based on a sample given to it), and think of 1 as
D
's