Computational Hardness and Cryptographic Security
The central insight of complexity-based cryptography — developed by Diffie, Hellman, Rivest, Shamir, and Adleman in the 1970s — is that security does not require a problem to be impossible to solve, only infeasible in practice. Infeasibility is given a precise meaning: a computation is feasible if it runs in polynomial time O(nk), and infeasible if it requires super-polynomial time on all known algorithms. This reframing connects cryptographic security to complexity theory.
It also reveals a troubling dependency: the security of most deployed cryptography is conditional, not proven. We believe certain problems are hard; we cannot prove it. The P vs NP question, unresolved since 1971, sits at the foundation of this belief.
A cryptographic scheme is computationally secure if no probabilistic polynomial-time (PPT) adversary can break it with non-negligible probability. A function f(n) is negligible if for every constant c, f(n) < n−c for all sufficiently large n. Security is always relative: it holds if and only if the underlying hardness assumption holds.
NP-hardness is a worst-case notion — there exist hard instances, but not necessarily most instances. Cryptography requires average-case hardness: the problem must be hard on typical, uniformly sampled inputs. An NP-hard problem whose random instances are easy cannot serve as a cryptographic assumption. This gap explains why most cryptographic assumptions are not "NP-hard problems" but specific structured problems believed hard on average.
Security proofs work by reduction: to prove scheme S is secure under assumption X, one shows that any PPT adversary against S can be converted into a PPT algorithm solving X — contradicting the hardness of X. Security therefore always reads: "if X is hard, then S is secure."
Cryptographic Assumptions: A Hardness Hierarchy
Assumptions form a hierarchy of strength. Stronger assumptions enable more powerful constructions; weaker assumptions provide stronger guarantees. The goal of theoretic cryptography is to build powerful primitives from the mildest possible assumptions.
One-Way Functions
One-way functions are the cornerstone of modern cryptography. Remarkably, their existence has never been proved — it remains an assumption supported by decades of failed attempts to disprove it and by the widespread belief that P ≠ NP.
A function f : {0,1}* → {0,1}* is one-way if:
- Easy to compute: There exists a polynomial-time algorithm computing f(x) for all x.
- Hard to invert: For every PPT algorithm A and every polynomial p(·), for sufficiently large n: Pr[f(A(1n, f(x))) = f(x)] < 1/p(n), where x ←R {0,1}n.
This is an average-case definition: A must fail on a non-negligible fraction of inputs, not just on adversarially chosen hard instances.
Easy direction: computing f(x)
- Integer multiplication: p · q computed in O(log² n) time
- Modular exponentiation: gx mod p via repeated squaring in O(log x) steps
- SHA-256: Any input hashed in linear time
- Lattice rounding: As · s + e computed in O(n²) time
Hard direction: inverting f
- Integer factoring: Best known (GNFS) is sub-exponential — infeasible for 2048-bit n
- Discrete logarithm: Recover x from gx mod p — sub-exponential algorithms known, hard for suitable groups
- SHA-256 preimage: No sub-exponential algorithm known
- LWE inversion: Recover s from {(aᵢ, aᵢ·s + eᵢ)} — as hard as worst-case lattice problems
Trapdoor One-Way Functions
A function f is a trapdoor one-way function if it is one-way but has an associated trapdoor t such that, given t, f can be efficiently inverted: there exists a PPT algorithm B with B(f(x), t) = x for all x. The trapdoor is secret and generated alongside f.
Trapdoor functions are the basis of public-key cryptography. The public key is the forward direction of f (easy to compute); the private key is the trapdoor t (enables inversion). In RSA, the public modulus n = pq and exponent e are easy to apply; decryption requires knowing φ(n) = (p−1)(q−1), which is easy only given p and q.
The Cryptographic Primitive Hierarchy
One of the deepest results in theoretical cryptography is that one-way functions are both necessary and sufficient for a large family of primitives (Goldreich, Håstad, Impagliazzo, Levin, Luby — 1980s–90s):
Each arrow represents a proven construction. The entire chain collapses if OWFs do not exist — making the OWF conjecture the single most foundational assumption in all of cryptography.
If f is a one-way function, then g(x, r) = (f(x), r) is a one-way function whose hard-core bit is ⟨x, r⟩ (inner product mod 2). This unpredictable bit is the seed of the PRG construction, establishing the chain from OWFs to pseudorandomness. The result is the key step showing every one-way function harbors computationally unpredictable information.
Evaluating Cryptographic Assumptions
Reduction-Based Security Proofs
A security reduction shows breaking a scheme is at least as hard as solving a known hard problem. Given any PPT adversary A against scheme S, one constructs a PPT algorithm RA solving the hard problem using A as a subroutine. If the hard problem is genuinely hard, no efficient adversary can exist.
- Assumption: The RSA problem is hard: given (n, e, y), compute x with xe ≡ y (mod n).
- Scheme: Textbook RSA: encrypt m as c = me mod n; decrypt using d = e−1 mod φ(n).
- Reduction: Any PPT algorithm decrypting arbitrary RSA ciphertexts directly solves the RSA problem. So if RSA is hard, no such decryptor exists.
- Caveat: Textbook RSA is deterministic and not semantically secure (CPA-insecure). Real-world RSA-OAEP achieves IND-CCA2 security under a tighter reduction in the random oracle model.
The Impagliazzo Five Worlds
Russell Impagliazzo's 1995 paper described five possible worlds based on which hardness assumptions hold — a framework that structures how complexity theory and cryptography relate:
- Algorithmica: P = NP. All efficiently verifiable problems are efficiently solvable. Cryptography as we know it does not exist.
- Heuristica: P ≠ NP but NP is easy on average. Hard instances exist in theory but are rare in practice. Most cryptographic hash functions fail.
- Pessiland: NP is hard on average but one-way functions do not exist. Hard to solve, but no trapdoor enables legitimate users to work faster than adversaries. The worst world for cryptographers.
- Minicrypt: One-way functions exist but public-key cryptography does not. Symmetric cryptography (encryption, MACs, PRGs) works; key exchange and public-key encryption require pre-shared secrets.
- Cryptomania: Public-key cryptography exists — trapdoor functions, PKE, digital signatures, and key agreement all work securely. The world we believe we inhabit.