Post-Quantum Cryptography: Preparing for the Quantum Era

Post-Quantum Cryptography: Preparing for the Quantum Era

Post-quantum cryptography (PQC) refers to cryptographic algorithms that are secure against attacks from both classical and quantum computers. Current widely used algorithms—RSA, Elliptic Curve Cryptography (ECC), and Diffie-Hellman—are vulnerable to quantum computers running Shor's algorithm. A sufficiently large quantum computer could break these algorithms in hours or minutes, rendering most of today's internet security obsolete. PQC develops new algorithms based on mathematical problems that are believed to be hard for both classical and quantum computers, ensuring long-term security in the quantum era.

To understand post-quantum cryptography properly, it helps to be familiar with public key cryptography, encryption fundamentals, and quantum computing basics.

┌─────────────────────────────────────────────────────────────────────────┐
│                     Post-Quantum Cryptography (PQC)                       │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                          │
│   Quantum Threat:                          PQC Solutions:               │
│   ┌─────────────────────────────────┐     ┌─────────────────────────┐   │
│   │ Shor's Algorithm breaks:        │     │ Lattice-Based Crypto    │   │
│   │ • RSA                           │     │ • CRYSTALS-Kyber (KEM)  │   │
│   │ • ECC (ECDH, ECDSA)             │     │ • CRYSTALS-Dilithium    │   │
│   │ • Diffie-Hellman                │     │   (Signatures)          │   │
│   └─────────────────────────────────┘     │ • FALCON (Signatures)   │   │
│                                            └─────────────────────────┘   │
│   Grover's Algorithm halves              ┌─────────────────────────┐   │
│   symmetric security:                    │ Code-Based Crypto       │   │
│   • AES-128 → 64-bit effective          │ • Classic McEliece (KEM)│   │
│   • Use AES-256 (still secure)          └─────────────────────────┘   │
│                                          ┌─────────────────────────┐   │
│                                          │ Multivariate Crypto     │   │
│                                          │ • Rainbow (broken)       │   │
│                                          └─────────────────────────┘   │
│                                          ┌─────────────────────────┐   │
│                                          │ Hash-Based Signatures   │   │
│                                          │ • SPHINCS+              │   │
│                                          └─────────────────────────┘   │
│                                                                          │
│   Timeline: NIST standardization complete 2022-2024.                   │
│   Migration expected 2025-2035.                                         │
│                                                                          │
└─────────────────────────────────────────────────────────────────────────┘

What Is Post-Quantum Cryptography?

Post-quantum cryptography is the study and development of cryptographic algorithms that remain secure against attacks from quantum computers. Unlike quantum cryptography (which uses quantum mechanics for key distribution), PQC uses classical mathematics but selects problems believed hard for quantum computers. PQC algorithms are designed to run on classical computers (no quantum hardware needed) while resisting both classical and quantum attacks.

• Quantum-Resistant: Algorithms believed secure against known quantum attacks.
• Classical-Compatible: Run on existing hardware (CPUs, not quantum computers).
• Standardization in Progress: NIST finalizing standards (2022-2024).

The Quantum Threat to Cryptography

Classical difficulty (factoring):
- RSA-2048: 2^100 operations (classical)

Quantum difficulty (Shor):
- RSA-2048: O((log n)^3) ≈ 10^10 operations
- Factor 2048-bit RSA in hours on large quantum computer

Threat timeline:
- Not yet (large-scale quantum computers not exist)
- "Harvest now, decrypt later" attackers record now
- Transition estimated within 10-20 years

Action needed: Migrate to PQC before quantum computers arrive

NIST Post-Quantum Cryptography Standardization

NIST (National Institute of Standards and Technology) began a multi-year process in 2016 to evaluate and standardize PQC algorithms. The process involved multiple rounds of public scrutiny and cryptanalysis.

2016 ── Call for proposals (82 submissions)
       │
       ▼
