Questions: Information-Theoretic Security

Question 1

Shannon proved that any perfectly secret cipher must have a key at least as long as the message. Why does this make perfect secrecy impractical for most applications?

• A. Long keys are computationally expensive to generate
• B. The key distribution problem: securely sharing a key as long as the message is essentially as hard as securely sharing the message itself — you have not reduced the problem, only shifted it to key distribution
• C. Long keys increase encryption latency
• D. Perfect secrecy is only possible for binary messages

Answer: (B)

If you need a key as long as the message, and the key must be shared secretly between sender and receiver before communication, then the key distribution problem is as hard as the original communication problem. This is why most real systems use computational security (AES, RSA, etc.) with short keys: they are secure under complexity assumptions but could theoretically be broken with enough computation. The one-time pad remains used only in extreme cases (diplomatic hotlines, some military communications) where key pre-distribution is feasible.

Question 2

In Wyner's wiretap channel, the eavesdropper receives a noisier version of the signal than the legitimate receiver. Positive secrecy rates are achievable even without a pre-shared key.

• T. True
• F. False

Answer: True

This is Wyner's remarkable result: when the eavesdropper's channel is degraded relative to the legitimate receiver's, the sender can transmit at a positive rate that is perfectly secret from the eavesdropper — with NO pre-shared key. The secrecy capacity is C_s = C_main - C_eavesdropper (the difference in channel capacities). The sender uses random coding to create confusion at the eavesdropper while maintaining reliable communication with the legitimate receiver. The extra noise on the eavesdropper's channel is the source of secrecy.

Question 3

Explain the fundamental difference between information-theoretic security and computational security, and why the distinction matters in the era of quantum computing.

Model answer: Information-theoretic security (like the one-time pad) guarantees I(M;C) = 0 — the ciphertext reveals literally no information about the message, regardless of the adversary's computational power. Computational security (like AES or RSA) guarantees that breaking the cipher requires solving a problem believed to be computationally hard (factoring, discrete log). If the hardness assumption fails — due to algorithmic breakthroughs or quantum computers — computational security breaks. Quantum computers threaten RSA and ECC via Shor's algorithm, making computational security time-limited. Information-theoretic security is immune to this: even a quantum adversary with unlimited resources cannot break it, because the security comes from information theory, not computational hardness.

This is why quantum key distribution (QKD) is valuable: it provides information-theoretically secure key distribution using quantum mechanics. Combined with the one-time pad, QKD provides end-to-end unconditional security. However, the practicality debate continues — QKD requires special hardware and has range limitations, while post-quantum cryptographic algorithms provide computational security that is believed (but not proved) to resist quantum attacks.