Defining Security

Why Encryption Must Be Randomized

The previous page fixed an encryption scheme as a family of injective maps \(E_e \colon \mathcal{M} \to \mathcal{C}\), one per key, and treated each \(E_e\) as a fixed function, so that a given plaintext under a given key always produces the same ciphertext. We flagged there that this deterministic choice carries a weakness, and set the repair aside. We collect that debt now. The weakness is a barrier that no deterministic scheme can clear, not a detail of one construction, and the security definitions that follow are built to measure exactly what clearing it requires.

Fix a key and consider what a deterministic \(E_e\) leaks before any question of key recovery arises. Three failures are structural, present in every deterministic scheme regardless of how hard its key is to find.

1. Repetition.
Because \(E_e\) is a function, \(m = m'\) forces \(E_e(m) = E_e(m')\), so equal plaintexts produce equal ciphertexts. An observer who sees the same ciphertext twice learns that the same message was sent twice, without breaking anything, since the equality of ciphertexts is visible directly. In a setting where messages recur, the pattern of repetitions is itself information, and a deterministic scheme transmits it in the clear.

2. Distribution dependence.
Suppose the adversary knows that the plaintext is drawn from a small or skewed set, such as a yes/no instruction, a choice among a handful of fixed commands, or a field whose likely values are few. Under Kerckhoffs's principle the scheme itself is public. If the encryption transformation is also public to the adversary, as in a public-key setting, the adversary can encrypt each likely plaintext directly. Even when the transformation is not public, a chosen-plaintext adversary can obtain such encryptions. Either way the adversary can compare against the observed ciphertext. A deterministic scheme offers no defense here, because the ciphertext it produces for a given plaintext is a fixed target the adversary can reproduce and match.

3. Partial information.
The third sharpens the second. Even when the adversary cannot recover the whole plaintext, a deterministic scheme may leak some part of it, for instance a predicate, a fragment, or a single bit that the ciphertext determines and the adversary can compute. Recovering the plaintext in full is only the crudest notion of a break. A scheme that hides the message but discloses a reliable bit of it has still failed against an adversary who needs only that bit. The work of the sections ahead is to make this precise: what it means to leak nothing, not merely to hide the whole.

All three failures share one root. A deterministic \(E_e\) is a fixed map, so the ciphertext is a deterministic function of the plaintext, and any structure in the plaintext passes through to structure in the ciphertext that the adversary can read or reproduce. The repair is to break the functional dependence. A randomized encryption scheme draws fresh randomness at encryption time, so that a single plaintext maps to many possible ciphertexts and the particular one sent carries no reproducible signature of the plaintext's structure.

The decryption condition forces a structural fact: distinct plaintexts must have disjoint ciphertext sets. If some ciphertext \(c\) could arise as \(E_e(m, r)\) and also as \(E_e(m', r')\) with \(m \neq m'\), then \(D_d(c)\) would have to equal both \(m\) and \(m'\), contradicting that decryption returns a single plaintext. So the ciphertext space partitions. Each plaintext owns a private region of \(\mathcal{C}\), and randomness selects which point of its own region a given encryption lands on. Re-encrypting a message now lands on a different point, and an adversary that encrypts a candidate plaintext itself cannot predict which point the sender chose.

Randomization is the precondition for the security this page defines, not an optional hardening of it. But possibility is not security. A plaintext having many ciphertexts is worthless if the adversary can still tell one plaintext's ciphertexts from another's. We need a definition that holds the scheme to the right standard. That standard is not "the adversary cannot recover the key," nor even "cannot recover the plaintext," but "cannot extract anything the plaintext was meant to hide."

The Indistinguishability Game

We want a definition of security that captures "the ciphertext reveals nothing useful," and we want it phrased so that it can be checked. The route is to turn security into a contest the adversary plays and is required to lose. If the best the adversary can do is no better than guessing, the scheme leaks nothing the adversary could act on.

The contest is sharp precisely because the adversary is handed every advantage short of the key. Rather than wait for messages it cannot control, the adversary itself names the two plaintexts whose encryptions it will try to tell apart. Knowing the candidates exactly, it faces the easiest possible discrimination task. It is then shown the encryption of one of them, chosen by a fair coin it cannot see, and asked which. A scheme that hides information must defeat the adversary even on this self-chosen, two-way choice. If it leaks enough to bias that one guess, it has leaked something.

Three features of the game are deliberate, and each answers a question the previous page left open.

The bound is stated against polynomial-time adversaries. This is where the complexity notions invoked on the previous page enter the definition itself. "The adversary cannot win" does not mean that no winning strategy exists in principle, since exhaustive key search always exists. It means that no strategy runs within the resource budget of a feasible attacker, made precise as time polynomial in the security parameter. A scheme is secure against the bounded adversary the previous page described, not against an unbounded one. The unbounded case is the separate and stronger guarantee taken up later.

