Alice uses a biased coin to create a onetime pad to encrypt

Alice uses a biased coin to create a one-time pad to encrypt a message m of 1 bit. The coin comes up 1 (Heads) 60% of the times and 0 (Tails) 40% of the times. Alice sends 0 as a message 75% of the times and 1 as a message 25% of the times. All of this is publicly known. Eve sees cipher c = 1. What was the probability that m = 1?

Solution

An encryption scheme (E, D) is perfectly secret if there for every set M {0, 1} ` of plaintexts, and for every strategy used by Eve, if we choose at random m M and a random key k {0, 1} n, then the probability that Eve guesses m after seeing Ek(m) is at most 1/|M|.

In particular, if we encrypt either “Yes” or “No” with probability 1/2, then Eve won’t be able to guess which one it is with probability better than half. In fact, that turns out to be the heart of the matter:

Two to Many Theorem: An encryption scheme (E, D) is perfectly secret if and only if for every two distinct plaintexts {m0, m1} {0, 1} ` and every strategy used by Eve, if we choose at random b {0, 1} and a random key k {0, 1} n, then the probability that Eve guesses mb after seeing Ek(mb) is at most 1/2.

Proof: The “only if” direction is obvious— this condition is a special case of the perfect secrecy condition for a set m of size 2

The “if” direction is trickier. We need to show that if there is some set M (of size possibly much larger than 2) and some strategy for Eve to guess (based on the ciphertext) a plaintext chosen from M with probability larger than 1/|M|, then there is also some set M0 of size two and a strategy Eve0 for Eve to guess a plaintext chosen from M0 with probability larger than 1/2.

Let’s fix the message m0 for example to be the all zeroes message. Since Eve(Ek(m0)) is a fixed string, if we pick a random m1 from M then it holds that

Pr[Eve(Ek(m0)) = m1] 1/|M|

while under our assumption, on average it holds that

Pr[Eve(Ek(m1)) = m1] > 1/|M|

Thus in particular, due to linearity of expectation, there exists some m1 satisfying Pr[Eve(Ek(m1)) = m1] > Pr[Eve(Ek(m0)) = m1] .

But this can be turned into an attacker Eve0 such that the probability that Eve0 (Ek(mb)) = mb is larger than 1/2. Indeed, we can define Eve0 (c) to output m1 if Eve(c) = m1 and otherwise output a random message in {m0, m1}. The probability that Eve0 (c) equals m1 is higher when c = Ek(m1) than when c = Ek(m0), and since Eve0 outputs either m0 or m1, this means that the probability that Eve0 (Ek(mb)) = mb is larger than 1/2 (Can you see why?) QED.

Exercise: Another equivalent condition for perfect secrecy is the following: (E, D) is perfectly secret if for every plaintexts m, m0 {0, 1} ` , the two random variables {Ek(m)} and {Ek0 (m0 )} (for randomly chosen keys k and k 0 ) have precisely the same distribution.

So, perfect secrecy is a natural condition, and does not seem to be too weak for applications, but can it actually be achieved? After all, the condition that two different plaintexts are mapped to the same distribution seems somewhat at odds with the condition that Bob would succeed in decrypting the ciphertexts and find out if the plaintext was in fact m or m0 . It turns out the answer is yes! For example, the table below details a perfectly secret encryption for two bits.

Table 1: A perfectly secret encryption scheme with 2 bit keys, plaintexts, and ciphertexts; the rows are indexed by possible ciphertexts, the columns indexed by possible plaintexts, and the (c, m) location of the matrix corresponds to the key that maps m to c.

=============================================
Plain: 00 01 10 11
Cipher: 00 00 01 10 11

01 01 00 11 10
10 10 11 00 01
11 11 10 01 00
==============================================

In fact, this can be generalized to any number of bits:

Theorem (One time pad, Vernam 1917): For every n, there is a perfectly secret encryption (E, D) with plaintexts of n bits, where the key size and the ciphertext size is also n.

Proof: The encryption scheme is actually very simple - to encrypt a message m {0, 1} n with key k {0, 1} n, we output Ek(m) = m k where is the exclusive or (XOR) operation. That is, m k is a vector in {0, 1} n such that (m k)i = ki + mi (mod 2). Decryption works identically - Dk(c) = c k. It is not hard to use the associativity of addition (and in particular XOR) to verify that Dk(Ek(m)) = (m k) k = m (k k) = m where the last equality follows from k k = 0n (can you see why?). Now we claim that for every message m {0, 1} n, the distribution Ek(m) for a random k is the uniform distribution Un on {0, 1} n. By the exercise above, this implies that the scheme is perfectly secret, since for every two messages m, m0 the distributions {Ek(m)} and {Ek0 (m0 )} will both be equal to the uniform distribution. To prove the claim we need to show that for every y {0, 1} n, Pr[Ek(m) = y] = 2n where this probability is taken over the choice of a random k {0, 1} n. Now note that Ek(m) = y if and only if m k = y or, equivalently, k = m y. Since k is chosen uniformly at random in {0, 1} n, the probability that it equals m y is exactly 2 n QED.

Note: Importance of using the one time pad only once:

The “one time pad” is a name analogous to the “point away from yourself gun”- the name suggests the fatal mistake people often end up doing. Perhaps the most dramatic example of the dangers of “key reuse” is the Venona Project. The Soviets have used the one-time pad for their confidential communication since before the 1940’s (WHEN?), and in fact even before Shannon apparently the U.S. intelligence already knew that it is in principle “unbreakable” in 1941 (see page 32 in the Venona document )). However, it turned out that the hassles of manufacturing so many keys for all the communication took its toll on the Soviets and they ended up reusing the same keys for more than one message, though they tried to use them for completely different receivers in the (false) hope that this wouldn’t be detected. The Venona project of the U.S. Army was founded in February 1943 by Gene Grabeel- a former highschool teacher from Madison Heights, Virgnia and Lt. Leonard Zukbo. In October 1943, they had their breakthrough when it was discovered that the Russians are reusing their keys (credit to this discovery is shared by Lt. Richard Hallock, Carrie Berry, Frank Lewis, and Lt. Karl Elmquist, see page 27 in the document). In the 37 years of its existence, the project has resulted in a treasure chest of intelligence, exposing hundreds of KGB agents and Russian spies in the U.S. and other countries, including Julius Rosenberg, Harry Gold, Klaus Fuchs, Alger Hiss, Harry Dexter White and many others.