Computational Security and the Adversary Model

Perfect secrecy, the gold standard from information theory, requires that a ciphertext reveal zero information about the plaintext to an adversary with unlimited computation and unlimited time. Shannon's theorem shows this forces the key to be at least as long as the message (the one-time pad is essentially the only scheme achieving it). This is unworkable for encrypting gigabytes of traffic with a 256-bit key. Computational security relaxes the definition along two independent axes, and it is the combination that makes the relaxation both meaningful and safe. The first axis restricts the adversary to probabilistic polynomial time (PPT): an algorithm that, given a security parameter $n$ (e.g., key length in bits), runs in time bounded by some polynomial $p(n)$, and may use random coins. This is the accepted formal proxy for "feasible computation." Anything requiring $2^{n}$ steps is treated as infeasible once $n$ is large enough (say $n = 128$), because $2^{128}$ steps exceeds any computation physically achievable with current or foreseeable technology. Polynomial time is a mathematical idealization — a $n^{100}$ algorithm is technically polynomial but useless — but in practice, natural cryptographic reductions produce small polynomials, so the abstraction tracks reality well. The second axis restricts the advantage the adversary is allowed: instead of zero information leakage, we tolerate a negligible function of $n$. A function $\varepsilon: \mathbb{N} \to [0,1]$ is negligible if, for every polynomial $p(n)$, there exists $N$ such that for all $n > N$,

Intuitively: $\varepsilon(n)$ shrinks faster than the reciprocal of any polynomial, no matter how large the polynomial's degree or coefficients. This matters because a PPT adversary can only run polynomially many "trials" — if it repeats an attack $p(n)$ times to boost its success chance, a negligible per-trial advantage still yields negligible overall success (by a union bound). No polynomial amount of extra effort can turn a negligible advantage into a substantial one. This is precisely why "negligible," not merely "small," is the right threshold — it is the threshold that is stable under all polynomial-time adversarial strategies. Both restrictions are essential together. Restricting only the adversary's running time without bounding advantage would let a scheme be "secure" even if a fast adversary succeeds half the time. Restricting only the advantage without bounding running time would be vacuous, since an unbounded adversary can always succeed via brute-force key search (this is exactly what defeats perfect secrecy for short keys). Computational security is the conjunction: efficient adversary, negligible edge.

Cryptographic definitions in this model are phrased as experiments (also called games): an interactive protocol between a challenger (who runs the real scheme honestly) and an adversary $\mathcal{A}$ (an arbitrary PPT algorithm). The scheme is declared secure for a given security notion if, for every PPT $\mathcal{A}$, the probability that $\mathcal{A}$ "wins" the experiment is at most $\tfrac12 + \varepsilon(n)$ for some negligible $\varepsilon$. The canonical example is indistinguishability under chosen-plaintext attack (IND-CPA), the baseline notion for encryption security. The experiment: ``` Experiment PrivK_cpa[A, Π]: // Π = (Gen, Enc, Dec), security parameter n 1. k ← Gen(1^n) // challenger samples a key 2. (m0, m1) ← A^Enc(k,·)(1^n) // A, given encryption oracle access, // outputs two equal-length messages 3. b ← {0,1} uniformly at random // challenger flips a fair coin 4. c ← Enc(k, m_b) // challenger encrypts the chosen message 5. b' ← A^Enc(k,·)(c) // A, still with oracle access, guesses b 6. output 1 if b' = b, else output 0 // A "wins" the experiment iff b' = b ``` The oracle access `A^Enc(k,·)` models a chosen-plaintext attack: the adversary may ask the challenger to encrypt messages of its choice before and after seeing the challenge ciphertext $c$, capturing real-world scenarios where an attacker can influence or observe what gets encrypted (e.g., via protocol side-channels). $\Pi$ is IND-CPA secure if for every PPT adversary $\mathcal{A}$ there is a negligible function $\varepsilon(n)$ such that

