A colleague proposes using a one-time pad but reusing the same key for two different messages to save on key distribution. Why does this completely destroy the security guarantee?
Think about your answer, then reveal below.
Model answer: If two messages m1 and m2 are encrypted with the same key k, the attacker can XOR the two ciphertexts: c1 XOR c2 = (m1 XOR k) XOR (m2 XOR k) = m1 XOR m2. The key cancels out, leaving the XOR of two plaintexts. With known plaintext statistics (letter frequencies, common words), the attacker can often recover both messages. Reuse converts the scheme from information-theoretically secure to trivially breakable.
The one-time pad's security depends entirely on each key bit being used exactly once. Reuse creates algebraic relationships between ciphertexts that eliminate the key from the equation. This was exploited in practice during the VENONA project, where Soviet intelligence reused one-time pad pages, allowing US cryptanalysts to decrypt thousands of messages over decades.
Question 2 Multiple Choice
Shannon proved that any perfectly secret encryption scheme must have a key space at least as large as the message space. What is the intuitive reason this bound is tight?
ASmaller key spaces mean the encryption algorithm runs faster, which attackers can exploit
BIf the key space is smaller than the message space, multiple messages must share a key, creating collisions that leak information
CIf the key space is smaller, some plaintexts produce the same ciphertext regardless of the key, so observing a ciphertext eliminates those plaintexts and changes the posterior
DShannon's proof relies on quantum mechanics, which limits key compression
With fewer keys than messages, the set of possible plaintexts consistent with a given ciphertext (the set {D_k(c) : k in K}) cannot cover the entire message space. Any plaintext outside this set has zero posterior probability given the ciphertext — the attacker knows it was not sent. This changes the posterior from the prior, violating perfect secrecy. The one-time pad achieves the bound exactly: each ciphertext is consistent with every possible plaintext of the same length, because for each (m, c) pair there exists exactly one key k = m XOR c.
Question 3 True / False
Perfect secrecy means no adversary — regardless of computational power — can learn anything about the plaintext from the ciphertext.
TTrue
FFalse
Answer: True
This is the defining strength of information-theoretic security: the guarantee holds against adversaries with unlimited computational resources, unlimited time, and arbitrary algorithms. No amount of computation changes the fact that every plaintext is equally consistent with the observed ciphertext. This contrasts with computational security, where the guarantee holds only against polynomially bounded adversaries. The tradeoff is that information-theoretic security demands impractically long keys.
Question 4 Multiple Choice
A 256-bit AES key can encrypt terabytes of data securely, while a one-time pad key must be as long as the data. Why doesn't this contradict Shannon's theorem?
AAES actually achieves perfect secrecy through a more efficient algorithm
BShannon's theorem only applies to substitution ciphers, and AES uses a different structure
CAES does not achieve perfect secrecy — it achieves computational security, which is a weaker guarantee that holds only against bounded adversaries. Shannon's theorem says this tradeoff is unavoidable
DAES keys are expanded internally to match the message length, satisfying Shannon's bound
Shannon's theorem is an impossibility result: perfect secrecy requires |K| >= |M|, period. AES sidesteps this by abandoning perfect secrecy in favor of computational security — no efficient algorithm can distinguish AES ciphertexts from random, but an adversary with unlimited computation could in principle break it. This is the foundational compromise of modern cryptography: accept a weaker (but still extremely strong) security guarantee in exchange for practical key sizes.
Question 5 True / False
If you encrypt a 1000-bit message with a truly random 1000-bit one-time pad key, the mutual information between the plaintext and ciphertext is zero.
TTrue
FFalse
Answer: True
Zero mutual information is equivalent to statistical independence between plaintext and ciphertext, which is equivalent to Shannon's definition of perfect secrecy. Observing the ciphertext provides literally no information about the plaintext — the posterior equals the prior. This is the strongest possible encryption guarantee and the formal content of 'the ciphertext reveals nothing.'