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.