Post-Quantum Cryptography: Why Infrastructure Must Adapt

Why cryptography needs to change at all

Almost every secure connection on the internet today depends on one of two hard math problems: factoring large numbers (RSA) or solving the discrete logarithm problem on an elliptic curve (ECDSA, ECDH). Classical computers cannot solve either efficiently at the key sizes in use, which is exactly why those systems have held up for decades.

A large enough quantum computer changes that calculus. Shor’s algorithm, running on a fault-tolerant quantum machine, can solve both factoring and discrete-log problems in polynomial time — fast enough to recover a private key from its public counterpart. No such machine exists yet at the scale required, but the standardization work cannot wait for one, because switching cryptographic infrastructure across an entire industry takes years, not months. This is the entire reason post-quantum cryptography exists as a field: to have replacement algorithms ready and standardized well before the threat materializes.

The three finalized standards

NIST’s Post-Quantum Cryptography Standardization project produced three finished Federal Information Processing Standards, all published on August 13, 2024, after nearly eight years of public evaluation.

FIPS 203 (ML-KEM) standardizes a key-encapsulation mechanism — the piece that lets two parties agree on a shared secret over a public channel. It is derived from CRYSTALS-Kyber and is “believed to be secure, even against adversaries who possess a quantum computer.” It ships in three parameter sets of increasing strength and decreasing performance: ML-KEM-512, ML-KEM-768 and ML-KEM-1024.

FIPS 204 (ML-DSA), derived from CRYSTALS-Dilithium, is a lattice-based digital signature standard used for the same jobs ECDSA and RSA signatures handle today: proving a message or software update came from the party that claims to have sent it.

FIPS 205 (SLH-DSA), derived from SPHINCS+, takes a completely different mathematical approach: it is a stateless hash-based signature scheme that leans on the security of cryptographic hash functions rather than lattice problems, which gives implementers a structurally independent fallback if a weakness were ever found in the lattice-based options.

NIST has also continued standardizing additional post-quantum cryptography candidates beyond the first three: Falcon, a compact lattice-based signature scheme, and HQC, a code-based key-encapsulation mechanism selected as a backup on March 11, 2025, specifically so the ecosystem is not depending on lattice math alone.

What actually makes the new math resistant

ML-KEM and ML-DSA both derive their security from the Module Learning with Errors problem: given a set of noisy linear equations over a structured lattice, recovering the underlying secret is believed to be hard for both classical and quantum computers, because no version of Shor’s algorithm is known to apply to lattice problems of this shape. SLH-DSA sidesteps lattice math entirely and instead builds signatures out of layered hash-function calls, relying only on the one-wayness of the hash function — a property Grover’s algorithm can weaken but not break, since Grover only offers a quadratic speedup rather than the exponential break Shor provides against factoring and discrete logs.

The migration timeline NIST has set

NIST IR 8547 lays out the deprecation schedule in plain terms: the agency plans to “deprecate and ultimately remove quantum-vulnerable algorithms from its standards by 2035, with high-risk systems transitioning much earlier.” That 2035 date is a backstop, not a target — it is the point by which laggard systems become non-compliant, not the point at which teams should start planning. The National Cybersecurity Center of Excellence runs a dedicated Migration to Post-Quantum Cryptography project specifically to give organizations tools, reference architectures and interoperability testing ahead of that deadline.

Where this touches real infrastructure

Post-quantum cryptography migration is not an abstract cryptography exercise; it touches TLS certificates and the libraries that negotiate them, VPN key exchange, code-signing for firmware and software updates, and any protocol that establishes a long-lived shared secret. The most urgent category is anything with a “harvest now, decrypt later” exposure: encrypted traffic captured today and stored by an adversary can be decrypted retroactively the moment a capable quantum computer exists, which is why long-lived secrets (state records, health data, infrastructure credentials) are the highest-priority migration targets, not just data created after a cutover date. A common interim approach is hybrid key exchange, which combines a classical algorithm with a post-quantum one so that breaking either alone is not enough to compromise the session.

What to do now

NIST’s own migration guidance breaks the work into four phases: discover and inventory every place a public-key algorithm is used across hardware, firmware, operating systems, protocols, libraries and applications; prioritize those systems using a risk framework informed by Mosca’s theorem, which weighs how long data must stay secure against how long migration will take and how soon a quantum threat might arrive; take a risk-informed approach that starts replacement work now rather than waiting for certainty about quantum timelines; and migrate systematically, asset type by asset type, rather than attempting a single flag-day cutover. Building crypto-agility — the ability to swap algorithms without re-architecting a system — is the practical foundation underneath all four phases, and it is the single habit that will matter most as post-quantum cryptography standards continue to evolve with new candidates like HQC.