Classic vs. Computational Cryptography: A Brief History

TL;DR

Pre-1949 cryptography (Caesar, Enigma) implemented substitution and permutation physically, with security resting on keeping the mechanism secret. Claude Shannon's 1949 paper Communication Theory of Secrecy Systems reframed encryption as a mathematical object and defined perfect secrecy: a cipher is perfectly secret iff $\Pr[M=m \mid C=c] = \Pr[M=m]$ for all messages and ciphertexts, which forces $H(K) \geq H(M)$ — the key must carry at least as much entropy as the message. This is achievable (one-time pad) but impractical at scale. Modern cryptography (RSA, ECC, AES) abandons unconditional security for computational security: secrecy holds only against adversaries bounded to polynomial-time computation, resting on the assumed hardness of specific math problems. That assumption is what quantum algorithms attack — see Shor's Algorithm.

Physical Cryptography: Substitution and Permutation

Classical ciphers implement two operations: substitution (replace a symbol with another) and permutation (reorder symbols). Both are expressible as group-theoretic operations over a finite alphabet.

The Caesar cipher is modular addition over $\mathbb{Z}_{26}$:

The key space is $|\mathbb{Z}_{26}| = 26$, trivially exhaustible. Enigma generalizes this to a composition of permutations — rotors, a reflector, and a plugboard — applied per keystroke:

Each $\pi_i \in S_{26}$, the symmetric group on 26 elements. The rotor state advances with every character, so the effective permutation changes each step. This inflates the key space to roughly $10^{23}$, but the security model is unchanged from Caesar's: an attacker who recovers the mechanism (rotor wiring, plugboard, initial state) recovers everything. There is no notion of security that survives disclosure of the algorithm — only of the key, and only informally.

The Conceptual Break: Shannon, 1949

Claude Shannon's Communication Theory of Secrecy Systems replaced "hard to break" with a formal, measurable claim. It defines a cipher as a triple of random variables — plaintext $M$, ciphertext $C$, key $K$ — and asks how much information $C$ leaks about $M$.

Entropy quantifies uncertainty over a random variable $X$ with distribution $p$:

Perfect secrecy is defined as: observing the ciphertext changes nothing about the attacker's belief in the plaintext.

Equivalently, mutual information between plaintext and ciphertext is zero: $I(M; C) = 0$. This is an unconditional, information-theoretic guarantee — it holds against an adversary with unbounded computation and unbounded time.

The one-time pad meets the bound, and defines its cost

The one-time pad, $C = M \oplus K$ with $K$ uniform and independent of $M$, achieves $I(M;C)=0$: for any fixed $c$, $M = C \oplus K$ is uniformly distributed over $\mathcal{M}$ regardless of $c$, since $K$ is uniform and independent.

Shannon also proved the converse: perfect secrecy requires

which for uniform variables means $|\mathcal{K}| \geq |\mathcal{M}|$ — the key space must be at least as large as the message space, and in practice a fresh, uniform key at least as long as the message, never reused. This is a hard information-theoretic floor, not an engineering inconvenience: no algorithmic cleverness lowers it. It is also why the one-time pad, despite being provably unbreakable, never scaled — key distribution costs as much as the message itself.

From Unconditional to Computational Security

Shannon's bound makes information-theoretic secrecy impractical for arbitrary-length communication with a short, reusable key. Modern cryptography drops the unconditional requirement and substitutes a computational one: secrecy holds only against adversaries restricted to probabilistic polynomial time (PPT) in a security parameter $\lambda$.

Security is now stated as indistinguishability under a bounded adversary $\mathcal{A}$, with advantage required to vanish faster than any inverse polynomial in $\lambda$ (a negligible function):

This guarantee is conditional: it holds if some underlying problem — integer factorization for RSA, the elliptic-curve discrete logarithm for ECC — has no PPT algorithm. Unlike $H(K) \geq H(M)$, this is not a proven lower bound; it is an unproven hardness assumption, empirically unbroken by classical algorithms after decades of cryptanalysis.

That distinction is exactly the crack a quantum adversary exploits. Shor's algorithm does not violate any information-theoretic law — it solves factoring and discrete log in polynomial time on a different model of computation, invalidating the assumption computational security was built on without touching Shannon's unconditional bound at all. See Shor's Algorithm for the mechanism.