Cryptography Reference
In-Depth Information
In particular,
z
n
may equal (
x
n
,y
n
). Thus, it is infeasible to distinguish
the encryptions of any two fixed messages (such as the all-zero message
and the all-ones message).
Definition 5.1 is more appealing in most settings where encryption is
considered the end goal. Definition 5.2 is used to establish the security
of candidate encryption schemes as well as to analyze their application
as modules inside larger cryptographic protocols. Thus, their equiva-
lence is of major importance.
Equivalence of Definitions 5.1 and 5.2 - proof ideas.
Intu-
itively, indistinguishability of encryptions (i.e., of the encryptions of
x
n
and
y
n
) is a special case of semantic security; specifically, it
corresponds to the case that
X
n
is uniform over
{x
n
,y
n
}
,
f
indi-
cates one of the plaintext s and
h
does not distinguish them (i.e.,
f
(
w
)=1iff
w
=
x
n
and
h
(
x
n
)=
h
(
y
n
)=
z
n
,where
z
n
is
as in Definition 5.2). The other direction is proved by considering
the algorithm
B
that, on input (1
n
,v
)where
v
=
h
(
x
), generates
(
e, d
)
G
(1
n
) and outputs
A
(
e, E
e
(1
n
)
,v
), where
A
is as in Defini-
tion 5.1. Indistinguishability of encryptions is used to prove that
B
performs as well as
A
(i.e., for every
h, f
and
ā
X
n
}
nā
N
, it holds that
Pr[
B
(1
n
,h
(
X
n
)) =
f
(
X
n
)] = Pr[
A
(
e, E
e
(1
n
)
,h
(
X
n
)) =
f
(
X
n
)] approxi-
mately equals Pr[
A
(
e, E
e
(
X
n
)
,h
(
X
n
))=
f
(
X
n
)]).
{
Probabilistic encryption:
It is easy to see that a secure
public-
key
encryption scheme must employ a probabilistic (i.e., randomized)
encryption algorithm. Otherwise, given the encryption-key as (addi-
tional) input, it is easy to distinguish the encryption of the all-zero
message from the encryption of the all-ones message.
2
This explains
the association of the aforementioned robust security definitions and
probabilistic encryption
, an association that goes back to the title of
the pioneering work of Goldwasser and Micali (80).
2
The same holds for (stateless)
private-key
encryption schemes, when considering the secu-
rity of encrypting several messages (rather than a single message as done above). For
example, if one uses a deterministic encryption algorithm then the adversary can distin-
guish two encryptions of the same message from the encryptions of a pair of different
messages.
