Post-Quantum Cryptography: An Introduction

A public-key cryptosystem is only as secure as the computational problem it is built on. RSA's security reduces to the hardness of factoring large integers; Diffie–Hellman and ECDSA reduce to the hardness of the discrete logarithm problem in some group. Both problems share a hidden algebraic structure: they can be phrased as finding the period of a function over an abelian group. Shor's algorithm uses quantum Fourier transforms to find that period in polynomial time, and once the period is known, factoring or discrete-log falls out by elementary number theory. This is not a minor speedup — it converts a problem believed to require sub-exponential or exponential classical time into one solvable in time polynomial in the bit-length of the modulus. Post-quantum cryptography's central idea is to abandon group-structured hardness altogether and build on problems that are not known to reduce to period-finding. The three mature families are:

• Lattice-based cryptography: security rests on problems like Shortest Vector Problem (SVP) and Learning With Errors (LWE) in high-dimensional lattices, which lack the smooth algebraic structure Shor's transform exploits.
• Code-based cryptography: security rests on the hardness of decoding a random linear error-correcting code, a problem (syndrome decoding) that is NP-hard in the worst case and has resisted 45+ years of cryptanalysis, classical and quantum.
• Hash-based cryptography: signature schemes built entirely from cryptographic hash functions, whose only required property is one-wayness/collision-resistance, quantities Grover's algorithm degrades only quadratically, not exponentially.

A fourth family, isogeny-based cryptography, looked promising (SIKE) until a 2022 classical attack (Castryck–Decru) broke it, illustrating that "post-quantum" is a moving target requiring ongoing cryptanalysis, not a permanent guarantee. This is why standards bodies favor problems with long track records and worst-case-to-average-case reductions, such as lattices.

Why Shor's algorithm breaks RSA and discrete log

Both factoring and discrete log reduce to order-finding: given group elements, find the smallest $r$ such that $a^r \equiv 1$. Shor's algorithm finds $r$ using a quantum circuit that computes $a^x \bmod N$ in superposition over all $x$, then applies the quantum Fourier transform (QFT) to extract the period $r$ with high probability, using only $O((\log N)^2 \log\log N)$ gates — polynomial in the input size. Classically, the best known factoring algorithm (the general number field sieve) runs in sub-exponential time $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$. The gap between polynomial quantum time and sub-exponential classical time is why a large enough fault-tolerant quantum computer would break RSA-2048 in hours, not centuries. Grover's algorithm, in contrast, searches an unstructured space of size $N$ in $O(\sqrt{N})$ quantum queries versus $O(N)$ classically — a quadratic, not exponential, speedup. This is why AES-256 and SHA-256 remain safe against quantum attack (with AES-128 downgraded to roughly 64-bit quantum security, motivating a move to 256-bit keys), while RSA and ECC of any practical size are completely broken. PQC therefore focuses entirely on replacing public-key primitives; symmetric cryptography needs only larger keys.

Lattice-based cryptography: Learning With Errors (LWE)

A lattice is the set of all integer combinations of basis vectors in $\mathbb{R}^n$. The Learning With Errors problem, introduced by Regev in 2005, asks an adversary to recover a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$ given many noisy linear equations: ``` given: (a_i, b_i) where b_i = + e_i (mod q) a_i drawn uniformly at random from Z_q^n e_i drawn from a small "error" distribution (e.g., discrete Gaussian) find: s ``` Without the noise $e_i$, this is trivial linear algebra (Gaussian elimination). The noise is what makes LWE hard: distinguishing $(a_i, b_i)$ from uniformly random pairs is believed to be as hard as solving worst-case lattice problems like the approximate Shortest Vector Problem, via a formal reduction proved by Regev. This "worst-case to average-case" reduction is a major reason lattices are trusted: breaking a randomly generated LWE instance would imply an efficient algorithm for the worst-case lattice problem, something 40+ years of lattice research has failed to find, quantumly or classically.

