I want to step back from specific algorithms in this file and talk about the theoretical framework that tells me why those algorithms are considered secure or insecure in the first place: computational complexity theory. Whenever I say something like “factoring is hard” or “this cipher is secure,” I’m implicitly making a claim rooted in complexity theory — about how the resources (time, memory) needed to solve a problem scale as the problem gets larger. I find this is the piece that ties the whole series together: complexity theory is the language cryptographers use to precisely state what “hard” and “secure” actually mean.
History and Background
I trace the formal origins of computational complexity theory to the 1930s work of Alan Turing, who introduced the Turing machine as an abstract model of computation, and to Alonzo Church’s related work on computability. But complexity theory as a distinct field — concerned not just with whether a problem is computable at all, but with how efficiently it can be computed — really took shape in the 1960s and 1970s. Juris Hartmanis and Richard Stearns formalized time and space complexity classes in 1965. Stephen Cook’s 1971 paper introduced the concept of NP-completeness and the Cook-Levin theorem, and Richard Karp’s 1972 paper showed 21 important problems were NP-complete, which together kicked off the modern study of computational hardness. Cryptography’s marriage to complexity theory happened almost immediately afterward: the 1976 Diffie-Hellman paper and the 1977 RSA paper both explicitly framed their security arguments in terms of the presumed computational hardness of certain number-theoretic problems, launching the field now known as “complexity-based” or “computational” cryptography — as opposed to the “information-theoretic” security I cover in the next file.
Problem Statement
Complexity theory, in the context I care about here, addresses the question: how do I formally classify computational problems by the resources required to solve them, and how does that classification let me build cryptographic systems whose security rests on rigorous (even if unproven) hardness assumptions? Specifically, cryptography needs problems that are easy to compute in one direction (so legitimate users can encrypt/decrypt/sign efficiently) but believed intractable to invert without a secret (so attackers cannot break the scheme in feasible time) — complexity theory gives me the vocabulary and proof techniques to reason precisely about this asymmetry.
Core Concepts
- Time complexity – the number of computational steps an algorithm takes as a function of input size, usually expressed with big-O notation.
- Polynomial time (class P) – problems solvable in time bounded by a polynomial function of the input size; generally considered “efficiently solvable” or “tractable.”
- Nondeterministic polynomial time (class NP) – problems where a proposed solution can be verified in polynomial time, even if finding that solution isn’t known to be possible in polynomial time.
- NP-completeness – the hardest problems within NP, such that any NP problem can be reduced to them in polynomial time; if any NP-complete problem were solved in polynomial time, all of NP would collapse into P.
- One-way functions – functions easy to compute in one direction but believed computationally infeasible to invert; the foundational building block of most modern cryptography.
- Trapdoor functions – one-way functions that become easy to invert given a secret piece of information (the trapdoor), which is exactly the structure underlying public-key cryptosystems like RSA and the knapsack cryptosystem.
- Reduction – a way of showing that solving problem A would let me solve problem B, used both to prove hardness (if B is known-hard, and B reduces to A, then A is at least as hard) and to build security proofs (if breaking a cryptosystem would let me solve a known-hard problem, the cryptosystem inherits that hardness).
- Asymptotic vs. concrete security – asymptotic security talks about how hardness scales as key size grows toward infinity; concrete security asks the more practically relevant question of exactly how many operations an attack requires for a specific, fixed key size.
How It Works
I think about applying complexity theory to a cryptosystem’s design in these stages:
- I identify a computational problem believed to be hard — for example, integer factorization, the discrete logarithm problem, or the subset-sum (knapsack) problem.
- I design a cryptographic scheme (encryption, signature, key exchange) whose security — specifically, an attacker’s ability to break confidentiality or forge signatures — can be shown to require solving that hard problem, typically via a reduction: “if an attacker can break this scheme, I can use that attacker as a subroutine to solve the underlying hard problem.”
- I choose parameter sizes (key lengths, group sizes) large enough that, given the best known algorithms for the underlying hard problem (as covered in the factoring and discrete-log files), the concrete number of operations required to break the scheme exceeds what’s feasible with realistic computational resources over a meaningful time horizon.
- I monitor ongoing cryptanalytic research; if better algorithms are found for the underlying hard problem (reducing its complexity), I may need to increase parameter sizes or migrate to different hardness assumptions entirely.
- For schemes without a formal reduction to a well-studied hard problem, I rely instead on extensive public cryptanalysis over time as an empirical (rather than provable) form of confidence — this is the situation with most symmetric ciphers, like AES, where no P vs NP-style reduction exists, and confidence is built through decades of failed attack attempts by the research community.
Working Principle
I find the core intellectual move here is turning an unproven mathematical belief (like “factoring is hard”) into a rigorous, quantitative promise about a cryptosystem’s security, using the machinery of reductions. A security proof by reduction says something precise: “any algorithm that breaks this cryptosystem with non-negligible probability, in polynomial time, can be transformed into an algorithm that solves the underlying hard problem, also in polynomial time.” Since no known polynomial-time algorithm exists for problems like factoring or discrete log (despite decades of dedicated effort by the world’s best mathematicians and computer scientists), this gives strong (though not absolute — since P vs NP itself remains unproven) practical confidence that the cryptosystem is secure as long as the underlying assumption holds. This is fundamentally different from “security through obscurity” — the security doesn’t rest on secrecy of the algorithm, but on a mathematically precise, publicly scrutinized computational hardness claim.
Mathematical Foundation
Big-O notation, describing an algorithm’s growth rate:
$$f(n) = O(g(n)) \iff \exists c, n_0 \text{ such that } f(n) \le c \cdot g(n) \text{ for all } n \ge n_0$$
Class P (polynomial time):
$$P = { L : L \text{ decidable by a deterministic Turing machine in time } O(n^k) \text{ for some constant } k }$$
Class NP (nondeterministic polynomial time), equivalently defined via verification:
$$L \in NP \iff \exists \text{ polynomial-time verifier } V \text{ such that } x \in L \iff \exists w, |w| = O(|x|^k), V(x, w) = \text{accept}$$
NP-completeness: a problem $L$ is NP-complete if $L \in NP$ and every problem in NP polynomial-time reduces to $L$:
$$\forall L’ \in NP, \quad L’ \le_p L$$
One-way function definition: a function $f$ is one-way if it is computable in polynomial time, but for every probabilistic polynomial-time algorithm $A$, the probability of inverting it is negligible:
$$\Pr_{x \leftarrow {0,1}^n} \big[ A(f(x)) \in f^{-1}(f(x)) \big] \le \text{negl}(n)$$
Security reduction (informal template), showing a scheme’s security reduces to a hard problem’s hardness: if an adversary $\mathcal{A}$ breaks scheme $S$ with probability $\epsilon$ in time $t$, I construct an algorithm $\mathcal{B}$ using $\mathcal{A}$ as a subroutine that solves hard problem $\Pi$ with probability related to $\epsilon$ in time close to $t$:
$$\text{Adv}{\mathcal{A}}^{S}(t) \le f\big(\text{Adv}{\mathcal{B}}^{\Pi}(t’)\big)$$
for some efficiently computable relationship $f$ and comparable running time $t’$, which is the standard form of a “tight” or “loose” security reduction found throughout modern cryptographic proofs.
Diagrams
flowchart TD
A[Choose a believed-hard computational problem] --> B[Design cryptographic scheme built on that problem]
B --> C[Construct security reduction: breaking scheme implies solving hard problem]
C --> D[Choose parameter sizes based on best known algorithm complexity]
D --> E[Monitor cryptanalysis research for algorithmic improvements]
E --> F{Better algorithm found?}
F -- Yes --> G[Increase key sizes or migrate assumptions]
F -- No --> H[Confidence maintained at current parameters]Pseudocode
// Conceptual template for a reduction-based security argument
function security_reduction(adversary_A, hard_problem_instance):
// Given an adversary that breaks the cryptosystem, build a
// solver for the underlying hard problem
function solver_B(problem_instance):
scheme_instance = embed_problem_into_scheme(problem_instance)
adversary_output = adversary_A(scheme_instance)
solution = extract_hard_problem_solution(adversary_output, problem_instance)
return solution
// If adversary_A succeeds with non-negligible probability,
// solver_B solves the hard problem with related probability,
// contradicting the assumed hardness of the problem
return solver_B
// Concrete security parameter selection (illustrative)
function choose_key_size(security_level_bits, best_known_attack_complexity_fn):
key_size = minimal_starting_size
while best_known_attack_complexity_fn(key_size) < 2^security_level_bits:
key_size = increase(key_size)
return key_size
Step-by-Step Example
I’ll trace a simplified, illustrative version of a security reduction — the kind of reasoning behind RSA’s textbook security discussion (informally, not the full formal RSA assumption proof, which has some subtleties around specific attack models).
- Suppose I claim: “if an attacker can compute the private RSA exponent $d$ from the public key $(n, e)$, then that attacker can factor $n$.”
- To justify this, I construct a reduction: given an algorithm $\mathcal{A}$ that outputs $d$ from $(n, e)$, I build a factoring algorithm $\mathcal{B}$ as follows.
- $\mathcal{B}$ calls $\mathcal{A}(n, e)$ to get $d$.
- Knowing $ed \equiv 1 \pmod{\varphi(n)}$, I can compute $ed – 1$, which is a multiple of $\varphi(n)$.
- Using a known number-theoretic technique (finding a nontrivial square root of 1 modulo $n$ using the multiple of $\varphi(n)$, similar in spirit to the Miller-Rabin structure I described in the prime-generation file), $\mathcal{B}$ can, with high probability, extract a nontrivial factor of $n$.
- So $\mathcal{B}$ successfully factors $n$ using $\mathcal{A}$ as a subroutine, in time close to $\mathcal{A}$’s running time.
- Conclusion: recovering the RSA private exponent is at least as hard as factoring $n$ (since I’ve shown a way to turn a $d$-recovering algorithm into a factoring algorithm) — so as long as factoring $n$ remains computationally infeasible for the chosen key size, recovering $d$ directly (via this particular attack strategy) is also infeasible.
I find this example valuable because it shows exactly how “security” claims get built, piece by piece, from more fundamental, well-studied hardness assumptions, rather than being asserted from thin air.
Time Complexity
Complexity theory itself doesn’t have a single “time complexity” — it’s the meta-framework for describing time complexity of everything else. But within cryptography, I typically care about three specific complexity regimes: polynomial time algorithms (efficient — what a legitimate user can do, like RSA encryption at $O(k^2 \log e)$ for $k$-bit numbers), subexponential time algorithms (like the Number Field Sieve for factoring, at roughly $L_n[1/3, c]$, too slow to be practical at large scale but faster than brute force), and exponential time algorithms (like brute-force key search, at $O(2^k)$ for a $k$-bit key, considered infeasible for sufficiently large $k$). Cryptographic security parameters are chosen specifically to push the best known attack complexity for a given scheme into the “practically exponential/infeasible” regime, even when the underlying problem is only proven subexponential or is merely conjectured to lack a polynomial-time solution.
Space Complexity
Similarly, space complexity considerations show up throughout cryptanalysis: some attacks (like meet-in-the-middle attacks, or Baby-step Giant-step for discrete logs, as I described earlier) trade increased memory usage for reduced time, and a full security analysis must account for both dimensions — a “time-space tradeoff” attack that needs infeasible amounts of memory (even if the raw operation count looks feasible) may not constitute a practical break. This is why modern security parameter recommendations (like NIST’s key-size guidelines) specify security levels in terms of a combined time-and-memory cost model, not time alone.
Correctness Analysis
I think “correctness” in complexity theory takes on a different character than in the specific algorithm files earlier in this series — here, the relevant claims aren’t “does this algorithm compute the right answer” but rather “does this classification of a problem’s difficulty hold up under formal scrutiny.” The P vs NP question itself remains formally unproven (it’s one of the seven Clay Millennium Prize problems), meaning that, strictly speaking, no cryptographic scheme based on an NP-hard or presumed-hard problem has an absolute proof of security in the way a mathematical theorem does — what I actually have is a conditional guarantee: “this scheme is secure, assuming problem X is hard,” backed by a rigorous reduction proof plus decades of failed attempts by the research community to solve X efficiently. This distinction — conditional, reduction-based security versus absolute mathematical proof — is one of the most important conceptual points in all of modern cryptography, and I think every cryptography student eventually needs to internalize it.
Advantages
- Complexity-theoretic security definitions give cryptographers a precise, mathematically rigorous vocabulary for stating exactly what a scheme protects against, rather than vague or informal claims.
- Reduction-based proofs let confidence in well-studied hard problems (like factoring, after decades of attack attempts) transfer systematically to newer cryptographic constructions, without needing to re-derive confidence from scratch for every new scheme.
- The framework naturally accommodates the empirical, evolving nature of cryptanalysis — parameter sizes can be adjusted precisely as the “best known algorithm” for the underlying hard problem improves, without needing to redesign the scheme itself.
Disadvantages
- Virtually all practical public-key cryptography rests on unproven hardness assumptions (P ≠ NP is not proven, and even more specific assumptions like “factoring is hard” have no proof) — so security claims are always conditional, not absolute.
- Even a formally proven reduction can hide “loose” security bounds, where the reduction only shows a much weaker connection between breaking the scheme and solving the hard problem than the informal statement suggests, sometimes requiring much larger key sizes than a naive reading would imply.
- Symmetric cryptography (block ciphers, hash functions) generally lacks reduction-based security proofs entirely, relying instead purely on empirical cryptanalytic resistance, which is a real limitation compared to the more rigorous public-key theory.
- Advances in algorithms (classical, like GNFS improvements, or quantum, like Shor’s algorithm) can retroactively undermine hardness assumptions that seemed solid for years, which is a permanent, structural risk in complexity-based security.
Applications
Complexity theory underlies the entire theoretical justification for public-key cryptography (RSA, Diffie-Hellman, ElGamal, elliptic curve cryptosystems), the formal security proofs used in modern cryptographic protocol design (provable security, exact/concrete security analysis), and the ongoing effort to design post-quantum cryptography, where new hardness assumptions (like lattice problems or hash-based constructions) are being formally studied precisely because Shor’s algorithm complexity-theoretically breaks the classical factoring and discrete-log assumptions. Beyond cryptography, complexity theory is foundational across all of theoretical computer science, algorithm design, and the study of computational limits generally.
Implementation in C
Because complexity theory itself is a mathematical and analytical framework rather than a single algorithm, I demonstrate its application here with a small C program that empirically measures and compares the growth rates of a polynomial-time algorithm versus an exponential-time algorithm, illustrating the practical gap complexity theory predicts.
#include <stdio.h>
#include <time.h>
#include <math.h>
/* Polynomial-time example: trial division primality check, O(sqrt(n)) */
int is_prime_trial_division(long long n) {
if (n < 2) return 0;
for (long long i = 2; i * i <= n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
/* Exponential-time example: brute-force subset-sum search, O(2^n) */
int subset_sum_exists(int arr[], int n, int target) {
for (long long mask = 0; mask < (1LL << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1LL << i)) sum += arr[i];
}
if (sum == target) return 1;
}
return 0;
}
int main(void) {
/* Demonstrate polynomial-time scaling */
printf("Trial division primality timing (polynomial-time O(sqrt n)):\n");
long long test_values[] = {104729, 1299709, 15485863};
for (int i = 0; i < 3; i++) {
clock_t start = clock();
int result = is_prime_trial_division(test_values[i]);
clock_t end = clock();
double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
printf(" n=%lld prime=%d time=%.6fs\n", test_values[i], result, elapsed);
}
/* Demonstrate exponential-time scaling */
printf("\nBrute-force subset-sum timing (exponential-time O(2^n)):\n");
for (int n = 15; n <= 22; n += 2) {
int arr[22];
for (int i = 0; i < n; i++) arr[i] = i + 1;
int target = -1; /* force worst case: no solution, must check all subsets */
clock_t start = clock();
int result = subset_sum_exists(arr, n, target);
clock_t end = clock();
double elapsed = (double)(end - start) / CLOCKS_PER_SEC;
printf(" n=%d subsets_checked=2^%d found=%d time=%.6fs\n", n, n, result, elapsed);
}
return 0;
}
I designed this program to make the abstract idea of “polynomial vs. exponential growth” concrete and measurable: the primality checks stay fast even as $n$ grows into the millions, while the subset-sum brute force visibly slows down dramatically with each small increase in $n$, which is exactly the qualitative distinction complexity theory formalizes.
Sample Input and Output
Input: primality checks on three values near 100,000–15,000,000, and brute-force subset-sum searches with no valid solution (worst case) for input sizes 15 through 22.
Output (illustrative timings; exact numbers vary by machine):
Trial division primality timing (polynomial-time O(sqrt n)):
n=104729 prime=1 time=0.000002s
n=1299709 prime=1 time=0.000006s
n=15485863 prime=1 time=0.000021s
Brute-force subset-sum timing (exponential-time O(2^n)):
n=15 subsets_checked=2^15 found=0 time=0.000112s
n=17 subsets_checked=2^17 found=0 time=0.000451s
n=19 subsets_checked=2^19 found=0 time=0.001823s
n=21 subsets_checked=2^21 found=0 time=0.007290s
Even at this tiny scale, I can already see the subset-sum timings roughly quadrupling with each 2-step increase in $n$ (consistent with $2^n$ growth), while the primality check timings barely move even as the numbers being tested grow by two orders of magnitude — a small, hands-on illustration of exactly the asymptotic gap complexity theory predicts, and exactly why cryptographers can confidently push key sizes into a regime where brute-force attacks become physically infeasible.
Optimization Techniques
- When a problem is proven NP-hard, the practical response isn’t to search for a faster general algorithm (which would be a landmark result), but to look for approximation algorithms, heuristics, or special-case structure that make specific real-world instances tractable — this is a very different mindset than optimizing a polynomial-time algorithm’s constants.
- In cryptographic security-parameter selection, using the most current, best-known attack complexity (rather than outdated estimates) is essential; complexity theory’s “asymptotic” results need periodic empirical recalibration against real cryptanalytic progress (as I discussed for factoring and discrete logs).
- Building security proofs with “tight” reductions (where breaking the scheme is essentially exactly as hard as solving the underlying problem, without significant loss) allows tighter, more efficient parameter choices than “loose” reductions, which often force larger, more conservative key sizes to compensate for the gap.
Common Mistakes
- Conflating “NP-complete” with “impossible” — NP-complete problems are solvable, just not (as far as we know) in worst-case polynomial time; many real-world instances of NP-complete problems are solved efficiently in practice using heuristics.
- Treating an unproven complexity assumption (like “factoring is hard”) as an absolute mathematical certainty rather than the best current empirical and theoretical belief — a healthy cryptographic mindset keeps this distinction in view.
- Choosing cryptographic parameters based on outdated complexity estimates, ignoring subsequent algorithmic improvements (like advances in the Number Field Sieve, or emerging quantum algorithms), which can silently erode a scheme’s real-world security margin.
- Assuming a scheme with a rigorous security reduction is automatically as secure in practice as the underlying hard problem suggests, without checking whether the reduction is tight or loose, and without accounting for implementation-level vulnerabilities (side channels, faulty randomness) that exist entirely outside the scope of the complexity-theoretic proof.
- Forgetting that complexity theory addresses worst-case or average-case computational hardness of a mathematical problem, not the security of a full real-world system, which also depends on implementation correctness, side-channel resistance, protocol design, and key management — areas complexity theory alone doesn’t cover.
Further Reading
- Cook, S., “The Complexity of Theorem-Proving Procedures,” STOC 1971 (the paper introducing NP-completeness): https://dl.acm.org/doi/10.1145/800157.805047
- Karp, R., “Reducibility Among Combinatorial Problems,” 1972: https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf
- Goldreich, O., Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press: https://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html
- Katz, J. and Lindell, Y., Introduction to Modern Cryptography, CRC Press — a standard textbook treatment of provable security and complexity-based cryptography.
- Sipser, M., Introduction to the Theory of Computation, Cengage Learning — a standard reference for complexity classes (P, NP, NP-completeness) generally.
- The Clay Mathematics Institute’s official P vs NP problem statement: https://www.claymath.org/millennium-problems/p-vs-np-problem
