Every RSA key exchange happening right now — every TLS handshake securing your bank login, every VPN tunnel protecting corporate traffic, every SSH session managing cloud servers — relies on a mathematical assumption: that factoring large numbers and computing discrete logarithms is computationally infeasible. For classical computers, that assumption has held for decades. A sufficiently powerful quantum computer running Shor's algorithm will break it in hours.
This is not a theoretical concern for the distant future. Nation-state intelligence agencies are already recording encrypted internet traffic with the explicit plan to decrypt it later when quantum computers become available. This "harvest now, decrypt later" strategy means the data you encrypt today with RSA or ECC may be readable by adversaries within the next decade. The post-quantum transition is not about preparing for a future threat — it is about addressing a threat that is already active.
The Quantum Threat to Modern Cryptography
What quantum computers break
Quantum computers threaten cryptography through two algorithms. Shor's algorithm efficiently solves integer factorization and the discrete logarithm problem — the mathematical foundations of RSA, DSA, ECDSA, ECDH, and all Diffie-Hellman variants. A cryptographically relevant quantum computer (CRQC) running Shor's algorithm could break RSA-2048 in hours, rendering the vast majority of internet encryption, digital signatures, and key exchange protocols useless.
Grover's algorithm provides a quadratic speedup for unstructured search, effectively halving symmetric key lengths. AES-256 drops to roughly 128-bit security, AES-128 drops to 64-bit security. SHA-256 collision resistance drops from 128 bits to approximately 85 bits. This means AES-256 and SHA-384/SHA-512 remain adequately secure against quantum attacks — the crisis is specifically in asymmetric (public-key) cryptography.
The specific crypto systems broken by quantum computers include:
Key exchange: RSA key transport, Diffie-Hellman, ECDH (X25519, P-256, P-384) — used in TLS/HTTPS, SSH, VPNs, Signal Protocol, and virtually every secure communication.
Digital signatures: RSA signatures, DSA, ECDSA (P-256, P-384), Ed25519 — used in TLS certificates, code signing, package managers (npm, pip, apt), document signing, blockchain, and authentication tokens.
Not significantly impacted: AES-256, ChaCha20-Poly1305, SHA-384, SHA-512, HMAC-SHA-256 with strong keys — symmetric algorithms and hash functions need larger parameters but are not fundamentally broken.
The harvest-now, decrypt-later timeline
The harvest-now, decrypt-later (HNDL) attack makes the quantum threat immediate rather than future. Intelligence agencies and advanced persistent threats are intercepting and storing encrypted communications today. When quantum computers become available, they will decrypt the archives. The risk calculation is straightforward:
If the time to migrate (T_migrate) plus the shelf life of your data (T_shelf) is greater than the time until a CRQC exists (T_quantum), you are already too late.
Consider: if your organization has data that needs to remain confidential for 20 years (medical records, legal communications, trade secrets), and migration to PQC takes 5-10 years (realistic for large enterprises), you needed to start migration when T_quantum was 25-30 years away. Most experts place T_quantum at 10-20 years. The math is clear: organizations with long-lived secrets should already be migrating.
The NSA acknowledged this urgency in its September 2022 announcement (CNSA 2.0), requiring all National Security Systems to transition to quantum-resistant algorithms by 2033, with software and firmware signing required by 2025 and web servers/cloud services by 2025.
NIST Post-Quantum Cryptography Standards
After an 8-year evaluation process that began in 2016 with 69 candidate submissions, NIST finalized three post-quantum cryptography standards in August 2024 (FIPS 203, 204, and 205). These are the algorithms the world will migrate to.
ML-KEM (FIPS 203) — Key Encapsulation
ML-KEM (Module-Lattice Key Encapsulation Mechanism, formerly CRYSTALS-Kyber) replaces ECDH and RSA key transport for key exchange. It is based on the Module Learning With Errors (MLWE) problem — a lattice-based mathematical problem that is believed to be hard for both classical and quantum computers.
ML-KEM comes in three parameter sets: ML-KEM-512 (NIST Security Level 1, roughly equivalent to AES-128), ML-KEM-768 (Level 3, roughly equivalent to AES-192), and ML-KEM-1024 (Level 5, roughly equivalent to AES-256). ML-KEM-768 is the recommended default for most applications.
Key sizes are larger than classical algorithms: ML-KEM-768 public keys are 1,184 bytes and ciphertexts are 1,088 bytes, compared to 32 bytes for X25519. However, ML-KEM is fast — encapsulation and decapsulation take roughly 100-200 microseconds on modern hardware, comparable to X25519. The larger sizes primarily impact bandwidth (TLS handshake size increases by approximately 2 KB when using hybrid key exchange) rather than computation time.
ML-DSA (FIPS 204) — Digital Signatures
ML-DSA (Module-Lattice Digital Signature Algorithm, formerly CRYSTALS-Dilithium) replaces RSA, ECDSA, and EdDSA signatures. It is also based on the MLWE problem, providing consistency with ML-KEM in the lattice-based security assumption.
ML-DSA comes in three parameter sets: ML-DSA-44 (Level 2), ML-DSA-65 (Level 3, recommended default), and ML-DSA-87 (Level 5). Signature sizes are significantly larger than classical algorithms: ML-DSA-65 signatures are 3,309 bytes (compared to 64 bytes for Ed25519) and public keys are 1,952 bytes (compared to 32 bytes for Ed25519). Signing and verification speeds are fast — ML-DSA-65 signs in approximately 500 microseconds and verifies in approximately 200 microseconds.
The large signature sizes are particularly impactful for: TLS certificate chains (each certificate in the chain includes a signature, and chains typically have 2-3 certificates), code signing (every signed artifact grows by several KB), DNSSEC (DNS responses with large signatures may exceed UDP packet sizes, forcing TCP fallback), and blockchain transactions.
SLH-DSA (FIPS 205) — Hash-Based Signatures
SLH-DSA (Stateless Hash-Based Digital Signature Algorithm, formerly SPHINCS+) is NIST's backup signature algorithm. Unlike ML-KEM and ML-DSA, SLH-DSA's security is based on hash functions rather than lattice problems. This provides a different mathematical foundation — if the MLWE assumption underlying ML-DSA is ever broken (unlikely but theoretically possible), SLH-DSA remains secure as long as hash functions remain secure.
The tradeoff is size and speed. SLH-DSA signatures range from 7,856 bytes (fast variant) to 49,856 bytes (small variant). Signing is significantly slower than ML-DSA (milliseconds to seconds depending on the parameter set). SLH-DSA is intended as a conservative fallback for applications that require long-term security guarantees and can tolerate larger signatures, such as firmware updates, certificate authority root certificates, and critical infrastructure signing.
Real-World PQC Deployments Already Happening
Post-quantum cryptography is not a future technology waiting for standards — it is already deployed in production systems used by billions of people.
Signal Protocol (PQXDH, September 2023): Signal upgraded its key agreement protocol from X3DH to PQXDH, which combines X25519 (classical ECDH) with ML-KEM-768 (post-quantum). Every new Signal conversation now uses hybrid post-quantum key exchange. If either the classical or PQC component is secure, the overall key exchange is secure — this "hybrid" approach provides protection against both classical and quantum adversaries while mitigating the risk that PQC algorithms have undiscovered weaknesses.
Apple iMessage PQ3 (March 2024): Apple deployed PQ3, which adds post-quantum key exchange to iMessage. PQ3 goes beyond initial key establishment — it periodically re-keys using post-quantum methods throughout the conversation, providing post-quantum protection for ongoing messages even if initial keys are compromised. Apple describes PQ3 as "Level 3" security (post-quantum protection with periodic re-keying), compared to Signal's PQXDH which provides post-quantum protection at initial key establishment.
Google Chrome (2024): Chrome enabled X25519Kyber768 hybrid key exchange for TLS by default starting in Chrome 124. This means every HTTPS connection from Chrome to a supporting server uses post-quantum key exchange. Google's servers support hybrid PQC, so all Chrome-to-Google traffic (Search, Gmail, YouTube, Drive) is protected against harvest-now-decrypt-later attacks.
Cloudflare (2024): Cloudflare enabled post-quantum TLS key exchange for all customers, meaning any website behind Cloudflare can benefit from PQC key exchange when visitors use browsers that support it. No configuration required by the website operator.
AWS KMS (2024): AWS Key Management Service added support for ML-KEM hybrid key establishment for TLS connections to the KMS API. AWS also published guidance on PQC migration for AWS services including S3, CloudFront, and API Gateway.
PQC Migration Strategy: A Step-by-Step Approach
Step 1: Build your Cryptographic Bill of Materials (CBOM)
Before you can migrate, you need to know what you are migrating from. A CBOM catalogs every cryptographic algorithm, key size, protocol version, and library in your systems. This is the PQC equivalent of a software bill of materials (SBOM) and is the foundation of any migration plan.
Your CBOM should include: TLS configurations (cipher suites, key exchange algorithms, certificate types), SSH key types and sizes, VPN protocols and their underlying crypto, code signing keys and algorithms, database encryption algorithms and key management, API authentication mechanisms (JWT signing algorithms, OAuth token signing), PKI infrastructure (CA algorithms, certificate chain algorithms), stored encrypted data (algorithms, key sizes, key management), and third-party dependencies that include crypto libraries (OpenSSL version, BoringSSL, libsodium, etc.).
Automated tools for CBOM generation include: IBM's Quantum Safe Explorer (scans Java, Python, C/C++ code for cryptographic usage), AWS encryption SDK's built-in algorithm cataloging, and custom scanning using grep/semgrep patterns for common crypto API calls. For TLS specifically, tools like SSLscan, testssl.sh, and Qualys SSL Labs provide cipher suite inventories.
Step 2: Classify data by quantum risk
Not all data faces equal quantum risk. Classify your data based on how long it needs to remain confidential:
Critical (migrate immediately): Classified or government data, long-term trade secrets, medical records (decades-long retention requirements), legal privilege communications, biometric data (cannot be changed if exposed), and cryptographic root keys (CA keys, HSM master keys).
High (migrate within 2-3 years): Financial records, customer PII, authentication credentials (but these are rotation-mitigated), intellectual property with 10+ year commercial value, and VPN traffic carrying sensitive corporate data.
Medium (migrate within 5 years): General encrypted communications, transactional data with shorter retention requirements, internal business data.
Low (migrate on natural upgrade cycle): Public-facing website TLS (content is not confidential), session tokens (short-lived), and data with sub-5-year confidentiality requirements.
Step 3: Deploy hybrid PQC for highest-priority systems
Hybrid cryptography combines classical and post-quantum algorithms so that security depends on either algorithm being secure. This is the industry-standard approach for early PQC deployment because it provides immediate quantum protection without depending solely on newly standardized algorithms that have not had decades of cryptanalysis.
For TLS connections: upgrade to OpenSSL 3.5+ or BoringSSL (Google's fork, used in Chrome), which support X25519Kyber768 hybrid key exchange. Configure servers to prefer hybrid cipher suites. Clients (browsers, API clients) supporting hybrid PQC will negotiate it automatically. CloudFront, Cloudflare, and nginx (with appropriate OpenSSL version) support hybrid PQC TLS.
For VPN: evaluate WireGuard implementations with PQC key exchange (Rosenpass, WireGuard Quantum), OpenVPN with PQC-enabled OpenSSL, or commercial VPN solutions that support hybrid PQC (Palo Alto Networks, Cisco, Juniper have announced PQC roadmaps).
For SSH: OpenSSH 9.0+ supports hybrid ML-KEM+X25519 key exchange (sntrup761x25519-sha512). Update to the latest OpenSSH version and configure PQC-preferred key exchange algorithms in sshd_config.
Step 4: Achieve cryptographic agility
Cryptographic agility is the ability to swap algorithms and parameters without code changes or application redeployment. This is the single most important long-term investment for PQC migration because:
PQC algorithms are newer than classical algorithms and may have undiscovered weaknesses. NIST selected algorithms based on the current state of cryptanalysis, but the history of cryptography includes schemes that were believed secure and later broken (MD5, SHA-1, DES, RC4). If ML-KEM or ML-DSA is broken by a new classical or quantum attack, you need the ability to swap to an alternative (SLH-DSA or a future algorithm) rapidly.
Achieving cryptographic agility means: centralizing crypto configuration (algorithm, key size, mode) in a configuration layer rather than hardcoding in application code, abstracting crypto behind provider interfaces (Java JCA, .NET CryptoServiceProvider, PKCS#11), versioning encrypted data (include algorithm identifiers in ciphertext headers so you can decrypt with the correct algorithm even after migration), and testing algorithm swaps in CI/CD to ensure applications function correctly with different algorithms.
Understanding Lattice-Based Cryptography
Both ML-KEM and ML-DSA are built on lattice problems — specifically, the Module Learning With Errors (MLWE) problem. Understanding the basics helps you evaluate the security claims and participate in informed decision-making about PQC adoption.
A lattice in cryptography is a regular grid of points in high-dimensional space. The fundamental hard problem is: given a point near a lattice, find the closest lattice point (the Closest Vector Problem, CVP) or find the shortest non-zero vector in the lattice (the Shortest Vector Problem, SVP). These problems are believed to be hard for both classical and quantum computers — there is no quantum algorithm that provides an exponential speedup for lattice problems the way Shor's algorithm does for factoring.
The Learning With Errors (LWE) problem adds noise to the system: given a set of linear equations with small errors, recover the secret values. Without errors, this is basic linear algebra (solvable in polynomial time). With carefully chosen errors, it becomes as hard as the worst-case lattice problems. ML-KEM and ML-DSA use the "module" variant (MLWE), which structures the lattice into modules over polynomial rings for better performance and smaller key sizes.
The security confidence in lattice-based cryptography is high: lattice problems have been studied by mathematicians and cryptographers for decades before the PQC standardization effort, no significant algorithmic breakthroughs have been found, and the connection between LWE and worst-case lattice problems provides a theoretical security foundation. However, the algorithms are newer than RSA (which has been deployed since the 1970s), and the parameters are chosen based on current understanding — this is why hybrid deployment (classical + PQC) is the recommended approach during the transition period.
Challenges and Practical Tradeoffs
Size and bandwidth impact
The most immediately visible impact of PQC is larger keys and signatures. A TLS handshake with hybrid X25519+ML-KEM-768 key exchange adds approximately 2 KB to the handshake. With ML-DSA-65 signatures in the certificate chain (2-3 certificates), handshake size increases by 10-15 KB. For most broadband connections, this is insignificant. For mobile networks with high latency, constrained IoT devices, or high-volume API endpoints handling millions of handshakes per second, the overhead is meaningful and requires testing.
DNSSEC is particularly impacted because DNS responses must fit within UDP packets (typically 1,232-4,096 bytes). ML-DSA-65 signatures alone are 3,309 bytes, which means signed DNS responses may exceed UDP limits and force TCP fallback, increasing latency and server load. Research into more compact PQC signature schemes for DNS is ongoing.
Performance considerations
PQC computation time is generally comparable to or faster than classical algorithms. ML-KEM-768 encapsulation takes approximately 150 microseconds (compared to approximately 100 microseconds for X25519 ECDH). ML-DSA-65 signing takes approximately 500 microseconds (compared to approximately 60 microseconds for Ed25519). For individual operations, these differences are negligible. For systems processing millions of TLS handshakes or signature verifications per second, the aggregate impact requires benchmarking.
Algorithm trust and maturity
RSA has been studied and attacked for over 45 years. ECC for over 30 years. ML-KEM and ML-DSA, while based on lattice problems studied for decades, have been specific algorithmic constructions for fewer than 10 years. The CRQC timeline (10-20 years) gives time for further cryptanalysis, but the HNDL threat means we cannot wait for decades of confidence before deploying. Hybrid deployment explicitly addresses this — if ML-KEM has an undiscovered weakness, X25519 still protects the key exchange.
In February 2024, a paper by Yilei Chen claimed a polynomial-time quantum algorithm for certain lattice problems, causing brief alarm in the cryptographic community. The paper was quickly found to contain errors and the claim was retracted. This episode illustrates both the active research into lattice security and the community's ability to rapidly evaluate new claims. The current consensus remains that MLWE is hard for quantum computers, but the hybrid approach provides insurance against such breakthroughs.
What You Should Do Now
The PQC transition is the largest cryptographic migration in computing history — far larger than the SHA-1 to SHA-2 migration or the TLS 1.0/1.1 deprecation. Start now, start with inventory, and start with hybrid deployment for your most sensitive systems. Here is your priority order:
Immediate (this quarter): Begin CBOM inventory. Update browsers and TLS libraries to versions supporting hybrid PQC (most are already updated). Evaluate SSH key exchange algorithms — update OpenSSH to 9.0+ and enable hybrid key exchange. For new deployments, choose TLS configurations that prefer hybrid PQC cipher suites.
Near-term (next 12 months): Deploy hybrid PQC on VPN connections carrying sensitive data. Begin testing PQC in your CI/CD pipeline. Evaluate your PKI for PQC readiness (certificate authority algorithms, certificate chain impact). Engage with your cloud providers about their PQC roadmaps (AWS, Azure, and Google all have published timelines).
Medium-term (1-3 years): Migrate internal PKI to support PQC certificates. Update code signing to PQC-hybrid where possible. Migrate stored encrypted data if using RSA or ECDH-based envelope encryption for key wrapping. Achieve full cryptographic agility across your application stack.
Ongoing: Monitor NIST PQC developments (additional algorithms under evaluation in Round 4, including BIKE and HQC for code-based key exchange). Track lattice cryptanalysis research. Test new algorithm implementations as they become available in your crypto libraries. Participate in industry migration efforts (IETF PQC working groups, industry-specific PQC guidelines from PCI SSC, HIPAA, etc.).
The quantum computer that breaks RSA does not exist today. But the encrypted traffic being recorded for future decryption is very real, very current, and very actively being collected. Post-quantum cryptography is not about preparing for a future threat — it is about closing a vulnerability window that is already open.
