Cryptography Reference
In-Depth Information
1
1
1
3
1
2
.
and, from this, we obtain that now the scheme is perfectly secret because:
•
(
=
)
=
2
·
4
+
2
·
4
=
Pr
C
1
1
2
•
Pr
(
C
=
0
|
M
=
0
)
=
Pr
(
K
=
0
)
=
=
Pr
(
C
=
0
).
1
2
•
Pr
(
C
=
0
|
M
=
1
)
=
Pr
(
K
=
1
)
=
=
Pr
(
C
=
0
).
1
2
•
(
=
|
=
)
=
(
=
)
=
=
(
=
).
Pr
C
1
M
0
Pr
K
1
Pr
C
1
1
2
•
Pr
(
C
=
1
|
M
=
1
)
=
Pr
(
K
=
0
)
=
=
Pr
(
C
=
1
).
In any encryption scheme with message space
M
and ciphertext space
C
the
inequality
holds because the encryption functions
Enc
k
:
M
→
C
are injective (otherwise unique decryption would not be possible). If, moreover, the
scheme has perfect secrecy then we can show that another size limitation holds: the
key space must be at least as large as the message space.
|
C
|≥|
M
|
Proposition 3.1
If
(
Gen
,
Enc
,
Dec
)
is a perfectly secret encryption scheme with
message space
M
and key space
K
, then
|
K
|≥|
M
|
.
Proof
Let
c
be a ciphertext that occurs with nonzero probability. Since the scheme
is perfectly secret we have that, for every
m
∈
M
,Pr
(
C
=
c
|
M
=
m
)
=
Pr
(
C
=
c
0. Thus the probability that
m
encrypts to
c
is positive and this means that
there exists a key
k
)>
c
. Similarly, if
m
,
m
∈
K
such that
Enc
k
(
m
)
=
∈
M
=
m
,
we have a key
k
k
for,
otherwise,
Enc
k
would not be injective. Thus we can define an injective map from
M
m
)
=
∈
K
such that
Enc
k
(
c
and this implies that
k
=
to
K
by assigning to
m
akey
k
such that
Enc
k
(
m
)
=
c
and this proves the
proposition.
In Example 3.1.1 we have seen an encryption scheme that not only satisfies the
inequality in the preceding proposition but, in fact, it also satisfies
M
=
K
=
C
without being perfectly secret. However, in Example 3.1.2 we have also seen that if
we modify this scheme by making the probability distribution on
K
uniform, then we
obtain a perfectly secret encryption scheme. This is a particular case of the following
celebrated theorem of Shannon:
Theorem 3.1
(Shannon's Theorem)
Let
(
Gen
,
Enc
,
Dec
)
be an encryption scheme
such that
|
M
|=|
C
|=|
K
|
. Then the system has perfect secrecy if and only if the
following conditions hold:
(i)
The probability distribution on
K
is uniform.
(ii) For every m
∈
M
and every c
∈
C
, there exists a unique k
∈
K
such that
Enc
k
(
m
)
=
c.
Proof
Suppose that the scheme is perfectly secret. As in the proof of Proposition
3.1 we see that, for each
c
∈
C
and each
m
∈
M
there exists at least one key
k
∈
K
such that
Enc
k
(
m
)
=
c
.Ifwefix
m
, this means that
|{
Enc
k
(
m
)
}
k
∈
K
|≥|
C
|
and,