Kyber (standardized as ML-KEM) is a key-encapsulation mechanism (KEM) built on Module-LWE, a structured variant of LWE that uses polynomial rings for efficiency. Here is the core mechanism, simplified to essentials: ``` PARAMETERS: ring R_q = Z_q[x] / (x^n + 1), matrix dimension k, error distribution χ KEYGEN(): A ← uniform random k×k matrix over R_q # public, can be a shared seed s, e ← sampled from error distribution χ, each a length-k vector over R_q t ← A·s + e # (mod q), the "noisy" public value public_key ← (A, t) secret_key ← s return (public_key, secret_key) ENCAPSULATE(public_key = (A, t)): r, e1, e2 ← sampled from χ u ← A^T·r + e1 # (mod q) v ← t^T·r + e2 + encode(m) # m: random shared-secret seed ciphertext ← (u, v) shared_secret ← KDF(m) return (ciphertext, shared_secret) DECAPSULATE(secret_key = s, ciphertext = (u, v)): m' ← decode(v - s^T·u) shared_secret ← KDF(m') return shared_secret ``` Decapsulation works because $v - s^T u \approx t^T r + \text{encode}(m) - s^T(A^T r) = (As+e)^T r + \text{encode}(m) - s^T A^T r = e^T r + \text{encode}(m)$, and the accumulated error $e^T r$ is small enough that `decode` (a rounding function) recovers $m$ correctly with overwhelming probability, while an eavesdropper who only sees $(A, t, u, v)$ faces a Module-LWE instance that is computationally indistinguishable from random.

Code-based cryptography: McEliece

The McEliece cryptosystem, proposed in 1978, is one of the oldest public-key schemes never broken by a structural attack, classical or quantum. It hides an efficiently decodable error-correcting code (a binary Goppa code) so that it looks like a random linear code, whose decoding problem (finding the nearest codeword given noise) is NP-hard in general. ``` KEYGEN(): Choose a binary Goppa code C with generator matrix G (k×n), able to correct t errors S ← random invertible k×k matrix # scrambler P ← random n×n permutation matrix # scrambler G_pub ← S·G·P # looks like a random linear code public_key ← (G_pub, t) secret_key ← (S, G, P, efficient_decoder_for_C) return (public_key, secret_key) ENCRYPT(public_key = (G_pub, t), message m): e ← random error vector of weight exactly t c ← m·G_pub + e return c DECRYPT(secret_key = (S, G, P), ciphertext c): c' ← c·P^{-1} # = m·S·G + e·P^{-1} m'·G ← decode_efficiently(c') # uses the Goppa structure m ← m'·S^{-1} return m ``` The scrambling matrices $S$ and $P$ disguise the Goppa code's structure so that an attacker sees only $G_{pub}$, from which recovering $m$ requires decoding a seemingly random linear code — believed hard even for quantum computers, since no quantum algorithm is known to solve general syndrome decoding faster than a modest (Grover-style, quadratic) speedup over the best classical decoding algorithms (information-set decoding). The tradeoff: public keys are large (hundreds of KB to ~1MB for Classic McEliece), but ciphertexts are small and the scheme's hardness assumption is exceptionally well-tested by decades of cryptanalysis.

Hash-based signatures: the Merkle tree construction

Hash-based signatures rest on the weakest possible assumption: that a cryptographic hash function is one-way and collision-resistant. The building block is a one-time signature (OTS) scheme, such as Lamport signatures, combined into a many-time scheme using a Merkle hash tree. ``` LAMPORT KEYGEN (one-time use only): for i in 1..256: # for each bit of a 256-bit message hash sk[i][0], sk[i][1] ← random 256-bit strings pk[i][0] ← H(sk[i][0]) pk[i][1] ← H(sk[i][1]) return (pk, sk) LAMPORT SIGN(message m, sk): h ← H(m) # 256-bit digest for i in 1..256: signature[i] ← sk[i][ bit_i(h) ] return signature LAMPORT VERIFY(message m, signature, pk): h ← H(m) for i in 1..256: if H(signature[i]) != pk[i][ bit_i(h) ]: return REJECT return ACCEPT ``` A Lamport key pair is secure for exactly one signature — reusing it leaks half of each `sk[i]` pair, letting a forger sign a second, different message. Merkle's insight (1979) was to authenticate many one-time public keys with a single, small public key using a binary hash tree: ``` MERKLE KEYGEN(height h): generate 2^h Lamport key pairs (pk_0..pk_{2^h - 1}, sk_0..sk_{2^h - 1}) leaves[i] ← H(pk_i) build binary tree: parent = H(left_child || right_child) root ← the single hash at the top public_key ← root secret_key ← all sk_i plus the tree structure (or seeds to regenerate them) return (public_key, secret_key) MERKLE SIGN(message m, index i, sk_i, auth_path_i): ots_sig ← LAMPORT_SIGN(m, sk_i) return (i, ots_sig, pk_i, auth_path_i) # auth_path: sibling hashes up to root MERKLE VERIFY(message m, signature = (i, ots_sig, pk_i, auth_path), public_key = root): if LAMPORT_VERIFY(m, ots_sig, pk_i) == REJECT: return REJECT node ← H(pk_i) for each sibling in auth_path (bottom to top): node ← H(node || sibling) or H(sibling || node) # per tree side return (node == root) ? ACCEPT : REJECT ``` Every leaf's one-time key is used exactly once, and the authentication path proves that leaf belongs to the tree without exposing other leaves' secrets. SPHINCS+ (standardized as SLH-DSA) extends this idea into a "stateless" hyper-tree of many such Merkle trees so that signers do not need to remember which leaf indices have already been used — a critical practical safety property, since reusing a Lamport leaf catastrophically breaks security.

Shor's algorithm. Factoring an $n$-bit integer classically via the general number field sieve costs $\exp\big(O(n^{1/3}(\log n)^{2/3})\big)$ — sub-exponential but super-polynomial. Shor's quantum algorithm costs $O(n^2 \log n \log\log n)$ gates, polynomial in $n$. The exponential-to-polynomial gap is the entire motivation for PQC: it is not that quantum computers are "somewhat faster," it is that the security parameter must be increased to infinity (impractical) to compensate, so the underlying problem must be replaced.

LWE-based schemes (Kyber/ML-KEM). Key generation, encapsulation, and decapsulation each perform $O(1)$ matrix–vector multiplications over a ring of dimension $n$ (typically $n=256$) with $k$ components (typically $k \in \{2,3,4\}$), using the Number Theoretic Transform (NTT) for $O(n \log n)$ polynomial multiplication. Total work per operation is $O(k^2 n \log n)$, which is a few hundred microseconds on commodity hardware — competitive with or faster than RSA-2048. Correctness (decapsulation recovers the right shared secret) holds as long as the accumulated noise term $e^T r$ stays below half the rounding threshold used by `decode`; parameters are chosen so this fails with probability below $2^{-128}$, an engineering choice, not a proof of unconditional correctness, but negligible for all practical purposes. Security reduces, via Regev's proof, to the worst-case hardness of approximating the shortest vector in an $n$-dimensional lattice to within a polynomial factor — a problem for which the best known quantum algorithm (still exponential in $n$) offers no meaningful advantage over the best classical lattice-reduction algorithms (e.g., BKZ).

McEliece. Encryption costs one matrix–vector multiplication, $O(nk)$ bit operations. Decryption's dominant cost is the Patterson decoding algorithm for Goppa codes, $O(n t)$ or better with modern implementations, still fast. The public key, however, is the full generator matrix, roughly $O(nk)$ bits — hundreds of kilobytes to over a megabyte, versus a few kilobytes for lattice schemes. Security rests on the assumed hardness of decoding a random-looking linear code; the best classical attacks (information-set decoding) run in time exponential in $n$, and known quantum speedups (via Grover-accelerated ISD) are only quadratic, so parameters need only modest inflation, not a change of algorithm family.