2018 ── Round 1 (69 algorithms advanced)
       │
       ▼
2019 ── Round 2 (26 algorithms)
       │
       ▼
2020 ── Round 3 (15 finalists + 8 alternates)
       │
       ▼
2022 ── Selected algorithms announced (4 + 4 alternates)
       │
       ▼
2024 ── Final standards published (expected)
       │
       ▼
2025+ ── Migration begins (industry adoption)

Selected Algorithms (July 2022)

Alternate Algorithms

Post-Quantum Cryptographic Families

Lattice-Based Cryptography

Most promising and most mature PQC family. Based on hardness of problems like Learning With Errors (LWE), Module-LWE, and NTRU. Advantages: strong security, reasonable key sizes, good performance. Standardized: Kyber (KEM), Dilithium, FALCON (signatures).

Code-Based Cryptography

Based on hardness of decoding general linear codes. Classic McEliece is oldest PQC (1978). Very large public keys (hundreds of KB to MB). Very fast encryption/decryption. Not broken by quantum (yet). Good alternate for conservative applications.

Hash-Based Signatures

Based only on security of hash functions (very conservative). SPHINCS+ is stateless (no state tracking needed). Large signatures (KB to tens of KB). Not efficient for large-scale usage. Good for firmware signing, certificates.

Multivariate Cryptography

Based on solving systems of multivariate quadratic equations. Rainbow had practical attack (2022). Ongoing research, less mature. Not currently standardized by NIST.

Family          Key Size    Signature/   Performance   Maturity
                             Ciphertext
─────────────────────────────────────────────────────────────────────────────
Lattice         Small       Small        Fast          High
(1-3KB)        (2-3KB)
Code-Based      Very Large  Very Small    Moderate      High
(McEliece)      (hundreds KB)
Hash-Based      N/A (sig)   Large         Slow          High
                (8-30KB)
Multivariate    Medium      Medium        Moderate      Low (break risk)
Isogeny         Very Small  Very Small    Very Slow     Broken (SIKE)

Hybrid Cryptography (Transition Strategy)

Hybrid cryptography combines classical (RSA/ECC) and post-quantum algorithms. Security depends on both: attacker must break both to compromise the system. Provides safety during transition while PQC confidence grows.

Traditional TLS:        Hybrid TLS:

Client Hello          Client Hello
    │                     │
    ▼                     ▼
Server Hello          Server Hello
    │                     │
    ▼                     ▼
Server Certificate    Server Certificate
(RSA/ECC)            (RSA/ECC)
    │                     │
    ▼                     ▼
Key Exchange          Key Exchange
(ECDHE) +            (ECDHE + Kyber)  ← hybrid
    │                     │
    ▼                     ▼
Finished              Finished

Result: Shared secret = KDF(secret_ECDHE || secret_Kyber)

Challenges of Post-Quantum Cryptography

• Larger Key and Signature Sizes: RSA-2048 key: 256 bytes; PQC (Kyber-1024) key: 1.5KB (6x). Classic McEliece key: 1MB+. Dilithium signature: 2-3KB (RSA-2048 signature: 256 bytes). Impacts TLS handshake latency, certificate sizes, storage.
• Performance Overhead: Key generation slower than RSA/ECC, signature generation slower (Dilithium ~ slower than RSA). Verification comparable or faster. Kyber comparable to ECDH for key exchange.
• Algorithm Maturity: RSA/ECC have decades of cryptanalysis. PQC algorithms newer, potential undiscovered weaknesses (Rainbow broken, SIKE broken). Confidence increases over time (not zero).
• Protocol Integration: Modifying TLS, SSH, IPsec, code signing, and PKI to support hybrid or pure PQC requires standards coordination, deployment across internet, and backward compatibility.
• Migration Complexity: Billions of devices (IoT, routers, browsers, servers) need updates or replacement. Long tail of legacy devices will remain vulnerable. Hybrid approach eases transition (works with existing classical systems).

