Decoding Cryptography: No Bit is Safe

Moving on from "Perfection"

In the last blog, I proved that the One-Time Pad achieves perfect secrecy, showed that any perfectly secure cipher demands keys as long as the message and forbids key reuse, and then made a pragmatic pivot. I traded perfection for two relaxations: security only against efficient (polynomial-time) adversaries, and tolerance for a negligible probability of failure. The result was computational security.

I promised to show what computational security actually looks like as a formal definition - the computational analogue of Shannon's perfect secrecy, to state it precisely, prove a scheme achieves it, and see the three principles of modern cryptography (define, assume, prove) in full action.

Let's get to it.

---

Semantic Security — The Original Definition

In Blog 3, I said that a computationally secure scheme is one where no efficient adversary can break it except with negligible probability. That sounds right, but it's vague. Break it how? What does "break" even mean?

Before answering that, let's nail down what "efficient" means. In cryptography, an efficient adversary is modeled as a probabilistic polynomial-time (PPT) algorithm. This means its running time is bounded by some polynomial function, and it's allowed to make random coin flips. I'll use the term PPT adversary from here on to mean "efficient attacker."

The original answer to what "break" means, called semantic security, was given in the following spirit. Consider the COA model (from Blog 1). A computationally bounded adversary sees a ciphertext c of some unknown message m, encrypted under an unknown key k. The adversary knows the encryption algorithm (Kerckhoffs' principle), just not the key or the message.

Intuitively, we want to say: the ciphertext reveals no additional information about the plaintext. But what counts as "information"? The adversary might want to know the message itself, or its first bit, or its parity, or its length, or anything. And the adversary might already have some background knowledge about the message before ever seeing the ciphertext.

To capture this, we introduce two abstract functions.

h(m) models any prior external information (the "history") about the plaintext that the adversary might already have, leaked through some other channel before the ciphertext was ever sent. Maybe the adversary knows the message is in English, or that it starts with "Dear". In some scenarios h(m) is empty (the adversary has nothing). In others, it's substantial. We leave it abstract to cover all cases.

f(m) models the additional information the adversary is trying to compute after seeing the ciphertext. This is the "target function." The adversary might want the full message (f(m) = m), or just the first bit (f(m) = m¹), or something else entirely.

To formalize this, let's use an analogy: The Alien Exam.

Imagine you are taking an open-book exam where you must answer a specific set of questions (this is the target function f(m)). You studied beforehand, so you have some background knowledge in your head (the history h(m)). But there's a twist: the professor hands you the textbook to use during the exam, but it has been encrypted into an incomprehensible alien script (the ciphertext c).

We compare two students taking this exam:
Student A (The Real Attack): Takes the exam using their background knowledge h(m) and the alien textbook c.
Student A' (The Baseline): Takes the exam using only their background knowledge h(m). They are not allowed to have the alien textbook.

Definition (Semantic Security, COA model): An encryption scheme π is semantically secure in the ciphertext-only attack model if for every PPT adversary A (Student A), there exists a PPT adversary A' (Student A') such that:

