Post Quantum Cryptography

Post Quantum Cryptography

by

Post Quantum Cryptography Unlike traditional cryptographic systems (e.g., RSA, ECC, and DH), which rely on the hardness of integer factorization or discrete logarithms, PQC uses mathematical problems that are believed to be resistant to quantum algorithms like Shor’s algorithm.

Post Quantum Cryptography

Why is PQC Important

  • Quantum computers, when sufficiently powerful, could break widely used public-key cryptosystems:
  • Shor’s algorithm can efficiently solve integer factorization and discrete logarithms, breaking RSA, ECC, and Diffie-Hellman.
  • Grover’s algorithm speeds up brute-force attacks, reducing symmetric key security by half (e.g., a 128-bit key becomes as weak as a 64-bit key).

Types of Post-Quantum Cryptographic Algorithms

  • The NIST PQC Standardization Project (2016–present) has evaluated multiple candidates. The selected standards (2022–2024) include:

1. Lattice-Based Cryptography

  • Security Basis: Hardness of problems like Learning With Errors (LWE) or Shortest Vector Problem (SVP).

Examples:

  • CRYSTALS-Kyber (Key Encapsulation Mechanism, NIST standard).
  • CRYSTALS-Dilithium (Digital Signature, NIST standard).
  • Falcon (Digital Signature, NIST standard).
  • Pros: Efficient, versatile.
  • Cons: Large key sizes.

2. Hash-Based Cryptography

  • Security Basis: Collision resistance of cryptographic hash functions.

Examples:

  • SPHINCS+ (Stateless hash-based signature, NIST standard).
  • Pros: Well-understood security.
  • Cons: Stateful schemes can be complex.

3. Code-Based Cryptography

  • Security Basis: Hardness of decoding random linear codes (e.g., syndrome decoding).

Examples:

  • Classic McEliece (KEM, NIST standard).
  • Pros: Long-standing security.
  • Cons: Large public keys.

4. Multivariate Cryptography

  • Security Basis: Solving systems of multivariate polynomial equations.

Examples:

  • Pros: Fast signatures.
  • Cons: Large keys, some schemes broken.

5. Isogeny-Based Cryptography

Examples:

  • SIKE (Broken in 2022, no longer considered secure).
  • Pros: Compact keys.
  • Cons: Newer, less tested.

NIST PQC Standardization (Finalists & Alternates)

Category                                                                                                                Selected Algorithms (2024)

Key Encapsulation (KEM)                                                                               CRYSTALS-Kyber, Classic McEliece, BIKE (alternate)

Digital Signatures                                                                                                   CRYSTALS-Dilithium, Falcon, SPHINCS+

Migration to Post-Quantum Cryptography

  • Hybrid Schemes: Combining classical and PQC algorithms (e.g., ECC + Kyber).
  • Industry Adoption: Google, Cloudflare, and others are already testing PQC in experiments.

Challenges

  • Performance: Some PQC algorithms have larger keys/signatures.
  • Legacy Systems: Updating embedded systems and hardware (HSMs, smart cards) is difficult.
  • Standardization: NIST is finalizing standards, but some schemes may still be broken.

Migration to Post-Quantum Cryptography

Detailed Breakdown of PQC Algorithms

  • (A) Lattice-Based Cryptography (Most Promising)

Key Algorithms:

Algorithm                                         Type                               Key Size (Approx.)                           Security Level                     Notes

Kyber                                            KEM (PKE)                              ~1-2 KB                            NIST L3 (AES-192)      Fast, chosen for standardization

Dilithium                                      Signature                                 ~2-4 KB                          NIST L3                               Primary NIST standard

Falcon                                         Signature                                  ~1-1.5 KB                        NIST L5 (AES-256)               Compact but complex

NTRU                                              KEM                                         ~1-2 KB                          Alternative                          Older, patent issues

Pros:

  • Best balance of security & efficiency.
  • Supports Fully Homomorphic Encryption (FHE).

Cons:

  • Larger keys than RSA/ECC.
  • Side-channel attacks possible.

