Helpful context:

Perfect security requires keys as long as messages - a condition that makes it unusable in practice. The resolution is a conceptual shift: instead of demanding security against all-powerful adversaries, demand security only against efficient adversaries. An adversary running in polynomial time cannot break the scheme except with negligible probability. This sounds weaker, but it is sufficient for every practical purpose, and it enables encryption with short keys. The entire edifice rests on a single unproven but widely believed assumption: that one-way functions exist.

The shift from information-theoretic to computational security is not a concession - it is a reframing that unlocks everything. Shannon’s perfect security tells us that a one-time pad with a key as long as the message is unbreakable. But that insight, while mathematically clean, offers no path forward for real systems. Computational security offers a different bargain: accept that an adversary with unlimited time could eventually break the scheme, but ensure that no efficient adversary can break it within the lifetime of the universe. This is not a gap in the theory; it is the theory becoming useful.

The key ingredient that makes this work is asymmetry. Some functions are easy to compute but hard to invert. Multiplying two large primes takes milliseconds; factoring their product is believed to take longer than the age of the universe with any known algorithm. Computational cryptography is the systematic exploitation of this asymmetry. What follows is the formal structure that makes that intuition precise.

Two Relaxations

Shannon’s perfect security is defined for computationally unbounded adversaries. Computational security makes two relaxations:

  1. Efficient adversaries only. The adversary is restricted to probabilistic polynomial-time (PPT) algorithms. This models realistic attackers with bounded resources.
  2. Negligible advantage. The adversary’s success probability may exceed random guessing, but only by a negligible amount - a function that shrinks faster than any inverse polynomial.

These relaxations are not arbitrary: they exactly capture what a realistic adversary can do, and they allow key lengths $n$ much shorter than the message length.

Negligible Functions

A function $\varepsilon: \mathbb{N} \to \mathbb{R}^{\geq 0}$ is negligible if for every polynomial $p(\cdot)$, there exists $N$ such that for all $n > N$: $$\varepsilon(n) < \frac{1}{p(n)}$$ It shrinks faster than any inverse polynomial. Examples:

  • $2^{-n}$ - negligible (shrinks exponentially)
  • $n^{-100}$ - not negligible (inverse polynomial)
  • $2^{-\sqrt{n}}$ - negligible (sub-exponential decay)

Closure properties. If $\varepsilon_1, \varepsilon_2$ are negligible and $p$ is a polynomial:

  • $\varepsilon_1 + \varepsilon_2$ is negligible (finite sums of negligible are negligible)
  • $p(n) \cdot \varepsilon_1(n)$ is negligible (polynomial factor does not rescue a negligible function)

Proof (sum is negligible). For any polynomial $q(n)$, we need $\varepsilon_1(n) + \varepsilon_2(n) < 1/q(n)$ for large $n$. Since $\varepsilon_1$ is negligible, it is eventually $< 1/(2q(n))$; same for $\varepsilon_2$. For large enough $n$, both hold simultaneously, so the sum is $< 1/q(n)$. $\square$

The security parameter $n$ is the key length (or the input length to Gen). All security guarantees are stated asymptotically in $n$.

One-Way Functions

A function $f: \{0,1\}^* \to \{0,1\}^*$ is a one-way function (OWF) if:

  1. Easy to compute: there is a polynomial-time algorithm computing $f(x)$.
  2. Hard to invert: for every PPT algorithm $A$ and all polynomials $p$, for large enough $n$: $$\Pr_{x \leftarrow \{0,1\}^n}[A(f(x)) \in f^{-1}(f(x))] < \frac{1}{p(n)}$$ Any PPT inverter succeeds with negligible probability over a random input.

Candidate OWFs. No function is proven to be one-way (this would imply P $\neq$ NP), but strong candidates exist:

  • Discrete logarithm problem (DLP): given a cyclic group $\mathbb{G}$ of prime order $q$ with generator $g$, and $y = g^x$, find $x$. $f: x \mapsto g^x$ is conjectured to be one-way.
  • Integer factoring: given $N = pq$ (product of two large primes), find $p$ and $q$. $f: (p,q) \mapsto pq$ is conjectured one-way.
  • Subset sum: given $a_1, \ldots, a_n, t$, decide if some subset sums to $t$. Average-case hard.

OWF vs. Trapdoor OWF. A trapdoor OWF is a OWF that is easy to invert given a secret trapdoor $td$. RSA is the canonical example: $f(x) = x^e \bmod N$ is hard to invert without the factorization of $N$ (the trapdoor), but easy to invert with it ($x = c^d \bmod N$ where $d = e^{-1} \bmod \phi(N)$). Trapdoor OWFs enable public key cryptography; plain OWFs are sufficient for symmetric key constructions.

Hardcore Predicates

Even if $f(x)$ hides $x$ completely, it might leak some bits. For example, if $f(x) = g^x$ in $\mathbb{Z}_p^*$, does $f(x)$ leak the least significant bit of $x$?

