Cryptography Reference
In-Depth Information
,
!
!
G
Figure 10.16
A randomized symmetric encryption system.
keys are equiprobable). In either case, it is reasonable to assume that
M
and
K
are independent (random variables). In addition to
M
and
K
, there is a third
random variable
C
that is distributed according to
P
C
:
+
. This random
variable models the ciphertext, and hence its probability distribution is completely
determined by
P
M
and
P
K
. The random variable
C
is the one that a passive attacker
will recognize, and—based on its analysis—he or she will try to derive information
about
M
or
K
. More specifically, he or she will try to find plaintext messages (or
keys) that are more likely than others.
If an adversary is able to eavesdrop on a communications line and analyze the
ciphertexts transmitted on it, he or she is also able, in principle at least, to determine
the
a posteriori
probabilities of the various plaintext messages. If these probabilities
are equal to the
apriori
probabilities of the plaintext messages, then the symmetric
encryption system is said to provide perfect secrecy. In this case, intercepting the
ciphertext(s) has given the adversary no information about the plaintext message(s)
actually transmitted. This means that the a posteriori probability of a plaintext
message, given that a ciphertext is observed, is identical to the a priori probability
of the message (i.e., observing the ciphertext does not help the adversary). This idea
(to formally define a perfectly secure symmetric encryption system) is captured in
Definition 10.1.
C→
R
Definition 10.1 (Perfectly secure symmetric encryption system)
A symmetric en-
cryption system
(
P
,
C
,
K
,
E
,
D
)
is
perfectly secure
if
H
(
M
|
C
)=
H
(
M
)
for every
probability distribution
P
M
.
For example, let
M
=
{
0
,
1
}
with
P
M
(0) = 1
/
4 and
P
M
(1) = 3
/
4,
K
.Then
the probability that the plaintext 0 is encrypted with key
A
is
P
MK
(0
,A
)=
=
{
A, B
}
with
P
K
(
A
)=1
/
4 and
P
K
(
B
)=3
/
4,and
C
=
{
a, b
}
