Roughly speaking, encryption is the problem of how two parties can communicate in secret in the
presence of an eavesdropper. The main goals of this chapter are to develop a meaningful and useful
definition of what we are trying to achieve, and to take some first steps in actually achieving it.
Suppose Alice and Bob share a secret key k, and Alice wants to transmit a message m to Bob over
a network while maintaining the secrecy of m in the presence of an eavesdropping adversary. This
chapter begins the development of basic techniques to solve this problem. Besides transmitting a
message over a network, these same techniques allow Alice to store a file on a disk so that no one
with access to the disk can read the file, but Alice herself can read the file at a later time.
We should stress that while the techniques we develop to solve this fundamental problem are
important and interesting, they do not by themselves solve all problems related to “secure communication.”
• The techniques only provide secrecy in the situation where Alice transmits a single message
per key. If Alice wants to secretly transmit several messages using the same key, then she
must use methods developed in Chapter 5.
• The techniques do not provide any assurances of message integrity: if the attacker has the
ability to modify the bits of the ciphertext while it travels from Alice to Bob, then Bob may
not realize that this happened, and accept a message other than the one that Alice sent. We
will discuss techniques for providing message integrity in Chapter 6.
• The techniques do not provide a mechanism that allow Alice and Bob to come to share a
secret key in the first place. Maybe they are able to do this using some secure network (or
a physical, face-to-face meeting) at some point in time, while the message is sent at some
later time when Alice and Bob must communicate over an insecure network. However, with
an appropriate infrastructure in place, there are also protocols that allow Alice and Bob to
exchange a secret key even over an insecure network: such protocols are discussed in Chapters
20 and 21.
2.2 Shannon ciphers and perfect security
2.2.1 Definition of a Shannon cipher
The basic mechanism for encrypting a message using a shared secret key is called a cipher (or
encryption scheme). In this section, we introduce a slightly simplified notion of a cipher, which we
call a Shannon cipher.
A Shannon cipher is a pair E = (E,D) of functions.
• The function E (the encryption function) takes as input a key k and a message m (also
called a plaintext), and produces as output a ciphertext c. That is,
c = E(k,m),
and we say that c is the encryption of m under k.
• The function D (the decryption function) takes as input a key k and a ciphertext c, and
produces a message m. That is,
m = D(k, c),
and we say that m is the decryption of c under k.
• We require that decryption “undoes” encryption; that is, the cipher must satisfy the following
correctness property: for all keys k and all messages m, we have
D(k, E(k, m) ) = m.
To be slightly more formal, let us assume that K is the set of all keys (the key space),Mis the
set of all messages (the message space), and that C is the set of all ciphertexts (the ciphertext
space). With this notation, we can write:
E : K⇥M!C,
D : K⇥C !M.
Also, we shall say that E is defined over (K,M, C).
Suppose Alice and Bob want to use such a cipher so that Alice can send a message to Bob.
The idea is that Alice and Bob must somehow agree in advance of a key k 2 K. Assuming this is
done, then when Alice wants to send a message m 2Mto Bob, she encrypts m under k,
obtaining
the ciphertext c = E(k,m) 2 C, and then sends c to Bob via some communication network.
Upon
receiving c, Bob decrypts c under k, and the correctness property ensures that D(k, c) is the same
as Alice’s original message m. For this to work, we have to assume that c is not tampered with in
transit from Alice to Bob. Of course, the goal, intuitively, is that an eavesdropper, who may obtain
c while it is in transit, does not learn too much about Alice’s message m — this intuitive notion is
what the formal definition of security, which we explore below, will capture.
In practice, keys, messages, and ciphertexts are often sequences of bytes. Keys are usually
of some fixed length; for example, 16-byte (i.e., 128-bit) keys are very common. Messages and
ciphertexts may be sequences of bytes of some fixed length, or of variable length. For example, a
message may be a 1GB video file, a 10MB music file, a 1KB email message, or even a single bit
encoding a “yes” or “no” vote in an electronic election.