Algorithm           Type              Public Key      Signature
─────────────────────────────────────────────────────────────────────────────
RSA-2048            Sign/Enc          256 bytes       256 bytes
ECDSA P-256         Signature         64 bytes        64 bytes
ECDH P-256          KEX               64 bytes        N/A

Post-Quantum:
Kyber-1024          KEX               1,568 bytes     N/A
Dilithium-3         Signature         1,472 bytes     2,701 bytes
FALCON-512          Signature         897 bytes       690 bytes
SPHINCS+-128f       Signature         64 bytes        17,088 bytes
Classic McEliece-   KEX               1,044,992 bytes N/A (enc: 188 bytes)

Post-Quantum TLS Implementation

Major browsers and cloud providers are experimenting with post-quantum TLS using hybrid key exchange (classical + PQC). Google Chrome has experimental support for X25519 + Kyber (hybrid). Cloudflare, AWS, and Google Cloud have deployed hybrid PQC in internal networks.

• Experimental Deployments: Google (Chrome, Google Cloud), Cloudflare (BoringSSL experiment), AWS (KMS, internal).

Post-Quantum Cryptography Anti-Patterns

• Waiting for Quantum Computers Before Migrating: Harvest now, decrypt later attacks already feasible. Large-scale quantum computers may arrive with little warning (break RSA instantly). Migration takes years and must start now.
• Using Broken Algorithms (SIKE, Rainbow): SIKE broken by classical computer (2022). Rainbow broken by classical computer (2022). Use only NIST-selected algorithms (Kyber, Dilithium, FALCON, SPHINCS+) or use hybrid to hedge bets.
• Premature Pure PQC (without hybrid): PQC confidence not yet as high as RSA/ECC. Pure PQC risks algorithm break. Hybrid provides safety (breaks both classical and PQC).
• Ignoring Performance Impact: Large keys and signatures affect latency, bandwidth, and storage. Test performance before production deployment. Optimize for your use case (choose smaller signatures, FALCON over Dilithium).
• Not Planning for Crypto-Agility: Cryptographic agility allows algorithm upgrades without redesign. Hardcode single algorithm → painful migration later. Use negotiation (TLS cipher suites) and hybrid agility (support multiple PQC algorithms).

❌ Wait for quantum computers before acting
❌ Use only one PQC algorithm (no backup)
❌ Replace classical crypto outright (no hybrid)
❌ Ignore performance impact on mobile/IoT
❌ Hardcode algorithm choices
❌ Assume all PQC algorithms are equally secure

✓ Harvest-now threats require action now
✓ Hybrid (classical + PQC) for safety
✓ Test performance on target hardware
✓ Design crypto-agility (symmetric to upgrade)
✓ Use NIST-selected algorithms only

Post-Quantum Cryptography Best Practices

• Start Planning Migration Now: Inventory cryptographic usage (RSA, ECC, DH). Identify systems with long-lived data sensitive from harvest now attack (encrypted backups, archived emails, long-term certificates). Create migration roadmap with hybrid deployment phase.
• Use Hybrid Cryptography Initially: Combine classical (RSA/ECC) with PQC (Kyber, Dilithium) in hybrid modes. Security depends on both, resisting attacks against either. Allows gradual migration as confidence in PQC grows. Maintains backward compatibility with classical-only systems.
• Choose NIST-Selected Algorithms: Kyber for KEM (key exchange), Dilithium or FALCON for signatures, SPHINCS+ for conservative applications. Avoid broken alternatives (SIKE, Rainbow). Prefer FALCON for smaller signatures (less bandwidth).
• Test Performance on Target Hardware: Measure handshake latency (TLS with PQC). Benchmark signature generation and verification. IoT devices may struggle with large signatures. Choose appropriate security levels (Kyber-512 vs Kyber-1024).
• Implement Crypto-Agility: Design systems to support algorithm negotiation and multiple algorithms simultaneously. Use TLS cipher suites for flexible negotiation. Store algorithm identifiers with protected data.

