Communication is the act of conveying information from a sender to a receiver. Secure communication refers to the problem of making the communication unavailable to anyone except the desired receiver. Secure communication is the oldest application of cryptography, and remains the centerpiece of cryptography to this day. After all, the word cryptography means “hidden writing” in Greek. So, secure communication is a natural place to start our study of cryptography.
History provides us with roughly 2000 years of attempts to secure sensitive communications in the presence of eavesdroppers. Despite the many brilliant minds that lived during this period of time, almost no useful concepts remain relevant to modern cryptography. In fact, it was not clear how to even formally define the goal of secure communication until the 1940s. The two modern definitions in use today were identified only in 1982 and 1990.
The only cryptographic method developed before 1900 that has stood the test of time is the one-time pad, which appears in some form in essentially every modern encryption scheme. In this chapter, we introduce the one-time pad and discuss its important characteristics. Along the way, we will start to get acclimated to cryptographic security definitions.
The cryptographic approach to secure communication is a tool known as encryption. Before discussing the specifics of one-time pad, we will first define what pieces comprise an encryption scheme in general.
A symmetric-key encryption (SKE) scheme consists of the following algorithms:
We call ? the key space, ? the message space, and ? the ciphertext space of the scheme. When we use a single variable — say, Σ — to refer to the scheme as a whole and distinguish one scheme from another, we write Σ.KeyGen, Σ, Enc, Σ.Dec, Σ.? , Σ, ?, and Σ.? to refer to its components.
The scheme satisfies correctness if for all k ∈ ? and all m ∈ ?,
Pr[Dec(k,Enc(k,m)) = m] = 1,where the probability is over the random choices (if any) made by Enc.
Encryption addresses the problem of secure communication in a very natural way:
Now with a clear definition of encryption syntax, we can give the specifics of one-time pad (OTP) encryption. The idea of one-time pad had historically been attributed to Gilbert Vernam, a telegraph engineer who patented the scheme in 1919. In fact, one-time pad is sometimes called “Vernam’s cipher.” However, an earlier description of one-time pad was recently discovered in an 1882 text on telegraph encryption by banker Frank Miller. 1
1 Steven M. Bellovin: “Frank Miller: Inventor of the One-Time Pad.” Cryptologia 35 (3), 2011.
Here are a few observations about one-time pad to keep in mind:
The correctness property of one-time pad follows from the properties of XOR listed in Section 0 . For all k, m ∈ λ , we have:
Consider using OTP encryption to encrypt the 20-bit plaintext m under the 20-bit key k given below:
The result is ciphertext c. Decrypting c using the same key k results in the original m:
A general-purpose security definition for encryption will be discussed in the next chapter. For now, we will show a simple but important property that one-time pad satisfies, and argue that it has some relevance to secure communication.
Imagine an eavesdropper who sees a single one-time pad ciphertext. The following algorithm describes what such an adversary will see if the plaintext happens to be m:
Since this algorithm involves random choices, its output on a particular m is not a fixed value but a random variable that follows some distribution. The important property of one-time pad has to do with this distribution:
For every m ∈ λ , the output distribution CTXT(m) is the uniform distribution over λ .
Before proving the claim, let’s break down why it should have any relevance to security:
We can now say that, by intercepting a single ciphertext, an eavesdropper sees a uniform sample from λ .
At this point you might be suspicious that I’m trying to talk you into a paradox: on one hand, the scheme satisfies the correctness property, so c can always be decrypted to reliably obtain m. On the other hand, I want you to be convinced that c carries no information whatsoever about m!
The answer to this riddle is that correctness is defined from the point of view of someone who knows the key k. Claim 1.3 is about the output distribution of the CTXT subroutine, which doesn’t contain k (see Exercise 1.6 ). In short, if you know k, then c can be decrypted to obtain m; if you don’t know k, then c might as well be uniformly distributed.
We now prove the claim:
Fix m,c ∈ λ ; what is the probability that CTXT(m) produces output c? That event happens only when
The equivalence follows from the properties of XOR given in Section 0 . We have fixed m and c, and hence fixed the right-hand side of the last equation. In other words, after fixing m and c, there is only one value of k that encrypts m to c (that value being m ⊕ c). Since CTXT chooses k uniformly from ? = λ , the probability of choosing the particular value k = m ⊕ c is 1/2 λ .
The keys in one-time pad are as long as the plaintexts they encrypt. This is more or less unavoidable; see Exercise 2.4 . Additionally, one-time pad keys can be used to encrypt only one plaintext (hence, “one-time” pad); see Exercise 1.5 . Indeed, we can see that the CTXT subroutine in Claim 1.3 provides no way for a caller to guarantee that two plaintexts are encrypted with the same key, so it is not clear how to use Claim 1.3 to argue about what happens in one-time pad when keys are reused in this way.
Despite these limitations, one-time pad is the conceptual core for all forms of encryption we will discuss in this course. The only way to hide information, throughout all of cryptography, is to mask it with a uniformly chosen one-time pad.
1.1: The one-time pad encryption of plaintext “mario” (written in ASCII) under key k is:
1000010000000111010101000001110000011101What is the one-time pad encryption of “luigi” under the same key?
1.2: Alice is using one-time pad and notices that when her key is the all-zeroes string k = 0 λ , then Enc(k, m) = m and her message is sent in the clear! To avoid this problem, she decides to modify KeyGen to choose a key uniformly from λ \ λ >. In this way, her plaintext is never sent in the clear.
Does Claim 1.3 still hold with respect to this modified one-time pad? Prove or disprove.
1.3: When Alice encrypts the key k itself using one-time pad, the ciphertext will always be the all-zeroes string! So if an eavesdropper sees the all-zeroes ciphertext, she learns that Alice encrypted the key itself. Does this contradict Claim 1.3 ? Why or why not?
1.4: Describe the flaw in this argument:
Consider the following attack against one-time pad: upon seeing a ciphertext c, the eavesdropper tries every k ∈ ? until she has found the one that was used, at which point she outputs the plaintext m. This contradicts the argument in Section 1.3 that the eavesdropper can obtain no information about m by seeing the ciphertext.
1.5: Suppose Alice encrypts two plaintexts m and m’ using one-time pad with the same key k. What information about m and m’ is leaked to an eavesdropper by doing this (assume the eavesdropper knows that Alice has reused k)? Be as specific as you can!
1.6: Suppose we modify the subroutine discussed in Claim 1.3 so that it also returns k:
Is it still true that for every m, the output of CTXT’ (m) is distributed uniformly in ( λ ) 2 ?
1.7: In this problem we discuss the security of performing one-time pad encryption twice:
(a). Consider the following subroutine that models the result of applying one-time pad encryption with two independent keys:
Show that the output of this subroutine is uniformly distributed in λ
(b). What security is provided by performing one-time pad encryption twice with the same key?
1.8: Show that the output of the following subroutine is uniformly distributed in ℤn:
