Post-Quantum Cryptography

Post-quantum cryptography (PQC) is the family of public-key schemes designed to resist attacks by large-scale quantum computers. The threat is concrete: Shor's algorithm factors integers and computes discrete logs in polynomial time on a quantum computer, which would break RSA, Diffie-Hellman, and all of ECC at once. PQC replaces those number-theoretic hardness assumptions with problems believed hard even for quantum machines - mostly lattice problems, plus hash-based and code-based alternatives.

In CTFs you rarely face a real PQC implementation. What you see is a toy version with deliberately weak parameters, a textbook LWE instance you are meant to solve with lattice reduction, or a historical scheme (like SIKE) presented as a puzzle. This page gives you the map.

Why Now: Shor, Grover, and "Harvest Now, Decrypt Later"

Grover only gives a quadratic speedup, so symmetric crypto and hashes survive by doubling key/output sizes (use AES-256, SHA-384). The crisis is entirely on the public-key side, which Shor demolishes.

The urgency driver is "harvest now, decrypt later": an adversary can record encrypted traffic today and decrypt it once a cryptographically relevant quantum computer exists. Anything that must stay secret for a decade needs PQC now, even though no such quantum computer is known to exist yet.

The NIST Standards (Finalized 2024)

After an eight-year competition begun in 2016, NIST published its first three finalized PQC standards in August 2024. Know these names - they are the canonical answers and the ones CTF flavor-text references.

• ML-KEM (Module-Lattice Key-Encapsulation Mechanism) replaces RSA/ECDH key exchange. It establishes a shared secret; you then run a normal symmetric cipher.
• ML-DSA (Module-Lattice Digital Signature Algorithm) is the default PQC signature - lattice-based, compact, fast.
• SLH-DSA (Stateless Hash-based Digital Signature Algorithm) is the conservative backup: its security rests only on hash functions, so it survives even if lattice assumptions fall. The trade-off is large signatures.

A code-based KEM, HQC, was selected in 2025 as a non-lattice backup to ML-KEM and is being standardized separately; its security rests on the hardness of decoding random linear codes rather than lattices.

Lattice Intuition: LWE and Module-LWE

Almost all the standardized schemes (ML-KEM, ML-DSA) rest on Learning With Errors (LWE) and its structured variants. The core problem is disarmingly simple: solving linear equations is easy, but solving noisy linear equations modulo $q$ is hard.

Plain LWE

Fix a modulus $q$, a secret vector $\mathbf{s} \in \mathbb{Z}_q^k$, and sample random rows $\mathbf{a}_i$ with small error $e_i$. You are given many pairs

Without the noise $e_i$, Gaussian elimination recovers $\mathbf{s}$ instantly. With small noise, recovering $\mathbf{s}$ is the search-LWE problem, believed hard for classical and quantum computers alike. In matrix form, $\mathbf{b} = A\mathbf{s} + \mathbf{e} \pmod q$.

# SageMath - generate and (for small parameters) break a toy LWE instance
q = 101            # tiny modulus for illustration
k = 10             # secret dimension
m = 40             # number of samples
s = vector(GF(q), [randint(0, q - 1) for _ in range(k)])
A = Matrix(GF(q), m, k, lambda i, j: randint(0, q - 1))
e = vector(GF(q), [randint(-1, 1) for _ in range(m)])   # small noise
b = A * s + e

# With small parameters, lattice reduction (embedding the LWE into a CVP/SVP) recovers s.
# For real ML-KEM parameters this is infeasible; for CTF toy params it is one LLL call.
print("recover s via the Kannan embedding + LLL on [[A | b], [0 | q]] style lattice")

Ring-LWE and Module-LWE

Plain LWE keys are large. Ring-LWE shrinks them by replacing vectors with polynomials in a ring $R_q = \mathbb{Z}_q[x]/(x^N + 1)$: one polynomial multiplication packs $N$ inner products. Module-LWE (the "M" in ML-KEM / ML-DSA) is the middle ground - small matrices of ring elements - giving a tunable security/size trade-off. Both reduce, in the worst case, to hard lattice problems (SVP/CVP), the same ones from the lattice attacks page.

Isogenies and the Fall of SIKE/SIDH

Isogeny-based cryptography was a leading PQC candidate built on walks in graphs of supersingular elliptic curves. SIDH (Supersingular Isogeny Diffie-Hellman) and its KEM form SIKE were attractive for their tiny key sizes and reached the fourth round of the NIST process.

The attack exploits the auxiliary torsion-point images that SIDH publishes, using a theorem of Kani to glue curves and reconstruct the secret isogeny. It does not affect lattice-, hash-, or code-based PQC - only the SIDH/SIKE construction. Newer isogeny schemes such as CSIDH and SQIsign use different structure and are not broken by Castryck-Decru, though they remain niche.

# SageMath - the SIDH setting (educational; the scheme itself is broken)
# Work over a supersingular curve E / F_{p^2}; parties walk distinct l-isogeny graphs.
p = 2**216 * 3**137 - 1     # SIKEp434-style prime shape: p = 2^a * 3^b - 1
F.<i> = GF(p**2, modulus=x**2 + 1)
E0 = EllipticCurve(F, [0, 6, 0, 1, 0])
print("supersingular?", E0.is_supersingular())
# Real challenges that revolve around SIDH expect you to apply the Castryck-Decru
# recovery (NCC Group and Fox-IT published SageMath implementations).

What Shows Up in CTFs

The recurring lesson: the standardized schemes are not broken, so a solvable challenge has a specific injected weakness - small parameters, missing noise, a reused value, or a withdrawn primitive. Identify the deviation from the real spec and the lattice (or algebra) does the rest. The mechanics of the lattice reduction are on the lattice attacks page.

Checklist

• Is the public key really PQC, or RSA/ECC in disguise? Shor only matters for the latter.
• LWE-shaped challenge ($\mathbf{b} = A\mathbf{s} + \mathbf{e} \bmod q$)? Check dimension, modulus, noise size.
• Parameters tiny or noise absent? Gaussian elimination or a single LLL/BKZ call.
• Names: ML-KEM = FIPS 203 (Kyber), ML-DSA = FIPS 204 (Dilithium), SLH-DSA = FIPS 205 (SPHINCS+).
• SIDH / SIKE mentioned? It is broken - apply Castryck-Decru, do not look for a lattice.
• Real-spec interop needed? Reach for liboqs; an exploit needs an injected bug, not a break of the scheme.

See Also

• Lattice Attacks - LLL, BKZ, and Coppersmith, the engine behind breaking toy LWE.
• RSA Basics - the factoring assumption Shor's algorithm destroys.
• ECC Basics - the discrete-log assumption Shor's algorithm also destroys.
• PRNG Attacks - another place "small parameters" turns a hard problem easy.

Last updated on Jun 15, 2026