The winning margin must be negligible. An adversary can always achieve exactly \(\tfrac{1}{2}\) by ignoring the ciphertext and flipping its own coin, and can do slightly better by luck on any given run. What security forbids is a margin that a feasible attacker can convert into a reliable advantage. A permitted margin must be small enough to be little-o of every inverse polynomial, so that it cannot be amplified into a usable edge by repeating the attack a feasible number of times. This is the precise form of the "non-negligible probability" the previous page used to separate a genuine break from a lucky guess.

The adversary chooses the plaintexts. This single feature subsumes the first two deterministic failures from the first section at once. If the scheme were deterministic, the adversary would name any two distinct plaintexts, encrypt \(m_0\) itself, and compare with the challenge. A match reveals \(b = 0\) and a mismatch reveals \(b = 1\), so the adversary wins with certainty. Indistinguishability is therefore unattainable for deterministic schemes, and the game formalizes exactly why randomization was forced.

The same feature also disposes of distribution dependence. By letting the adversary pick the worst pair of plaintexts, the definition demands security for every distribution over messages, not merely an average-case one, since the hardest two-point distribution is among the adversary's choices.

One further constraint of the game is not a design choice but an honest accounting of what encryption does not promise to hide. The plaintexts \(m_0\) and \(m_1\) are required to have equal length. A ciphertext generally reveals the length of its plaintext, and an adversary allowed to submit plaintexts of different lengths could win trivially by reading off the ciphertext size, defeating the scheme for a reason that has nothing to do with the secrecy of content. Fixing equal lengths isolates the property we actually want: that nothing about the content leaks. The question of concealing length is a separate concern addressed by other means.

Semantic Security

The indistinguishability game is a clean test, but it phrases security negatively and narrowly, as the adversary's failure to win one specific two-way guessing contest. The intuition we began with was broader and positive. A ciphertext should betray nothing about its plaintext that the adversary could not already have known. We now state that intuition directly, in a form that makes no reference to any game.

The difficulty is to say what "betray nothing" means without smuggling in a list of forbidden leaks. We cannot enumerate every fact an adversary might extract, such as a parity bit, a price bracket, or whether the message names a particular person. The semantic formulation avoids the list by comparing two worlds. In one, the adversary holds the ciphertext. In the other, it holds nothing but the public description of the message distribution. The scheme is secure if these two worlds are computationally the same, that is, if anything the adversary can compute from the ciphertext it could already compute without it.

The simulator is the heart of the definition. It is a hypothetical algorithm that must reproduce the adversary's success while being denied the one thing the adversary has, namely the ciphertext. If such a simulator always exists, the ciphertext was useless to the adversary. Every inference it supported was already available from public knowledge of the message distribution and the plaintext's length alone.

The semantic definition retires the third deterministic failure from the first section. There we observed that a scheme can hide a plaintext in full yet leak a reliable bit of it, and that recovering the whole message is too crude a notion of a break.

Semantic security is the notion that is not too crude. It forbids leaking any function \(f\) of the plaintext, from the whole message down to a single predicate, because \(f\) ranges over everything the adversary might want. A scheme that disclosed even one reliable bit would be caught, because that bit is an \(f\) that the adversary computes from the ciphertext and no simulator can match.

The definition also ties secrecy to the whole message distribution rather than to a single message. The guarantee is quantified over every distribution, and it must hold whether the plaintext is a uniform random string or one of two known commands. The indistinguishability game reached the same universality from the opposite side, by letting the adversary choose the plaintexts. There the adversary picks the worst case, and here the guarantee holds in all cases. That the two routes lead to the same place is the content of the next section.

The Two Definitions Agree

We now have two definitions of the same intention. Indistinguishability is operational and narrow. It asks only that the adversary win a two-way guessing game no more often than chance. Semantic security is conceptual and broad. It asks that no function of the plaintext leak beyond what is already public. The first is easy to test against a scheme, and the second states what we want. Their value comes from a single fact: they are the same condition.

The two directions are unequal in difficulty, and seeing why is more instructive than a formal reduction. We give the mechanism of each.

Semantic security implies indistinguishability.
This direction is immediate in contrapositive, because an adversary who wins the indistinguishability game is already a violation of semantic security. Suppose some adversary distinguishes the encryptions of two chosen plaintexts \(m_0, m_1\) with non-negligible advantage. Take the message distribution in the semantic definition to be uniform on \(\{m_0, m_1\}\), and take the function \(f\) to be the single bit "is the plaintext \(m_1\) rather than \(m_0\)." From the ciphertext, the winning adversary computes this bit with probability non-negligibly above one half. No simulator denied the ciphertext can match this. A simulator knows only that the plaintext is one of \(m_0, m_1\), each equally likely, so its best blind guess of the bit succeeds with probability exactly one half. The adversary's edge over every simulator is therefore non-negligible, which is precisely the failure of semantic security. A semantically secure scheme thus admits no distinguishing adversary and has indistinguishable encryptions.

