Cryptography Reference
InDepth Information
every probabilistic polynomialtime algorithm,
A
, there exists a prob
abilistic polynomialtime algorithm
B
so that for every two functions
f,h
:
}
∗
→{
}
∗
such that
{
0
,
1
0
,
1

h
(
x
)

=poly(

x

), and all probabil
ity ensembles
{
X
n
}
n∈
N
,where
X
n
is a random variable ranging over
n
, it holds that
Pr[
A
(
e, E
e
(
x
)
,h
(
x
))=
f
(
x
)]
<
Pr[
B
(1
n
,h
(
x
))=
f
(
x
)] +
µ
(
n
)
.
{
0
,
1
}
where the plaintext
x
is distributed according to
X
n
, the encryption
key
e
is distributed according to
G
(1
n
), and
µ
is a negligible function.
That is, it is feasible to predict
f
(
x
)from
h
(
x
) as successfully as it is
to predict
f
(
x
)from
h
(
x
)and(
e, E
e
(
x
)), which means that nothing
is gained by obtaining (
e, E
e
(
x
)). Note that no computational restric
tions are made regarding the functions
h
and
f
. We stress that the
above definition (as well as the next one) refers to publickey encryp
tion schemes, and in the case of privatekey schemes algorithm
A
is not
given the encryptionkey
e
.
A good disguise should not allow a mother
to distinguish her own children.
Shafi Goldwasser and Silvio Micali, 1982
The following technical interpretation of security states that it is infeas
ible to distinguish the encryptions of two plaintext s (of the same
length).
Definition 5.2.
(indistinguishability of encryptions (following (80))):
A
publickey
encryption scheme (
G, E, D
)has
indistinguishable encryp
tions
if for every probabilistic polynomialtime algorithm,
A
,andall
sequences of triples, (
x
n
,y
n
,z
n
)
n∈
N
,where

x
n

=

y
n

=
n
and
z
n

=poly(
n
),

Pr[
A
(
e, E
e
(
x
n
)
,z
n
)=1]
−
Pr[
A
(
e, E
e
(
y
n
)
,z
n
)=1]

=
µ
(
n
)
.
Again,
e
is distributed according to
G
(1
n
), and
µ
is a negligible func
tion.