Cryptography Reference
In-Depth Information
every probabilistic polynomial-time algorithm,
A
, there exists a prob-
abilistic polynomial-time 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 public-key encryp-
tion schemes, and in the case of private-key schemes algorithm
A
is not
given the encryption-key
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
public-key
encryption scheme (
G, E, D
)has
indistinguishable encryp-
tions
if for every probabilistic polynomial-time 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.