Use Case                    Recommended Algorithm(s)
─────────────────────────────────────────────────────────────────────────────
TLS key exchange            Kyber-768 (hybrid with X25519)
Code signing                Dilithium-3 or FALCON-512
Firmware signing            SPHINCS+ (conservative) or Dilithium
Email encryption (PGP)      Kyber + Classic McEliece (hybrid)
Long-term archives          Kyber + Classic McEliece (hybrid, defense depth)
Blockchain transactions     FALCON (small signatures) (QC risk for blockchain)
Certificate authorities     Dilithium (future CA certificates)
VPN (IPsec)                 Kyber + ECDH (hybrid)

Harvest Now, Decrypt Later Attacks

• Attack Description: Adversary records encrypted traffic today (while quantum computers not yet available). Stores ciphertexts (TLS sessions, backups, emails, encrypted files). Waits for quantum computer to break RSA/ECC and decrypts stored data years later. Long-lived secrets remain vulnerable for decades.
• Mitigations: Use PQC (or hybrid) for new communications. Re-encrypt historical backups with PQC. Short-lived data (session keys) less concerning (long-term documents high risk).

Data Type               Risk (Harvest-now)        Mitigation
─────────────────────────────────────────────────────────────────────────────
TLS web sessions        Low (short-lived)         PQC for long sessions
Email archives          High (years retention)    PQC migration
Encrypted backups       Very High                 Re-encrypt with PQC
Long-term certificates  High                      Shorter lifetimes
Medical records         Very High                 PQC encryption
Sensitive documents     Very High                 PQC + forward secrecy
Financial tx history    High                      PQC during transition

Future Outlook

NIST standards expected 2024-2025. Browser and cloud providers will enable PQC (hybrid) by 2026-2028. Enterprise migration 2025-2035 (phased). Legacy systems will remain vulnerable (long tail).

NIST PQC Home:     https://csrc.nist.gov/projects/post-quantum-cryptography
Open Quantum Safe (liboqs):  https://openquantumsafe.org
Cloudflare PQC:    https://blog.cloudflare.com/post-quantum-crypto-experiment/
Google PQC:        https://security.googleblog.com/2021/07/experimenting-with-post-quantum.html

Frequently Asked Questions

1. When will quantum computers break RSA/ECC?
   No one knows. Practical estimates range 5-20 years (optimistic) to 30+ years. Uncertainty demands action now: migration takes years, harvest now attacks already happening. Assume eventual break (risk assessment for long-lived data).
2. Does quantum computing affect symmetric encryption (AES)?
   Yes (Grover's algorithm). AES-128 effective key size reduces to 64 bits (vulnerable). AES-256 effective reduces to 128 bits (still secure). Recommendation: use AES-256 for quantum-resistance. AES-256 is quantum-safe (128-bit post-quantum security).
3. What is the difference between post-quantum and quantum cryptography?
   Post-quantum cryptography is classical cryptography that resists quantum attacks (runs on classical computers). Quantum cryptography uses quantum mechanics to detect eavesdropping (requires quantum hardware). PQC is practical today; quantum cryptography is still emerging.
4. Is NIST selection final?
   Selected algorithms likely final. Alternate algorithms may be standardized later. Algorithms not selected (Rainbow, SIKE etc.) should be avoided.
5. When should I migrate to PQC?
   For long-lived data (archives, medical records, backups): start now (hybrid). For short-lived web sessions: prepare, but less urgent. For certificates: plan shorter lifetimes and transition to hybrid CA.
6. What should I learn next after post-quantum cryptography?
   After mastering post-quantum cryptography, explore lattice-based cryptography (LWE, Kyber), NIST PQC standards details, hybrid cryptography implementation, liboqs for developers, crypto-agile design patterns, and quantum key distribution (QKD).