Cryptography Reference
In-Depth Information
=
H
(
K
|
C
)+
H
(
M
|
CK
)
=
H
(
K
|
C
)
≤
H
(
K
)
In the first line, we employ the definition of perfect secrecy, namely that
H
(
M
)=
H
(
M
C
). In the second line, we
use the basic expansion rule for uncertainties (generalized to conditional uncertain-
ties). In the third line, we use the fact that
H
(
M
|
C
) and the fact that
H
(
MK
|
C
) is at least
H
(
M
|
CK
)=0for any symmetric
encryption system (i.e., it is required that a plaintext can be uniquely decrypted if a
ciphertext and a key are known). The inequality stated in the theorem then follows
immediately.
|
A practical encryption scheme that can be proven information-theoretically
secure (using, for example, Shannon's Theorem) was proposed by Gilbert Vernam in
1917 [26].
Vernam's one-time pad
consists of a randomly generated and potentially
infinite stream of key bits
k
=
k
1
,k
2
,k
3
,...
that is shared between the sender and
the recipient. To encrypt the plaintext message
m
=
m
1
,m
2
,...,m
n
, the sender
adds each bit
m
i
(1
≤
i
≤
n
) modulo 2 with a key bit
k
i
:
c
i
=
m
i
⊕
k
i
for
i
=1
,...,n
The ciphertext
c
=
c
1
,c
2
,c
3
,...,c
n
is sent from the sender to the recipient.
It is then up to the recipient to recover the plaintext by adding each ciphertext bit
c
i
modulo 2 with the corresponding key bit
k
i
:
p
i
=
c
i
⊕
k
i
=(
p
i
⊕
k
i
)
⊕
k
i
=
p
i
⊕
(
k
i
⊕
k
i
)=
p
i
⊕
0=
p
i
for
i
=1
,...,n
Consequently, the plaintext is recovered by adding each ciphertext bit with
the corresponding key bit. Vernam's one-time pad is
perfect
when the key is truly
random and used only once. In this case, the ciphertext gives no information about
the plaintext.
In addition to perfect security as expressed in Definition 10.1, Shannon also
introduced the notion of ideal security. The idea of ideal security is that an adversary
does not get any information about a key from a ciphertext of arbitrary length.
Alternatively speaking, no matter how much ciphertext an adversary knows, the
entropy of
K
is not decreased. This idea is captured and formally expressed in
Definition 10.2.
