Post-Quantum Cryptography: Preparing for Tomorrow's Threats

For decades, the security of the internet has rested on a mathematical foundation: the computational difficulty of factoring large integers and computing discrete logarithms. RSA, Diffie-Hellman, ECDH, and ECDSA — the algorithms that secure TLS connections, authenticate code signing certificates, and protect email — all derive their security from problems that classical computers cannot solve in practical timeframes. Quantum computers, leveraging the principles of quantum mechanics, threaten to upend this foundation. Understanding the threat and the response — the NIST post-quantum cryptography standards finalized in 2024 — is now a necessary competency for anyone responsible for security architecture.

Classical computers operate on bits, each representing either 0 or 1. Quantum computers operate on qubits, which leverage two principles of quantum mechanics that have no classical analog:

• Superposition: A qubit can represent 0 and 1 simultaneously until measured. An n-qubit register can represent 2^n states simultaneously. This allows certain computations to explore an exponentially large search space in parallel.
• Entanglement: Qubits can be correlated in ways that have no classical equivalent. Measuring one entangled qubit instantaneously determines the state of its partner, regardless of distance. Entanglement allows quantum algorithms to coordinate computation across qubits in ways that amplify correct answers and cancel incorrect ones.

Quantum computers are not simply faster classical computers. They are fundamentally different computational machines that excel at a specific set of problems — and are actually slower than classical computers for most tasks. The threat to cryptography comes from two specific quantum algorithms that happen to target the mathematical problems underlying today's public-key cryptography.

In 1994, mathematician Peter Shor published a quantum algorithm for integer factorization and the discrete logarithm problem that runs in polynomial time on a quantum computer. On a classical computer, factoring a 2048-bit RSA modulus would take longer than the age of the universe using the best known algorithms. On a sufficiently powerful quantum computer running Shor's algorithm, the same problem could be solved in hours or days.

The impact is catastrophic for asymmetric cryptography:

• RSA — All key sizes are vulnerable. Factoring the modulus yields the private key.
• Diffie-Hellman (DH and DHE) — The discrete logarithm problem is directly solvable by Shor's algorithm.
• Elliptic Curve Cryptography (ECDH, ECDSA) — The elliptic curve discrete logarithm problem is also vulnerable to a variant of Shor's algorithm. Despite ECDSA using much smaller key sizes than RSA, it provides no quantum resistance.

All key exchange, digital signature, and certificate operations in TLS, PKI, SSH, and PGP that rely on these algorithms will be broken by a cryptographically relevant quantum computer (CRQC).

Grover's algorithm provides a quadratic speedup for searching unstructured databases. Applied to symmetric key search, it effectively halves the security level of symmetric ciphers. AES-128 currently has 128 bits of security against classical computers; Grover's algorithm reduces this to 64 bits of effective security against a quantum computer — insufficient for long-term security. AES-256 is reduced to 128 bits of effective security, which remains acceptable. The practical response is straightforward: migrate from AES-128 to AES-256 for data that must remain confidential for extended periods.

Similarly, SHA-256 has its collision resistance weakened from 128 bits to 85 bits by quantum attacks; SHA-384 and SHA-3/384 are recommended for applications requiring long-term quantum-resistant hash security.

The most urgent near-term threat is not an attacker who has already built a CRQC — no such machine exists today with the qubit count and error rates required to run Shor's algorithm against real-world keys. The threat is harvest now, decrypt later (HNDL): nation-state adversaries and well-resourced criminals are collecting encrypted traffic today, storing it, and planning to decrypt it once CRQCs become available.

Communications encrypted with RSA-2048 or ECDH that are collected today could potentially be decrypted in 5–15 years. For data that must remain confidential beyond that horizon — classified government communications, long-term medical records, trade secrets with a decade-long competitive lifecycle — the quantum threat is already operational. This reality drives the urgency of migration timelines.

After a multi-year competition and evaluation process, NIST finalized three post-quantum cryptographic standards in August 2024:

FIPS 203 — ML-KEM (Kyber): Key Encapsulation

ML-KEM (Module Lattice-based Key Encapsulation Mechanism), originally called Kyber, is the primary standard for key exchange and encryption. It is based on the Module Learning With Errors (MLWE) problem, which involves finding a secret vector given noisy linear equations over a structured lattice. No known quantum algorithm provides significant speedup for this problem class.

