Cryptography Reference
In-Depth Information
scheme used, and we consider probability distributions defined on these sets and
random variables
M
,
,
K
that represent the values of the message, the ciphertext
and the key. The probability distribution over
C
will be simply the one defined
by running a probabilistic algorithm that outputs the key and it will usually be the
uniform distribution although this need not be the case. For
k
K
∈
K
we denote, as
usual, by Pr
(
K
=
k
)
the probability that the chosen key is equal to
k
. Similarly,
if
m
is the probability that the message is equal to
m
, and the
probability distribution on
∈
M
,Pr
(
M
=
m
)
may vary depending on the parties using the scheme,
the language used and so on. Thus we will allow an arbitrary distribution for the
messages and it is reasonable to assume that the adversary might even have some
knowledge about it or, at least, that some specific messages have a much larger
probability of being sent than others.
We will also assume that the probability distributions on
M
are indepen-
dent, which is reasonable bearing in mind that the key is chosen before knowing
what the message will be. For
c
K
and
M
denote the probability that
the ciphertext is
c
and we observe that its distribution on
∈
C
we let Pr
(
C
=
c
)
C
is determined by the
distributions on
because the probability that, for a given key
k
and a given
plaintext
m
, the ciphertext is equal to
c
is just the probability that the decryption of
c
is the plaintext. Therefore, if
Dec
k
is the decryption algorithm corresponding to the
key
k
,Pr
K
and
M
)
=
k
∈
K
.
To define perfect secrecy we may assume that Eve knows the probability dis-
tribution on
(
C
=
c
Pr
(
K
=
k
)
Pr
(
M
=
Dec
k
(
c
))
and observes a ciphertext being sent by Alice to Bob. The idea is
then that this observation should not have any effect on the knowledge that Eve
has about the message sent, i.e., that the probability that a given message
m
was
sent given the ciphertext observed by Eve is the same as the a priori probability
that
m
would be sent. This captures the idea that Eve, on observing the ciphertext,
learns nothing about the message sent even if she has unbounded computational
power.
M
Definition 3.1
An encryption scheme
(
Gen
,
Enc
,
Dec
)
with message space
M
and
ciphertext space
C
has
perfect secrecy
if, for every probability distribution on
M
,
every message
m
∈
M
, and every ciphertext
c
∈
C
for which Pr
(
C
=
c
)>
0,
Pr
(
M
=
m
|
C
=
c
)
=
Pr
(
M
=
m
).
The concept of perfect secrecy is also called
unconditional security
and hence in
this case we can also say that the encryption scheme is
unconditionally secure
or
secure in the information-theoretic sense. Note that the condition Pr
0
above is a technical one required for the conditional probability appearing in the
definition to be defined. We will assume in the sequel that the probability distributions
on
(
C
=
c
)>
assign nonzero probabilities to all the elements of these sets, so that we
always have Pr
M
and
C
(
=
)>
(
=
)>
0 (this is only amatter of convenience
and all the results can be adapted to the case of arbitrary distributions, at the cost of
a longer wording). With this convention we note that it follows from Bayes' formula
M
m
0 and Pr
C
c