The baseline $\tfrac12$ is exactly the success rate of an adversary who ignores the ciphertext and guesses $b'$ by flipping a coin — so the definition says "you cannot do meaningfully better than blind guessing," which is the computational analogue of perfect secrecy's "the ciphertext reveals zero information." A companion notion for computational hardness is negligible advantage in a decision problem, formalized by defining the adversary's advantage as

and requiring $\text{Adv}_{\mathcal{A}}(n)$ to be negligible for every PPT $\mathcal{A}$. Security proofs in this model typically proceed by reduction: assume a hypothetical PPT adversary $\mathcal{A}$ breaks scheme $\Pi$ with non-negligible advantage, then construct a PPT algorithm $\mathcal{B}$ that uses $\mathcal{A}$ as a subroutine to solve some problem $X$ believed to be hard (e.g., factoring, discrete log, or distinguishing a pseudorandom generator's output from random). Since $X$ is assumed intractable for all PPT algorithms, no such $\mathcal{A}$ can exist — hence $\Pi$ is secure, conditional on the hardness of $X$. ``` Reduction template: Given: adversary A breaking Π with non-negligible advantage ε(n) Build: algorithm B that solves hard problem X B(instance x of X): simulate challenger of Π for A, embedding x into the simulated scheme run A as a black box, answering its oracle queries using x when A outputs its guess/answer for the Π-experiment, translate that answer into a solution/guess for x output the derived solution to X Correctness: if A wins the Π-experiment with prob ≥ 1/2 + ε(n), then B solves X with related non-negligible probability, contradicting the assumed hardness of X. Efficiency: B runs A once (or polynomially many times) plus polynomial overhead, so B is PPT whenever A is PPT. ```

Running time. By definition, every adversary considered in the model runs in time $O(p(n))$ for some polynomial $p$, so the total work an attacker can invest scales polynomially with the security parameter, while a well-designed scheme forces the best known attack to cost $2^{\Omega(n)}$ (exponential). This exponential gap is what makes the asymptotic definition track real security: doubling the key length (roughly doubling $n$) squares the brute-force cost, while it only polynomially increases the honest parties' encryption/decryption time (typically linear or near-linear in $n$). This is the entire reason short keys suffice — the ratio of attacker cost to defender cost diverges as $n$ grows, unlike in perfect secrecy where key length must equal message length exactly.

Space. Honest algorithms (`Gen`, `Enc`, `Dec`) use space polynomial in $n$ — typically $O(n)$ for symmetric primitives (a key, a block, some state) and $O(n)$ to $O(n^2)$ or so for public-key schemes involving multi-precision integers. The adversary's PPT bound implicitly caps its space usage too, since an algorithm running in time $p(n)$ cannot address more than $p(n)$ memory cells.

Why the definition is correct — reasoning, not assertion. The core mathematical content justifying "negligible" as the right threshold is a closure property: negligible functions are closed under addition and under multiplication by any fixed polynomial. Claim: if $\varepsilon_1(n), \varepsilon_2(n)$ are negligible, then $\varepsilon_1(n) + \varepsilon_2(n)$ is negligible, and $p(n)\cdot \varepsilon_1(n)$ is negligible for any polynomial $p$. Proof sketch: For the sum, fix any polynomial $q(n)$. Since $\varepsilon_1$ is negligible, there is $N_1$ with $\varepsilon_1(n) < \tfrac{1}{2q(n)}$ for $n > N_1$; likewise $N_2$ for $\varepsilon_2$. For $n > \max(N_1,N_2)$, $\varepsilon_1(n)+\varepsilon_2(n) < \tfrac{1}{q(n)}$. For the scaling property, given polynomial $p$ and target polynomial $q$, apply the negligibility of $\varepsilon_1$ to the polynomial $p \cdot q$ instead of $q$: there is $N$ with $\varepsilon_1(n) < \tfrac{1}{p(n)q(n)}$ for $n>N$, hence $p(n)\varepsilon_1(n) < \tfrac{1}{q(n)}$. $\blacksquare$ This closure property is exactly why the model is stable: if a scheme is used $q(n)$ times (any polynomial number of sessions), or an adversary is allowed $q(n)$ attempts, the total advantage stays negligible, since a union bound over $q(n)$ negligible-advantage trials gives $q(n)\cdot\varepsilon(n)$, still negligible. So the definition is future-proof against any polynomially-bounded amplification strategy — repeated attacks, parallel attacks, adaptive strategies — none of them turn a negligible per-attempt edge into a substantial overall edge. Without this closure fact, "negligible" would be an arbitrary-looking threshold; with it, negligible is provably the unique right notion of "cryptographically irrelevant probability."

The honesty of the model — tradeoffs. Computational security is not unconditional. Every proof is a reduction to an assumption (factoring is hard, discrete log is hard, AES has no exploitable structure) that is itself unproven — cryptography currently lacks unconditional proofs that any one-way function exists (this would imply P ≠ NP). Computational security is therefore relative security: "if $X$ is hard, then $\Pi$ is secure." Additionally, "polynomial time" is an asymptotic idealization; a concrete deployed scheme is evaluated via concrete security (bit-security estimates, e.g., "$2^{128}$ operations") rather than pure asymptotics, but the asymptotic framework is what makes the proofs composable and the definitions unambiguous.

Consider a toy encryption scheme built from a (assumed secure) pseudorandom generator Pseudorandomness and Pseudorandom Generators $G$ that stretches an $n$-bit seed into a much longer pseudorandom string, used as in a stream cipher: $\text{Enc}(k, m) = m \oplus G(k)$. Suppose a careless variant instead reuses $G(k)$'s first bit as a "checksum" appended to the ciphertext, accidentally leaking one extra bit of $G(k)$ per encryption. We trace how a distinguishing adversary's advantage is measured and shown negligible (or not). Let $n = 128$ (key length). Say cryptanalysis shows that an adversary running in time $T$ can guess the leaked bit correctly with probability $\tfrac12 + \delta(T)$ where $\delta(T) \approx T / 2^{128}$ (linear search over related keys, say).

The key qualitative fact the table illustrates: as we let $n \to \infty$ (imagine a scaled-up version of this scheme with longer keys), any adversary confined to time $p(n)$ — no matter how large a polynomial $p$ — has $\delta(p(n)) = p(n)/2^n \to 0$ faster than $1/q(n)$ for every polynomial $q$, because exponentials dominate polynomials. This is the concrete instantiation of the abstract negligibility argument from the previous section: the scheme family, not a single fixed instance, is what is proven secure, and the proof holds simultaneously against every polynomial-time strategy. Now compare to the perfect-secrecy world: a one-time pad with a 128-bit key encrypting a 129-bit message is provably breakable — Shannon's argument gives certainty, not merely a negligible probability, because there aren't enough keys to cover the message space. The computational model is a genuinely different regime: it accepts a residual, quantifiable, vanishingly-small risk in exchange for keys that don't grow with message length.

The computational security paradigm emerged from combining Shannon's information-theoretic rigor with ideas from computational complexity theory, once researchers recognized that perfect secrecy's key-length requirement made large-scale digital cryptography impractical.

Every widely deployed cryptographic protocol is designed and analyzed in the computational security model. TLS (securing HTTPS) relies on IND-CPA/IND-CCA-secure symmetric encryption and computational assumptions like elliptic-curve discrete log for key exchange. Disk encryption (BitLocker, LUKS) and messaging apps (Signal) use AES, whose security claim is entirely computational — "no known or foreseeable PPT adversary can distinguish AES output from random with non-negligible advantage." Digital signatures underpinning software updates and blockchain transactions rely on the hardness of factoring (RSA) or discrete log (ECDSA) exactly as formalized here. The entire discipline of provable security, including Pseudorandomness and Pseudorandom Generators used to build Stream Ciphers and block ciphers, is a direct application of the PPT-adversary/negligible-advantage template introduced in this article; understanding it is a prerequisite for reading any modern cryptographic security proof.

Ask the tutor: How does the definition of IND-CPA security change if we give the adversary a decryption oracle as well, and why does that stronger game (IND-CCA) matter for real protocols?