Post-Quantum Cryptography

Post-quantum cryptography (PQC) refers to classical cryptographic algorithms, running on ordinary computers, that are designed to resist attacks from quantum computers. The term “classical” here means the algorithms run on standard CPUs; no quantum hardware is needed to use them. They replace vulnerable algorithms like RSA and elliptic-curve cryptography (ECC) with new mathematical problems that quantum computers cannot efficiently solve.

The urgency is real. Shor’s algorithm running on a sufficiently large fault-tolerant quantum computer would break RSA and ECC entirely. That machine does not yet exist, but encrypted data captured today can be stored and decrypted later, once the hardware exists.

The details

RSA and ECC derive their security from the assumed computational difficulty of integer factoring and discrete logarithm problems, respectively. Shor’s algorithm solves both in polynomial time on a quantum computer, breaking these systems completely.

NIST ran a multi-year competition to standardize post-quantum algorithms, completing its first set of standards in 2024:

CRYSTALS-Kyber (now ML-KEM, FIPS 203): A key encapsulation mechanism (KEM) based on the hardness of the Module Learning with Errors (MLWE) problem. This replaces RSA and Diffie-Hellman for establishing shared secrets.

CRYSTALS-Dilithium (now ML-DSA, FIPS 204): A digital signature scheme also based on lattice problems. Replaces RSA and ECDSA for authentication.

SPHINCS+ (now SLH-DSA, FIPS 205): A hash-based signature scheme. Security relies only on the properties of cryptographic hash functions, with no dependence on number-theoretic assumptions. Larger signatures than Dilithium, but a very conservative security assumption.

FALCON (FIPS 206): A lattice-based signature scheme with compact signatures, standardized alongside Dilithium.

The mathematical foundation of lattice-based cryptography is the hardness of the Shortest Vector Problem (SVP) in high-dimensional lattices. No efficient quantum algorithm is known for this problem. The security does not rely on Shor’s algorithm being inapplicable; the best known quantum algorithms for lattice problems provide only modest speedups.

Grover’s algorithm provides a quadratic speedup on symmetric-key and hash-based schemes (halving the effective security level), which is addressed by using longer key lengths: AES-256 instead of AES-128, SHA-384 instead of SHA-256.

Why it matters for learners

PQC is one of the most immediate practical consequences of quantum computing. Organizations deploying cryptographic systems today must plan for quantum threats, even if fault-tolerant quantum computers are still years away. The “harvest now, decrypt later” threat model means data encrypted now with RSA may be decrypted by a quantum adversary in the 2030s.

Understanding the difference between PQC and quantum key distribution (QKD) is important:

• PQC runs on classical hardware, is deployable over existing internet infrastructure, and provides computational security (security based on hardness assumptions)
• QKD requires quantum hardware and quantum channels, but provides information-theoretic security (security based on physical laws, not computational assumptions)

For most organizations, PQC is the practical near-term path. QKD is the physically guaranteed long-term option for high-value links.

Migration timelines are long. Updating cryptographic libraries, protocols (TLS, SSH, S/MIME), hardware security modules, and embedded systems takes years. NIST guidance recommends beginning inventory and migration planning now.

Common misconceptions

Misconception 1: PQC and quantum cryptography are the same thing. They are different. Quantum cryptography (specifically QKD) uses quantum mechanics to distribute keys with physically guaranteed security. PQC uses classical mathematics specifically chosen to resist quantum attacks. PQC does not require any quantum hardware.

Misconception 2: We have years before we need to worry. The threat timeline depends on when fault-tolerant quantum computers with millions of physical qubits become available, which is uncertain. But the “harvest now, decrypt later” attack is happening now. Data with long-term confidentiality requirements (government secrets, medical records, financial data) may be at risk if encrypted today with RSA.

Misconception 3: Post-quantum algorithms are just larger versions of RSA. PQC algorithms use entirely different mathematical structures. Lattice problems, hash functions, and code-based problems are not generalizations of factoring or discrete log; they are different areas of mathematics with different hardness assumptions and very different performance characteristics.

See also

• Shor’s Algorithm
• Quantum Key Distribution
• Quantum Cryptography
• Grover’s Algorithm