Cryptography Reference
In-Depth Information
the adversary to easily distinguish the plaintexts. Now, according to the previous
remarks, the definition of security should formalize the fact that the probability that
the adversary succeeds in the previous experiment is negligibly greater than 1
/
2
(as succeeding with probability 1
/
2 is easy just by outputting a random bit). The
definition is then the following:
Definition 3.22
A private-key encryption scheme
has
indis-
tinguishable encryptions in the presence of an eavesdropper
if, for every PPT adver-
sary
E
=
(
Gen
,
Enc
,
Dec
)
A
, there exists a negligible function
negl
such that:
PrivK
ind-eav
A,E
Pr
(
(
n
)
=
1
)
≤
1
/
2
+
negl
(
n
),
where the probability is taken over the random bits used by
, as well as the random
bits used elsewhere in the experiment (i.e., when running
Gen
, when choosing a
random bit
b
and when running
Enc
in case this algorithm is probabilistic).
A
Remarks 3.7
1. As mentioned above, this definition does not seem, at first sight, to formalize the
idea that it should be infeasible for a polynomially bounded adversary to learn
any partial information about the plaintext from the ciphertext. However, it can
be shown that the formalization of this intuitive idea, namely
semantic security
,
is actually equivalent to the above definition based on indistinguishability. Intu-
itively, this is clear if the messages to be encrypted consist of a single bit, and this
basic idea can be used to show that indistinguishability implies that no single
bit of a randomly chosen plaintext can be guessed with probability significantly
better than 1
2 (see [109, Claim 3.10]). This is not yet semantic security but is
a step in this direction. See [109, 3.2.2] for a discussion of this and [87] for a
proof of the equivalence between the two definitions.
2. The quantity
/
PrivK
ind-eav
A
,
E
|
Pr
(
(
n
)
=
1
)
−
1
/
2
|
is often called the
advantage
of the adversary
. The absolute value in the definition makes sense because
it ensures that the advantage is always non-negative. Then it can be said that
the system has indistinguishable encryptions when the advantage of any PPT
adversary is negligible as a function of the security parameter. This is clear
because if Pr
A
PrivK
ind-eav
A,E
(
(
n
)
=
1
)<
1
/
2 and
A
has non-negligible advantage,
A
may be constructed by reversing the output of
then a new adversary
A
,so
A
has non-negligible advantage too.
3. It is customary to use the notation XXX-YYY to denote a security notion,
where XXX refers to the adversary goal—usually, the adversary will try to
break indistinguishability—and YYY to its capabilities. With this convention,
indistinguishability to eavesdroppers is often denoted IND-EAV.
PrivK
ind-eav
that Pr
(
A
,
E
(
n
)
=
1
)>
1
/
2 and
Exercise 3.19
prove that the one-time pad has indistinguishable encryptions in the
presence of an eavesdropper.More generally, prove that perfect secrecy for an encryp-
tion scheme
E
=
(
Gen
,
Enc
,
Dec
)
can be characterized in terms of an experiment
PrivK
ind-eav
A,E
similar to the one in Definition 3.21 except for the fact that now the
