Post-quantum cryptography

The primary threat is Shor's algorithm, which can factor integers and compute discrete logarithms in polynomial time on a sufficiently large quantum computer, rendering RSA, DSA, and ECC obsolete¹. Grover's algorithm also provides a quadratic speedup for brute-force searches, weakening symmetric-key security but not catastrophically. The 'harvest now, decrypt later' attack—where adversaries store encrypted data today to decrypt it once quantum computers mature—adds urgency for long-term confidentiality. PQC aims to provide algorithms that resist these quantum attacks while remaining practical on classical hardware.

PQC candidates fall into several families. Lattice-based schemes, such as CRYSTALS-Kyber and CRYSTALS-Dilithium, rely on the hardness of learning-with-errors problems and offer strong security with efficient implementations. Hash-based signatures, like SPHINCS+, use only hash functions and are highly conservative but have larger signatures. Code-based cryptography, exemplified by McEliece, uses error-correcting codes and has a long history of cryptanalysis. Multivariate polynomial and isogeny-based schemes have also been studied, though some, like SIKE, were broken by classical attacks².

In 2022, NIST selected CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium, Falcon, and SPHINCS+ for digital signatures, with final standards released in 2024³. These algorithms are being integrated into protocols like TLS, SSH, and X.509 certificates. Hybrid schemes, combining classical and PQC algorithms, are common during transition to mitigate risks. However, deployment faces challenges: larger key sizes, performance overhead, and the need to update infrastructure. The NSA and other agencies have published timelines for migration, urging adoption by the mid-2030s⁴.

Beyond the NIST finalists, several alternative approaches exist. Isogeny-based cryptography, once promising, suffered a setback when SIKE was broken in 2022 using classical mathematics². Code-based schemes like Classic McEliece offer high security but have very large public keys (megabytes). Lattice-based schemes, while efficient, have subtle implementation pitfalls, such as side-channel leakage and decryption failures. The 'cryptographic doom principle' warns that hybrid systems must be carefully designed to avoid downgrade attacks. Additionally, PQC is not just about public-key; symmetric algorithms like AES are already quantum-resistant with increased key sizes, and quantum key distribution (QKD) is a separate, complementary technology.

Lattice-based cryptography

A family of PQC algorithms based on the hardness of lattice problems like Learning With Errors (LWE).

Shor's algorithm

A quantum algorithm that efficiently factors integers and computes discrete logarithms, threatening RSA and ECC.

Hybrid scheme

A cryptographic protocol that combines classical and post-quantum algorithms to provide security even if one is broken.