Post-Quantum Cryptography

Cryptographic algorithms designed to be secure against both classical and quantum computers.

Post-Quantum Cryptography (PQC), also called quantum-resistant or quantum-safe cryptography, refers to cryptographic algorithms that remain secure even if an adversary has a quantum computer.

The Threat

Shor’s algorithm can break:

• RSA: Factoring large numbers
• ECC: Discrete logarithm on elliptic curves
• DH/DSA: Discrete logarithm in finite fields

These underpin most of today’s public-key cryptography. A large quantum computer would compromise secure communications, digital signatures, and more.

The Timeline

“Harvest now, decrypt later”: Data encrypted today could be stored and decrypted once quantum computers exist.

PQC Approaches

Lattice-Based Cryptography

Based on hard lattice problems (e.g., Learning With Errors).

• Examples: Kyber (key exchange), Dilithium (signatures)
• Pros: Efficient, well-studied
• Cons: Larger keys than classical

Hash-Based Signatures

Security relies only on hash function properties.

• Examples: SPHINCS+, XMSS
• Pros: Conservative security assumptions
• Cons: Larger signatures, stateful versions have management challenges

Code-Based Cryptography

Based on error-correcting codes.

• Examples: Classic McEliece, BIKE
• Pros: Long history (1978)
• Cons: Very large public keys

Isogeny-Based

Based on maps between elliptic curves.

• Examples: SIKE (broken in 2022!)
• Status: Active research, some schemes broken

Multivariate Cryptography

Based on solving multivariate polynomial equations.

• Examples: Rainbow (broken), ongoing research
• Status: Several schemes broken, active area

NIST Standardization

NIST’s post-quantum cryptography project (2016-2024) selected:

Key Encapsulation (Encryption)

• ML-KEM (Kyber): Primary standard

Digital Signatures

• ML-DSA (Dilithium): Primary standard
• SLH-DSA (SPHINCS+): Hash-based alternative
• FN-DSA (Falcon): Efficient signatures

Migration Strategy

Hybrid Approaches

Combine classical and post-quantum algorithms:

Hybrid Key = Classical_KEM(key) || PQ_KEM(key)

Secure if either is unbroken.

Crypto Agility

Design systems to swap algorithms easily, which is needed for future updates.

PQC vs QKD

Most organizations need PQC. QKD is complementary for highest-security applications.

See also: Shor’s Algorithm, Quantum Key Distribution, Lattice-Based Cryptography, Quantum-Safe