Post-Quantum Cryptography

Shor's algorithm solves the integer factoring problem in polynomial time on a quantum computer, threatening the security of RSA, Diffie-Hellman, and elliptic-curve schemes that classical computers cannot break efficiently. Post-quantum cryptography (PQC) is the discipline of designing and standardizing classical (non-quantum) algorithms that remain hard even when an adversary possesses a large-scale quantum computer.

What Shor's algorithm actually threatens

RSA security rests on the hardness of factoring an $n$ -bit integer $N = p \cdot q$ . The best classical algorithm (the general number field sieve) runs in sub-exponential time $\exp\!\bigl(O(n^{1/3} (\log n)^{2/3})\bigr)$ , which is still super-polynomial and keeps 2048-bit RSA safe today. Shor's algorithm factors $N$ in $O(n^2 \log n \log \log n)$ gate operations — fully polynomial — so a sufficiently large quantum computer would break 2048-bit RSA in hours rather than billions of years.

Elliptic-curve discrete-log (used in ECDSA and ECDH) is similarly vulnerable: Shor's period-finding subroutine can be adapted to the discrete-logarithm problem with comparable overhead. Both RSA and ECC are therefore quantum-broken algorithms.

Symmetric ciphers (AES, ChaCha20) and hash functions (SHA-2, SHA-3) are only weakened, not broken: Grover's algorithm yields a quadratic speedup for brute-force search, effectively halving the security parameter. Doubling the key length (e.g., AES-256 instead of AES-128) restores the original security margin.

The NIST PQC standardization process

Recognising the threat early, NIST opened a public competition in 2016 to standardize quantum-safe algorithms. After three rounds of global analysis, NIST selected its first standards in 2022:

| Standard | Algorithm | Problem basis | |---|---|---| | FIPS 203 | ML-KEM (CRYSTALS-Kyber) | Module learning with errors (MLWE) | | FIPS 204 | ML-DSA (CRYSTALS-Dilithium) | Module short integer solution (MSIS) | | FIPS 205 | SLH-DSA (SPHINCS+) | Hash-function security |

A fourth standard, FIPS 206 (FN-DSA, based on FALCON — also a lattice scheme), was finalized in August 2024.

Lattice-based cryptography

The leading family of post-quantum algorithms is built on lattice problems, particularly the Learning With Errors (LWE) problem introduced by Regev (2005). A lattice in $\mathbb{R}^n$ is the set of all integer linear combinations of $n$ linearly independent basis vectors. Hard lattice problems ask for the shortest vector (SVP) or the closest vector (CVP) in high-dimensional lattices.

In LWE-based encryption the public key encodes a noisy system of linear equations over $\mathbb{Z}_q$ :

\mathbf{A}\,\mathbf{s} + \mathbf{e} \equiv \mathbf{b} \pmod{q},

where $\mathbf{A}$ is a random matrix, $\mathbf{s}$ is the secret, and $\mathbf{e}$ is a small noise vector. Recovering $\mathbf{s}$ from $(\mathbf{A}, \mathbf{b})$ is believed to be hard even for quantum computers: no polynomial-time quantum algorithm is known for LWE, and the best known quantum attacks offer only modest speedups over classical ones.

The module variant (MLWE) used in Kyber and Dilithium operates over polynomial rings for efficiency, achieving compact key sizes while preserving the hardness assumption.

Other families

Code-based cryptography relies on the hardness of decoding a random linear code over a finite field (the syndrome decoding problem). The classic McEliece scheme (1978) has withstood decades of cryptanalysis, but its public keys are large. NIST's alternate candidate HQC (Hamming Quasi-Cyclic) uses structured codes to shrink key sizes.

Hash-based signatures (SPHINCS+, XMSS) derive security entirely from the collision-resistance and second-preimage resistance of hash functions. Their quantum security follows from the fact that Grover's quadratic speedup is fully accounted for by choosing a larger hash output. These schemes are the most conservatively secure because their hardness assumption is minimal, though they tend to produce larger signatures.

Multivariate polynomial schemes and isogeny-based schemes round out the landscape; the main isogeny candidate SIKE was broken classically in 2022 and eliminated from the NIST process, illustrating that post-quantum security must be actively verified rather than assumed.

Migration considerations

Transitioning to PQC is a large systems problem. Key points for practitioners:

Hybrid key exchange combines a classical ECDH with an MLWE key-encapsulation, so security is maintained even if one of the two is later broken. TLS 1.3 extensions for hybrid schemes are already deployed by major browsers and CDNs.
Harvest-now-decrypt-later attacks: an adversary can record encrypted traffic today and decrypt it retroactively once a quantum computer is available. Long-lived secrets (government documents, medical records, financial contracts) need PQC protection now, before quantum hardware matures.
Performance: lattice-based schemes are fast in practice. ML-KEM encapsulation and decapsulation each run in under a microsecond on modern CPUs, comparable to X25519 ECDH. Signature sizes are larger than Ed25519 but within tolerable bounds for most protocols.

Summary

Shor's algorithm threatens public-key schemes whose security rests on factoring (RSA) or the discrete-logarithm (ECC). Post-quantum cryptography replaces them with algorithms — lattice-based, code-based, and hash-based — whose hardness is not known to be broken by any quantum algorithm. NIST finalized its first PQC standards in 2022, and migration is already underway in production systems.