|Pr[A outputs f(m) given c, h(m)] − Pr[A' outputs f(m) given h(m)]| ≤ negl(n)

In plain English: whatever you could compute with the ciphertext, you could have computed almost as well without it. The ciphertext is deadweight. It provides no meaningful advantage in computing any function of the plaintext, regardless of what prior information the adversary had.

This is a beautiful definition. It says exactly what we want: the ciphertext is useless to the adversary.

But there's a practical problem. If you want to prove that a specific encryption scheme is semantically secure, you have to deal with every possible history function h(m) and every possible target function f(m). That's a lot of universally quantified objects to juggle in a proof.

It turns out there's an equivalent definition that is much easier to work with.

---

The Indistinguishability Experiment

In the proof of OTP's perfect secrecy (Blog 3), I implicitly used an indistinguishability-style argument: the ciphertext distribution is the same regardless of which message was encrypted. Now I'll formalize this for computational security.

Recalling the Perfect Secrecy Version

In Blog 3, the argument for perfect secrecy had this flavor: the adversary is given a ciphertext c, and it could be the encryption of m₀ or m₁. The adversary (computationally unbounded) must guess which. Perfect secrecy demanded that the adversary cannot do better than a random coin flip, i.e. probability of guessing correctly is exactly 1/2.

Three Changes for Computational Security

To move from perfect secrecy to computational security, I make exactly three changes.

Change 1: Bounded adversary. The adversary is no longer computationally unbounded. As established above, it is now a PPT algorithm, meaning its running time is bounded by some polynomial in the security parameter n.

Change 2: Security parameter. The experiment now depends on n. The key generation algorithm takes n as input (determining key length, etc.), and the adversary's running time is poly(n).

Change 3: Negligible slack. Instead of requiring the adversary's success probability to be exactly 1/2, I allow it to be at most 1/2 + negl(n). This extra negligible wiggle room is the price of the second relaxation from Blog 3: we tolerate a tiny, vanishing probability of failure.

The Formal Experiment

Here is the experiment, which I'll call PrivK^COA_A,π(n).

The COA Indistinguishability Experiment PrivK^COA_A,π(n):

1. The adversary A receives the security parameter n. It chooses two messages m₀, m₁ from the plaintext space, with |m₀| = |m₁|, and sends them to the challenger.
2. The challenger runs Gen(n) to generate a key k. It picks a random bit b ∈ {0, 1}, computes c = Enc(m_b, k), and sends c to the adversary.
3. The adversary outputs a bit b'.
4. The experiment outputs 1 (adversary wins) if b' = b, and 0 otherwise.

The adversary knows the scheme π, picks its own messages, gets one ciphertext, and must figure out which message was encrypted.

Definition (COA-secure / Computationally Indistinguishable Encryption): A scheme π = (Gen, Enc, Dec) has indistinguishable encryptions in the COA model if for every PPT adversary A:

Pr[PrivK^COA_A,π(n) = 1] ≤ 1/2 + negl(n)

This means that under this scheme, a PPT adversary has at most 1/2 + negl(n) probability to output the message bit.

Notice how clean this is compared to the semantic security definition. No history function. No arbitrary f(m). Just one game: "guess which message I encrypted."

The Equivalence

At first glance, these definitions do not even look related. One talks about computing arbitrary functions from a ciphertext, while the other just asks the adversary to guess a coin flip between two chosen messages.

Surprisingly, they are equivalent. If a scheme satisfies one, it satisfies the other. The proof is non-trivial and I will not reproduce it here (see Katz and Lindell, Chapter 3, for the full details), but the intuition is straightforward:

• Indistinguishability ⇒ semantic security: if the ciphertext looks the same whether m₀ or m₁ was encrypted, then no function f(m) can be computed any better with the ciphertext than without it.
• Semantic security ⇒ indistinguishability: if the ciphertext reveals nothing about any function of the plaintext, then in particular it reveals nothing about which of two specific messages was encrypted.

This equivalence also generalizes. In the CPA model, where the adversary has an encryption oracle, we can define both a semantic security version and an indistinguishability version, and they remain equivalent. The same holds for the CCA model. The pattern is universal.

Because the indistinguishability definition is far easier to work with in proofs, that's the one I'll use from here on.

A Note on Probabilities

One subtlety worth calling out. When I write Pr[PrivK^COA_A,π(n) = 1] ≤ 1/2 + negl(n), the probability is over all the randomness in the experiment: the random choice of b by the challenger, the randomness in Gen and Enc, and any internal coin flips of the adversary. The entire experiment is randomized, and the bound must hold over all of it.

---

The Distinguishing Advantage

There's a second way to state the same indistinguishability condition, and depending on the proof you're writing, one form can be more convenient than the other.

The first formulation says: the adversary's probability of correctly guessing b is at most 1/2 + negl(n).

The alternate formulation says: the adversary's output doesn't change based on which message was encrypted, except with negligible probability.

Formally:

Definition (Indistinguishable Encryption, alternate form): A scheme π has indistinguishable encryptions in the COA model if for every PPT adversary A:

|Pr[A outputs 1 | b = 1] − Pr[A outputs 1 | b = 0]| ≤ negl(n)

The left-hand side is called the distinguishing advantage of A. It measures how differently the adversary behaves when seeing an encryption of m₀ versus an encryption of m₁. If the advantage is negligible, the adversary essentially cannot tell the two cases apart.

Proving the Equivalence

Let me prove that these two formulations are the same. This is a short, clean calculation, and it's worth seeing because the same algebraic trick shows up repeatedly.

Proof (Condition 2 ⇒ Condition 1):

Assume the distinguishing advantage is at most negl(n). I want to show Pr[b' = b] ≤ 1/2 + negl(n).

Start by expanding Pr[b' = b] over the two cases for b.

Pr[b' = b] = 1/2 · Pr[b' = 0 | b = 0] + 1/2 · Pr[b' = 1 | b = 1]

(Each case occurs with probability 1/2 because b is a fair coin flip.)

Rewrite the first term using its complement:

Pr[b' = 0 | b = 0] = 1 − Pr[b' = 1 | b = 0]

Substitute:

Pr[b' = b] = 1/2 · (1 − Pr[b' = 1 | b = 0]) + 1/2 · Pr[b' = 1 | b = 1]

Distribute:

Pr[b' = b] = 1/2 + 1/2 · (Pr[b' = 1 | b = 1] − Pr[b' = 1 | b = 0])

Now, the quantity (Pr[b' = 1 | b = 1] − Pr[b' = 1 | b = 0]) is at most the distinguishing advantage in absolute value, which by assumption is at most negl(n). So:

Pr[b' = b] ≤ 1/2 + 1/2 · negl(n) = 1/2 + negl'(n)

where negl'(n) = 1/2 · negl(n) is still negligible (recall from Blog 3: a polynomial times a negligible function is negligible, and 1/2 is certainly bounded by any polynomial).   ▮

The reverse direction (Condition 1 ⇒ Condition 2) can similarly be shown.

So, depending on which is more convenient for a particular proof, I can use either formulation. Both say the same thing: the encryption is indistinguishable.

---

No Bit Is Safe

Here's where things get exciting. I've defined what it means for a scheme to be COA-secure. But does that definition actually do what we want? Does indistinguishability really imply that the adversary can't learn anything about the plaintext?

Let me prove that it does, using the reduction-based proof.

The Claim

Suppose the plaintext is a uniformly random ℓ-bit string (so M = {0, 1}^ℓ), and suppose our encryption scheme π is COA-secure.

Claim: For every i ∈ {1, ..., ℓ} and every PPT algorithm A:

Pr[A(Enc(m, k)) outputs mⁱ] ≤ 1/2 + negl(n)

where m is chosen uniformly at random from {0, 1}^ℓ, k is generated by Gen(n), and mⁱ denotes the i-th bit of m.

In words: no efficient adversary, given an encryption of a random message, can predict any single bit of that message with probability significantly better than 1/2.

The function f(m) = mⁱ (the i-th bit) is one particular function the adversary might want to compute. By proving this claim, I'm showing that the indistinguishability definition protects against at least this family of target functions, which helps build the intuition for why indistinguishability is equivalent to full semantic security.

The Problem

If I want to prove this directly, I would have to analyze how the adversary's code works when it tries to extract the i-th bit. That is impossible as adversaries can run arbitrary polynomial-time algorithms.

Instead, I will use a proof by contradiction. Suppose there is an adversary A that can predict the i-th bit with non-negligible advantage. That is:

Pr[A(Enc(m, k)) outputs mⁱ] ≥ 1/2 + ε(n)

where ε(n) is some non-negligible function.

The Idea

If predicting a bit is easy, I want to use that fact to win the indistinguishability game.

I will build a new adversary A' that plays the indistinguishability game against a challenger. A' does not know how to break the encryption itself, but it knows A does. So A' will run A internally as a subroutine.

The Construction

A' participates in the PrivK^COA_A',π(n) experiment as follows.

Step 1. A' picks two messages m₀ and m₁ from {0, 1}^ℓ, where:

• m₀ has its i-th bit set to 0, all other bits chosen uniformly at random.
• m₁ has its i-th bit set to 1, all other bits chosen uniformly at random.

A' submits (m₀, m₁) to the challenger.

Step 2. The challenger picks a random coin b ∈ {0, 1}, encrypts m_b, and returns the challenge ciphertext c. A' needs to figure out what b is.

Step 3. A' hands the ciphertext c to A and asks: "What is the i-th bit of the plaintext encrypted in c?"

Step 4. A outputs a bit, call it β. A' simply copies A's answer, setting its own guess b' = β, and outputs it to the challenger.

The Illusion

A has no idea it's participating in a reduction. From its perspective, it's just solving the same problem it always solves.

From A's perspective, it expects to receive an encryption of a uniformly random message. Has A' provided that?

Yes. Look at the messages A' sent to the challenger. With probability 1/2, the challenger chose b = 0, so the i-th bit of the underlying plaintext is 0. With probability 1/2, the challenger chose b = 1, so the i-th bit is 1. All the other bits were chosen uniformly at random by A'.

Overall, the message encrypted in c is exactly a uniformly random ℓ-bit string. A's view in this simulated game is statistically identical to the real world. A is completely unaware that it is being used inside a larger game. Because the environment is perfect, A will succeed with its usual probability.

The Contradiction

If the challenger encrypted m₀ (i-th bit is 0), and A correctly guesses 0, then A' outputs b' = 0 = b.
If the challenger encrypted m₁ (i-th bit is 1), and A correctly guesses 1, then A' outputs b' = 1 = b.

Whenever A guesses the i-th bit correctly, A' wins the indistinguishability game.

Pr[A' outputs b' = b] = Pr[A correctly outputs mⁱ_b] ≥ 1/2 + ε(n)

This means A' wins the COA experiment with probability at least 1/2 + ε(n). But we assumed π is COA-secure, which means no efficient adversary can win with probability more than 1/2 + negl(n).

Contradiction. Therefore, no such adversary A can exist. No bit is safe to predict.   ▮

What Just Happened?

Let me highlight a few things about this proof, because this pattern will repeat throughout cryptography.

1. Black-box usage. A' used A as a black box. It didn't need to know how A works internally. It just fed A an input and used its output. This is standard in reduction-based proofs.

2. Running time. If A runs in time p(n) for some polynomial p, then A' runs in time p(n) + O(n) (the overhead of picking two random messages and forwarding a bit). So A' is polynomial-time whenever A is.

3. The view is identical. The most critical part of any reduction is ensuring that the "inner" adversary (A) sees exactly the distribution it expects. If the view weren't identical, the success probability wouldn't carry over.

4. The structure. This is the three-principles paradigm in action. I defined security (indistinguishability). I assumed π is COA-secure. I proved a consequence (no bit can be predicted). Define, assume, prove. This is how modern cryptography works.

---

A Quick Breather

If you are feeling a bit overwhelmed by the math, take a deep breath. We have covered a lot of ground, and this is a good moment to pause and look at the map.

Where we came from: In Blog 3, we proved that the One-Time Pad is perfectly secure, but realized that perfect secrecy requires impractically long keys. To get short, reusable keys, we had to compromise. We traded absolute perfection for computational security (assuming the attacker is bounded by polynomial time, and tolerating a negligible chance of failure).

What we just did: We took that vague idea of "computational security" and turned it into a rigorous mathematical game: the Indistinguishability Experiment. We then used a reduction proof to show that if an encryption scheme passes this game, it is virtually impenetrable as an efficient attacker cannot even predict a single bit of the plaintext. We have successfully defined what secure encryption looks like in the modern world.

Where we are going next: Having a definition is great, but we still need to actually build a cipher that achieves it. How do we get the security of the One-Time Pad but with a short, practical key? We need a way to take a small amount of true randomness and stretch it out so that it looks completely random to any efficient attacker.

Enter the first major building block of computational cryptography.

---

PRGs

Everything so far has been about defining security. Now let's build something.

Recall from Blog 3 the two limitations of perfect secrecy: the key must be as long as the message, and the key can't be reused. I said computational security would buy us short keys (we will see now) and key reuse.

The Idea

The One-Time Pad encrypts an ℓ-bit message m by XORing it with an ℓ-bit uniformly random key k:

c = m ⊕ k

This is perfectly secure but requires |k| = |m|. Now, suppose instead of using a truly random ℓ-bit string as the key, we generate a long string from a short one. Specifically, imagine a function G that takes a short seed s of length l bits and produces a long output of length L bits, where L > l (both l and L are polynomial in the security parameter n).

The modified scheme works like this:

• Alice and Bob share a short, uniformly random seed s ∈ {0, 1}^l
• To encrypt: c = m ⊕ G(s)
• To decrypt: m = c ⊕ G(s)

The key is only l bits, but the message can be L bits. Short key, long message.

Wait! G is a deterministic function with only 2^l possible inputs. Its output can take at most 2^l distinct values, which is a tiny fraction of all 2^L possible L-bit strings. A computationally unbounded adversary could notice this. So this scheme is not perfectly secure.

That's fine. We're in the computational security world now. We don't need G(s) to be a uniformly random string. We just need it to look like one to any efficient observer. That's the idea behind a pseudorandom generator.

The Paradox

Wait! G is a deterministic function. It maps an l-bit seed to an L-bit output. Can this possibly be secure?

Let's look at the math. For simplicity, assume G doubles the seed length, so L = 2l.

The range of G—the set of all possible outputs it can ever produce—has at most 2^l elements (one for each possible seed). But the total number of 2l-bit strings is 2^2l.

|Range(G)| ≤ 2^l ≪ 2^2l = |{0, 1}^2l|

The fraction of 2l-bit strings that G can produce is at most 2^l/2^2l = 2^−l. For l = 128, that's 1 in 2¹²⁸. Almost every string of length 2l is not in the range of G.

A truly random 2l-bit string lands in Range(G) with probability at most 2^−l.

This gives us a devastating distinguishing strategy:

The Brute-Force Distinguisher: Given a challenge string y of length 2l bits, enumerate all 2^l possible seeds. For each seed s, check if G(s) = y. If any match is found, output 1 ("Generated by G"). Otherwise, output 0 ("Truly random").

If y was generated by G, this check finds the seed with 100% certainty.
If y is truly random, it only matches a valid output with probability at most 2^−l.

The distinguishing advantage is |1 − 2^−l| ≈ 1. This is a near-perfect break.

So it seems deterministic expansion is fundamentally insecure. A computationally unbounded adversary can always distinguish the output of G from a truly random string. Does this mean we have to abandon the idea?

The Resolution

No. Look at the brute-force distinguisher again. It enumerates all 2^l possible seeds. That takes O(2^l) time, which is exponential in l.

And our new computational security model only guarantees security against polynomial-time (PPT) adversaries. An exponential-time attack is outside the threat model.

This is exactly why the restriction to efficient adversaries matters. Without it, no deterministic expansion function could ever look random. But as long as no efficient algorithm can tell the difference, we are safe.

This brings us to the formal definition of a PRG.

The Definition

Definition (Pseudorandom Generator): A deterministic polynomial-time algorithm G is a pseudorandom generator (PRG) if:

1. Expansion: There exists an expansion function L(n) such that for every seed s of length l(n), the output G(s) has length L(n), with L(n) > l(n).

2. Pseudorandomness: For every PPT distinguisher D:

|Pr[D(G(s)) = 1] − Pr[D(r) = 1]| ≤ negl(n)

where s ← {0, 1}^l is a uniformly random seed and r ← {0, 1}^L is a uniformly random string. It means G(s) is indistinguishable from r, except with negl probablility.

Note that the description of G is public (Kerckhoffs' principle applies here too). What's hidden is the seed s.

Breaking a Bad PRG

Definitions are best understood through examples, and even better through counter-examples. Here's a candidate PRG that fails.

The construction: G takes an input s = (s₁, s₂, ..., s_l) of length l bits and outputs l + 1 bits:

G(s) = s₁, s₂, ..., s_l, (s₁ ⊕ s₂ ⊕ ... ⊕ s_l)

In other words, it copies the input and appends one extra bit: the XOR of all input bits.

This satisfies the expansion requirement (output is l + 1 bits, one more than the input). And it runs in polynomial time. But is it pseudorandom?

The attack. Consider the following efficient distinguisher D. Given a sample y = (y₁, ..., y_l, y_l+1) of length l + 1 bits:

D outputs 1 (labels y as "PRG output") if and only if y_l+1 = y₁ ⊕ y₂ ⊕ ... ⊕ y_l

This is a simple XOR check. It takes O(l) time. Now let's compute the distinguishing advantage.

Case b = 1 (y = G(s) for random s): By construction, the last bit of G(s) is always the XOR of the first l bits. So D always outputs 1.

Pr[D outputs 1 | b = 1] = 1

Case b = 0 (y is truly random): Each bit of y is independent and uniformly random. The probability that y_l+1 happens to equal the XOR of the first l bits is exactly 1/2 (it's an independent coin flip).

Pr[D outputs 1 | b = 0] = 1/2

Distinguishing advantage: |1 − 1/2| = 1/2. This is a constant, not negligible. D distinguishes with overwhelming success.

So G is not a PRG. The problem is clear: the output has a deterministic pattern (the last bit is a function of the others) that a truly random string would not have. Any efficient test that checks for this pattern breaks pseudorandomness.

The PRG Indistinguishability Experiment

Just like for encryption, we can capture pseudorandomness through an experiment.

The PRG Experiment:

1. The verifier flips a coin b ∈ {0, 1}.
2. If b = 1: the verifier picks s ← {0, 1}^l and sets y = G(s).
   If b = 0: the verifier picks y ← {0, 1}^L uniformly at random.
3. The distinguisher D receives y and outputs a bit b'.
4. The experiment outputs 1 if b' = b.

G is a PRG if: Pr[b' = b] ≤ 1/2 + negl(n) for every PPT distinguisher D.

Why 1/2? Because a trivial strategy (always guess b' = 0, or flip a coin) succeeds with probability exactly 1/2. We're saying: no efficient distinguisher can do significantly better than this trivial baseline.

And the extra negl(n)? Same reason as before. We're in the computationally secure world, and negligible failure probabilities are the price of admission.

Two Equivalent Formulations

Just as with the COA indistinguishability definition, we have two equivalent ways to state PRG security.

Formulation 1 (game-based): Pr[D correctly identifies the mechanism] ≤ 1/2 + negl(n).

Formulation 2 (distinguishing advantage): |Pr[D(G(s)) = 1] − Pr[D(r) = 1]| ≤ negl(n).

The equivalence proof is the exact same algebraic trick as in the COA case (expand Pr[b' = b] by conditioning on b, rewrite one term as its complement, rearrange). I will spare you the repetition.

---

The Next-Bit Prediction Definition

There's one more equivalent way to define pseudorandom generators, and it offers a rather different intuition.

Truly Random Strings Are Unpredictable

Consider a truly random generator G' that outputs L independent, uniformly random bits. If you've seen the first i bits of its output (for any i ∈ {1, ..., L − 1}), can you predict the next bit? No. Each bit is an independent coin flip. The best you can do is guess, and you'll be right with probability exactly 1/2.

PRG Outputs Should Be Too

The next-bit prediction definition says: a PRG should have the same property. Even though the output bits of G(s) are not independent (they're all deterministic functions of s), no efficient algorithm should be able to exploit that dependence.

The Next-Bit Prediction Experiment:

1. The verifier picks a uniformly random seed s ← {0, 1}^l and computes y = G(s) = (y₁, ..., y_L).
2. The adversary A chooses an index i ∈ {1, ..., L − 1}.
3. The adversary receives the prefix (y₁, ..., y_i).
4. The adversary outputs a bit, its prediction for y_i+1.

Definition (Unpredictable PRG): G is unpredictable if for every PPT adversary A and every index i ∈ {1, ..., L − 1}:

Pr[A(y₁, ..., y_i) = y_i+1] ≤ 1/2 + negl(n)

The seed s is unknown to the adversary. If s were known, predicting y_i+1 would be trivial (just compute G(s) yourself). The challenge is predicting without the seed.

The trivial strategy (guess randomly) gives probability 1/2. The definition says no efficient adversary can beat this by more than a negligible amount.

Equivalence

It turns out that unpredictability and the indistinguishability-based definition of a PRG are equivalent. If (G) is unpredictable, then it is a PRG (under the indistinguishability definition), and vice versa. The proof is another reduction: if a distinguisher exists, it can be converted into a predictor, and if a predictor exists, it can be converted into a distinguisher.

The intuition is that a distinguisher cannot magically recognize an entire pseudorandom string all at once. If it can tell a PRG output apart from a truly random string, there must be some point where changing a single bit changes its decision. That means the distinguisher is implicitly extracting information about that bit, allowing us to predict it better than random guessing. Conversely, if you could predict the next bit of a PRG output, you could use that information to distinguish it from a truly random sequence, since the next bit of a random sequence is completely unpredictable.

This gives us a menu of equivalent definitions for PRGs, and depending on the context, one may be more natural than another.

(While looking for this Equivalence Proof, I stumbled upon a great resource : MIT 6.875 (Fall 2025) Foundations of Cryptography. I have got to say that I absoulutely love MIT OCW. You can find the proof in Lecture 3 of this course.)

---

What's Next?

Let me recap what this blog covered.

• Semantic security in the COA model: the ciphertext reveals no additional information about the plaintext, even to an adversary with prior background knowledge
• Indistinguishability-based definition, a cleaner equivalent: no PPT adversary can tell whether it's seeing an encryption of m₀ or m₁ with non-negligible advantage
• The distinguishing advantage formulation, yet another equivalent view, and the proof that it's equivalent to the game-based formulation
• Reduction-based proofs, the central technique of modern cryptography: I showed that indistinguishable encryption implies no single bit of the plaintext can be efficiently extracted
• Pseudorandom generators, the first primitive of computational cryptography: a deterministic function that stretches short seeds into long, random-looking strings
• A non-example that shows what happens when a PRG candidate leaks structural information
• The brute-force distinguisher, which shows why the restriction to efficient adversaries is essential
• The next-bit prediction definition, an equivalent characterization of PRGs through unpredictability

I've now defined the security goal (indistinguishability) and introduced the tool (PRGs). But I haven't yet put them together. Can I actually prove that the PRG-based encryption scheme (c = m ⊕ G(s)) is COA-secure? And what happens when I want to compose PRGs, running them multiple times with independent seeds to get even more pseudorandom output?

That's the next blog. I'll prove the PRG-based scheme is COA-secure via a reduction to the PRG assumption, introduce parallel composition of PRGs, and meet a powerful proof technique called the hybrid argument that lets us reason about multiple copies of a primitive at once.

---

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 claims their encryption is "secure," ask them: secure against what? If they can't tell you the experiment, the adversary model, and the negligible bound... well, they haven't read this blog yet.

---

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.