Hash-based signatures. Signing and verifying a Merkle tree of height $h$ costs $O(h)$ hash evaluations for the authentication path plus $O(\ell)$ for the one-time signature, where $\ell$ is the hash output length in bits (e.g., 256). SPHINCS+'s hypertree structure trades signature size (tens of kilobytes) for a stateless signer — no risk of catastrophic key reuse from state corruption, at the cost of speed and size. Correctness is immediate from hash-tree consistency: verification succeeds iff every hash on the path from leaf to root matches, which happens exactly when the signer possessed the correct leaf secret. Security reduces solely to the hash function's collision-resistance and (second-)preimage resistance — properties Grover's algorithm only weakens quadratically, meaning doubling the hash output length restores the original security margin. This is the most conservative of the three families precisely because it makes the fewest new assumptions.

Honest tradeoff summary. No PQC family is a strict improvement on RSA/ECC across every axis. Lattice schemes are fast and compact but rely on assumptions only ~20 years old (LWE, 2005) compared to RSA's 45+ years, and rely on structured variants (Ring-LWE, Module-LWE) whose extra algebraic structure is a theoretical (if not yet practical) attack surface. Code-based McEliece has the oldest track record but the largest keys. Hash-based signatures make the weakest assumptions but produce the largest signatures and, in stateful variants, require careful state management to avoid catastrophic reuse.

Trace a small, illustrative (non-parameter-accurate) Module-LWE-style encapsulation with tiny numbers to make the arithmetic concrete. Use modulus $q = 17$, a single ring element treated as a plain integer (i.e., $k=1$, no polynomial structure) purely to show the noise cancellation.

Setup (KeyGen).

Public key: $(a, t) = (5, 16)$. Secret key: $s = 3$.

Encapsulation. Alice wants to send shared-secret bit $m = 1$ (encoded as $\lfloor q/2 \rfloor = 8$, a standard "round to half the modulus" encoding).

Ciphertext sent: $(u, v) = (11, 6)$.

Decapsulation. Bob computes $v - s\cdot u \bmod q$:

Compare $7$ to the two possible encodings: $0$ (for $m=0$) or $8$ (for $m=1$). Since $7$ is closer to $8$ than to $0$ (distance 1 vs. distance 7, on the cyclic modulus), `decode` outputs $m=1$ — correct.

Why it worked. Expand algebraically:

The "signal" term $\text{enc}(m) = 8$ survives, perturbed only by the small combined noise term $er + e_2 - se_1 = -1$, which is far smaller than $q/4$, so rounding still recovers $m$ correctly. In real Kyber, $q=3329$, error terms are drawn from a centered binomial distribution, and the ring dimension is 256, but the cancellation mechanism is identical: the honest party's secret $s$ makes the large structured terms cancel, leaving only a small noise term that rounding can absorb, while an eavesdropper without $s$ sees values computationally indistinguishable from uniform random.

Web browsers and TLS libraries (Chrome, Firefox, BoringSSL, OpenSSL) have already deployed hybrid key exchange combining classical X25519 with ML-KEM (Kyber), so that a connection stays secure even if one of the two mechanisms is later broken. Signal and other secure-messaging protocols use similar hybrid PQC key agreement to defend against harvest-now-decrypt-later attacks on today's captured ciphertext. Governments — the U.S. National Security Agency's CNSA 2.0 suite, and equivalents in the EU and China — mandate migration timelines for classified and critical infrastructure systems. Hardware security modules, smart cards, and firmware/software update-signing systems are adopting SLH-DSA or ML-DSA for signatures where long-term trust in the algorithm matters more than signature size. Certificate authorities and the Web PKI are prototyping PQC-capable X.509 certificates, and cryptographic library maintainers (e.g., liboqs, OpenSSL 3.x providers) now ship ML-KEM and ML-DSA implementations as first-class options, marking one of the largest coordinated cryptographic migrations since the move from DES to AES.

Ask the tutor: How does the choice between ML-KEM, McEliece, and SPHINCS+ change if I'm designing a constrained IoT device versus a long-term software update signing system?