Indistinguishability implies semantic security.
This direction carries the real content, and its mechanism is the construction of a simulator. We are given that no efficient adversary wins the guessing game, and must produce, for any adversary \(\mathcal{A}\) that computes some \(f(m)\) from the ciphertext, a simulator \(\mathcal{S}\) that does as well without it. The simulator's strategy is to run \(\mathcal{A}\) on a decoy. Rather than the true ciphertext, which it does not have, \(\mathcal{S}\) encrypts a fixed dummy plaintext of the correct length, drawing the randomness itself, and feeds the result to \(\mathcal{A}\). The simulator can do this because encryption is available to it just as it is to the adversary. Indistinguishability guarantees that \(\mathcal{A}\) cannot tell it has been fed a decoy rather than a real challenge, since if it could, that detection would itself win the guessing game. So \(\mathcal{A}\) computes \(f\) on the decoy run essentially as well as it would have on the real ciphertext, and the simulator simply reports \(\mathcal{A}\)'s output. The ciphertext is thereby shown to have been dispensable. Whatever \(\mathcal{A}\) extracted from it could be extracted from a decoy carrying none of the true plaintext's information. Any gap between the two runs would be a distinguisher, contradicting the hypothesis.

The equivalence also closes the account opened on the previous page, where security split into the unconditional and the computational. Perfect secrecy demanded that the ciphertext be statistically independent of the plaintext, so that even an adversary of unlimited power gains no information from it, and we saw it costs a key at least as long as the message.

Semantic security is the computational shadow of that demand. The ciphertext need not be independent of the plaintext, only independent as far as a polynomial-time adversary can tell. Relaxing "no information" to "no efficiently extractable information" is exactly what lifts the key-length barrier. A short key can then protect a long message, which is the trade the one-time pad could not make. The unconditional guarantee and its computational relaxation are the same idea held to two different standards of adversary, and the definitions of this page are the computational one made exact.

Stronger Notions

Semantic security, in either of its equivalent forms, is the baseline an encryption scheme is expected to meet. It is not the ceiling. The guessing game of this page gave the adversary one specific power, the ability to choose plaintexts and see their encryptions. Real adversaries have more. Strengthening the definition is a matter of enlarging what the adversary may do, and the same game-shaped template absorbs each enlargement.

The first enlargement follows the attack hierarchy of the previous page. The indistinguishability game as stated lets the adversary obtain encryptions of plaintexts it chooses, and so defines security against a chosen-plaintext attack. But the previous page placed a stronger adversary above it. That adversary can also obtain decryptions of ciphertexts of its choosing, even adaptively and even after seeing the challenge, though never of the target ciphertext itself.

Granting the game's adversary that decryption access, and still demanding it cannot win, defines security against an adaptive chosen-ciphertext attack. The definition keeps its shape, since it is the same guessing game with a more powerful player. The bar, however, is far higher, and schemes deployed in adversarial settings are held to it because real systems do decrypt attacker-supplied ciphertexts.

A second strengthening asks for something the guessing game does not directly address: non-malleability. A scheme is malleable if, given a ciphertext, an adversary can produce a different ciphertext whose plaintext is related to the original in a controlled way, without ever learning either plaintext. Indistinguishability forbids reading the message, and non-malleability forbids tampering with it coherently.

Non-malleability is the stronger requirement. A non-malleable scheme is also semantically secure, so non-malleability sits strictly above the baseline of this page. The distinction matters wherever a ciphertext is not merely read but acted upon, as with a transferred amount or a command, since there the threat is an adversary who alters the effect without breaking the secrecy.

These notions branch from a single baseline along two independent axes, and the branching pattern is itself the durable object. Each stronger notion is the same construction, instantiated against a stronger adversary or aimed at a different goal. The construction is a game in which an adversary, granted some catalog of powers, must fail to win. The catalog grows, but the shape does not.

The template is the framework the previous page promised would survive even a change in the model of computation. The definitions of security are claims about what a bounded adversary cannot do, and they remain meaningful whatever the adversary is built from, classical or quantum. What a quantum adversary changes is not the definitions but which schemes meet them, that is, which underlying problems remain hard enough to anchor the bound.

Every definition on this page is conditional. A scheme is secure if no efficient adversary wins, and whether one exists turns on the hardness of some computational problem the scheme is built from. We have defined what security means without yet exhibiting a single scheme that achieves it, because achieving it requires a problem believed intractable and a way to bind a scheme's security to that problem.