Hash-Based Cryptography (Simple & Secure

  • Core Idea: Use hash functions (e.g., SHA-3) to build signatures.
  • One-Time Signatures (OTS): Each key pair used once (e.g., Lamport).
  • XMSS, SPHINCS+: Stateful (XMSS) vs. stateless (SPHINCS+).

Algorithm Type Signature Size Security

  • SPHINCS+ Stateless ~8-50 KB NIST L3 Slow but ultra-secure

Pros:

  • Unbreakable if hash function is secure.
  • No quantum vulnerability.

Cons:

  • Huge signatures (~40x larger than ECDSA).
  • Slower verification.

Code-Based Cryptography (Old but Reliable)

  • Core Problem: Syndrome Decoding – Correct errors in random linear codes.

Algorithm Type Public Key Size Notes

  • Classic McEliece KEM ~1 MB (!) NIST standard, but impractical for many uses

Pros:

  • Survived attacks for 40+ years.

Cons:

Massive keys (~1MB).

Multivariate & Isogeny-Based (Less Mature)

  • Multivariate (e.g., Rainbow): Broken in NIST Round 3.
  • Isogeny-Based (e.g., SIKE): Broken in 2022 using GPST attack.
  • Status: Not currently recommended.

Real-World Adoption & Challenges

(A) Industry Progress

Organization                                                                                            PQC Implementation

Google                                                                                                    Testing KYBER in Chrome.

Cloud flare                                                                                                 PQC TLS experiments.

AWS                                                                                                          Exploring KYBER in KMS.

Signal                                                                                                       PQXDH (KYBER+ X25519).

Migration Challenges

Performance Overhead:

  • KYBER is ~10x slower than ECC for keygen.
  • SPHINCS+ signatures are ~50KB vs. ECDSA’s 64 bytes.

Legacy Systems:

  • Smart cards, IoT devices may struggle with large keys.

Hybrid Deployments:

  • Most real-world systems use ECC + KYBER for now.

3. Attacks on PQC Schemes

Algorithm                                                                    Attack  Type                                                          Status

SIKE                                                                             GPST Attack (2022)                                               Broken

Rainbow                                                                      Min Rank Attack (2022)                                         Broken

LWE/Lattice                                                                Side-Channel (Timing)                                  Mitigated in latest schemes

  • Takeaway: Lattice & hash-based schemes remain secure.

4. Future of PQC

  • NIST’s Timeline:
  • 2024: Final standards published.
  • 2025–2030: Gradual industry adoption.

Research Directions:

  • Faster Lattice Crypto: Improving Dilithium/Falcon.
  • ZK-SNARKs with PQC: Combining privacy + PQ security.

5. What Should You Do Today?

  • Inventory: Identify systems using RSA/ECC.
  • Hybrid Mode: Deploy ECDHE + Kyber in TLS.
  • Monitor NIST: Follow final standards.
  • Mathematical Core of PQC Algorithms

Lattice-Based Cryptography: The Hard Problems

  • Learning With Errors (LWE)
  • Quantum Resistance: Best known attacks require sub-exponential time even for quantum computers.
  • Ring-LWE (Efficient Variant)
  • Operates in polynomial ring
    SPHINCS+ uses a hyper-tree of OTS to scale to many signatures.

Lattice-Based Cryptography The Hard Problems

2. Implementation Challenges & Pitfalls

  • Side-Channel Attacks on Lattice Schemes

Timing Attacks:

  • KYBER’ s NTT (Number Theoretic Transform) can leak secrets via cache timing.
  • Fix: Constant-time implementations (e.g., masking).

Power Analysis:

  • FPGA/ASIC implementations may leak secrets via power traces.

Large Keys in Code-Based Crypto

  • Classic MCELIECE public key: 1 MB (vs. RSA’s 0.5 KB).
  • Workaround: Use Quasi-Cyclic variants (e.g., BIKE), but NIST did not standardize them due to security concerns.

Statefulness in Hash-Based Signatures

  • XMSS requires a state (counter) to prevent reuse.
  • Lose the state? Security breaks completely.
  • SPHINCS+ is stateless but slower (~40K signatures/sec vs. Ed25519’s 100K).

3. Advanced Attacks & Cryptanalysis

Key Recovery in LWE

Dual Lattice Attack: Reduces LWE to finding short vectors in the dual lattice.

Best Known Complexity:

  • For Kyber-512: ~21502150classical, ~2100 2100 quantum.
  • Conclusion: Still secure, but parameters may need adjustment.

Attacks on Isogenies (SIKE Break)

  • GPST Attack (2022): Exploited torsion-point information to recover secret isogeny in polynomial time.
  • Lesson: New math can break seemingly secure schemes.

Fault Attacks

  • Countermeasure: Redundant checks in hardware.

4. Beyond NIST: Cutting-Edge PQC Research

  • Zero-Knowledge Proofs (ZKPs) with PQC
  • Problem: Current ZKPs (e.g., Bulletproofs) rely on discrete logs.

Solution:

  • Lattice-based ZKPs (e.g., Banquet).
  • Hash-based ZKPs (e.g., Picnic).
  • Fully Homomorphic Encryption (FHE)
  • LWE is the foundation of FHE (e.g., TFHE, CKKS).
  • Challenge: Bootstrapping a PQC-secure FHE is ~1000x slower than classical.

Quantum-Secure Blockchain

  • QRL (Quantum Resistant Ledger): Uses XMSS.
  • Mina Protocol: Exploring PQC for SNARKs.
  • Nuclear-Grade Math: The Underlying Hard Problems

Lattice Problems: Beyond LWE

Module-LWE vs. Ring-LWE

  • KYBER uses Module-LWE: Harder to attack than pure Ring-LWE due to mixing multiple rings.
  • Security proof: Reduces to worst-case hardness of Shortest Independent Vectors Problem (SIVP).
  • NTRU’s Hidden Polynomial Rings
  • Original NTRU uses convolutions in

Code-Based Crypto: Beyond McEliece

  • Quasi-Cyclic (QC) Codes (e.g., BIKE, HQC)
  • Idea: Use structured matrices to shrink keys (from 1MB → 10KB).
  • NIST Rejection: BIKE’s security proofs were incomplete.
  • Attack: GBA (Guess-and-Backtrack) can break weak QC variants.
  • Rank-Metric Codes (e.g., RQC, LRPC)
  • Uses matrix rank instead of Hamming distance.
  • Advantage: Keys ~5x smaller than McEliece.
  • Risk: Overstretched parameters may fall to algebraic attacks.

Isogeny-Based: Post-SIKE Resurrection?

  • CSIDH (Commutative Super singular Isogenies)
  • Pros: Tiny keys (~64 bytes), perfect for IoT.
  • Cons: Broken by GPST attack if used for signatures.
  • Hope: SQI Sign (2023) resists known attacks but is slow.

Leave a Comment