Cryptography Reference
In-Depth Information
3.1
Computational indistinguishability
Indistinguishable things are identical
(or should be considered as identical).
The Principle of Identity of Indiscernibles
G.W. Leibniz (1646-1714)
(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 polynomial-time 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     Search WWH ::

Custom Search