Decoding Cryptography: From Perfect Secrecy to Computational Security
(Lion Roaring)…
In Blog 1, I set up Alice, Bob, and the postman. In the last blog, I broke three historical ciphers, watched the postman evolve from barbarian to statistician to pattern hunter, and arrived at three pillars of modern cryptography: formal definitions, precise assumptions, and rigorous proofs.
I ended with a mathematical definition that looked like this:
∀ m0, m1 ∈ M, ∀ c ∈ C: Pr[C = c | M = m0] = Pr[C = c | M = m1]
I'd promised to explain what this means, build something that achieves it, and then show why even that isn't enough.
More math incoming, I said. I wasn't kidding.
Computation Theory Primer
In math, vague words cause vague security, and vague security is no security at all.
Before I can define what "perfect" security means, I need three precise concepts. Think of them as the grammar we'll write the rest of modern cryptography in.
The Security Parameter
Imagine your encryption system has one master control: how hard it is to break. Crank it up, and the system becomes more secure, but also slower. Crank it down, and it's faster but weaker.
This control has a name: the security parameter, denoted n.
In symmetric encryption, n is typically the key length in bits (128, 256, etc). Once we fix n, everything becomes a function of it:
- The running time of Gen, Enc, Dec
- The running time of any adversarial algorithm
- The probability that an adversary breaks the scheme
By expressing everything as a function of n, we can talk about how quantities grow as we scale, rather than arguing about specific numbers. A question like "is this cipher secure?" becomes "does security hold for all sufficiently large n?"
Efficient Algorithms
Not all algorithms are created equal. An algorithm that takes n² steps is fine. One that takes n10 steps is annoying but feasible. One that takes 2n steps? For n = 256, that's too much.
An algorithm A is efficient (or polynomial-time) if there exists a polynomial p(·) such that for every input x, A terminates within p(|x|) steps, where |x| is the size of the input.
Polynomial: n2, n3, n10. Superpolynomial: 2n, n!, nn. The gap between these two worlds is the difference between efficient and inefficient.
Why does this matter? It gives us a sanity requirement on any encryption scheme.
Gen, Enc, and Dec must all run in polynomial time in n.
If decryption takes 2n steps, even Bob can't read his own messages. Not useful.
Pause. So far: n is the dial, polynomial time is "efficient". One more concept to go.
Negligible Functions
Intuitively, a negligible quantity is one that is "so small, we can safely ignore it." But how small is that? Smaller than 1/1000? Smaller than 1/1020? Those are concrete numbers. But negligible is a comparative term.
What I want is something that shrinks faster than the inverse of any polynomial.
A function f(n) is negligible if ∀ positive polynomials p(n), ∃ N such that ∀ n > N:
f(n) < 1/p(n)
Equivalently, ∀ positive constants c, ∃ N such that ∀ n > N, f(n) < n−c.
(These are equivalent because any polynomial p(n) is eventually dominated by nc for some c. So "smaller than 1/p(n) for every polynomial" means the same as "smaller than n-c for every constant c".)
The key observation: no polynomial function is ever negligible, no matter how large the exponent. But exponential (and sub-exponential) decay is negligible. There's a hard divide between these worlds.
A concrete sanity check. Take f(n) = 2−n. For any polynomial p(n) = nd, choose N = 2d. Then for all n > N:
2−n < 2−d log2 n = n−d = 1/p(n)
So 2−n is indeed negligible. ✓
Let's build some intuition.
| Function | Negligible? | Why |
|---|---|---|
| 2−n | ✓ Yes | Shrinks exponentially, easily beats any 1/p(n) |
| 2−√n | ✓ Yes | Slower, but still eventually beats every polynomial inverse |
| n−1000 | ✗ No | It is 1/p(n) for p(n) = n1000. It can't be less than 1/n1001 for all large n |
Why is n−10 not negligible? Pause on this, it's the most common mistake. The definition demands f(n) < 1/p(n) for every polynomial p. Pick p(n) = n11. Then 1/p(n) = n−11. Is n−10 < n−11 for all large n? No, n−10 > n−11 always. So it fails the definition.
Okay, enough definitions for now. Let's see why cryptographers actually care about these properties.
Why These Two Concepts Work Together
Here's the key insight: negligible functions behave exactly the way we'd hope when combined. Adding two negligible quantities doesn't suddenly make them significant. And multiplying a negligible quantity by something that grows polynomially still gives you something negligible.
Formally, if negl1(n) and negl2(n) are negligible, then the following holds.
- negl1(n) + negl2(n) is negligible
- p(n) · negl1(n) is negligible, for any polynomial p(n)
And if p1(n) and p2(n) are polynomial, then:
- p1(n) + p2(n) is polynomial
- p1(n) · p2(n) is polynomial
(Both negligible properties can be proved by contradiction. Assume the result is not negligible ⇒ there exists a polynomial it doesn't eventually go below ⇒ one of the originals wasn't negligible either. Contradiction.)
The second negligible property is the one I want you to remember. It means there is no amplification of a negligible advantage.
Here's a vivid way to see it. Toss n fair coins. The probability of all heads is (1/2)n = 2−n, which is negligible. Now repeat this experiment p(n) times, say n² times. What's the probability that at least one trial gives all heads?
Pr[∃ success in n² trials] ≤ n² · 2−n
(This is an upper bound via the union bound, not necessarily equality — two trials could both succeed on the same outcome.) By the closure property, n² · 2−n is still negligible. You could run the experiment a polynomial number of times and still have a negligible chance of the rare event occurring.
For cryptography, this implies that if an adversary's advantage in one attack is negligible, running the attack polynomially many times doesn't help. Attempts don't compound into a real threat.
Good. We have our vocabulary: efficient means polynomial time, negligible means shrinks faster than any inverse polynomial, and these two concepts compose cleanly. Now let's use them.
Perfect Secrecy
At the end of the last blog, I sketched a requirement. The ciphertext distribution should be completely independent of which message was encrypted. Now I can state this formally.
What Can Be Perfect?
What would it mean for a cipher to be truly, perfectly, unbreakably secure? Not "hard to break." Not "would take a million years." Not "probably safe." But perfectly secure, where the ciphertext reveals absolutely nothing about the plaintext, no matter how much time and computation the adversary has.
This is not a philosophical question. It has a precise mathematical answer, and it was given by Claude Shannon in 1949.
Shannon's Definition
Definition (Perfect Secrecy): An encryption scheme (Gen, Enc, Dec) over message space M has perfect secrecy if for every probability distribution over M, for every pair of messages m0, m1 ∈ M, and for every ciphertext c ∈ C with Pr[C = c] > 0:
Pr[C = c | M = m0] = Pr[C = c | M = m1]
Read it aloud. The probability that ciphertext c was produced, given that the plaintext was m0, equals the probability that c was produced given the plaintext was m1. For any two messages and any ciphertext.
The distribution of the ciphertext is independent of the underlying plaintext. Observing c gives the adversary zero additional information about which message was encrypted.
The adversary (our postman, with unlimited time, unlimited computing power, unlimited cleverness) stares at the ciphertext and learns absolutely nothing. Not a single bit of information. This is the strongest possible notion of secrecy.
An Equivalent View
There is another way to read the same definition, and this form is closer to the intuition behind the reference. It says that the ciphertext distribution is independent of the plaintext distribution. Once the attacker sees c, nothing about the message has become more likely than before. In probability language, the posterior belief about the plaintext is unchanged by the ciphertext.
Equivalently, for every message m and every ciphertext c with non-zero probability,
Pr[M = m | C = c] = Pr[M = m]
This is the same idea expressed from the other side. The ciphertext does not update the attacker's belief at all. That is what perfect secrecy really means. The attacker may see the whole ciphertext, but the mathematics says the ciphertext carries no information about which plaintext was sent.
Beautiful definition. But can anything actually achieve it?
The One-Time Pad
The Perfect Mask
Before I build a perfectly secure cipher, I need one basic operation. Let's start with a single bit b (either 0 or 1). I want to apply a "mask" bit that could hide that bit or leave it as it is.
b' = b masked with mask
| b | mask | b' |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
If the mask is 0, leave it alone. If the mask is 1, hide it. Another way to see it is that if both bits are the same, output 0 and if different, output 1.
Now here's the magic: masking is its own inverse.
(b masked with mask) masked with mask = b
Why? If mask = 0, nothing happened either time. If mask = 1, it flipped twice, right back to the original. Mask once to encrypt, mask again to decrypt. One can also observe that this mask is associative and commutative.
In computer science, we have a name for this exact operation. It is XOR (exclusive or, denoted ⊕).
For bit strings of length ℓ, XOR operates bit by bit.
(1, 0, 1, 1) ⊕ (0, 1, 1, 0) = (1, 1, 0, 1)
The Construction
The One-Time Pad (OTP), also called the Vernam cipher, is beautifully simple. The message space, key space, and ciphertext space are all ℓ-bit strings.
M = K = C = {0, 1}ℓ
where ℓ is a publicly known system parameter. The scheme works as follows.
Gen(): Output a uniformly random key k ∈ {0, 1}ℓ
Enc(m, k): Output c = m ⊕ k (bitwise XOR)
Dec(c, k): Output m = c ⊕ k (bitwise XOR)
That's it. Just XOR the message with a uniformly random key.
Note that Enc here is deterministic, meaning there's no internal randomness. All the randomness comes from Gen, which produces the key. This is fine as long as the key is used only once (I'll show why shortly).
Correctness
From Blog 1, the correctness requirement is that Dec(Enc(m, k), k) = m for every message m and every key k that Gen could output.
Dec(Enc(m, k), k) = Dec(m ⊕ k, k) = (m ⊕ k) ⊕ k = m ⊕ (k ⊕ k) = m ⊕ 0ℓ = m ✓
XOR of k with itself is all zeros. XOR with all zeros is the identity. Done.
The Proof
Now the main event. I'll prove OTP achieves Shannon's definition of perfect secrecy.
Claim: ∀ m0, m1 ∈ {0, 1}ℓ and ∀ c ∈ {0, 1}ℓ:
Pr[C = c | M = m0] = Pr[C = c | M = m1]
Proof:
Fix an arbitrary plaintext m0 and an arbitrary ciphertext c. The encryption Enc(m0, k) = m0 ⊕ k produces c precisely when:
m0 ⊕ k = c ⇒ k = m0 ⊕ c
So the conditional probability is the following.
Pr[C = c | M = m0] = Pr[k = m0 ⊕ c]
Since Gen outputs k uniformly at random from {0, 1}ℓ, the probability of any specific ℓ-bit string is as follows.
Pr[k = m0 ⊕ c] = 1/2ℓ
Now do the exact same calculation for m1.
Pr[C = c | M = m1] = Pr[K = m1 ⊕ c] = 1/2ℓ
Both probabilities equal 1/2ℓ, regardless of what m0, m1, or c are. ▮
The postman stares at the ciphertext and is, mathematically, completely clueless. Every plaintext is equally likely to have produced any ciphertext. Perfect secrecy achieved. ____
Don't Strive for Perfection
The One-Time Pad is perfectly secure, yes. But it comes with two devastating limitations. And these aren't quirks of OTP, they're inherent to any perfectly secure cipher.
Limitation 1: The Key Must Be as Long as the Message
Theorem: If an encryption scheme (Gen, Enc, Dec) is perfectly secure, then |K| ≥ |M|.
The key space must be at least as large as the message space. This is not about OTP specifically — it's about any scheme that achieves perfect secrecy.
Proof (by contradiction):
Suppose, for contradiction, that our scheme is perfectly secure but |K| < |M|. Consider the uniform distribution over M, and fix a ciphertext c with Pr[C = c] > 0.
Define the set of all valid decryptions of c.
M(c) = {Dec(c, k) : k ∈ K}
Each key k gives exactly one decryption Dec(c, k), but two different keys might decrypt to the same message. So the set M(c) has at most |K| elements.
|M(c)| ≤ |K| < |M|
Since M(c) is strictly smaller than M, there exists some message m* ∈ M that is not in M(c). This means no key in K maps c back to m*:
Pr[C = c | M = m*] = 0
But m* has non-zero probability under the uniform distribution, so for any m ∈ M(c), Pr[C = c | M = m] > 0.
We got our contradiction.
Assertion -> If keys are x-bit strings and messages are y-bit strings:
|K| ≥ |M| ⇒ 2x ≥ 2y ⇒ x ≥ y
Want to encrypt a 1 GB file? You need a 1 GB key. Want to encrypt a 10 GB video call? You need a 10 GB key. And you had to somehow securely share that key beforehand, which was the entire problem we were trying to solve in the first place! (T_T)
Limitation 2: The Key Cannot Be Reused
For OTP specifically:
Suppose Alice reuses the same key k for two messages m0 and m1, producing c0 = m0 ⊕ k and c1 = m1 ⊕ k. The postman intercepts both and computes the following.
c0 ⊕ c1 = (m0 ⊕ k) ⊕ (m1 ⊕ k) = m0 ⊕ m1 ⊕ (k ⊕ k) = m0 ⊕ m1
The key cancels out. The postman now holds the XOR of the two plaintexts, a significant amount of information, especially if the messages are natural language text. Enough to begin recovering both.
As Turing Award winner Michael Rabin put it: "You should never reuse a one-time pad. It is like toilet paper. If you reuse it, things get messy."
For any perfectly secure cipher (proof sketch).
This isn't just an OTP problem. Suppose any perfectly secure cipher reuses key k for two messages m1 ≠ m2. Now consider the postman intercepting the pair of ciphertexts (c1, c2).
Perfect secrecy would require (c1, c2) to look identical whether the sender encrypted (m1, m1) or (m1, m2). But if c2 can be the encryption of both m1 and m2 under the same key k, then Dec(c2, k) would have to return two different answers. Decryption is a function — it can't. Contradiction.
So perfect secrecy with key reuse contradicts correctness. Each encryption must use an independently generated key. ▮
Need to chillax
Let's take stock of what perfect secrecy demands.
| Requirement | Practical? |
|---|---|
| Key as long as the message | Encrypt a 1 GB file → share a 1 GB key first |
| Fresh key for every message | 100 messages → share 100 independent keys |
If Alice and Bob could securely share a 1 GB key for every message, they might as well share the 1 GB message directly.
And here's the thing: remember from Blog 2 that even the most powerful supercomputers can't exceed about 1020 (roughly 267) operations per second. The postman, formidable as he is, has neither unlimited computation nor unlimited time. So why am I defending against an infinitely powerful adversary?
Perfect secrecy is the mathematical gold standard. But the gold standard is too expensive for everyday use.
The Birth of Computational Security
Here's the pivot. Instead of demanding that the adversary learns absolutely nothing, we make 2 concessions and in return, we get what we actually need. Short, reusable keys.
Why These Concessions Are Necessary
Consider any encryption scheme where the same key k is used for multiple messages. In the KPA model (from Blog 1), the adversary has a collection of (message, ciphertext) pairs encrypted under the same unknown k.
Two trivial attacks are unavoidable against any such scheme:
Attack 1: Brute-Force Key Recovery
The adversary tries every k' ∈ K. For each candidate, it checks whether Dec(ci, k') = mi for all known pairs. When it finds the right one, it has the key.
| Property | Value |
|---|---|
| Running time | O(|K|), linear in the key space size |
| Success probability | 1 (100%) |
For |K| = 2256, this takes on the order of 2256 operations. At 1020 operations per second, that's roughly 1057 years. Not practical.
Attack 2: Guessing
The adversary picks a single random k' ∈ K and checks if it's correct.
| Property | Value |
|---|---|
| Running time | O(1), constant, near instant |
| Success probability | 1/|K| |
For |K| = 2256, the success probability is 1/2256.
These two attacks represent extremes: one guarantees success but takes essentially forever; the other is instant but almost certainly fails.
We accept both realities and build the security model around them.
Relaxation 1 (Effort): We only require security against efficient (polynomial-time) adversaries.
Brute force succeeds with probability 1, but its running time is exponential in n, so it's not efficient. We declare: attacks that take superpolynomial time don't count.
Relaxation 2 (Chance): We allow the scheme to be broken with negligible probability.
Guessing works in O(1) time, but its success probability 1/2n is negligible. So we declare: attacks that succeed with only negligible probability don't count either.
Notice — the terms efficient and negligible are the ones I defined at the beginning of this blog. I was laying the groundwork for exactly this moment.
With these two relaxations, we arrive at computational security.
Computational Security: An encryption scheme is computationally secure if no efficient adversary can break it except with negligible probability.
Compare this with perfect secrecy.
| Perfect Secrecy | Computational Security | |
|---|---|---|
| Adversary | Computationally unbounded | Computationally bounded (polynomial time) |
| Security guarantee | Adversary learns absolutely nothing | Adversary learns something with negligible probability |
This is weaker than perfect secrecy. Given enough time, a computationally secure scheme can be broken. But the time required is so vast, and the probability of a shortcut so tiny, that for practical purposes, the scheme might as well be perfectly secure.
If the postman can't crack the letter in his lifetime, Alice and Bob's secret stays safe.
And the relaxation buys us two things we couldn't have before, which I'll formally prove in future blogs:
- Short keys — a 128 or 256-bit key to encrypt arbitrarily long messages
- Key reuse — the same key can be used for multiple messages
Choosing n: Where You Draw the Line
One final subtlety. These definitions are asymptotic, meaning they describe what happens as n → ∞. But in practice, you pick a concrete value of n and deploy the scheme. Choose poorly, and asymptotic security is worthless.
Imagine a cipher where any adversary running for n2 steps succeeds with probability n5 · 2−n. Asymptotically, the success probability is negligible. Looks safe on paper.
But plug in concrete values.
| n (key bits) | Adversary runtime | Success probability | Verdict |
|---|---|---|---|
| 10 | 100 steps ≈ instant | 105 · 2−10 ≈ 97% | Completely broken |
| 30 | 900 steps ≈ instant | 305 · 2−30 ≈ 0.02% | Marginal |
| 256 | 65536 steps ≈ instant | 2565 · 2−256 ≈ 2−216 | GGs |
At n = 10, an instant attack succeeds 97% of the time. At n = 256, that same attack succeeds with probability so small it makes the number of atoms in the universe look large.
This is exponential returns on security: each extra bit of n doubles the exponent in the denominator, so the safety gain accelerates as n grows. The first 10 bits bought almost nothing; bits 200–256 buy you astronomical safety.
The security parameter is where you draw that line. Push it right, and you pay more in running time (Gen, Enc, Dec all scale with poly(n)), but buy exponentially more safety. Pull it left, and operations are faster but you erode that margin. Choosing the right setting is an engineering decision — it requires understanding the concrete numbers, not just the asymptotic story.
What's Next?
To summarize what I did in this blog.
- Built the vocabulary: the security parameter n, efficient algorithms (polynomial-time), and negligible functions (shrinks faster than any polynomial inverse)
- Stated Shannon's perfect secrecy — the strongest possible notion of security
- Proved the One-Time Pad achieves it
- Proved two fundamental impossibilities inherent to any perfectly secure cipher: keys must be as long as messages, and no key can be reused
- Modern cryptography didn't abandon perfect secrecy because it failed. It abandoned it because its costs outweigh its benefits for most applications.
- Introduced computational security, the pragmatic bargain that trades perfection for practicality — secure against efficient adversaries, breakable only with negligible probability
But I haven't yet said what computational security looks like as a formal definition. What's the computational analogue of Shannon's perfect secrecy? How do I state it precisely, and, critically, how do I prove a scheme achieves it?
That's the next blog. I'll formalize computational indistinguishability, meet the first provably secure construction under a hardness assumption, and see the three principles of modern cryptography (define, assume, prove) in full action.
Acknowledgment
The technical content in this blog draws from "Introduction to Modern Cryptography (Second Edition)" by Jonathan Katz and Yehuda Lindell, and from Professor Ashish Choudhury's lecture series on Foundations of Cryptography.
So the next time someone offers you perfect security, ask them about the key length. If it's shorter than the message... well, you've read this blog. You know what Shannon would say.
Note: The mathematical formulations in this blog are simplified for readability. The proofs are faithful to the originals. The images and diagrams in this blog are AI-generated and meant to be illustrative, not precise technical specifications.