ML-KEM comes in three parameter sets: ML-KEM-512 (security roughly equivalent to AES-128), ML-KEM-768 (comparable to AES-192), and ML-KEM-1024 (comparable to AES-256). For most TLS and general-purpose applications, ML-KEM-768 is the recommended starting point. Public keys are approximately 1,184 bytes for ML-KEM-768 — significantly larger than ECDH's 32-64 bytes, which has implications for protocol performance and handshake sizes.

FIPS 204 — ML-DSA (Dilithium): Digital Signatures

ML-DSA (Module Lattice-based Digital Signature Algorithm), originally called Dilithium, is the primary standard for digital signatures. It is also based on lattice problems (specifically the Module Short Integer Solution problem and MLWE). ML-DSA signatures are larger than ECDSA signatures — approximately 2,420 bytes for ML-DSA-44 — which affects certificate chain sizes and code signing workflows.

FIPS 205 — SLH-DSA (SPHINCS+): Hash-Based Signatures

SLH-DSA is a stateless hash-based signature scheme. Unlike ML-DSA, it derives its security entirely from the properties of hash functions (specifically SHA-256 or SHAKE variants), not from any algebraic problem. This makes it a conservative choice — if lattice-based cryptography were unexpectedly broken, SLH-DSA would remain secure. The tradeoff is significantly larger signatures (7,856 to 49,856 bytes depending on parameter set) and slower signing performance.

During the transition period, security-conscious organizations are deploying hybrid schemes that combine classical and post-quantum algorithms. A hybrid TLS handshake, for example, might perform both X25519 (classical ECDH) and ML-KEM-768, then combine the shared secrets using a KDF. The connection is secure if either algorithm is secure — an attacker who breaks one still gains nothing. Google, Cloudflare, and major browsers have already deployed hybrid X25519+ML-KEM support in TLS 1.3. IETF RFC 9370 defines the hybrid key exchange mechanism for TLS.

The practical deployment timeline for post-quantum TLS is accelerating. As of 2025, Chrome and Firefox support X25519Kyber768 (hybrid) in TLS 1.3 by default. The IETF has active working group drafts for ML-KEM-only and hybrid ciphersuites. Certificate authorities are evaluating ML-DSA for code signing and TLS certificates, though the larger signature sizes complicate certificate chain delivery. NSA's Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) mandates post-quantum algorithms for national security systems by 2030, with hybrid use required starting in 2025.

Organizations should begin post-quantum migration planning now, not when CRQCs arrive:

1. Cryptographic inventory: Document all uses of RSA, ECDH, ECDSA, DH in your environment — TLS certificates, code signing, SSH keys, VPN configurations, encrypted data at rest, API authentication tokens.
2. Prioritize long-lived data: Identify what data encrypted today must remain confidential beyond 2030. This data faces the most urgent harvest-now-decrypt-later risk.
3. Enable hybrid TLS: Configure web servers and load balancers to support X25519+ML-KEM hybrid ciphersuites. This provides immediate quantum protection for data in transit with minimal risk.
4. Monitor vendor support: Track when your HSM vendors, PKI solutions, VPN platforms, and programming language libraries add ML-KEM and ML-DSA support.
5. Test performance impact: Larger key and signature sizes will increase handshake overhead. Benchmark ML-KEM in your specific environment before deploying to production.
6. Plan certificate migration: When CAs begin offering ML-DSA certificates, plan the rollout carefully — some clients may not support the new algorithm.

NIST Special Publication 800-208 provides guidance on stateful hash-based signature schemes (XMSS and LMS), which are appropriate for specific use cases like firmware signing where stateful operation is acceptable. Unlike ML-DSA, these schemes rely entirely on hash function security and are considered extremely conservative quantum-resistant choices. They are standardized in NIST SP 800-208 and are appropriate for root CAs and long-lived signing keys that sign infrequently.

Post-quantum cryptography is not a future concern — it is a present migration challenge. The NIST standards are finalized, browser support is shipping, and the harvest-now-decrypt-later threat means that data encrypted today may be at risk. Security teams should complete cryptographic inventories, enable hybrid TLS immediately where possible, and build PQC migration into multi-year security roadmaps. The transition is not instantaneous — it requires changes to every component that performs key exchange or digital signature operations — but the work must begin now to be complete before cryptographically relevant quantum computers arrive.