A hardcore predicate of $f$ is a bit $b(x)$ that is computationally indistinguishable from a random bit given $f(x)$: for all PPT $A$: $$\Pr[A(f(x)) = b(x)] \leq \frac{1}{2} + \varepsilon(n)$$ for negligible $\varepsilon$. Even knowing $f(x)$, no efficient algorithm can predict $b(x)$ better than a coin flip.

The Goldreich-Levin theorem: for any OWF $f$, the inner product $b(x, r) = \langle x, r \rangle = \bigoplus_{i=1}^n x_i r_i$ is a hardcore predicate of $g(x, r) = (f(x), r)$. This is constructive: any OWF can be augmented to have a proven hardcore predicate.

DLP and LSB/MSB. For $f(x) = g^x$ in $\mathbb{Z}_p^*$:

  • LSB: The least significant bit of $x$ can be shown to be a hardcore predicate of the DLP function - recovering LSB is as hard as solving DLP in its entirety (a reduction shows that an LSB oracle solves DLP).
  • MSB: Similarly, the most significant bit is hard to recover. The proof uses a polynomial interpolation argument: if you could recover MSB, you could solve DLP by binary search.

These results mean that the DLP function hides individual bits completely - you cannot learn even a single bit of $x$ from $g^x$ more easily than solving the whole discrete log.

Pseudorandom Generators

A pseudorandom generator (PRG) is a deterministic, polynomial-time computable function $G: \{0,1\}^n \to \{0,1\}^{\ell(n)}$ with $\ell(n) > n$ (it stretches the input) such that: $$\{G(U_n)\} \approx_c \{U_{\ell(n)}\}$$ The output of $G$ on a uniform $n$-bit seed is computationally indistinguishable from a uniform $\ell(n)$-bit string. No PPT distinguisher can tell $G$’s output apart from true randomness.

Why we need this. A PRG lets us expand a short secret key (the seed) into a long pseudorandom string, which can be XOR’d with a message like a OTP - but with a short key. This gives computationally secure stream encryption.

From OWF + HCP to PRG

Theorem (Blum-Micali, Yao). If OWFs exist, then PRGs exist.

The construction uses a hardcore predicate. Let $f$ be a OWF with hardcore predicate $b$. Define: $$G(s) = b(s) | b(f(s)) | b(f^2(s)) | \cdots | b(f^{n-1}(s)), \quad f^i(s) = f(f(\cdots f(s)\cdots))$$ Output one bit per application of $f$, using the hardcore predicate. Security: if any prefix of the output is distinguishable from random, we can recover the hardcore predicate of $f$ at some step - contradicting the HCP assumption.

Extending PRGs

From $n$ to $n+1$ bits. If $G: \{0,1\}^n \to \{0,1\}^{n+1}$ is a PRG, it is secure because any distinguisher for the $n+1$-bit output could be used to recover the seed or violate pseudorandomness.

From $n$ to $\ell(n)$ bits (arbitrary polynomial stretch). Apply the $n$-to-$n+1$ PRG repeatedly: use the first $n$ output bits as the new seed, output the last 1 bit. After $\ell(n)$ steps, we have $\ell(n)$ pseudorandom bits from an $n$-bit seed. Security reduces: a distinguisher for the $\ell(n)$-bit output implies a distinguisher for the $n+1$-bit output (by a hybrid argument - the distinguisher must succeed on some consecutive pair of hybrid distributions).

The hybrid argument is the key technique: define $\ell(n)+1$ hybrid distributions $H_0, H_1, \ldots, H_{\ell(n)}$ where $H_i$ has $i$ truly random bits followed by $\ell(n)-i$ PRG-generated bits. $H_0$ is the PRG output; $H_{\ell(n)}$ is truly random. If a distinguisher tells $H_0$ from $H_{\ell(n)}$ with non-negligible probability, by averaging it must distinguish some adjacent $H_i$ from $H_{i+1}$ with non-negligible probability - but that adjacent pair differs only in one step of the $n$-to-$n+1$ PRG.

The Assumption Landscape

The hierarchy of assumptions: $$\text{OWF exists} \Longrightarrow \text{PRG exists} \Longrightarrow \text{stream cipher exists}$$ $$\text{Trapdoor OWF exists} \Longrightarrow \text{public key encryption possible}$$

OWFs are the minimal assumption for private-key cryptography. The existence of OWFs is equivalent to P $\neq$ NP in a certain average-case sense (though this connection is subtle - worst-case NP-hardness does not immediately give average-case hardness). State of the art: we have candidate OWFs (DLP, factoring, lattice problems) but no proof that any of them is actually one-way.

Summary

Concept Definition
Negligible function Shrinks faster than any inverse polynomial
OWF Easy to compute, hard to invert for PPT adversary
Trapdoor OWF OWF invertible with secret trapdoor; enables PKC
Hardcore predicate Bit hidden by the OWF output; formally: $\Pr[A(f(x))=b(x)] \leq 1/2 + \varepsilon$
PRG Deterministic stretch: $n$-bit seed $\to$ $\ell(n)$ pseudorandom bits
Blum-Micali OWF + HCP $\to$ PRG via iterated $f$
Hybrid argument Key technique for extending PRG security to polynomial stretch

Read next: